Thesis of Marc Jourdan

Résoudre les problèmes d'exploration pure avec l'approche Top Two

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 collecter des é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’agent cherche à 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 est opposé à un challenger, ce qui oriente les efforts d’échantillonnage ultérieurs pour valider la 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 leur interprétabilité, de leur généralisation et de leur polyvalence, les algorithmes Top Two sont prometteurs pour être adoptés pour différentes applications. Cette thèse s’efforce d’établir l’approche Top Two comme une méthodologie fondée sur des principes statistiques, offrant des garanties théoriques quasiment optimales ainsi que des performances empirique excellentes. Nous abordons différentes formulations de bandits stochastiques à plusieurs bras, avec des classes de distributions variées ou des hypothèses structurelles sur les moyennes. Nous avons aussi étudié différents problèmes d’exploration pure, notamment l’identification du meilleur bras ou d’un bras de qualité acceptable. La principale contribution de cette thèse réside dans l’obtention de garanties théoriques pour l’approche Top Two avec plusieurs mesures de performance. Dans le cas où un niveau de confiance est donné, les algorithmes Top Two collectent un nombre moyen d’échantillons qui est asymptotiquement optimal (lorsque le niveau de confiance tend vers un). Par ailleurs, nous proposons un algorithme Top Two qui offre à tout moment des garanties sur la probabilité de se tromper dans l’identification d’un bras de qualité acceptable.

Jury

Mme Emilie KAUFMANN Université de Lille Directrice de thèse, M. Rémy DEGENNE Centre Inria de l'Université de Lille Examinateur, M. Alexandre PROUTIèRE KTH Royal Institute of Technology Rapporteur, M. Sandeep JUNEJA School of Technology and Computer Science Rapporteur, M. Aurélien GARIVIER Ecole Normale Supérieure de Lyon Examinateur, M. Wouter M. KOOLEN Centrum Wiskunde & Informatica Examinateur, M. Junya HONDA Kyoto University. Invité.

Thesis of the team SCOOL defended on 14/06/2024