Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy
Abstract
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.
Related
- Simple Strategy-Iteration with Dantzig's Rule is not Strongly Polynomial on Turn-Based Deterministic Games
- Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processes
- SDDP has polynomial iteration complexity in the horizon
- A deterministic polynomial-time algorithm for the Bilu--Linial signing problem on bipartite graphs
- Algorithmic Non-dimensionalisation of Polynomial Dynamical Systems with CRNNondim
BibTeX
@misc{zhong2026policy,
title = {{Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy}},
author = {Han Zhong and Yinyu Ye},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.40147},
eprint = {2609.40147},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.40147},
}
RIS
TY - UNPB
TI - Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy
AU - Han Zhong
AU - Yinyu Ye
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2609.40147
UR - https://arxiv.org/abs/2609.40147
AB - 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.
ER -