Apprentissage par différence temporelle

Introduction

Principal algorithme d'apprentissage par renforcement utilisant la différence temporelle, nous étudions le Q-Learning.

Schéma algorithmique du Q-Learning

Dans le cas d'une tâche se terminant, le Q-Learning consiste à itérer des épisodes. Un épisode est une séquence d'interactions qui se poursuit jusqu'à atteindre un état terminal. Une interaction consiste à déterminer une action à réaliser dans l'état courant, l'effectuer, observer l'état atteint et le retour perçu, et enfin, mettre à jour l'estimation de la fonction Q. Un peu plus précisément, le Q-Learning est décrit ci-dessous :

1. Initialiser l'algorithme.
2. Répéter :
   1. /* on réalise un épisode. */
   2. Initialiser l'état ; \( t \gets 0 \)
   3. Tant-que \( e_t \) n'est pas terminal :
      1. /* on fait une interaction : */
      2. en fonction de l'état courant e_t, choisir l'action a_t,
      3. effectuer a_t et observer l'état suivant e_t+1 et le retour immédiat r_t,
      4. mettre à jour Q : \( Q (e_t, a_t) \gets Q (e_t, a_t) + \alpha (e_t, a_t) [r_t + \gamma \max_{a' \in {\cal A}} Q (e_{t+1}, a') - Q (e_t, a_t) ] \),
      5. \( t \gets t + 1 \).

Implantation

À faire : implanter le Q-Learning. Tout comme dans le TP de programmation dynamique en PDI, faire en sorte que l'implantation soit générique. Assurez-vous qu'elle n'est pas buggée.
On prendra \( \alpha (e, a) = \frac{1}{n (e, a) + 1} \) où \( n (e, a) \) est le nombre de visites à la paire \( (e, a) \).
On utilisera un choix d'action ε-glouton avec ε décroissant. La décroissance de ε est délicate à régler. On multipliera ε par une valeur proche et inférieure à 1 à l'issue de chaque épisode, par exemple 0,99. Par la suite dans les expériences, on vérifiera toujours que ce facteur convient et ne provoque pas une décroissance d'ε trop rapide, ou trop lente.

Expérimentation

Vos expériences doivent être reproductibles.

Problème du chauffeur de taxi

Résoudre le problème du chauffeur de taxi avec le Q-Learning. On prend γ = 0,9. Comme il n'y a pas d'état terminal, on arrête un épisode lorsque γ^t est petit (10^-6 par exemple).
Vérifier que la politique gloutonne tend vers la politique optimale déterminée dans le module TP de programmation dynamique. Combien d'épisodes sont nécessaires pour cela ?
Vous étudierez par exemple combien d'interactions sont nécessaires pour apprendre cette politique. Exécutez plusieurs fois l'algorithme, calculez la moyenne, la médiane et l'écart-type de ce nombre d'interactions.
Pour vous donner quelques repères : en réalisant 1 épisode d'une centaine de pas, j'ai déjà calculé la politique optimale.

Problème de labyrinthes

Résoudre le labyrinthe dont \( {\cal P} \) et \( {\cal R} \) sont fournies dans ce fichier. 4 actions sont possibles, une par direction cardinale : aller une case à gauche, aller une case vers le haut, aller une case vers la droite, aller une case vers le bas. Lorsqu'une action est empéchée par un mur, l'état reste inchangé. Ce fichier suit le format vu dans le TP de programmation dynamique. Chaque épisode part de l'état orange et se termine lorsque l'état vert est atteint. Un retour immédiat +1 est perçu lorsque la case verte est atteinte ; la fonction de retour est nulle sur toutes les autres transitions ; une fois sur la case verte, toutes les actions sont sans effet. Les états sont numérotés à partir de 0 pour la case en haut à gauche puis de gauche vers la droite et de haut en bas. Déterminer la politique gloutonne à l'issue de l'apprentissage. Lors d'une exécution, on mesure la somme des retours immédiats pondérés \( R = \sum_{t\ge{}0} \gamma^t r_t \). Prendre γ = 0,95.

On nomme courbe d'apprentissage le graphique indiquant \( R \) en fonction du numéro de l'épisode.
Réalisez plusieurs exécutions. On réalise plusieurs courbes d'apprentissage  :
Pour vous donner quelques repères : en réalisant 12 épisodes comprenant 200 interactions chacun au maximum, avec γ = 0,9 et facteur de décroissance de ε = 0,98, mon implantation du Q-Learning réalise une trajectoire optimale.

• version 1 : tracer l'évolution de \( R \) au fil des épisodes pour chacune des exécutions.
• version 2 : tracer la valeur moyenne de \( R \) au fil des épisodes et +/- 1 écart-type.
• version 3 : tracer la valeur médiane de \( R \) au fil des épisodes et les quartiles 25 et 75%.

Faites la même chose avec le labyrinthe du contrôle de PDI (version non venteuse) : labyrinthe du CC de PDI.
Pour vous donner quelques repères : en réalisant 25 épisodes comprenant 750 interactions chacun au maximum, avec γ = 0,9 et facteur de décroissance de ε = 0,98, mon implantation du Q-Learning réalise une trajectoire optimale.

21 avec un dé

Résolvez le 21 avec un dé avec le Q-Learning.

Choix de l'action

Implanter la méthode de Botzmann-Gibbs. Comparez les performances obtenues avec celle-ci à celles obtenues précédemment par ε-décroissant glouton.

Traces d'éligibilité

Implanter l'algorithme Q (λ) et le tester sur ces 3 problèmes. Q(λ) est spécifié par l'algorithme 6 du polycopié.
Comparer les performances du Q-learning avec le Q(λ).

À l'issue de ce TP, votre Q-Learning et votre Q(λ) doivent pouvoir être appliqués à n'importe quel problème de décision de Markov.