Improved bound on the worst case complexity of Policy Iteration

Hollanders, Romain;Gerencser, Balazs;Delvenne, Jean-Charles;Jungers, Raphaël
(2016) Operations Research Letters — Vol. 44, p. 267-272 (2016)

Files

1-s20-S0167637716000201-main.pdf
  • Closed Access
  • Adobe PDF
  • 412.59 KB
Request a copy

Details

Authors
Abstract
Solving Markov Decision Processes is a recurrent task in engineering which can be performed efficiently in practice using the Policy Iteration algorithm. Regarding its complexity, both lower and upper bounds are known to be exponential (but far apart) in the size of the problem. In this work, we provide the first improvement over the now standard upper bound from Mansour and Singh (1999). We also show that this bound is tight for a natural relaxation of the problem.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Hollanders, R., Gerencser, B., Delvenne, J.-C., & Jungers, R. (2016). Improved bound on the worst case complexity of Policy Iteration. Operations Research Letters, 44, 267-272. https://doi.org/10.1016/j.orl.2016.01.010 (Original work published 2016)