On the Complexity of Policy Iteration

Abstract

Decision-making problems in uncertain or stochastic domains are often formulated as Markov decision processes (MDPs). Policy iteration (PI) is a popular algorithm for searching over policy-space, the size of which is exponential in the number of states. We are interested in bounds on the complexity of PI that do not depend on the value of the discount factor. In this paper we prove the first such non-trivial, worst-case, upper bounds on the number of iterations required by PI to converge to the optimal policy. Our analysis also sheds new light on the manner in which PI progresses through the space of policies.

Appears in Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence (UAI1999)

Cited by in corpus (10)

• A Learning Theoretic Approach to Energy Harvesting Communication System Optimization
• Primal-Dual $\pi$ Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems
• Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity
• Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Running Time
• Lower Bound On the Computational Complexity of Discounted Markov Decision Problems
• The greedy strategy in optimizing the Perron eigenvalue
• Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes
• Policy Iteration is well suited to optimize PageRank
• Geometric Policy Iteration for Markov Decision Processes
• Faster Algorithms for Quantitative Analysis of Markov Chains and Markov Decision Processes with Small Treewidth