Value Iteration with Guessing for Markov Chains and Markov Decision Processes
Krishnendu Chatterjee, Mahdi JafariRaviz, Raimundo Saona ∗, Jakub Svoboda · 2025
Read Value Iteration with Guessing for Markov Chains and Markov Decision Processes by Krishnendu Chatterjee, Mahdi JafariRaviz, Raimundo Saona ∗, Jakub Svoboda (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-06769.txt.
Introduction
Chatterjee and co-authors present a 2025 paper on speeding value iteration for Markov chains and decision processes. These models drive planning under chance, and value iteration is their workhorse. Its local Bellman updates can, worst case, number exponentially many. A standing question asks whether smart preparation can cut that bill below exponential.
Their answer seeds the process with guessed values after a fast, nearly linear preparation pass. For chains, the updates then stay sub-exponential. For decision processes, a sharper convergence analysis and a practical algorithm follow. Experiments show hefty gains over plain iteration. The work joins theory and practice for a core planning algorithm.
Catalog record
| CREATOR | Krishnendu Chatterjee, Mahdi JafariRaviz, Raimundo Saona ∗, Jakub Svoboda |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 110 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-06769
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Value Iteration with Guessing for Markov Chains and Markov Decision Processes Krishnendu Chatterjee, Mahdi JafariRaviz, Raimundo Saona ∗, Jakub Svoboda Abstract 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. 1 Introduction Markov Chains and Markov Decision Processes. Markov chains (MCs) and Markov decision processes (MDPs) [ 2 , 20 , 38 ] are widely used mathematical models with applications in various fields including computer science, economics, operations research, and engineering. These models study dynamical systems that exhibit stochastic behavior. MCs consist of a finite state space and a stochastic transition function. MDPs extend MCs with non-deterministic choices over actions of a controller that determines the stochastic transition function at each period. Objectives and Value. Objectives define the payoff to be optimized by the controller. The classic objectives for MCs and MDPs that arise in control, verification, and planning problems are [ 2 , 38 ] : (i) weighted reachability objectives and (ii) stochastic shortest path (SSP) objectives. In weighted reachability objectives, we are given a target set of states and weights on them. Then, the payoff of a path is, if it reaches a target state, the weight of that state, otherwise zero. In SSP objectives, we are given a target set and a positive cost at every state. Then, the cost of a path is, if it reaches a target state, the sum of the cost till a target state is reached, otherwise infinity. In MCs, the value is the expectation of the objective. In MDPs, the value is the optimal expectation over all resolutions of the non-deterministic choices. Value Iteration. Both MCs and MDPs with the above objectives can be solved in polynomial time [ 2 , Chapter 10] by a reduction to linear programming (LP) [ 7 ] . Even though linear programming yields a polynomial-time solution, the algorithm most used in practice is Value Iteration (VI), which is a classic and well-studied algorithmic approach [ 14 ] . Given an initial value vector, the VI algorithm iteratively applies local updates, called Bellman updates [ 6 ] , to approach the value vector. The two key advantages of VI over LP are the following. First, the VI algorithm is simple, elegant, and space-efficient (i.e., it requires linear space) whereas (to the best of our knowledge) linear-space LP-based algorithms for MDPs are not known. Second, the VI algorithm has symbolic implementations which scales to large state spaces, e.g., representing value vectors as multiterminal binary decision diagrams and applying local updates [ 30 , 34 ] , whereas LP-based algorithms do not. Given the advantages of VI over linear programming, VI is the most widely used approach in several tools for probabilistic verification, e.g., PRISM [ 33 ] and STORM [ 30 ] . See [ 26 ] for a thorough comparative study. Preprocessing. MCs and MDPs are often preprocessed to speed up computation. For example: in weighted reachability objectives with binary weights, a preprocessing step is to compute all states with values of either zero or one; in SSP objectives, similar computations identify all states with value infinity. The desired properties of preprocessings are: (a) discrete and graph-theoretical, i.e., it does not depend on the precise transition probabilities; and (b) linear space, so it ensures space efficiency. For various preprocessings for VI, see [ 9 , 24 , 27 , 40 ] . Question. Given the practical relevance of VI, multiple VI-based approaches have been proposed in the literature including Interval VI [ 24 , 3 ] , Variance-reduced VI [ 42 ] , Sound VI [ 40 ] , and Optimistic VI [ 27 ] . However, they all require exponentially many Bellman updates in the number of states in the worst case. Thus, a fundamental question is the existence of an efficient preprocessing that can achieve VI with sub-exponentially many Bellman updates. Our Contribution. Our main contributions are the following. • Sub-exponential VI for MCs. We present an almost linear-time preprocessing algorithm for MCs which, along with guessing values, requires only subexponentially many Bellman updates to approximate the value. Informally, the preprocessing obtains a set of states to guess values which are verified by solving the rest of the MC. The preprocessing to obtain the set of states where values will be guessed is based on breadth-first-search and set cardinality, so it can be symbolically implemented. See Theorem 3.1 for details. • VI convergence for MDPs. We present a new analysis of the speed of convergence of VI for MDPs. This improves on the previous bounds given in [ 24 ] and motivates the use of guessing in MDPs. • Practical approach for MDPs and experimental results. We present a new practical VI-based approach for MDPs called Guessing VI. We have implemented our approach on STORM [ 30 ] . We evaluate our approach on the Quantitative Verication Benchmark Set [ 28 ] against all existing VI-based approaches. We consider 474 examples: (i) in 170 examples all approaches run very fast (less than 100 milliseconds); (ii) in 135 examples, all approaches perform similarly (the max and min are within 10 % of each other); (iii) in 83 examples, there is a winner among the previous VI-based approaches over our approach, however, in these examples, the average improvement of each previous approach over ours is at most 1.15 times (i.e., 15% improvement); and (iv) in 86 examples our approach is the fastest, with an average improvement of at least 1.27 times (i.e., 27% improvement). Our experimental results show that our approach provides significant improvement over existing VI-based approaches. Related Works. There are three main preprocessings for MDPs used in the literature: (i) graph connectivity [ 17 , Section 3] ; (ii) qualitative reachability [ 21 , Algorithms 1-4] ; and (iii) collapsing Maximal end components (MECs) [ 11 ] . All these preprocessings run in subquadratic time and are standard in the literature. For example, after collapsing MECs, an MDP is usually referred to as contracting or halting [ 24 ] . For a given horizon, VI provides a strategy that is optimal, and