le 25 février 2025 à 14:30
Solving pure exploration tasks in bandit models and beyond
Les modèles de bandits sont bien étudiés dans la communauté de l’apprentissage automatique en raison de leurs nombreuses applications à l’optimisation du contenu en ligne. Dans un modèle de bandit à plusieurs bras, un agent essaie séquentiellement différentes actions, appelées bras. Chaque bras est associé à une distribution de probabilité inconnue. Dans une tâche d’exploration pure, l’agent veut apprendre quelque chose sur ces distributions (par exemple, quel bras a la plus grande espérance) en interrogeant le moins d’échantillons possible. Je commencerai par présenter un algorithme générique, appelé Track and Stop, qui atteint la complexité d’échantillonnage minimale dans un régime asymptotique dans lequel la probabilité d’erreur est faible. Le coût de calcul élevé de Track and Stop a conduit au développement d’autres types d’algorithmes qui sont plus attrayants sur le plan du calcul tout en conservant une complexité d’échantillonnage (presque) optimale. En particulier, je préconiserai l’utilisation des algorithmes dits “Top Two”. Enfin, je présenterai quelques résultats concernant l’exploration pure dans les processus décisionnels de Markov dans lesquels l’état de l’agent peut évoluer avec l’action choisie et l’objectif est d’apprendre une bonne politique (correspondance entre l’état et l’action).
En savoir plus...Amphi Ircica - 50 avenue Halley - Haute Borne - Villeneuve d'Ascq
français
English