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.
Type de document :
Article dans une revue
Journal of Machine Learning Research, Journal of Machine Learning Research, 2013, 14, pp.1175-1221
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00759102
Contributeur : Bruno Scherrer <>
Soumis le : vendredi 26 avril 2013 - 10:28:52
Dernière modification le : jeudi 11 janvier 2018 - 06:25:23
Document(s) archivé(s) le : samedi 27 juillet 2013 - 04:04:42

Fichiers

article.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

366

Téléchargements de fichiers

390