# On the Complexity of Value Iteration

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jul 2018.

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

- [Risk-aware Stochastic Shortest Path](https://mlsanity.com/paper/2203.01640/) (2022)
- [Federated Learning With Energy Harvesting Devices: An MDP Framework](https://mlsanity.com/paper/2405.10513/) (2024)
- [On the Hardness of Reinforcement Learning with Transition Look-Ahead](https://mlsanity.com/paper/2510.19372/) (2025)
- [Stopping Criteria for Value Iteration on Stochastic Games with Quantitative Objectives](https://mlsanity.com/paper/2304.09930/) (2023)
- [Reductive MDPs: A Perspective Beyond Temporal Horizons](https://mlsanity.com/paper/2205.07338/) (2022)
- [Markov Decision Processes with Time-Varying Geometric Discounting](https://mlsanity.com/paper/2307.10491/) (2023)
- [Value Iteration with Guessing for Markov Chains and Markov Decision Processes](https://mlsanity.com/paper/2505.06769/) (2025)
- [Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead](https://mlsanity.com/paper/2609.11807/) (2026)

## Abstract (arXiv)

Value iteration is a fundamental algorithm for solving Markov Decision Processes (MDPs). It computes the maximal n-step payoff by iterating n times a recurrence equation which is naturally associated to the MDP. At the same time, value iteration provides a policy for the MDP that is optimal on a given finite horizon n. In this paper, we settle the computational complexity of value iteration. We show that, given a horizon n in binary and an MDP, computing an optimal policy is EXP-complete, thus resolving an open problem that goes back to the seminal 1987 paper on the complexity of MDPs by Papadimitriou and Tsitsiklis. As a stepping stone, we show that it is EXP-complete to compute the n-fold iteration (with n in binary) of a function given by a straight-line program over the integers with max and + as operators.