Adaptation à la structure en théorie des bandits

Understanding the dynamics of complex systems, and how to optimally act in them impacts all aspects of human societies where a careful management of natural, energetic, human and computational resources is required. To overcome the limitations of human capabilities to process large amounts of data, researchers from the field of machine learning and mathematical statistics for sequential decision making pursue the long-term goal of developing an optimal and automatic method that can, from partial observations and sequential interactions with a complex system, learn an optimal behavior. While optimal control considers the dynamics of the system is assumed to be known, reinforcement learning is interested in the case when the dynamics is unknown and must be learned from observations only. A key difficulty to design a solution for these problems is that typically, when a decision is made, one only gets to see a noisy effect of that decision, and little about the effect of other alternatives. This gives rise to the study of the fundamental exploration- exploitation trade-off: Shall we follow a algorithm that has been used a lot in the past and has empirically proven good until now (exploitation), or shall we explore a less known but potentially promising algorithm (exploration)? Addressing this trade-off does not yield the same approach depending on the underlying structure of the dynamicalsystem, where structure can be understood in several ways. Since not takingadvantage of this (possibly hidden) structure is prone to obtaining loose algorithms, it is crucial to investigate how to build learning algorithms that can be adaptive to it.In this thesis, we want to better understand how the notion of structure modifies the learning guarantees and suggests novel improved algorithms in the context of bandits. We give special attention to the cases of unimodal, multimodal and graph structure. We introduce an algorithm for each of these structures, respectively IMED-UB, IMED-MB and IMED-GS. These algorithms are extensions of the popular Indexed Minimum Empirical Divergence (IMED) algorithm from Honda et Takemura (2015) to the considered structures. We provide a finite time analysis for each of them and prove their asymptotic optimality. In particular, we considered new exploring mechanisms (second order exploration allowed by IMED approach) and developed new tools (concentrations inequalities) we think that are are of independent interest for the bandit community. Furthermore, these novel algorithms perform well in practice. This is confirmed by numerical illustrations on synthetic data.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