# On the Complexity of Policy Iteration

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jan 2013.

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

- [Geometric Policy Iteration for Markov Decision Processes](https://mlsanity.com/paper/2206.05809/) (2022)
- [Howard's Policy Iteration is Subexponential for Deterministic Markov Decision Problems with Rewards of Fixed Bit-size and Arbitrary Discount Factor](https://mlsanity.com/paper/2505.00795/) (2025)
- [Efficient Computation of Blackwell Optimal Policies using Rational Functions](https://mlsanity.com/paper/2508.18252/) (2025)

## Abstract (arXiv)

Decision-making problems in uncertain or stochastic domains are often formulated as Markov decision processes (MDPs). Policy iteration (PI) is a popular algorithm for searching over policy-space, the size of which is exponential in the number of states. We are interested in bounds on the complexity of PI that do not depend on the value of the discount factor. In this paper we prove the first such non-trivial, worst-case, upper bounds on the number of iterations required by PI to converge to the optimal policy. Our analysis also sheds new light on the manner in which PI progresses through the space of policies.