Séminaire de Probabilités et Statistique :

Le 14 mars 2011 à 15:00 - UM2 - Bât 09 - Salle 331 (3ème étage)

Présentée par Garivier Aurélien - LTCI, CNRS - TELECOM ParisTech

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

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 bandits manchots plus ou moins avantageux, doit à chaque instant choisir l'un d'eux 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 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