Vitesse de convergence et borne d'erreur pour l'algorithme LSTD($\lambda$)

Manel Tagorti (1) , Bruno Scherrer (1)

1 MAIA - Autonomous intelligent machine

On considère l'algorithme LSTD($\lambda$) (least-squares temporal-difference) avec traces d'éligibilité proposé par Boyan (2002). Cet algorithme renvoie, pour une politique fixée, une approximation linéaire de la fonction de valeur $v$ pour les processus décisionnels de Markov admettant un grand espace d'états. On se restreint dans cet article au cas des chaînes de Markov $\beta$-mélangeantes. Sous cette hypothèse, on estime la vitesse de convergence de cet algorithme pour n'importe quelle valeur de $\lambda\in(0,1)$. La borne d'erreur obtenue étend et améliore celle introduite par Lazaric et al. (2012) pour le cas $\lambda=0$. L'analyse proposée permet de quantifier l'influence du paramètre $\lambda$, de l'espace linéaire de projection et du nombre d'échantillons utilisés.

Domaines: Apprentissage [cs.LG]; Intelligence artificielle [cs.AI]; Optimisation et contrôle [math.OC]; Machine Learning [stat.ML]

Manel Tagorti, Bruno Scherrer. Vitesse de convergence et borne d'erreur pour l'algorithme LSTD($\lambda$). JFPDA - 9èmes Journées Francophones sur la Planification, la Décision et l'Apprentissage pour la conduite de systèmes, May 2014, Liège, Belgique. ⟨hal-00990508⟩