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 2

Pour pouvoir résoudre un problème complexe de bout en bout avec un algorithme de reinforcement learning, plusieurs étapes de développement doivent être réalisées, dont certaines sont parfois chronophages. Pour comprendre les défis qui se posent lorsque l’on souhaite proposer des solutions de reinforcement learning, nous allons explorer une famille d’algorithmes appelée les value optimizer, présenter les outils permettant de les déployer et évoquer certaines des difficultés à surmonter pour que le projet soit un succès.

Le fonctionnement des algorithmes de la famille des value optimizer

La famille des value optimizer est un ensemble d’algorithmes dont l’objectif est de prédire, pour chaque état s_t la valeur de chacune des actions possibles (a₁, a₂, a₃, …, am) afin de pouvoir choisir la meilleure d’entre elles. Nous avons vu dans l’article de la partie 1 que le Q-learning fait un mapping de chaque couple (s_i, aj) avec une valeur. Mais cet algorithme a des limites en raison de son manque de généralisation.

Généraliser l’apprentissage [Deep Q network – DQN]

Lorsque le nombre de couples état-action possibles est grand, deux problèmes se posent avec un modèle de Q-learning :

Il faut stocker en mémoire un grand nombre d’informations (de l’ordre de grandeur |S|x|A|). Dans le cas d’un environnement dont les états sont des images en niveaux de gris de taille 84×84, il y a 256^84×84 ≈ 3×10¹⁶⁹⁹² états potentiels ;
Chaque expérience à l’instant t ne permet d’apprendre que pour le couple état-action correspondant à cette expérience. En d’autres termes, une expérience ne se généralise pas.

L’apprentissage est donc potentiellement lourd et lent. Pour résoudre ce problème on approxime la fonction Q par une fonction plus générale, ici un réseau de neurones noté Q_θ, où θ sont les paramètres du réseau. Le réseau est défini sur l’ensemble des états s et à valeur dans un ensemble de dimension égale au nombre d’actions possibles.

On a donc :

Dans cet exemple il y a trois actions possibles. Le réseau de neurones renvoie 3 valeurs,

1 pour chaque action possible

Le processus d’apprentissage est le suivant :

on crée une target (valeur cible) à partir de (c’est un vecteur) :

2. on remplace la valeur pour l’action choisie uniquement, puisque l’expérience ne donne d’information que pour cette action :

3. est mise à jour par une descente de gradient sur ses paramètres :

avec le taux d’apprentissage.

Le deep-Q network ouvre la voie à de nombreux autres algorithmes. Nous allons voir quelques-unes des évolutions pouvant être utilisées avec le deep reinforcement learning.

Apprendre dans un environnement en mouvement

Lorsque les états renvoyés par l’environnement sont des images, il est difficile de repérer le mouvement. Pour s’en convaincre, il suffit d’essayer de deviner si notre vaisseau de Space Invader ci-dessous se déplace à gauche ou à droite en n’utilisant qu’une seule image :

L’information contenue dans chaque état n’est pas suffisante pour que l’agent apprenne parfaitement à jouer à Space Invaders. La solution est d’utiliser plusieurs images à chaque étape (step). Chaque état est par exemple une agrégation (une stack) des 4 dernières images. Cette solution permet de donner à l’agent une information sur les mouvements : direction, vitesse, etc.

Rejouer ses expériences [experience replay]

Les états successifs renvoyés par l’environnement sont souvent fortement corrélés. Par exemple, pour un jeu vidéo les images qui se suivent (éventuellement stackées, cf. partie précédente) vont fortement se ressembler les unes après les autres pour que l’action soit continue (le rendu est une vidéo). Cette corrélation pose une difficulté pour la mise à jour du réseau de neurones.

L’augmentation de la valeur associée à un couple état-action (s, a) va entraîner “mécaniquement” l’augmentation de la valeur des couples état-action proches. Cela fonctionne un peu à la manière d’une maille d’un filet de pêche tirée vers le haut^{^[1]} et qui entraîne la montée des mailles qui l’entourent.

Lorsque l’apprentissage est réalisé à chaque étape dans l’ordre chronologique des expériences, il va y avoir un surajustement du réseau pour l’ensemble de couples état-action d’une séquence homogène, ce qui peut entraîner un ralentissement de la convergence.

La solution va être de doter l’agent d’une mémoire, d’y enregistrer un grand nombre d’expériences, puis de réaliser la descente de gradient à partir de mini-batchs tirés au hasard dans la mémoire de l’agent. Cette technique est appelée l’experience replay.

Fixer sa cible

La target calculée à chaque step n’est en fait qu’une approximation (faute de mieux) de la cible réelle qui reste inconnue. La difficulté vient du fait que la cible est calculée à partir de la fonction que l’on met à jour à chaque étape. La cible est donc mouvante, ce qui peut ralentir la convergence de l’algorithme. Voici une illustration^{^[2]} du chemin parcouru inutilement par nos pondérations pour atteindre la vraie cible :

La solution est de “fixer” la target pendant un temps pour éviter qu’il y ait trop de perturbations. Le processus d’apprentissage devient alors :

tous les T steps seulement la fonction qui sert au calcul de la target est remplacée par

2. on créer une target à partir de :

3. on remplace la valeur pour l’action choisie :

4. la mise à jour de la fonction passe par la mise à jour des paramètres par descente de gradient :

Découpler le choix de l’action et la prédiction de valeur [double DQNs]

Le réseau de neurones utilisé pour calculer la target n’est mis à jour que tous les T steps (cf. étape précédente) afin de stabiliser la cible et donc de faciliter la convergence de l’algorithme. En faisant cela on fixe (la connaissance de notre environnement) utilisée pour calculer la target, mais également pour calculer le choix de la meilleure action pour un état donné.

Or risque de prédire une action qui n’est pas la meilleure action connue à la date t (celle prédite par ).

Une solution simple est de découpler le choix de l’action et la prédiction de la valeur de l’état suivant dans le calcul de la target.

Distinguer valeur intrinsèque d’un état et avantage comparatif des actions [Dueling DQN]

Les états ont une valeur intrinsèque qui peut être plus ou moins élevée. L’exemple de Tetris ci-dessous illustre deux états dont les valeurs intrinsèques sont manifestement très différentes.

Suite à ce constat, l’intuition est qu’il serait peut-être plus efficace de calculer, d’une part, la valeur intrinsèque de l’état et, d’autre part, la “valeur ajoutée” de chaque action. La solution est de calquer l’architecture du réseau de neurones pour coller à cette intuition et tenter d’améliorer l’apprentissage. En d’autres termes, « on structure le réseau de neurones pour qu’il corresponde à la physique du problème » (expression proposée par Pierre Sendorek, Data Scientist chez PSE).

Voici ce que donne l’architecture présentée par Thomas Simonini dans ses cours en ligne.

Schéma issu des cours de Thomas Simonini (suivre ce lien)

Prioriser les expériences choisies [PER – prioritized experience replay]

Les expériences pour lesquelles il y a une grande différence entre la valeur prédite et la target sont celles à partir desquelles l’algorithme apprend le plus. Or si les batchs sont tirés avec équiprobabilité à partir des expériences enregistrées en mémoire, ces événements risquent de ne servir que rarement à l’entraînement du modèle.

Solution : pondérer les expériences en fonction de leur intérêt

Il est possible d’affecter des pondérations en fonction de l’importance de l’écart entre la target et la prédiction, ce qui permet de tirer avec plus de chance les expériences les plus pertinentes pour l’apprentissage.

Résoudre son problème de bout en bout

Créer un environnement

Nous avons vu dans l’article précédent que l’on peut utiliser GYM comme wrapper de l’environnement. Ce package est très pratique, car il s’intègre avec d’autres outils. En revanche, il ne réduit pas le temps de développement de l’environnement qui peut prendre la forme :

d’un simulateur, de nombreux existent déjà (jeux vidéo, robotique, etc.) mais ne sont pas forcément adaptés au problème auquel on souhaite s’attaquer ;
d’une interface vers un système réel, interrogée par des requêtes envoyées par l’agent et renvoyant des réponses (états) auxquelles peuvent être associées des récompenses.

Orchestrer des cycles d’apprentissage

Plusieurs packages peuvent être utilisés pour l’entraînement d’agents. Ils sont plus ou moins faciles d’accès et comprennent un éventail d’agents plus ou moins grand. RL Coach est un package qui nous semble particulièrement pratique en raison de sa maturité (version 1.0.0 délivrée à l’été 2019) et de l’étendue des algorithmes disponibles. Ce package possède également de nombreuses fonctionnalités pour organiser les cycles d’entraînement, sauvegarder les agents entraînés, monitorer les performances, etc.

Un article à venir sera consacré à cet outil.

Quel algorithme choisir ?

Un modèle de deep RL peut être doté d’une ou plusieurs features parmi celles qui ont été présentées dans la première partie de cet article. Les résultats ne sont pas toujours meilleurs avec des algorithmes qui pourtant semblent a priori plus avancés. Pour le jeu Pong, dont l’objectif est de remporter les 20 points de la partie (le score varie entre -20 et 20), un Deep Q-Network (DQN) suffit à gagner systématiquement une partie contre “l’ordinateur” après un millier de parties.

Lorsque l’on tente de réaliser des entraînements avec des algorithmes utilisant plusieurs réseaux de neurones (Dueling-DDQN) ou lorsque que l’on utilise le prioritized experience replay (PER) les performances ne sont pas forcément meilleures et peuvent même être moins bonnes.

Considérant l’ensemble des paramètres à choisir et la diversité des algorithmes il peut être coûteux d’avancer à l’aveugle. Les retours d’expérience que l’on trouve dans des papiers de recherche ou des articles de blog peuvent être une source d’inspiration précieuse lorsque l’on s’attaque à une nouvelle problématique. Mais il sera probablement nécessaire de tester, tester et encore tester avant d’avoir des résultats satisfaisants… et cela peut prendre du temps.

Conclusion

Face à un problème d’apprentissage nouveau ou complexe, plusieurs étapes sont nécessaires avant d’envisager une solution de Deep Reinforcement Learning :

formuler son problème sous la forme d’une prise de décision ;
s’assurer qu’il est envisageable de définir un simulateur ou une API interfacée avec un système réel ;
prévoir du temps pour choisir un algorithme et des paramètres satisfaisants.

Des outils sont disponibles pour faciliter le développement de solutions de Deep Reinforcement Learning, GYM qui va permettre de wrapper son environnement et RL Coach pour orchestrer ses entraînements. Mais nous ne sommes pourtant pas au bout de nos peines, plusieurs questions doivent encore être discutées pour apporter une vision complète d’un projet de Deep Reinforcement Learning :

Quelle fonction de reward choisir pour assurer la convergence de l’apprentissage ?
Comment gérer le risque lié à l’exploration lors de l’apprentissage ?
Comment prendre des décisions dans un ensemble continu ?

Nous discuterons de ces questions dans un prochain article.

Références

[1] Jonathan Hui, https://medium.com/@jonathan_hui/rl-dqn-deep-q-network-e207751f7ae4

[2] Articles de Thomas Simonini : https://simoninithomas.github.io/Deep_reinforcement_learning_Course/

[3] Alexis Pan, Deep reinforcement learning doesn’t work yet, (2018)

Reinforcement learning, partie 2 : one step deeper