Performance Bounds for Lambda Policy Iteration and Application to the Game of Tetris

Bruno Scherrer 1
1 MAIA - Autonomous intelligent machine
Inria Nancy - Grand Est, LORIA - AIS - Department of Complex Systems, Artificial Intelligence & Robotics
Abstract : We consider the discrete-time infinite-horizon optimal control problem formalized by Markov decision processes (Puterman, 1994; Bertsekas and Tsitsiklis, 1996). We revisit the work of Bertsekas and Ioffe (1996), that introduced $\lambda$ policy iteration-a family of algorithms parametrized by a parameter $\lambda$-that generalizes the standard algorithms value and policy iteration, and has some deep connections with the temporal-difference algorithms described by Sutton and Barto (1998). We deepen the original theory developed by the authors by providing convergence rate bounds which generalize standard bounds for value iteration described for instance by Puterman (1994). Then, the main contribution of this paper is to develop the theory of this algorithm when it is used in an approximate form. We extend and unify the separate analyzes developed by Munos for approximate value iteration (Munos, 2003) and approximate policy iteration (Munos, 2003), and provide performance bounds in the discounted and the undiscounted situations. Finally, we revisit the use of this algorithm in the training of a Tetris playing controller as originally done by Bertsekas and Ioffe (1996).. Our empirical results are different from those of Bertsekas and Ioffe (which were originally qualified as "paradoxical" and "intriguing"). We track down the reason to be a minor implementation error of the algorithm, which suggests that, in practice, $\lambda$ policy iteration may be more stable than previously thought.
Complete list of metadatas

Cited literature [23 references]  Display  Hide  Download

https://hal.inria.fr/hal-00759102
Contributor : Bruno Scherrer <>
Submitted on : Friday, April 26, 2013 - 10:28:52 AM
Last modification on : Tuesday, December 18, 2018 - 4:40:21 PM
Long-term archiving on : Saturday, July 27, 2013 - 4:04:42 AM

Files

article.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00759102, version 2
  • ARXIV : 0711.0694

Citation

Bruno Scherrer. Performance Bounds for Lambda Policy Iteration and Application to the Game of Tetris. Journal of Machine Learning Research, Journal of Machine Learning Research, 2013, 14, pp.1175-1221. ⟨hal-00759102v2⟩

Share

Metrics

Record views

408

Files downloads

468