Reference:

Christoph Haase and Stefan Kiefer. The odds of staying on budget. In Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP), part II, volume 9135 of LNCS, pages 234–246, Kyoto, Japan, 2015. Springer.

Abstract:

Given Markov chains and Markov decision processes (MDPs) whose transitions are labelled with non-negative integer costs, we study the computational complexity of deciding whether the probability of paths whose accumulated cost satisfies a Boolean combination of inequalities exceeds a given threshold. For acyclic Markov chains, we show that this problem is PP-complete, whereas it is hard for the PosSLP problem and in PSPACE for general Markov chains. Moreover, for acyclic and general MDPs, we prove PSPACE- and EXP-completeness, respectively. Our results have direct implications on the complexity of computing reward quantiles in succinctly represented stochastic systems.

Suggested BibTeX entry:

@inproceedings{15HK-ICALP,
    address = {Kyoto, Japan},
    author = {Christoph Haase and Stefan Kiefer},
    booktitle = {Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP), part II},
    pages = {234--246},
    publisher = {Springer},
    series = {LNCS},
    title = {The Odds of Staying on Budget},
    volume = {9135},
    year = {2015}
}