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  :

• 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%.

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.

Choix de l'action

Implanter la méthode de Boltzmann-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(λ).

21 avec un dé

Premier pas

Résolvez le 21 avec un dé avec le Q-Learning. Je vous laisse choisir la méthode de sélection que vous voulez.
Observez votre Q-Learning jouer. Trouvez-vous qu'il joue bien ?
Vous pouvez aussi jouer quelques parties contre lui et voir qui gagne et s'il joue comme vous.

Raffinement

Le 21 avec un dé étant une tâche stochastique, le retour suivant un lancer peut varier fortement. Cela entraîne que par hasard, si le Q-Learning a de la chance, il va par exemple corriger positivement le fait de lancer le dé quand son total courant est 19 si le dé tombe sur 2, alors que la probabilité qu'il dépasse 21, donc perdre, est bien plus élevée que celle d'atteindre 21 ou 20.
Pour contrer cet effet du au hasard, on peut essayer de ne pas corriger Q après chaque coup, mais de temps en temps, après avoir joué un certain nombre de coups, et ainsi de faire une espèce de moyenne de ce qui est arrivé dans telle ou telle situation.
Modifiez votre Q-Learning pour qu'il agisse ainsi. C'est-à-dire que'au lieu de mettre à jour Q à chaque itération, vous stockez les quadruplets (s_t, a_t, r_t, s_t+1) et de temps en temps (par exemple tous les 30 épisodes), vous mettez à jour Q avec tous ces quadruplets.
Est-ce que votre Q-Learning apprend mieux ? Joue mieux ?
Pour mesurer sa performance, on fait jouer un certain nombres de parties (50 par exemple) de 21 avec un dé et on mesure la moyenne, la médiane, l'écart-type de la performance par exemple. Quand on fait cela, on utilise la politique apprise par le Q-Learning et celle-ci est fixe : on ne met pas à jour Q et on sélectionne l'action de manière gloutonne.

Labyrinthe avec porte

On reprend le labyrinthe du CC2 de PDI dont je rappelle le fonctionnement ci-dessous.
On part de la case indiquée en bleu et que l’on doit atteindre la case indiquée en vert ; à chaque itération, on peut se déplacer d’une case vers la gauche, ou vers la droite, ou vers le haut ou vers le bas ; on peut également rester sur place (ne pas changer d’état). Il y a des couloirs et des murs : les couloirs sont indiqués en blanc, les murs en noir ; on ne peut pas traverser les murs, on doit toujours être localisé sur une case blanche. Les cases couloir sont numérotées de haut en bas, de gauche vers la droite. La case orange est donc la case 0. La case de départ (bleue) est donc numérotée 19, la case verte est numérotée 12. J’ai indiqué quelques numéros sur la figure ci-dessous.
Les transitions sont déterministes : par exemple, si on décide d’aller à gauche, si la case à gauche n’est pas un mur (cellule noire), alors on se déplace bien d’une case sur la gauche. Les retours sont nuls sur toutes les transitions sauf quand on atteint la case verte : dans ce cas, le retour vaut 1. Le retour est également 1 si étant sur la case verte, on effectue l’action « ne pas bouger ».
Une porte existe dans le labyrinthe, représentée par la case grise dans la figure ci-dessous. Pour ouvrir la porte, il faut aller chercher une clé qui se trouve dans la case 0 (case orange en haut à gauche sur la figure) et aller ensuite dans la case 9 en exactement 3 actions : dans ce cas, et dans ce cas seulement, la porte s’ouvre et on atteint la case 10 en faisant un déplacement vers la droite, la porte se referme, la clé a disparu dans la serrure de la porte.



Résolvez-le avec le Q-Learning. Pour vous simplifier la tâche, je mets à votre disposition le fichier décrivant une certaine modélisation de ce labyrinthe (vue en cours) au format habituel ici.

SARSA vs. Q-Learning

Reprendre tout ce TP avec SARSA. Comparer les performances du Q-Learning et de SARSA sur ces différentes tâches.
Pour mesurer les performances lors de l'apprentissage, vous pratiquez comme ci-dessus :

• Répéter pendant un certain nombre d'épisodes (par exemple 200, ce nombre dépend de la difficulté de la tâche) :
  • Exécuter l'algorithme pendant quelques épisodes (10 par exemple, nombre qui à nouveau dépend de la difficulté de la tâche)
  • Tester la politique gloutonne pendant quelques épisodes (pendant lesquels vous ne modifiez pas Q). Pour chacune de ces exécutions, stocker la valeur de ζ dans un tableau en l'associant au nombre d'épisodes d'entraînement réalisés.
• Avec les valeurs numériques indiquées, vous avez maintenant une table contenant 20 paquets de 10 mesures de performance. Pour chacun des algorithmes que vous comparez, vous pouvez réaliser un graphique montrant l'évolution de sa performance au fil du temps.
  Les figures ci-dessous, totalement fictives, illustrent ce que j'attends que vous représentiez graphiquement .
  
  Ces trois figures sont basées sur les mêmes données qui auraient été collectées après 30, 60, 90, 120 et 150 épisodes d'entraînement, pour deux algorithmes, l'un représenté en vert, l'autre en rouge. On chacun, on aurait effectué 10 épisodes d'évaluation.
  À gauche, sont représentés pour chaque algorithme les 10 courbes d'évolution de leur performance au fil des épisodes. Est également indiqué en gras la performance moyenne.
  En milieu, sont représentés la moyenne des performance en gras et une zone située à ± 1 écart-type autour de la moyenne.
  À droite, la même chose avec une plus, en couleur plus claire, la performance moyenne ± 2 écarts-types.

Comparaison expérimentale de la performance de deux algorithmes

En apprentissage par renforcement, comme dans d'autres domaines, on ne sait pas comparer théoriquement la performance d'algorithmes. Pour comparer deux algorithmes, on doit le faire expérimentalement. S'agissant d'algorithmes stochastiques, on exécute chaque algorithme un certain nombre de fois et on doit ensuite utiliser les performances obtenues lors de ces exécutions pour déterminer lequel des algorithmes est le plus performant.
Attention, c'est un problème difficile. Bien que la plupart des publications en apprentissage par renforcement contiennent une partie expérimentale où les auteurs comparent la performance de différents algorithmes, la plupart de ces publications sont incorrectes.
Si en principe, les statistiques peuvent nous fournir la solution à ce problème, en réalité, ce n'est pas si simple et il n'est pas rare que les statistiques soient mal utilisées et que les conclusions que l'on tire ne soient pas fondées.

Supposons donc que l'on ait exécuté N fois un algorithme A et un algorithme B. Chaque exécution fournit une performance mesurée ici par \( \zeta = \sum_t \gamma^t r_t \) durant un épisode. Si N est suffisamment grand et si la performance de chaque algorithme est distribuée de manière à peu près normale, un test de Welch donne la réponse à notre questionnement. Celui-ci va nous indiquer si les performances des deux algorithmes diffèrent de manière statistiquement significative et si l'un est plus performant que l'autre. S'agissant d'un test d'hypothèse, la conclusion est valable avec une certaine probabilité, généralement fixée à 95 ou 99% (c'est-à-dire au risque 0,05 ou 0,01).
Pour appliquer ce test, on fait comme suit : supposons que ma et mb soient deux tableaux contenant les N mesures de performance des algorithmes A et B respectivement.

from scipy.stats import ttest_ind
ttest_ind (ma, mb, equal_var = False, alternative = "greater").pvalue

renvoie la probabilité que A ne soit pas plus performant que B, ce que l'on appelle la p-value (la probabilité que l'hypothèse soit rejetée). Si l'on s'autorise une probabilité de 5% de se tromper, si cette valeur renvoyée est inférieure à 0,05, c'est que le test est vérifié. Cela ne veut pas dire que l'algorithme A est meilleur que l'algorithme B, cela veut dire qu'il l'est avec une certaine probabilité qui est supérieure au risque que l'on accepte de se tromper que l'on s'est fixé. Si le test n'est pas vérifié, on peut remplacer greater par less pour tester si les données collectées permettent de conclure que l'algorithme A est moins bon que l'algorithme B avec une certaine probabilité. On peut aussi tester si la performance des deux algorithmes n'est pas distingable avec les données collectées en indiquant two-sided.
Dans le cas où les performances ne sont pas distribuées normalement, on doit utiliser un autre test, le test U de Mann-Whitney. Celui-ci ne fait pas d'hypothèse sur la distribution des données qu'il compare, il est dit « non paramétrique ».

from scipy.stats import mannwhitneyu
mannwhitneyu (ma, mb, alternative = "greater").pvalue

renvoie à nouveau la p-value pour le test : est-ce que les performances mesurées pour l'algorithme A et l'algorithme B permettent de conclure que A est plus performance que B ?

À faire : mettre en œuvre un test pour déterminer si SARSA ou le Q-Learning est plus performant que l'autre sur le 21-avec-un-dé. Comparer également SARSA et le Q-Learning au Q(λ).

Remarque importante : j'écris dans ce paragraphe que l'on compare des « algorithmes ». c'est un raccourci de langage qui peut induire en erreur. Ce que l'on compare vraiment, ce sont les implantations de deux algorithmes, paramétrés d'une certaine manière. Des implantations différentes de ces algorithmes pourrait peut-être mener à des conclusions différentes ; un autre paramétrage aussi. Et bien sûr, les éventuelles conclusions que l'on tire ne sont valables que pour la tâche sur laquelle les mesures de performance ont été collectées. La comparaison expérimentale de la performance d'algorithmes est vraiment un sujet difficile et très souvent mal traité dans les publications. Je ne fais ici que traiter les bases de cette problématique.

Ci-dessus, j'écris que le test de Student/Welch suppose que les données sont distribuées normalement. C'est une hypothèse à vérifier. Pour cela, il existe des tests statistiques, mais leur utilisation est sujette à caution. Finalement, en pratique, un diagnotic visuel fournit assez souvent un diagnostic clair. Pour cela, on réalise un probplot (souvent appelé improprement un QQ-plot) qui compare la distribution d'un ensemble de données avec une distribution normale.
Pour cela, on pratique comme suit :

fig, ax = plt.subplots ()
sm. qqplot (ma, line='s', ax = ax)
fig. show ()

ce qui produit la figure suivante :

Si les données contenues dans le tableau ma sont distribuées normalement, les points visibles sur le graphique doivent s'aligner avec la droite rouge. Ici, c'est plutôt convaincant.
Voici un autre exemple qui montre un cas où les données ne sont pas distribuées normalement :

Pour ces deux illustrations, les échantillons contiennent le même nombre de données, 50.
On note que même avec 10 données, la visualisation est informative :

Les données s'alignent mieux avec la droite dans le graphique de gauche que dans celui de droite. Néanmoins, 10 données, c'est peu.

À 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.