Combinés à des réseaux de neurones profonds ("Deep Neural Networks"), certains algorithmes d'apprentissage par renforcement tels que "Q-learning" ou "Policy Gradient" sont désormais capables de battre les meilleurs joueurs humains à la plupart des jeux de console Atari ainsi qu'au jeu de Go. Malgré des résultats spectaculaires et très prometteurs, ces méthodes d'apprentissage par renforcement dit "profond" ("Deep Reinforcement Learning") requièrent un nombre considérable d'observations pour apprendre, limitant ainsi leur déploiement partout où l'obtention de nouveaux échantillons s'avère "coûteuse". Le manque d'efficacité de tels algorithmes dans l'exploitation des échantillons peut en partie s'expliquer par l'utilisation de réseaux de neurones profonds, connus pour être très "gourmands" en données. Mais il s'explique surtout par le recours à des algorithmes de renforcement explorant leur environnement de manière inefficace et non ciblée. Ainsi, des algorithmes tels que Q-learning ou encore Policy-Gradient exécutent des actions partiellement randomisées afin d'assurer une exploration suffisante. Cette stratégie est dans la plupart des cas inappropriée pour atteindre un bon compromis entre l'exploration indispensable à la découverte de nouvelles régions avantageuses (aux récompenses élevées), et l'exploitation de régions déjà identifiées comme telles. D'autres approches d'apprentissage par renforcement ont été développées, pour lesquelles il est possible de garantir un meilleur compromis exploration-exploitation, parfois proche de l'optimum théorique. Cet axe de recherche s'inspire notamment de la littérature sur le cas particulier du problème du bandit manchot, avec des algorithmes s'appuyant souvent sur le principe "d'optimisme dans l'incertain". Malgré les nombreux travaux sur le compromis exploration-exploitation, beaucoup de questions restent encore ouvertes. Dans cette thèse, nous nous proposons de généraliser les travaux existants sur le compromis exploration-exploitation à des contextes différents, avec plus ou moins de connaissances a priori. Nous proposons plusieurs améliorations des algorithmes de l'état de l'art ainsi qu'une analyse théorique plus fine permettant de répondre à plusieurs questions ouvertes sur le compromis exploration-exploitation. Nous relâchons ensuite l'hypothèse peu réaliste (bien que fréquente) selon laquelle il existe toujours un chemin permettant de relier deux régions distinctes de l'environnement. Le simple fait de relâcher cette hypothèse permet de mettre en lumière l'impact des connaissances a priori sur les limites intrinsèques du compromis exploration-exploitation. Enfin, nous montrons comment certaines connaissances a priori comme l'amplitude de la fonction valeur ou encore des ensembles de macro-actions peuvent être exploitées pour accélerer l'apprentissage. Tout au long de cette thèse, nous nous sommes attachés à toujours tenir compte de la complexité algorithmique des différentes méthodes proposées. Bien que relativement efficaces, tous les algorithmes présentés nécessitent une phase de planification et souffrent donc du problème bien connu du "fléau de la dimension", ce qui limite fortement leur potentiel applicatif (avec les méthodes actuelles). L'objectif phare des présents travaux est d'établir des principes généraux pouvant être combinés avec des approches plus heuristiques pour dépasser les limites des algorithmes actuels.
M. Aurélien GARIVIER Ecole Normale Supérieure de Lyon Examinateur M. Peter AUER Université de Leoben Rapporteur Mme Shipra AGRAWAL Columbia University Rapporteur M. Marc TOMMASI Université de Lille Examinateur Mme Doina PRECUP McGill University Examinateur M. Alessandro LAZARIC Inria Examinateur
français
English