# Value Iteration with Guessing for Markov Chains and Markov Decision Processes

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 44 references that are in the map.
- First posted on arXiv 10 May 2025.

## Builds on (most cited first, 12 of 12)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [The Probabilistic Model Checker Storm](https://mlsanity.com/paper/2002.07080/) (2020)
- [Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes](https://mlsanity.com/paper/1710.09988/) (2017)
- [Verification of Markov Decision Processes using Learning Algorithms](https://mlsanity.com/paper/1402.2967/) (2014)
- [A Practitioner's Guide to MDP Model Checking Algorithms](https://mlsanity.com/paper/2301.10197/) (2023)
- [On the Complexity of Value Iteration](https://mlsanity.com/paper/1807.04920/) (2018)
- [Optimistic Value Iteration](https://mlsanity.com/paper/1910.01100/) (2019)
- [Sound Value Iteration](https://mlsanity.com/paper/1804.05001/) (2018)
- [Bounded Model Checking for Probabilistic Programs](https://mlsanity.com/paper/1605.04477/) (2016)
- [Widest Paths and Global Propagation in Bounded Value Iteration for Stochastic Games](https://mlsanity.com/paper/2007.07421/) (2020)
- [Lower Bounds for Symbolic Computation on Graphs: Strongly Connected Components, Liveness, Safety, and Diameter](https://mlsanity.com/paper/1711.09148/) (2017)
- [Correct Probabilistic Model Checking with Floating-Point Arithmetic](https://mlsanity.com/paper/2110.08785/) (2021)

## Abstract (arXiv)

Two standard models for probabilistic systems are Markov chains (MCs) and Markov decision processes (MDPs). Classic objectives for such probabilistic models for control and planning problems are reachability and stochastic shortest path. The widely studied algorithmic approach for these problems is the Value Iteration (VI) algorithm which iteratively applies local updates called Bellman updates. There are many practical approaches for VI in the literature but they all require exponentially many Bellman updates for MCs in the worst case. A preprocessing step is an algorithm that is discrete, graph-theoretical, and requires linear space. An important open question is whether, after a polynomial-time preprocessing, VI can be achieved with sub-exponentially many Bellman updates. In this work, we present a new approach for VI based on guessing values. Our theoretical contributions are twofold. First, for MCs, we present an almost-linear-time preprocessing algorithm after which, along with guessing values, VI requires only subexponentially many Bellman updates. Second, we present an improved analysis of the speed of convergence of VI for MDPs. Finally, we present a practical algorithm for MDPs based on our new approach. Experimental results show that our approach provides a considerable improvement over existing VI-based approaches on several benchmark examples from the literature.