The complexity of Policy Iteration is exponential for discounted Markov Decision Processes
Romain Hollanders, Jean‐Charles Delvenne, Raphaël M. Jungers · 2012
The question of knowing whether the Policy Iteration algorithm (PI) for solving stationary Markov Decision Processes (MDPs) has exponential or (strongly) polynomial complexity has attracted much attention in the last 25 years. Recently, a family of examples on which PI requires an exponential number of iterations to converge was proposed for the total-reward and the average-reward criteria. On the other hand, it was shown that PI runs in strongly polynomial time on discounted-reward MDPs, yet only when the discount factor is fixed beforehand. In this work, we show that PI needs an exponential number of steps to converge on discounted-reward MDPs with a general discount factor.