Exponential Lower Bounds For Policy Iteration
Computer Science - Data Structures and Algorithms
arxiv: Computer Science::Computer Science and Game Theory
We study policy iteration for infinite-horizon Markov decision processes. It has recently been shown policy iteration style algorithms have exponential lower bounds in a two player game setting. We extend these lower bounds to Markov decision processes with the total reward and average-reward optimality criteria.