{"id":"arxiv/2609.40147","url":"https://arxiv.org/abs/2609.40147","tags":["cs.LG","cs.DS","math.OC"],"score":0,"title":"Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy","domain":"cs.LG","source":"arxiv","authors":["Han Zhong","Yinyu Ye"],"reviews":0,"subject":"cs.LG","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-30","reactions":{}}