The complexity of Policy Iteration is exponential for discounted Markov Decision Processes
Authors:
- 1 December 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 01912216,p. 5997-6002
Abstract
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.Keywords
This publication has 13 references indexed in Scilit:
- Smart finite state devices: A modeling framework for demand response technologies2011
- The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount RateMathematics of Operations Research, 2011
- Lower Bounds for Howard’s Algorithm for Finding Minimum Mean-Cost CyclesLecture Notes in Computer Science, 2010
- Fragile link structure in PageRank computation2009
- The Complexity of Solving Stochastic Games on Graphs2009
- Smoothed analysis of algorithmsJournal of the ACM, 2004
- Markov Decision Processes1994
- A Survey of Applications of Markov Decision ProcessesJournal of the Operational Research Society, 1993
- An Analysis of Stochastic Shortest Path ProblemsMathematics of Operations Research, 1991
- A polynomial time bound for Howard's policy improvement algorithmOR Spectrum, 1986