# Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 15 references that are in the map.
- First posted on arXiv 30 Sep 2026.

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

- [Improved and Generalized Upper Bounds on the Complexity of Policy Iteration](https://mlsanity.com/paper/1306.0386/) (2013)
- [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)
- [Lower Bound on Howard Policy Iteration for Deterministic Markov Decision Processes](https://mlsanity.com/paper/2506.12254/) (2025)

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

- [Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processes](https://mlsanity.com/paper/2610.02131/) (2026)

## Abstract (arXiv)

We establish exponential iteration lower bounds in the number of states for Howard's policy iteration on deterministic discounted and average-reward Markov decision processes (MDPs), with a constant number of actions per state. This rules out strong polynomiality of Howard's policy iteration in both settings. We further prove that a Dantzig counterpart of Howard's policy iteration runs in strongly polynomial time on deterministic average-reward MDPs. Together with the known strongly polynomial bound for Dantzig's rule on deterministic discounted MDPs, these results establish an exponential separation between the two algorithms in both settings. This separation between Howard's decentralized and simultaneous selfish improvements and Dantzig's coordinated selection of a single action with the largest improvement across all states reveals a ``price'' of algorithmic anarchy.