* Emilie Kaufmann (LTCI - Telecom ParisTech) - MAP5-UMR 8145

Emilie Kaufmann (LTCI – Telecom ParisTech)

Un point de vue bayésien pour des algorithmes de bandits plus performants

jeudi 21 février 2013, 16h00 - 17h00

Salle de réunion, espace Turing


{{Abstract :}}

Le « multi-armed bandit problem » (problème de bandit à plusieurs bras) est un problème statistique fondamentalement {fréquentiste} : chaque bras consiste en une distribution de probabilité dépendant d’un {paramètre inconnu}, et on cherche à maximiser les récompenses qu’on obtient en jouant les bras séquentiellement. Si la dénomination ‘bandit à un bras’ se réfère à une machine à sous, nous présenterons plutôt les applications des algorithmes de bandits dans des cadres bien différents d’un casino!

Les variantes de l’algorithme le plus célèbre (UCB – Upper Confidence Bounds) exploitent le point de vue fréquentiste puisqu’ils se servent d'{intervalles de confiance} sur le paramètre de chacun des bras pour déterminer le bras à jouer à chaque tour. Nous présenterons ici deux exemples d’algorithmes d’inspiration bayésienne, c’est-à-dire utilisant un {apriori} sur les paramètres des bras : Bayes-UCB et Thompson Sampling. Nous comparerons ces deux approches différentes et établirons les premières garanties théoriques pour des algorithmes bayésiens. Les performances pratiques de ces algorithmes semblent de plus meilleures que celles des UCB les plus récents, pour une implémentation souvent plus rapide. Go Bayesian!