Approximate modified policy iteration and its application to the game of Tetris - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Journal of Machine Learning Research Année : 2015

Approximate modified policy iteration and its application to the game of Tetris

Mohammad Ghavamzadeh
  • Fonction : Auteur
  • PersonId : 868946
Victor Gabillon
  • Fonction : Auteur
  • PersonId : 925091
Boris Lesner
  • Fonction : Auteur
  • PersonId : 933391

Résumé

Modified policy iteration (MPI) is a dynamic programming (DP) algorithm that contains the two celebrated policy and value iteration methods. Despite its generality, MPI has not been thoroughly studied, especially its approximation form which is used when the state and/or action spaces are large or infinite. In this paper, we propose three implementations of approximate MPI (AMPI) that are extensions of the well-known approximate DP algorithms:~fitted-value iteration, fitted-Q iteration, and classification-based policy iteration. We provide error propagation analysis that unify those for approximate policy and value iteration. We develop the finite-sample analysis of these algorithms, which highlights the influence of their parameters. In the classification-based version of the algorithm (CBMPI), the analysis shows that MPI's main parameter controls the balance between the estimation error of the classifier and the overall value function approximation. We illustrate and evaluate the behavior of these new algorithms in the Mountain Car and Tetris problems. Remarkably, in Tetris, CBMPI outperforms the existing DP approaches by a large margin, and competes with the current state-of-the-art methods while using fewer samples.
Fichier principal
Vignette du fichier
final.pdf (736.54 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01091341 , version 1 (08-12-2014)

Licence

Paternité

Identifiants

  • HAL Id : hal-01091341 , version 1

Citer

Bruno Scherrer, Mohammad Ghavamzadeh, Victor Gabillon, Boris Lesner, Matthieu Geist. Approximate modified policy iteration and its application to the game of Tetris. Journal of Machine Learning Research, 2015, 16, pp.1629−1676. ⟨hal-01091341⟩
815 Consultations
643 Téléchargements

Partager

Gmail Facebook X LinkedIn More