Abstract
We establish an exponential iteration lower bound in the number of states for Howard's policy iteration on deterministic discounted Markov decision processes, with at most two actions per state. This rules out strong polynomiality of Howard's policy iteration when the discount factor is part of the input and yields an exponential separation from the simplex method with Dantzig's pivoting rule, which is proved to be strongly polynomial on this class. Even when each reward is restricted to logarithmic bit length, we obtain a stretched-exponential iteration lower bound. The gap between Howard's decentralized and simultaneous selfish improvements and Dantzig's coordinated selection of a single action with the largest gain across all states reveals a ``price'' of algorithmic anarchy.
Keywords
Subject
Publication details
- Journal
- Not available
- Open access
- Green open access
Cite this article
APA 7
Zhong, H., & Ye, Y. (2026). Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy. https://omanscience.com/en/articles/policy-iteration-is-not-strongly-polynomial-for-deterministic-markov-decision-processes-the-price-of-algorithmic-anarchy
MLA 9
Zhong, Han, and Yinyu Ye. "Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy." https://omanscience.com/en/articles/policy-iteration-is-not-strongly-polynomial-for-deterministic-markov-decision-processes-the-price-of-algorithmic-anarchy.
Chicago (author–date)
Zhong, Han, and Yinyu Ye. 2026. "Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy." https://omanscience.com/en/articles/policy-iteration-is-not-strongly-polynomial-for-deterministic-markov-decision-processes-the-price-of-algorithmic-anarchy.
Harvard
Zhong, H. and Ye, Y. (2026) 'Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy', Available at: https://omanscience.com/en/articles/policy-iteration-is-not-strongly-polynomial-for-deterministic-markov-decision-processes-the-price-of-algorithmic-anarchy.
Vancouver
Zhong H, Ye Y. Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy. https://omanscience.com/en/articles/policy-iteration-is-not-strongly-polynomial-for-deterministic-markov-decision-processes-the-price-of-algorithmic-anarchy
IEEE
H. Zhong, and Y. Ye, "Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy," https://omanscience.com/en/articles/policy-iteration-is-not-strongly-polynomial-for-deterministic-markov-decision-processes-the-price-of-algorithmic-anarchy.