De nombreux problèmes intréssants de prise de décision séquentielle peuvent être formulés comme des problèmes d'apprentissage par renforcement. En apprentissage par renforcement, un agent interagit avec un environnement dynamique, stochastique et qu'il ne connaît que partiellement, dans le but de trouver une stratégie de prise d'actions, ou politique, qui maximise une certaine mesure de performance à long terme. Les algorithmes de programmation dynamique sont les outils les plus puissants pour résoudre les problèmes d'apprentissage par renforcement, c'est à dire pour trouver la politique optimale. Cependant, pour ces algorithmes, la découverte du comportement décisionnel optimal n'est garantie que si l'environnement (à savoir, la dynamique de l'état du système et les récompenses) est connu de manière complète et que les espaces d'état et d'action ne sont pas de trop grandes tailles. Lorsque l'une de ces conditions se trouve violée (par exemple si l'unique information disponible sur l'environnement prend la forme d'échantillons de transitions et de récompenses), des algorithmes d'approximation sont requis, et dès lors, les méthodes de programmation dynamique se convertissent en méthodes de programmation dynamique approchée et en algorithmes d'apprentissage par renforcement. La théorie de l'apprentissage statistique est fondamentale pour l'étude des propriétés statistiques des algorithmes développés en apprentissage automatique. En particulier, apprentissage statistique décrit l'interaction entre le processus générant les échantillons et l'espace d'hypothèse utilisé par l'algorithme d'apprentissage, et établit à quelles conditions et dans quelles mesures les problèmes de régression et de classification peuvent être résolus. Ces résultats ont aussi montré leur utilité pour dimensionner les problèmes d'apprentissage automatique (nombre d'échantillons, complexité de l'espace d'hypothèse) et pour ajuster les paramètres des algorithmes (par exemple le paramètre de régularisation des méthodes de régularisation). L'objet principal de ce travail est d'employer les outils de l'apprentissage statistique afin d'étudier les performances des algorithmes d'apprentissage par renforcement hors ligne et de programmation dynamique approchée pour aboutir à des bornes en échantillons finis sur la perte en performance (par rapport à la politique optimale) de la politique apprise par ces algorithmes. Un tel objectif demande de combiner efficacement des outils de l'apprentissage statistique avec les algorithmes de programmation dynamique approchée, et de montrer comment l'erreur se propage d'itération en itération chez ces algorithmes itératifs. Nous considérons différents types d'algorithmes de programmation dynamique approchée : basés soit sur une régression, une classification ou une méthode de point fixe, et, pour chacun, nous soulignons les principaux défis que posent leurs analyses en échantillons finis.
defended on 11/06/2014
français
English