Avis de soutenance
Raymond Zhang
Vendredi 12 décembre 2025 à 15h00
Au Bâtiment DIGITEO 660, 1 Rue René Thom 91190, 91190 Gif-sur-Yvette.
La soutenance sera également diffusée sur teams.
URL de la salle virtuelle de soutenance ouverte au public : Soutenance Raymond Zhang | Meeting-Join | Microsoft Teams
Vous êtes également conviés au pot qui sera organisé à l’issue de la soutenance.
(Semi-)Bandits Linéaires en Grandes Dimensions, Algorithmes Efficaces et Optimalité
Thèse préparée dans l’unité de recherche L2S (Université Paris-Saclay, CentraleSupélec, CNRS), sous la direction de Sheng Yang,Professeur, la co-direction de Richard Combes, Maitre de conférence
Composition du jury :
Mme Emilie KAUFMANN, CNRS/Université de Lille, Rapporteure
M. Vianney PERCHET, ENSAE Paris – Institut Polytechnique de Paris Rapporteur
M. Kevin JAMIESON, University of Washington, Examinateur
Mme Michèle WIGGER, Télécom Paris – Institut Polytechnique de Paris, ExaminatriceMots-clés : Bandit,Bayésien,Grandes dimensions,Apprentissage Séquentielle,Optimisation,
Résumé :
Dans cette thèse, nous étudions une généralisation du modèle des bandits manchots classique appelée le problème des (semi-)bandits linéaires. Dans ce problème d’apprentissage séquentiel, un apprenant sélectionne, à chaque tour, une action représentée par un vecteur potentiellement de grande dimension. L’apprenant reçoit alors une récompense qui est une fonction linéaire inconnue de l’action choisie, perturbée par du bruit. L’objectif de l’apprenant est de maximiser sa récompense cumulée sur un horizon de temps donné. Nous étudions d’abord un algorithme bayésien appelé Thompson Sampling (TS) dans le cadre des semi-bandits combinatoires linéaires. Nous montrons que lorsque les récompenses sont de Bernoulli, le regret de Thompson Sampling avec une a priori bêta croît exponentiellement avec la dimension. Nous proposons ensuite une modification de l’algorithme pour remédier à ce problème. Cette modification consiste à utiliser une a priori et une postérieure gaussiennes, même si les récompenses ne le sont pas. Ce nouvel algorithme ne présente pas de croissance exponentielle du regret avec la dimension. Nous appelons ce phénomène le « Paradoxe du Mésappariement ». Dans le cadre des bandits linéaires, lorsque l’ensemble des actions est un ellipsoïde, nous établissons une borne inférieure localement asymptotiquement minimax sur le regret de tout algorithme. Nous proposons ensuite un algorithme efficace appelé E2TC, qui est localement asymptotiquement minimax optimal, à une constante multiplicative près. Nous présentons également des résultats d’impossibilité pour le problème d’optimisation bilinéaire que tout algorithme optimiste doit résoudre. Cependant, nous proposons un algorithme efficace pour ce problème lorsque l’ensemble des actions est un ellipsoïde. Enfin, nous étudions une autre extension du problème des bandits manchots dans laquelle plusieurs joueurs sélectionnent chacun un bras à chaque tour ; la récompense de chaque joueur est affectée par la présence des autres joueurs. Nous étudions les limites fondamentales de la communication entre les joueurs, en montrant comment les collisions peuvent être utilisées pour améliorer la performance d’apprentissage de l’ensemble des joueurs.
Abstract :
In this thesis, we study a generalization of the multi-armed bandit model called the linear (semi-)bandit problem. In this sequential learning problem, a learner selects, at each round, an action represented by a possibly high-dimensional vector. The learner then receives are ward that is an unknown linear function of the chosen action, corrupted by noise. The goal of the learner is to maximize their cumulative reward over a given time horizon.We first study a Bayesian algorithm called Thompson Sampling (TS) in the combinatorial linear semi-bandit setting. We prove that, when the rewards are Bernoulli distributed, the regret of Thompson Sampling with a Beta prior scales exponentially with the dimension. We then pro-pose a modification of the algorithm to address this issue. This modification involves using a Gaussian prior and posterior, despite the re-wards not being Gaussian. This new algorithm does not exhibit exponential regret growth with the dimension. We refer to this phenomenon as the “Missmatched Paradox”. In the linear bandit setting, when the action set is an ellipsoid, we establish a locally asymptotic minimax lower bound on the regret of any algorithm. We then propose a computationally efficient Exploration and Commit based algorithm called E2TC, which is locally asymptotically minimax optimal up to a multiplicative constant factor. We also present impossibility results for the bilinear optimization problem that any optimistic algorithm must solve. However, we propose an efficient algorithm for this problem when the action set is an ellipsoid. Finally, we study an extension of the multi-armed bandit problem in which multiple players select an arm to pull at each round, and the reward of each player is affected by the presence of the other players. We investigate the fundamental limits of communication between players, demonstrating how collisions can be leveraged to enhance the learning performance of all players.
