# Efficient Strategy Iteration for Mean Payoff in Markov Decision Processes

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jul 2017.

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

- [Stopping Criteria for Value Iteration on Stochastic Games with Quantitative Objectives](https://mlsanity.com/paper/2304.09930/) (2023)
- [Abstraction-based Probabilistic Stability Analysis of Polyhedral Probabilistic Hybrid Systems](https://mlsanity.com/paper/2304.02647/) (2023)

## Abstract (arXiv)

Markov decision processes (MDPs) are standard models for probabilistic systems with non-deterministic behaviours. Mean payoff (or long-run average reward) provides a mathematically elegant formalism to express performance related properties. Strategy iteration is one of the solution techniques applicable in this context. While in many other contexts it is the technique of choice due to advantages over e.g. value iteration, such as precision or possibility of domain-knowledge-aware initialization, it is rarely used for MDPs, since there it scales worse than value iteration. We provide several techniques that speed up strategy iteration by orders of magnitude for many MDPs, eliminating the performance disadvantage while preserving all its advantages.