* Aurélien Garivier (LTCI Telecom ParisTech, CNRS UMR 5141) - MAP5-UMR 8145

Aurélien Garivier (LTCI Telecom ParisTech, CNRS UMR 5141)

L’algorithme KL-UCB pour les bandits bornés, et au-delà

vendredi 29 avril 2011, 9h30 - 10h45

Salle de réunion, espace Turing


L’apprentissage par renforcement se distingue des autres théories
d’apprentissage statistique en ce qu’il place en son coeur la dimension
temporelle, mais aussi interactive, du phénomène d’apprentissage. Les
modèles les plus simples qui s’y rattachent sont communément appelés
« problèmes de bandits » : un agent, faisant face à une collection de
machines à sous plus ou moins avantageuses, doit à chaque instant
choisir l’une d’elle et reçoit une récompense en conséquence – avec pour
objectif de maximiser la somme des récompenses reçues. Derrière cette
mise en situation un peu baroque, on devine sans peine une grande
variété de motivations pratiques, des essais cliniques au routage de
paquets sur internet.
Parmi les stratégies proposées en apprentissage par renforcement, on
distingue les algorithmes optimistes : ils agissent à chaque instant
comme s’ils se trouvaient dans l’environnement le plus favorable pour
eux parmi tous ceux qui rendent les observations passées suffisamment
vraisemblables. Nous verrons comme le paradigme optimiste peut être mis
en oeuvre efficacement et simplement ici, et comment l’algorithme
KL-UCB, en introduisant une notion de divergence sur l’espace des
récompenses adaptée au problème, conduit à des résultats
significativement meilleurs que ses concurrents.

Basé sur l’article :

The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond
par Aurélien Garivier and Olivier Cappé
disponible (à partir du 15/02) sur arxiv