Exponential Lower Bounds for Policy Iteration
作者： John Fearnley
DOI: 10.1007/978-3-642-14162-1_46
关键词:
摘要: We study policy iteration for infinite-horizon Markov decision processes. It has recently been shown style algorithms have exponential lower bounds in a two player game setting. extend these to processes with the total reward and average-reward optimality criteria.
springer.com
core.ac.uk
warwick.ac.uk
harvard.edu
springerlink.com参考文章(10)
Robert B. Ash, Catherine Doléans-Dade, Probability and measure theory ,(1999)
Yishay Mansour, Satinder Singh, On the complexity of policy iteration uncertainty in artificial intelligence. pp. 401- 408 ,(1999)
Jens Vöge, Marcin Jurdziński, A Discrete Strategy Improvement Algorithm for Solving Parity Games computer aided verification. pp. 202- 215 ,(2000) , 10.1007/10722167_18
Oliver Friedmann, A Super-Polynomial Lower Bound for the Parity Game Strategy Improvement Algorithm as We Know it arXiv: Computer Science and Game Theory. ,(2009)
Ronald A. Howard, Dynamic Programming and Markov Processes ,(1960)
Martin L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming ,(1994)
Oliver Friedmann, An Exponential Lower Bound for the Parity Game Strategy Improvement Algorithm as We Know it logic in computer science. pp. 145- 156 ,(2009) , 10.1109/LICS.2009.27
Mary Melekopoglou, Anne Condon, On the Complexity of the Policy Improvement Algorithm for Markov Decision Processes Informs Journal on Computing. ,vol. 6, pp. 188- 192 ,(1994) , 10.1287/IJOC.6.2.188
Markov Decision Processes Journal of The Royal Statistical Society Series A-statistics in Society. ,vol. 158, pp. 636- ,(1994) , 10.1002/9780470316887
Marcin Jurdzinski, Jens Voge, A discrete strategy improvement algorithm for solving parity games (extended abstract) computer aided verification. pp. 202- 215 ,(2000)