Finite-Sample Analysis of Least-Squares Policy Iteration

Alessandro Lazaric 1 Mohammad Ghavamzadeh 1 Rémi Munos 1
1 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal, Inria Lille - Nord Europe
Abstract : In this paper, we report a performance bound for the widely used least-squares policy iteration (LSPI) algorithm. We first consider the problem of policy evaluation in reinforcement learning, that is, learning the value function of a fixed policy, using the least-squares temporal-difference (LSTD) learning method, and report finite-sample analysis for this algorithm. To do so, we first derive a bound on the performance of the LSTD solution evaluated at the states generated by the Markov chain and used by the algorithm to learn an estimate of the value function. This result is general in the sense that no assumption is made on the existence of a stationary distribution for the Markov chain. We then derive generalization bounds in the case when the Markov chain possesses a stationary distribution and is $\beta$-mixing. Finally, we analyze how the error at each policy evaluation step is propagated through the iterations of a policy iteration method, and derive a performance bound for the LSPI algorithm.
Type de document :
Article dans une revue
Journal of Machine Learning Research, Journal of Machine Learning Research, 2012, 13, pp.3041-3074
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00772060
Contributeur : Alessandro Lazaric <>
Soumis le : mercredi 9 janvier 2013 - 18:52:59
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : mercredi 10 avril 2013 - 03:56:32

Fichier

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

Identifiants

  • HAL Id : hal-00772060, version 1

Collections

Citation

Alessandro Lazaric, Mohammad Ghavamzadeh, Rémi Munos. Finite-Sample Analysis of Least-Squares Policy Iteration. Journal of Machine Learning Research, Journal of Machine Learning Research, 2012, 13, pp.3041-3074. 〈hal-00772060〉

Partager

Métriques

Consultations de la notice

297

Téléchargements de fichiers

193