Université Lille1 - Sciences et Technologies Sample complexity in sequential decision-making Complexité d’échantillonnage pour la prise de décision séquentielle Apprentissage par renforcement Apprentissage statistique Échantillons finis 519.54 Prise de décision (statistique) Apprentissage automatique Programmation dynamique Échantillonnage (statistique) Algorithmes d'approximation De nombreux problèmes intéressants 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. Electronic Thesis or Dissertation Text en application/pdf 1 : 1374 Ko https://pepite-depot.univ-lille.fr/LIBRE/HDR/2014/HDR2014LIL110.pdf Ghavamzadeh Mohammad 1972-09-07 FR 181393115 2014-06-11 Mathématiques Université Lille1 - Sciences et Technologies thesis.degree.grantor_1 026404184 HDR non oui Preux Philippe intervenant_1 059896353 ecoleDoctorale_1 Institut national de recherche en informatique et en automatique (France). Centre de recherche Lille - Nord Europe partenaireRecherche_1 185432247 ddc:510 Preux Philippe Université Lille1 - Sciences et Technologies Université Lille1 - Sciences et Technologies Institut national de recherche en informatique et en automatique (France). Centre de recherche Lille - Nord Europe ASCII PDF 1406889