# Improved and Generalized Upper Bounds on the Complexity of Policy Iteration

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

## Key facts

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

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

- [On the Linear convergence of Natural Policy Gradient Algorithm](https://mlsanity.com/paper/2105.01424/) (2021)
- [Acting in Delayed Environments with Non-Stationary Markov Policies](https://mlsanity.com/paper/2101.11992/) (2021)
- [Optimal Convergence Rate for Exact Policy Mirror Descent in Discounted Markov Decision Processes](https://mlsanity.com/paper/2302.11381/) (2023)
- [Homotopic Policy Mirror Descent: Policy Convergence, Implicit Regularization, and Improved Sample Complexity](https://mlsanity.com/paper/2201.09457/) (2022)
- [Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factor](https://mlsanity.com/paper/2302.00036/) (2023)
- [Approximate Policy Iteration with Bisimulation Metrics](https://mlsanity.com/paper/2202.02881/) (2022)
- [Continual Auxiliary Task Learning](https://mlsanity.com/paper/2202.11133/) (2022)
- [Planning and Learning with Adaptive Lookahead](https://mlsanity.com/paper/2201.12403/) (2022)
- [Truncated Variance Reduced Value Iteration](https://mlsanity.com/paper/2405.12952/) (2024)
- [TensorPlan and the Few Actions Lower Bound for Planning in MDPs under Linear Realizability of Optimal Value Functions](https://mlsanity.com/paper/2110.02195/) (2021)
- [The complexity of non-stationary reinforcement learning](https://mlsanity.com/paper/2307.06877/) (2023)
- [Policy Mirror Descent with Lookahead](https://mlsanity.com/paper/2403.14156/) (2024)
- [Why Policy Gradient Algorithms Work for Undiscounted Total-Reward MDPs](https://mlsanity.com/paper/2510.18340/) (2025)
- [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)
- [Geometric Re-Analysis of Classical MDP Solving Algorithms](https://mlsanity.com/paper/2503.04203/) (2025)
- [Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy](https://mlsanity.com/paper/2609.40147/) (2026)
- [Acceleration in Policy Optimization](https://mlsanity.com/paper/2306.10587/) (2023)
- [Natural Policy Gradient as Doubly Smoothed Policy Iteration: A Bellman-Operator Framework](https://mlsanity.com/paper/2605.10671/) (2026)
- [Mathematical methods of reinforcement learning](https://mlsanity.com/paper/2607.06935/) (2026)
- [Limiting-Kernel Q(λ): Bridging Short and Long Horizons](https://mlsanity.com/paper/2609.27741/) (2026)

## Abstract (arXiv)

Given a Markov Decision Process (MDP) with n states and a totalnumber m of actions, we study the number of iterations needed byPolicy Iteration (PI) algorithms to converge to the optimalγ-discounted policy. We consider two variations of PI: Howard'sPI that changes the actions in all states with a positive advantage,and Simplex-PI that only changes the action in the state with maximaladvantage. We show that Howard's PI terminates after at most Oleft(fracm1-γlogleft(frac11-γright)right)iterations, improving by a factor O(log n) a result by Hansen etal., while Simplex-PI terminates after at most Oleft(fracnm1-γlogleft(frac11-γright)right)iterations, improving by a factor O(log n) a result by Ye. Undersome structural properties of the MDP, we then consider bounds thatare independent of the discount factor~γ: quantities ofinterest are bounds τt and τr---uniform on all states andpolicies---respectively on the expected time spent in transientstates and the inverse of the frequency of visits in recurrentstates given that the process starts from the uniform distribution.Indeed, we show that Simplex-PI terminates after at most tilde Oleft(n3 m2 τt τr right) iterations. This extends arecent result for deterministic MDPs by Post & Ye, in which τt≤ 1 and τr ≤ n, in particular it shows that Simplex-PI isstrongly polynomial for a much larger class of MDPs. We explain whysimilar results seem hard to derive for Howard's PI. Finally, underthe additional (restrictive) assumption that the state space ispartitioned in two sets, respectively states that are transient andrecurrent for all policies, we show that both Howard's PI andSimplex-PI terminate after at most tilde O(m(n2τt+nτr))iterations.