Reference:

Christoph Haase and Stefan Kiefer. The odds of staying on budget. Technical report, arXiv.org, 2015. Available at http://arxiv.org/abs/1409.8228.

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:

@techreport{15HK-ICALP-TR,
    author = {Christoph Haase and Stefan Kiefer},
    institution = {arXiv.org},
    note = {Available at http://arxiv.org/abs/1409.8228},
    title = {The Odds of Staying on Budget},
    year = {2015}
}