Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy
This research proves that Howard's policy iteration algorithm requires an exponential number of steps to solve deterministic discounted Markov decision processes, even when each state has at most two actions. This result contrasts sharply with strongly polynomial methods like Dantzig’s pivoting rule, highlighting the significant computational cost associated with Howard's decentralized approach.