# Stopping Criteria for Value Iteration on Stochastic Games with Quantitative Objectives

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 51 references that are in the map.
- First posted on arXiv 19 Apr 2023.

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

- [Verification of Markov Decision Processes using Learning Algorithms](https://mlsanity.com/paper/1402.2967/) (2014)
- [A storm is Coming: A Modern Probabilistic Model Checker](https://mlsanity.com/paper/1702.04311/) (2017)
- [Topological Value Iteration Algorithms](https://mlsanity.com/paper/1401.3910/) (2014)
- [A Practitioner's Guide to MDP Model Checking Algorithms](https://mlsanity.com/paper/2301.10197/) (2023)
- [Value Iteration for Simple Stochastic Games: Stopping Criterion and Learning Algorithm](https://mlsanity.com/paper/1804.04901/) (2018)
- [On the Complexity of Value Iteration](https://mlsanity.com/paper/1807.04920/) (2018)
- [Optimistic Value Iteration](https://mlsanity.com/paper/1910.01100/) (2019)
- [Value Iteration for Long-run Average Reward in Markov Decision Processes](https://mlsanity.com/paper/1705.02326/) (2017)
- [Sound Value Iteration](https://mlsanity.com/paper/1804.05001/) (2018)
- [Comparison of Algorithms for Simple Stochastic Games (Full Version)](https://mlsanity.com/paper/2008.09465/) (2020)
- [Conditional Value-at-Risk for Reachability and Mean Payoff in Markov Decision Processes](https://mlsanity.com/paper/1805.02946/) (2018)
- [Risk-aware Stochastic Shortest Path](https://mlsanity.com/paper/2203.01640/) (2022)
- [On Strong Determinacy of Countable Stochastic Games](https://mlsanity.com/paper/1704.05003/) (2017)
- [Efficient Strategy Iteration for Mean Payoff in Markov Decision Processes](https://mlsanity.com/paper/1707.01859/) (2017)
- [Widest Paths and Global Propagation in Bounded Value Iteration for Stochastic Games](https://mlsanity.com/paper/2007.07421/) (2020)
- [Approximating Values of Generalized-Reachability Stochastic Games](https://mlsanity.com/paper/1908.05106/) (2019)

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

- [Solving Robust Markov Decision Processes: Generic, Reliable, Efficient](https://mlsanity.com/paper/2412.10185/) (2024)
- [Playing Games with your PET: Extending the Partial Exploration Tool to Stochastic Games](https://mlsanity.com/paper/2405.03885/) (2024)
- [Stopping Criteria for Value Iteration on Concurrent Stochastic Reachability and Safety Games](https://mlsanity.com/paper/2505.21087/) (2025)

## Abstract (arXiv)

A classic solution technique for Markov decision processes (MDP) and stochastic games (SG) is value iteration (VI). Due to its good practical performance, this approximative approach is typically preferred over exact techniques, even though no practical bounds on the imprecision of the result could be given until recently. As a consequence, even the most used model checkers could return arbitrarily wrong results. Over the past decade, different works derived stopping criteria, indicating when the precision reaches the desired level, for various settings, in particular MDP with reachability, total reward, and mean payoff, and SG with reachability. In this paper, we provide the first stopping criteria for VI on SG with total reward and mean payoff, yielding the first anytime algorithms in these settings. To this end, we provide the solution in two flavours: First through a reduction to the MDP case and second directly on SG. The former is simpler and automatically utilizes any advances on MDP. The latter allows for more local computations, heading towards better practical efficiency. Our solution unifies the previously mentioned approaches for MDP and SG and their underlying ideas. To achieve this, we isolate objective-specific subroutines as well as identify objective-independent concepts. These structural concepts, while surprisingly simple, form the very essence of the unified solution.