Master MVA Année 2012 - 2013

Cours "Apprentissage par renforcement" Master Mathématiques, Vision, Apprentissage, ENS Cachan



Notes de cours :

Chapitre 1: Introduction générale à l'A/R et aux processus de décision markoviens
Chapitre 2: Algorithmes d'apprentissage par renforcement (et intro aux algorithmes d'approximation stochastiques)
Chapitre 3: Introduction aux algorithmes de bandit
   Bandits stochastiques: UCB
   Bandits adversarials: Exp3
Chapitre 4: Programmation dynamique avec approximation
   Analyse en norme sup de la programmation dynamiques avec approximation
   Quelques algorithmes: Fitted value iteration, Policy Iteration avec LSTD, Bellman residual
Chapitre 5: Sample complexity en apprentissage par renforcement
   Quelques outils statistiques
   Analyse de LSTD

Horaires des cours et TP (année 2012-2013): ENS Cachan, les mardi:

Les séances de TP seront assurées par Emilie Kaufmann.

Support de cours :

Propositions de stage recherche:

  1. Apprentissage par renforcement et algorithmes de bandit pour la prise de décision dans l'incertain 

  2. Reinforcement Learning with Random Projections 

  3. Monte-Carlo Tree Search, des algorithmes à la théorie 



Autres ressources sur l'Apprentissage par renforcement (Reinforcement Learning):

Exemple d'algorithmes d'apprentissage par renforcement:

Référence en neurosciences : Chapitre 9 du livre de Dayan et Abbott, Theoretical Neuroscience (disponible à la bibliothèque de l'ENS Cachan). Articles de Kenji Doya: http://www.cns.atr.jp/~doya/papers/index.html

Exemples de jeux programmés :

Validation du cours :

Travail demandé: en binôme ou seul,

Ce qui m'intéresse : que vous fassiez un sujet qui vous intéresse ! Que vous compreniez l'algo utilisé, que vous réfléchissiez aux applications potentielles de l'algo, la validité des hypothèses, bref que vous vous posiez les bonnes questions, que vous fassiez un bon rapport, une bonne soutenance, et que vous travailliez ! Je voudrais que pour la validation de ce module vous soyez en situation comparable à celle que vous rencontrerez lorsque vous ferez de la recherche. Vous êtes libres de choisir votre sujet, mais je veux que vous travailliez intelligemment et bien !

Timing:

Propositions de mini-projets :

  1. La stratégie optimiste pour l'apprentissage par renforcement en-ligne.
    Lire l'article Near-optimal regret bounds for reinforcement learning. Thomas Jaksch, Ronald Ortner, and Peter Auer. Journal of Machine Learning Research, 11:1563–1600, 2010. Il s'agit d'une extension des algorithmes de bandit style UCB à l'apprentissage par renforcement.
    Implémenter l'algorithme sur un problème de votre choix (labyrinthe ou autre), ou bien faire une étude plus théorique en analysant la notion de "diamètre" du MDP. Est-ce que les bornes sont fines en terme du nombre d'états, du diamètre?

  2. Algorithmes de bandit stochastique de type UCB
    Partir de l'article [Auer et al.,     Finite-time analysis of the multi-armed bandit problem, 2002], puis [Audibert, Munos, Szepesvari,Use of variance estimation in the multi-armed bandit problem 2009] utilisant la variance empirique et [Cappé, Garivier, Maillard, Munos, Stoltz, 2012, Kullback-Leibler upper confidence bounds for optimal sequential allocation] utilisant la divergence de Kullback Liebler pour affiner les intervalles de confiance.

  3. Algorithmes de bandit contre un adversaire, type EXP3
    Partir de l'article [Auer, Cesa-Bianchi, Freund, and Schapire. The nonstochastic multi-armed bandit problem. 2003]. Les récompenses sont choisies par un adversaire. On compare nos performances à celles qu'on aurait obtenues en suivant la meilleure stratégie (dans une classe de comparaison donnée). Permet de calculer des équilibres de Nash dans un jeu à 2 joueurs à somme nulle (voir par exemple http://www.cs.cmu.edu/~avrim/Papers/regret-chapter.pdf ). Utiliser cette méthode pour calculer l'équilibre de Nash d'un jeu matriciel.

  4. Bandit avec un nombre infini de bras
    Partir de l'article [Wang, Audibert, Munos,     Algorithms for inifinitely many-armed bandits. 2008]. Il y a un nombre dénombrable de bras. Hypothèse : un nouveau bras a une probabilité $\epsilon^\beta$ d'être $\epsilon$-optimal. Compromis entre exploration - exploitation - découverte. Question: que faire si l'on ne connait pas à l'avance le paramètre $\beta$?

  5. Monte-Carlo Tree Search: UCT, HOO
    Voir A survey on Monte-Carlo Tree Search et l'article The Optimistic Principle applied to Games, Optimization, and Planning. Utilisation d'algorithmes de bandits de manière hiérarchique pour effectuer une recherche dans des grands arbres. Projet : utiliser un algo de ce type (UCT, HOO, MCTS) pour programmer un jeu. Des exemples de jeux deja programmés se trouvent sur la page du projet EXPLORA ou dans les articles mentionnés ci-dessus.

  6. Planification optimiste dans les Processus de Décision Markoviens
    Planification optimiste en explorant en priorité les séquences d'actions les plus prometteuses (de manière similaire aux bandits hiérarchiques de type UCT, HOO précédemment cités). Ici on utilise la spécificité du problème de décision markovien pour déterminer une stratégie optimiste de planification. Références: The Optimistic Principle applied to Games, Optimization, and Planning. et Optimistic planning in markov decision processes. Coder un algo de type planification optimiste pour résoudre un processus de décision markovien déterministe ou stochastique.

  7. Optimisation de politique par gradient pour un POMDP (Partially Observable Markov Decision Problem). Lorsque l'état du système est partiellement observable, une technique usuelle pour reconstruire une fonction de croyance (distribution) sur l'état à partir des observations consiste à utiliser les méthodes de filtrage particulaires. Outils de calcul du gradient présenté dans l'article [Coquelin et al. Particle Filter-based Policy Gradient in POMDPs. 2008] qui utilise les méthodes particulaires. Par exemple application à la digestion anaérobie, dont un modèle simplifié (2 variables, 4 paramètres) des dynamiques d'état est décrit dans : modèle AMH1 [Bernard et al., 2005].

  8. Apprentissage d'une stratégie de Nash dans un jeu : Un domain particulièrement intéressant actuellement lié à l'apprentissage multi-agents est le calcul d'équilibre de Nash dans des jeux multi-joueurs. Une méthode assez récente consiste à ce que chaque joueur apprenne à jouer
    de mieux en mieux contre des adversaires dans un jeu répété, et si chaque joueur fait de même, on peut montrer que leur stratégie jointe converge vers un équilibre.

    Une bonne manière pour chaque joueur d'apprendre à joueur consiste à "minimiser le regret". Voir par exemple:
    http://www.cs.cmu.edu/~avrim/Papers/regret-chapter.pdf
    http://people.csail.mit.edu/lpk/papers/2005/icml2005-chang.pdf
    http://citeseer.ist.psu.edu/193720.html

    Une belle application concerne le jeu de poker. Voir l'article:
    http://www.cs.ualberta.ca/~maz/publications/regretpoker.pdf

    Le sujet consiste à étudier un (ou plusieurs) de ces articles, et faire, soit un travail théorique sur un sujet de votre choix (à en discuter avec moi avant), soit une implémentation informatique sur un jeu de votre choix.

    Si le poker vous intéresse, vous pouvez envisager de calculer l'équilibre de Nash pour le poker à une carte cachée, par exemple décrit ici:
    http://www.cs.cmu.edu/~ggordon/poker/

    Une autre possibilité est le jeu d'Alésia, dont voici une applet pour jouer contre le Nash:
    http://www.grappa.univ-lille3.fr/~loth/alesia/play_nash.php

  9. Apprentissage de Tétris.

    Lire les références données sur le site des compétitions en apprentissage par renforcement :
    http://rl-competition.org/content/view/19/35/ Choisir une méthode et l'inplémenter pour faire un programme apprenant à jouer à Tétris. Je vous recommande l'approche     Least-Squares Policy Iteration (Lagoudakis et R. Parr) ou celui-ci.

    Autre proposition : étudier un autre domaine sur le même site http://rl-competition.org

  10. Sample complexity in reinforcement learning

    Articles sur LSTD [Lazaric, Ghavamzadeh, and Munos. Finite-sample analysis of LSTD, 2010] et Bellman Residual Minimization [Maillard, Munos, Lazaric, and Ghavamzadeh, Finite sample analysis of bellman residual minimization, 2010]