On-Policy and Off-Policy Learning for Large Action Spaces

Abstract

Cette thèse étudie l'apprentissage de politiques dans les systèmes interactifs où un agent observe un contexte, choisit une action parmi un très grand ensemble, puis reçoit un retour partiel. Le cadre principal est celui des bandits contextuels, avec deux paradigmes : l'apprentissage en ligne, où l'agent interagit séquentiellement avec l'environnement et minimise le regret, et l'apprentissage hors politique, où il apprend à partir de données journalisées par une politique de logging. Dans les grands espaces d'actions, ces deux cadres soulèvent des difficultés majeures : exploration coûteuse, faible couverture des données, forte variance des poids d'importance, biais d'extrapolation et objectifs difficiles à optimiser. La première partie propose des méthodes bayésiennes structurées pour l'apprentissage en ligne. Nous introduisons meTS, une extension de Thompson sampling fondée sur des effets mixtes, puis dTS, qui exploite des priors inspirés des modèles de diffusion. Ces méthodes partagent l'information entre actions et obtiennent des garanties de regret dépendant d'un nombre effectif d'actions. La seconde partie traite l'apprentissage hors politique. Nous proposons sDM, une méthode directe structurée fondée sur des variables latentes, montrons que l'erreur d'optimisation peut dominer l'erreur d'estimation dans les grands espaces d'actions, et introduisons des objectifs de vraisemblance pondérée par la politique, concaves et efficaces à optimiser. Enfin, nous développons des méthodes pessimistes différentiables fondées sur le lissage exponentiel et des bornes PAC-bayésiennes pour contrôler le compromis biais-variance des estimateurs par importance sampling.