# The Odds of Staying on Budget

arXiv: https://arxiv.org/abs/1409.8228 · HTML: https://mlsanity.com/paper/1409.8228/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Sep 2014.

## Built on by (most cited first, 1 of 1)

- [Categorizer Automata for Discounted-Sum Payoffs](https://mlsanity.com/paper/2608.26763/) (2026)

## Abstract (arXiv)

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.