dimanche 15 mai 2011

Présentation du 10/06/2011 reinforcement learning et problème des bandits bornés

Date : vendredi 10/06/2011
Lieu :
ENGREF
19 avenue du Maine
75732 PARIS
Métro : Montparnasse, Falguière
Amphi 7



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

par Aurélien Garivier (CNRS, Enst)

Résumé :
L'apprentissage par renforcement se distingue des autres théories
d'apprentissage statistique en 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é
http://arxiv.org/abs/1102.2490