Dans nos sociétés modernes, une gestion minutieuse des ressources naturelles, énergétiques, humaines et informatiques est nécessaire. Comprendre les dynamiques de systèmes complexes et gérer les interactions de manière optimale constituent un enjeu majeur. Pour surmonter la limite des capacités humaines à traiter de grandes quantités de données, les chercheurs en apprentissage automatique et statistiques mathématiques pour la prise de décision séquentielle ont pour objectif de développer une méthode automatique et optimale pouvant, à partir d'observations partielles et d'interactions séquentielles avec un système complexe, apprendre un comportement optimal. Alors que le contrôle optimal considère que la dynamique du système est supposée connue, l'apprentissage par renforcement s'intéresse au cas où la dynamique est inconnue et doit être apprise uniquement à partir d'observations. Une difficulté clé pour concevoir une solution à ces problèmes est que, lorsqu'une décision est prise, seulement un effet bruité de cette décision est observée. Et cela renseigne peu sur les décisions alternatives. Cela donne lieu à l’étude du compromis fondamental entre exploration et exploitation: doit-on suivre un algorithme déjà beaucoup utilisé par le passé et empiriquement viable (exploitation) ou doit-on explorer un algorithme moins connue mais potentiellement meilleur (exploration)? Aborder ce compromis donne lieu à diverses approches en fonction de la structure sous-jacente au système dynamique, la notion de structure pouvant être comprise de différentes façons. Puisque ne pas tirer avantage de la structure (éventuellement cachée) est susceptible d’occasionner des algorithmes largement sous-optimaux, il est crucial d’examiner la manière de concevoir des algorithmes d’apprentissage qui peuvent s’adapter à celle-ci. Dans cette thèse, nous souhaitons mieux comprendre comment la notion de structure modifie les garanties d’apprentissage et suggère de nouveaux algorithmes plus performants dans le contexte des bandits. Notre attention sera particulièrement portée sur les structures dites unimodal, multimodal et de graphe. Pour chacune de ces structures nous introduisons un algorithme, respectivement IMED-UB, IMED-MB et IMED-GS, dont nous prouvons l’optimalité asymptotique et dont nous étudions les performances à horizon fini. Ces algorithmes vise à adapter l’algorithme IMED introduit par Honda et Takemura (2015) pour le cas des bandits non-structurés au cas des bandits unimodaux, multimodaux et structure de graphe. En outre, l’étude de ces algorithmes, nous a amené à développer des outils nouveaux (inégalités de concentration) et considérer de nouveaux mécanismes d’exploration (exploration de second ordre permise par l’approche IMED) dont nous pensons qu’ils bénéficieront à la communauté. Enfin, nous illustrons par des simulations l’efficacité pratique de ces nouveaux algorithmes.
M. Odalric-Ambrym MAILLARD Inria Lille - Nord Europe Directeur de thèse M. Gilles STOLTZ Université Paris-Saclay Rapporteur M. Junya HONDA Kyoto University Rapporteur M. Arnak DALALYAN ENSAE / CREST Examinateur Mme Claire VERNADE DeepMind in London UK Examinatrice M. Alexandre PROUTIERE KTH/EES Examinateur M. Richard COMBES CentraleSupélec Invité
Thesis of the team SCOOL defended on 19/12/2022
français
English