The variance-penalized stochastic shortest path problem

Research output: Contribution to book/conference proceedings/anthology/reportConference contributionContributedpeer-review



The stochastic shortest path problem (SSPP) asks to resolve the non-deterministic choices in a Markov decision process (MDP) such that the expected accumulated weight before reaching a target state is maximized. This paper addresses the optimization of the variance-penalized expectation (VPE) of the accumulated weight, which is a variant of the SSPP in which a multiple of the variance of accumulated weights is incurred as a penalty. It is shown that the optimal VPE in MDPs with non-negative weights as well as an optimal deterministic finite-memory scheduler can be computed in exponential space. The threshold problem whether the maximal VPE exceeds a given rational is shown to be EXPTIME-hard and to lie in NEXPTIME. Furthermore, a result of interest in its own right obtained on the way is that a variance-minimal scheduler among all expectation-optimal schedulers can be computed in polynomial time.


Original languageEnglish
Title of host publication49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022
EditorsMikołaj Bojańczyk, Emanuela Merelli, David P. Woodruff
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Number of pages19
ISBN (Electronic)9783959772358
ISBN (Print)978-3-95977-235-8
Publication statusPublished - 1 Jul 2022

Publication series

Series49th EATCS International Conference on Automata, Languages, and Programming (ICALP 2022) ; Vol. 229


Title49th EATCS International Colloquium on Automata, Languages and Programming
Abbreviated titleICALP 2022
Duration4 - 8 July 2022
Degree of recognitionInternational event

External IDs

Scopus 85133468318
dblp conf/icalp/PiribauerSB22
Mendeley 4b556c64-0cd5-3b56-a6aa-bf19263a8017
ORCID /0000-0002-5321-9343/work/142236696


Research priority areas of TU Dresden

DFG Classification of Subject Areas according to Review Boards

Subject groups, research areas, subject areas according to Destatis

ASJC Scopus subject areas


  • Markov decision process, variance, stochastic shortest path problem