Policy iteration faces exponential slowdown on some decision problems

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

Machine LearningData Structures and Algorithms

Summary

The paper shows that a common method for solving decision-making problems called Howard's policy iteration can take a very long time on certain types of problems, even if the problem is simple with just two choices at each step. This method is slower than another approach called the simplex method in these cases. They explain that this difference happens because Howard's method improves decisions locally and independently, while the simplex method picks the very best improvement globally. This finding is important for understanding the limits of popular algorithms in decision tasks.

What this means in practice

A theory result. No direct application yet.

Authors

Han Zhong, Yinyu Ye

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.
View PDFOpen arXiv