Lieu : Equipe SEQUEL – INRIA Lille Nord Europe
Encadrant : Rémi Munos, Email : remi.munos@inria.fr
Mots-clés
Algorithmes des bandits manchots, apprentissage par renforcement, optimisation, prise de décisions dans l'incertain.
Sujet
La méthode de Monte-Carlo Tree Search (MCTS) a contribué de manière spectaculaire à l'avancée du domaine du computer-go (voir [4,5]) en fournissant une nouvelle méthode d'exploration de très grands espaces de recherche inspirée du principe de "l'optimisme dans l'incertain". Basées sur des algorithmes de bandit (dont l'algorithme UCB (Upper Confidence Bound) [6] et variantes [9]) utilisés de manière hiérarchique les méthodes de MCTS (dont UCT [1], BAST [2], HOO [3]) sont très efficaces numériquement pour des problèmes d'optimisation et de planification de grande taille. A l'heure actuelle il paraît essentiel de développer une analyse mathématique permettant de comprendre leur fonctionnement en profondeur et permettre de prédire leur performance (vitesse de convergence) en fonction d'une mesure de complexité du problème.
Ce stage de Master Recherche Informatique est rémunéré par l'équipe SEQUEL et se fera dans le cadre du projet européen COMPLACS (Composing Learning for Artificial Cognitive Systems).
Le travail à mener durant ce projet :
Etat de l’art sur les algorithmes MCTS et algorithmes de type optimistes dans l'incertain et leur champs d'application
Approfondissement de la méthode d'"optimisation optimiste simultanée" initiés dans [10], en particulier on étudiera l'extension au cas stochastique.
Application d'une stratégie de ce type à un problème d'optimisation, de planification ou jeux.
Analyse théorique et / ou développement d'un logiciel mettant en oeuvre cette stratégie et tests numériques, avec éventuellement participation à des compétitions (dans le cas de la programmation d'un jeu).
Si les travaux sont suffisamment avancés, nous proposerons la rédaction d'un article scientifique à soumettre dans une conférence internationale.
Possibilité de participer à des événements scientifiques nationaux ou internationaux (ex: ICML 2013, COLT 2013).
Possibilité de collaborations avec les partenaires européens du projet CompLacs.
Nous comptons proposer un sujet de thèse comme poursuite de ce travail.
Références
[1] Levente Kocsis and Csaba Szepesvari. Bandit based monte-carlo planning. ECML 2006.
[2] Pierre-Arnaud Coquelin and Remi Munos. Bandit algorithms for tree search. UAI 2007.
[3] Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvari. Online optimization in X-armed bandits. NIPS 2008.
[4] Gelly, Wang, Munos, Teytaud, Modification of UCT with Patterns in Monte-Carlo Go, INRIA, Research Report (RR-6062), 2006.
[5] Gelly, Munos, L'Ordinateur, champion de go ?, Pour la Science, 354:28-35, Avril 2007.
[6] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multi-armed bandit problem. Machine Learning, 47(2/3):235–256, 2002.
[7] Jean Francois Hren and Remi Munos. Optimistic Planning of Deterministic Systems. EWRL 2008.
[8] Nicolo Cesa-Bianchi and Gabor Lugosi. Prediction, Learning, and Games.Cambridge University Press, 2006.
[9] Jean-Yves Audibert, Rémi Munos, and Csaba Szepesvari. Exploration-exploitation trade-off using variance estimates in multi-armed bandits. Theoretical Computer Science, 410:1876-1902, 2009.
[10] Rémi Munos, Optimistic optimization of deterministic functions without the knowledge of its smoothness. NIPS 2011.