Lieu : Equipe SEQUEL – INRIA Lille Nord Europe
Encadrant / Contact : Rémi Munos, Email : remi.munos@inria.fr
Mots-clés
Apprentissage par renforcement, compromis exploration-exploitation, algorithmes de bandit, optimisme dans l'incertain. Applications en optimisation, contrôle, et programmation de jeux.
Sujet
Ce projet aborde la question de savoir comment utiliser au mieux les ressources numériques disponibles (mémoire, temps CPU) afin d'optimiser la performance d'un problème de prise de décisions. Bien utiliser les ressources disponibles signifie définir une stratégie d'exploration permettant d'allouer ces ressources de manière appropriée afin de maximiser (dans l'espace des stratégies d'allocation possibles) la performance de la tâche résultante. Les applications potentielles sont nombreuses et concernent des domaines où une décision unique ou une séquence de décisions doivent être prises, tels que l'optimisation, le contrôle, l'apprentissage et les jeux [8].
A cette fin, nous considérerons plusieurs manières de combiner des outils qui gèrent bien le compromis de ressources allouées à l'exploitation (prendre la meilleure décision en fonction de nos connaissances actuelles, éventuellement imparfaites) et à l'exploration (décisions qui peuvent être sous-optimales mais qui permettent d'acquérir de l'information afin d'améliorer les décisions futures). Ces algorithmes d'exploration/exploitation, appelés aussi algorithmes d'apprentissage par renforcement, dont les plus élémentaires sont les algorithmes de "bandit manchot", sont les constituants de base qui peuvent être combinés de manière hiérarchique (exemple les algorithmes UCT, BAST, HOO et SOO voir respectivement [1], [2], [3], [10]).
Un exemple concerne la recherche arborescente min-max dans des jeux de grande taille. L'objectif ici est de déterminer le meilleur coup à jouer, sachant que les ressources numérique permises (temps CPU) sont limitées. Ici, l'allocation de ressources signifie une stratégie d'exploration des branches (séquence d'actions) ; le but étant que lorsque les ressources disponible sont épuisées, l'information collectée permettre de prendre la meilleure décision. Des précédents travaux utilisant des "bandits" hiérarchiques appliqués au jeu de go ont démontré des résultats très prometteurs (le programme MoGo [4, 5] est actuellement parmi les meilleurs au monde). Ces résultats ont motivé nos recherches pour étendre à la fois l'analyse théorique des idées sous-jacentes et la portée des applications potentielles.
L'objectif de ce stage sera d'étudier plus précisément les stratégies de type "optimistes dans l'incertain" (dont l'algorithme UCB (Upper Confidence Bound) [6] et variantes [9]) et d'appliquer cette stratégie à des problèmes de planification (voir par exemple [7]), contrôle ou de prise de décision dans un jeu [8].
Ce travail se fera dans le cadre du projet européen COMPLACS (Composing Learning for Artificial Cognitive Systems).
Le travail à mener durant ce stage :
Etat de l’art sur les algorithmes de type "optimistes dans l'incertain" et leur champs d'application
Application d'une stratégie de ce type à un problème de planification, contrôle 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).
Ce stage de Master sera rémunéré par l'équipe SEQUEL
Poursuite possible par une thèse à SEQUEL.
Autres informations:
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 2012, COLT 2012).
Possibilité de collaborations avec plusieurs laboratoires européens : John Shawe Taylor (UCL), Peter Auer (University Leoben), Jan Peters (Max Planck Institute), Bert Kappen (University of Nijmegen), Chris Watkins (Royal Holloway), Nello Cristianini (University of Bristol), Manfred Opper (Technical University Berlin) dans le cadre du projet CompLacs.
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 knokledge of its smoothness. NIPS 2011.