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

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.
Keywords :
Document type :
Journal articles
Domain :
Complete list of metadatas

Cited literature [23 references]

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⟩

Record views

Files downloads