Reinforcement learning, partie 1 : introduction

 

 

Introduction

Le reinforcement learning (apprentissage par renforcement) est une méthode d’apprentissage machine permettant de réaliser des tâches complexes de façon autonome. Encore récemment, cette famille d’algorithmes a fait parler d’elle dans le domaine de l’e-sport lors de la sortie d’AlphaStar, algorithme développé par DeepMind pour défier les meilleurs joueurs du monde à Starcraft II. Ces algorithmes ont un fort potentiel mais s’avèrent parfois très longs à construire et paramétrer.
Pour découvrir comment tirer parti de ces algorithmes et résoudre des problèmes concrets en production, nous vous proposons une série d’articles détaillant les mécanismes d’apprentissage, les outils disponibles, certains pièges à éviter et des astuces pratiques. L’objectif de cette série est de vous permettre de comprendre ce qu’est le reinforcement learning et de gagner du temps lors de l’implémentation de ce type de solution.

Les thèmes qui sont abordés dans cette série sont les suivants.

★ Partie 1 : présentation générale du reinforcement learning, explication du Q-learning et premiers pas vers une implémentation avec GYM.

★ Partie 2 : présentation générale du deep reinforcement learning, explication du fonctionnement des algorithmes “value optimizer” et discussion sur l’utilisation d’un simulateur.

 

Partie 1

Pour solutionner des problèmes de prédiction, un modèle de machine learning supervisé classique apprend à prédire un output y’ en fonction d’un input x’. Pour cela on l’entraîne sur des données labellisées, cela signifie que pour chaque individu x des données d’entraînement, on connaît la valeur de la variable que l’on cherche à prédire y (appelé le label).

Dans le cas du reinforcement learning, les prédictions sont des actions devant permettre de réaliser une tâche dans un environnement donné. Par exemple, quelles actions doivent être prises pour un algorithme devant gagner au jeu du Space Invaders ? A chaque moment, la meilleure action dépend à la fois de l’état de la partie et de ses conséquences futures.

Avec le reinforcement learning, il n’est pas nécessaire d’avoir des données labellisées. L’algorithme apprend la meilleure prédiction grâce à une fonction de récompense (reward function) qui renvoie une valeur plus ou moins grande en fonction de l’action choisie (déplacement d’une pièce aux échecs par exemple) et de l’état dans lequel se trouve l’environnement (position des pièces sur le plateau). C’est pour cela que les algorithmes de reinforcement learning sont dits semi-supervisés.

Pour comprendre comment ces algorithmes fonctionnent nous allons poser les concepts clefs de manière un peu plus formalisé, puis nous détaillerons le fonctionnement de l’un des algorithmes les plus simples (le Q-learning) et nous verrons comment l’implémenter en python.

Le reinforcement learning comment ça marche ?

Commençons par une définition un peu formelle

Le reinforcement learning est une méthode d’apprentissage machine dont l’objectif est de permettre à un agent (entité virtuelle : robot, programme, etc.), placé dans un environnement interactif (ses actions modifient l’état de l’environnement), de choisir des actions maximisant des récompenses quantitatives.

L’agent fait des essais et améliore sa stratégie d’action en fonction des récompenses fournies par l’environnement.

Les informations échangées entre l’agent et l’environnement : les états, les actions et les récompenses (S, A, R)

L’ensemble des états de l’environnement noté S. L’environnement est ce qui représente le “monde” dans lequel se situe notre problème. C’est par exemple un plateau de jeu avec des pièces dessus et des règles de déplacement (pour les échecs, les dames, etc.). L’ensemble S est l’ensemble des états possibles de l’environnement. Pour les échecs ce sera toutes les positions des pièces possibles. Chaque nouvel état répond à l’état précédent, l’action de l’agent et la dynamique interne de l’environnement.

L’environnement n’est pas forcément déterministe, le choix d’une action dans un état donné ne donne pas toujours exactement le même état en retour ni la même récompense.

L’ensemble des actions A. L’ensemble des actions est le champ des possibilités de l’agent. Pour une partie d’échecs, ce sont tous les déplacements réglementaires des pièces.

L’ensemble des rewards noté R. Les rewards (ou récompenses) sont la valorisation immédiate d’une action dans un état donné.

Pour les échecs par exemple on peut penser au système de récompense suivant :

• l’agent reçoit 0 après chaque coup qui ne met pas fin à la partie ;
• au dernier coup il reçoit 1 s’il gagne ou -1 s’il perd.

Mais il y a d’autres manières de lui donner des récompenses, par exemple valoriser le fait de prendre des pièces adverses importantes.

La définition d’une bonne fonction de reward sera déterminante pour que l’apprentissage converge et que l’agent réponde correctement à la tâche que l’on souhaite lui assigner. Nous discuterons plus en détail la manière de construire une fonction de reward dans un prochain article.

A chaque instant t on a un état de l’environnement (s_t dans S), une récompense (r_t dans R) en fonction de l’action précédente et une nouvelle action (a_t dans A). Le cycle d’interaction entre l’agent et l’environnement est décrit par le schéma suivant.

Inspiré de : Sutton, Richard S., and Andrew G. Barto.

« Reinforcement learning : an introduction. » (2011).

 

Exemple du Space Invaders. Lorsque l’on joue à Space Invaders nous avons un flux d’images (flux d’états successifs) au cours duquel nous pouvons prendre des décisions (actions), pour pouvoir maximiser le score (somme des rewards). Pour un état nous avons ceci :

 

La politique π : comment choisir ses actions ?

La politique d’action (ou “politique” tout court) est la stratégie adoptée par l’agent. Cette politique associe donc une action a_t à un état s_t.

La politique n’est pas fixe, elle peut (et même doit) évoluer au cours du temps pour être améliorée : c’est l’apprentissage. On utilisera parfois l’indice t pour noter qu’elle dépend du temps.

Souvent, au début de l’apprentissage, la politique est simplement de choisir une action au hasard.

La fonction action-valeur (Q): quelle valeur pour une action ?

En reinforcement learning, la fonction “action-valeur” associe à une action (a_t) et un état (s_t) l’espérance des gains futurs actualisés. En d’autres termes, c’est la somme des récompenses futures que l’on peut espérer, en pondérant d’autant moins une récompense qu’elle va arriver dans longtemps.

Cette valeur n’est pas uniquement celle de la prochaine récompense (reward) car nous voulons anticiper les récompenses futures et adopter une stratégie à long terme : on préfère prendre une action avec une reward immédiate faible mais offrant des possibilités de récompenses futures importantes.

Formellement la fonction est définie comme suit :

Avec :

• s_t, l’état dans lequel se trouve l’environnement à l’instant t
• a_t, l’action choisie par l’agent à l’instant t
• π_t, la politique d’action de l’agent
• r_i, la reward reçu par l’agent à l’instant i
• λ, le facteur de discount (taux d’actualisation) compris entre 0 et 1

Ici λ est un facteur de discount (taux d’actualisation), ce qui signifie que plus sa valeur est proche de 0, plus on a une préférence pour des récompenses présentes. À l’inverse, si sa valeur est 1, on est indifférent entre une récompense à l’instant t ou une récompense dans très longtemps.

Décomposition du cycle d’entraînement

L’entraînement d’un agent est décomposé en épisodes. Chaque épisode représente une expérience complète qui prend fin pour l’une des trois raisons suivantes : un time-out a été atteint, l’agent a perdu, l’agent a achevé la tâche assignée.

 

Par exemple un épisode peut être :

• une partie d’un jeu (échecs, jeu vidéo, etc.) qui prend fin lorsque l’agent gagne ou perd ;
• une tentative de sortie d’un labyrinthe qui prend fin lorsque l’agent sort ou lorsqu’il a passé trop de temps à essayer de sortir ;
• etc.

 

Chaque épisode se décompose en step correspondant à un cycle complet d’actions de l’agent et réactions de l’environnement

Lors du cycle d’apprentissage, la fonction valeur va être mise à jour en fonction des récompenses (rewards) reçues. L’algorithme que nous allons voir maintenant permet de construire une fonction action-valeur et de la mettre à jour afin de l’affiner au cours de l’apprentissage.

Un algorithme de base : le Q-learning

Il existe de nombreux algorithmes de reinforcement learning catégorisés en plusieurs sous-familles. Le Q-learning est à la fois relativement simple et permet en même temps de comprendre des mécanismes d’apprentissage communs à beaucoup d’autres modèles.

Pour illustrer le fonctionnement d’un algorithme de Q-learning nous allons voir comment il fonctionne pour résoudre un problème basique : le jeu du labyrinthe. L’objectif du jeu est d’apprendre au robot à sortir le plus rapidement possible alors qu’il est placé aléatoirement sur l’une des cases blanches.

Trois étapes sont au coeur du processus d’apprentissage :

• Connaître : définir une fonction action-valeur Q ;
• Renforcer ses connaissances : mettre à jour la fonction Q ;
• Agir : adopter une stratégie d’action π

Connaître : construire une fonction d’association action-valeur Q

La fonction action-valeur Q (connaissance de l’agent) dans un algorithme de Q-learning se résume à une association de chaque couple état-action (s_i, aj) avec une valeur (v estimée).

 

Dans cet exemple il y a m états et n actions possibles.

Pour chaque couple(s_i,a_j) la valeur associée est initialisée au hasard. L’objectif de l’algorithme est, pour chaque couple (s_i,a_j), d’affiner la valeur v associée afin qu’elle converge vers la “vraie” valeur de la somme des récompenses futures espérées lorsque l’agent choisit l’action a_j dans l’état s_i.

Dans le labyrinthe, au départ le robot se déplace au hasard puisque les valeurs qu’il associe à chaque action sont tirées au sort. Au bout d’un moment, le robot va finir par sortir du labyrinthe malgré tout. Il recevra alors une récompense (rewards) positive valant 1.

Renforcer ses connaissances : la mise à jour de Q

Lors de sa première sortie, le robot a appris que lorsqu’il est en h5, s’il va à droite il a une reward de 1. Il met à jour sa fonction Q.

Lors du deuxième essai, les connaissances du robot restent limitées. Mais il arrive par hasard sur la case g5 par exemple et choisit au hasard d’aller à droite. Une fois sur h5 , il utilise ses “connaissances” et choisit d’aller à droite pour sortir du labyrinthe.

Il apprend de cette expérience !

En g5, en allant à droite il sait maintenant qu’il va gagner 0 immédiatement, mais qu’il peut gagner 1 à l’étape d’après. Dans l’exemple on choisit un facteur de discount valant 0,9.

En h5, il confirme que choisir d’aller à droite lui rapporte 1. Il va donc renforcer sa connaissance initiale en faisant un “mix” entre la connaissance passée et celle présente. Ici cela ne change rien, car il a reçu 1 dans les deux cas. Dans l’exemple on mixe moitié-moitié.

L’opération sera répétée de nombreuses fois, jusqu’à ce que la connaissance de l’agent (notre robot) soit suffisante pour sortir du labyrinthe rapidement.

Comme la fonction Q évolue au fur et à mesure de l’apprentissage, on utilise parfois un indice pour identifier le nombre d’itérations passées. On part donc de Q₀ pour l’initialisation et l’on arrive à Q_t après t itérations.

 

Formellement, ça donne quoi ?

L’apprentissage se fait en trois étapes :

1/ Dans l’état s_t, l’agent choisit une action a_t et observe la réponse de l’environnement : r_t la récompense immédiate et s_t+1 le nouvel état de l’environnement.

2/ On calcule une target qui approxime la valeur que l’on peut imputer au couple (a_t,s_t). Elle est composée de la récompense immédiate exacte (r_t) et de l’ensemble des récompenses futures espérées à partir de t+1, qui est approximé grâce aux connaissances actuelles (Q_t) et “corrigé” du facteur d’actualisation (λ).

3/ On met à jour la fonction pour le couple en “mixant” la connaissance passée et celle issue de l’expérience immédiate (la target) :

Une manière d’implémenter cet apprentissage en python serait de commencer par créer un DataFrame pandas nommé Q avec l’ensemble des couples état-action possibles et 0 comme valeur par défaut. Nous verrons dans la suite comment définir l’environnement noté env.

 

Pour la mise à jour, la fonction doit prendre en compte à la fois l’état présent et l’état suivant.

 

 

Agir : la politique π

La politique d’action π est de type ε-greedy, cela signifie que, dans l’état s, l’agent choisit une action au hasard avec une probabilité ε et que le reste du temps il choisit l’action qui maximise son espérance de gains futurs. Les actions prises au hasard correspondent à des phases d’exploration, celles prises pour maximiser les gains sont celles des phases d’exploitation.

Le choix de la valeur doit faire l’objet d’un arbitrage :

• si l’agent n’explore pas assez, il va apprendre lentement. Il va mettre longtemps à converger vers une stratégie d’action optimale (voire ne convergera jamais si ε vaut 0) ;
• si l’agent explore trop, les actions choisies seront sous-optimales.

Une bonne stratégie sera par exemple de choisir une valeur élevée pour ε au début de l’apprentissage, puis de diminuer cette valeur au fur et à mesure jusqu’à un seuil proche de 0 (mais pas nulle, pour garder une capacité d’adaptation).

Les graphiques ci-dessous montrent les résultats d’entraînement d’un algorithme de Q-learning apprenant à sortir d’un labyrinthe. Lorsque ε est très faible (graphique de droite) il y a peu d’exploration ce qui fait qu’en fin d’apprentissage le robot est plus performant en moyenne que lorsque l’exploration est plus élevée (ε vaut 0,3 pour le graphique de gauche), ce qui est normal puisque l’on prend plus souvent la décision optimale.

En revanche, une exploration plus élevée permet de découvrir l’environnement plus rapidement.

 

Performances du Q-learning pour résoudre le labyrinthe

L’implémentation en python de la politique peut être la suivante.

 

GYM : un outil pour créer son environnement

De nombreux outils existent pour développer des solutions utilisant le reinforcement learning. L’un des incontournables est GYM ([3]) qui est une librairie python permettant de wrapper des environnements de façon standardisée. Plusieurs environnements reproduisant des problèmes standards sont disponibles d’origine, par exemple MountainCar-v0, dont le but est de faire arriver le chariot en haut de la colline de droite.

Le chariot du MountainCar-v0 essayant de gravir la colline

L’ensemble des environnements est disponible ici. L’utilisation d’un environnement GYM prédéfini est relativement simple, il suffit de créer l’environnement, l’initialiser, puis d’interagir avec lui.

 

 

Vous pouvez retrouver un exemple complet d’implémentation du Q-learning ici. Il s’agit d’un labyrinthe simple avec des pièges et une part d’aléatoire dans la réaction de l’environnement. Pour plus d’informations sur l’environnement vous pouvez suivre ce lien.

Conclusion

En théorie donc, le reinforcement learning permet à un algorithme d’apprendre à réaliser des tâches en anticipant les récompenses futures espérées sans avoir à lui montrer la meilleure stratégie, puisqu’il doit la découvrir lui-même. Cela semble une piste très prometteuse de résolution de problème de prise d’actions complexes.

Nous avons vu qu’un agent peut apprendre une tâche simple avec le Q-learning dans le cas du jeu du labyrinthe. Mais lorsque la tâche est plus difficile, que l’environnement est plus complexe et que l’on doit passer en production, peut-on toujours utiliser du reinforcement learning ?

Nous verrons dans un prochain article comment le reinforcement learning permet de résoudre des tâches bien plus complexes, notamment en utilisant la puissance des réseaux de neurones artificiels.

Références

[1] Sutton, Richard S., and Andrew G. Barto. « Reinforcement learning : an introduction. » (2011)

[2] Steeve Huang. “Introduction to Various Reinforcement Learning Algorithms. Part I” (Q-Learning, SARSA, DQN, DDPG)”. (2018)

[3] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, Wojciech Zaremba. “OpenAI Gym”. (2016)