The variance-penalized stochastic shortest path problem
From International Center for Computational Logic
The variance-penalized stochastic shortest path problem
Jakob PiribauerJakob Piribauer, Ocan SankurOcan Sankur, Christel BaierChristel Baier
Jakob Piribauer, Ocan Sankur, Christel Baier
The variance-penalized stochastic shortest path problem
Proc. of the 49rd International Colloquium on Automata, Languages and Programming (ICALP), Leibniz International Proceedings in Informatics (LIPIcs), 2022. Schloss Dagstuhl - Leibniz-Zentrum für Informatik
The variance-penalized stochastic shortest path problem
Proc. of the 49rd International Colloquium on Automata, Languages and Programming (ICALP), Leibniz International Proceedings in Informatics (LIPIcs), 2022. Schloss Dagstuhl - Leibniz-Zentrum für Informatik
- KurzfassungAbstract
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. - Forschungsgruppe:Research Group: Algebraische und logische Grundlagen der InformatikAlgebraic and Logical Foundations of Computer Science
@inproceedings{PSB2022,
author = {Jakob Piribauer and Ocan Sankur and Christel Baier},
title = {The variance-penalized stochastic shortest path problem},
booktitle = {Proc. of the 49rd International Colloquium on Automata, Languages
and Programming (ICALP)},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2022},
doi = {10.4230/LIPICS.ICALP.2022.129}
}