Un bandit est un problème d'apprentissage dans lequel un agent choisit séquentiellement de tester une action parmi un ensemble de candidats fixé, collecte une récompense, et met en place une stratégie dans le but de maximiser son gain cumulé. Motivés par une étude de cas dans le domaine de l'agriculture, nous abordons dans cette thèse plusieurs problématiques pertinentes pour les applications réelles des bandits. La première question que nous considérons concerne les hypothèses faites sur les distribution des récompenses. Alors qu'en théorie il est généralement commode de considérer des hypothèses paramétriques simples (par exemples, des distributions gaussiennes), le practicien peut avoir des difficultés à trouver le bon modèle adapté à son problème. Pour cette raison, nous étudions deux familles d'algorithmes non-paramétriques, dans la mesure où ils ne nécessitent pas d'hypothèses paramétriques fortes sur les distributions pour leur implémentation. Nous montrons que ces deux approches peuvent obtenir de bonnes garanties théoriques pour le problème de bandits usuel, tout en utilisant moins d'hypothèses que les méthodes précédemment proposées. Nous proposons ensuite différentes extensions de ces algorithmes afin de faciliter leur mise en pratique. La deuxième question principalement étudiée dans nos travaux concerne la prise en compte de critères de performance alternatifs à l'espérance des récompenses cumulées, qui pourraient potentiellement mieux refléter les préférences réelles du practicien. Nous proposons notamment des algorithmes sensibles au risque, pour des problèmes dans lesquels l'objectif est d'identifier un bras peu risqué selon une mesure: la Conditional-Value-at-Risk. Nous proposons également des algorithmes efficaces pour un problème analogue au cas limite du précédent, appelé Bandits Extrêmes. Enfin, nous adaptons nos méthodes pour traiter des variantes usuelles du problème de bandit, avec notamment le cas de récompenses non-stationnaires et un exemple où les données sont collectées dans des groupes d'observations et non dans un cadre purement séquentiel.
M. Odalric-Ambrym MAILLARD Inria Lille Directeur de thèse M. Stéphan CLEMENCON Télécom Paris Rapporteur M. Shie MANNOR The Technion Faculty of Electrical Engineering Rapporteur Mme Audrey DURAND Université Laval, Québec Examinatrice M. Vianney PERCHET CREST, ENSAE Paris Examinateur Mme Emilie KAUFMANN CNRS Co-directrice de thèse M. Marc ABEILLE Criteo Invité
Thèse de l'équipe SCOOL soutenue le 05/12/2022