Note ABES Solving pure exploration problems with the Top Two approach Résoudre les problèmes d'exploration pure avec l'approche Top Two Prise de décision séquentielle Problème de bandit à plusieurs bras Exploration pure Identification du meilleur bras Sequential decision making Multi-Armed bandits Pure exploration Best-Arm identification Prise de décision (statistique) Problème du bandit manchot Échantillonnage adaptatif (statistique) Tests d'hypothèses (statistique) Dans les problèmes d'exploration pure pour les bandits stochastiques à bras multiples,l'objectif est de répondre à des questions concernant un ensemble de distributions inconnues(modélisant par exemple l'efficacité d'un traitement) à partir desquelles nous pouvons collecterdes échantillons (mesurer son effet), et de fournir ensuite des garanties sur la réponse proposée.L'exemple archétypal est le problème de l'identification du meilleur bras, dans lequel l'agentcherche à identifier le bras étant le plus efficace en moyenne.Cette thèse s'intéresse à la classe des algorithmes Top Two, dans lesquels un leader estopposé à un challenger, ce qui oriente les efforts d'échantillonnage ultérieurs pour validerla supériorité du leader. Nous avons introduit une définition unifiée de l'approche Top Two,mettant en avant quatre composants importants. Compte tenu de leur simplicité, de leurinterprétabilité, de leur généralisation et de leur polyvalence, les algorithmes Top Two sontprometteurs pour être adoptés pour différentes applications. Cette thèse s'efforce d'établirl'approche Top Two comme une méthodologie fondée sur des principes statistiques, offrant desgaranties théoriques quasiment optimales ainsi que des performances empirique excellentes.Nous abordons différentes formulations de bandits stochastiques à plusieurs bras, avecdes classes de distributions variées ou des hypothèses structurelles sur les moyennes. Nousavons aussi étudié différents problèmes d'exploration pure, notamment l'identification dumeilleur bras ou d'un bras de qualité acceptable. La principale contribution de cette thèseréside dans l'obtention de garanties théoriques pour l'approche Top Two avec plusieurs mesuresde performance. Dans le cas où un niveau de confiance est donné, les algorithmes Top Twocollectent un nombre moyen d'échantillons qui est asymptotiquement optimal (lorsque leniveau de confiance tend vers un). Par ailleurs, nous proposons un algorithme Top Two quioffre à tout moment des garanties sur la probabilité de se tromper dans l'identification d'unbras de qualité acceptable. In pure exploration problems for stochastic multi-armed bandits, the objective is to answerinquiries regarding a set of unknown distributions (modeling for example the efficacy of atreatment) from which we can collect samples (measure its effect), and subsequently provideguarantees on the candidate answer. The archetypal example is the best arm identificationproblem, in which the agent aims at identifying the arm with the highest mean.This thesis delves into the class of Top Two algorithms, wherein a leader is pitted against achallenger, directing subsequent sampling efforts to validate the superiority of the leader. Weintroduce a unified definition of the Top Two approach, putting forward four key components.Given their simplicity, interpretability, generalizability, and versatility, Top Two algorithms arepromising for widespread adoption among practitioners. This thesis endeavors to establish theTop Two approach as a principled methodology offering nearly optimal theoretical guaranteesalongside state-of-the-art empirical performance.We address several stochastic multi-armed bandits settings, such as various classes ofdistributions or structural assumptions on the means. We also study different pure explorationproblems, including the identification of the best arm or one of acceptable quality. The principalcontribution of this thesis lies in establishing theoretical guarantees for the Top Two approachacross several performance metrics. In the fixed-confidence setting, we prove that many Top Twoalgorithms have an asymptotically optimal expected sample complexity (number of collectedsamples when the confidence level goes to one). In the anytime setting, we propose a Top Twoalgorithm which has guarantees on the probability of misidentifying a good enough arm atany time. Electronic Thesis or Dissertation Text en PDF 3508640 https://pepite-depot.univ-lille.fr/LIBRE/EDMADIS/2024/2024ULILB011.pdf https://theses.hal.science/tel-04804590 https://theses.hal.science/tel-04804590 https://theses.fr/2024ULILB011/abes https://theses.hal.science/tel-04804590 https://theses.hal.science/tel-04804590 https://theses.hal.science/tel-04804590 Jourdan Marc Jourdan 1995-05-05 FR 281676577 https://theses.fr/2024ULILB011 2024ULILB011 https://doi.org/10.70675/ca5c3644z5549z4170zba9cz535f50f6b133 2024-06-14 Informatique et applications Université de Lille (2022-....) 259265152 Doctorat Docteur es non oui Kaufmann Emilie MADS_DIRECTEUR_DE_THESE_1 197040810 Degenne Rémy MADS_DIRECTEUR_DE_THESE_2 253866685 Koolen Wouter MADS_PRESIDENT_DU_JURY 281676046 Garivier Aurélien MADS_MEMBRE_DU_JURY_1 111902495 Proutière Alexandre MADS_RAPPORTEUR_1 17544126X Juneja Sandeep MADS_RAPPORTEUR_2 281675872 École graduée Mathématiques, sciences du numérique et de leurs interactions (Lille ; 2021-....) MADS_ECOLE_DOCTORALE_1 258621362 Centre de Recherche en Informatique, Signal et Automatique de Lille MADS_PARTENAIRE_DE_RECHERCHE_1 410272 18388695X Centre Inria de l'Université de Lille MADS_PARTENAIRE_DE_RECHERCHE_2 104752 185432247 ddc:004 Kaufmann Emilie Degenne Rémy Koolen Wouter Garivier Aurélien Proutière Alexandre Juneja Sandeep École doctorale Mathématiques, sciences du numérique et de leurs interactions (Lille ; 2021-....) Centre de Recherche en Informatique, Signal et Automatique de Lille Centre Inria de l'Université de Lille PDF 3508640