Introduction à l'apprentissage par renforcement profond

Du Q-Learning au Deep Q-Learning

Vous allez découvrir la version profonde de l’algorithme du q-learning. Pour illustrer cette méthode, je vais vous montrer comment créer une IA parvenant à jouer au casse-brique. La particularité de ce projet tiendra au fait que l’IA ne connaîtra ni les règles du jeu, ni la position exacte de la balle. De même, elle ne saura pas qu’elle contrôle le paddle etc. Les seules informations dont elle disposera seront les images du jeu. Malgré ces contraintes, elle réalisera une belle performance:

Cette prouesse est possible grâce à l’Apprentissage par renforcement profond (Deep Reinforcement Learning en anglais) et en particulier du Deep Q-Learning. Cette technique n’est bien entendu pas la seule existante dans ce domaine, je vous en dévoilerai d’autres.

Prérequis

Théoriques

Vous devez connaitre l’algorithme Q-Learning et avoir assimilé les bases en apprentissage profond : savoir ce qu’est un CNN, un minibatch, une fonction de perte etc. Le code sera écrit en python.

Matériels

Vous devez avoir au moins 12 Go de RAM.
Un GPU compatible avec CUDA, mon code a été exécuté sur un GTX 1050.
Avoir installé:
-CUDA
-tensorflow-gpu
-keras
-gym qui est un émulateur de jeux vidéo conçu par OpenAI

Apport de l’apprentissage profond pour l’apprentissage par renforcement

Pour rappel, l’algorithme de l’apprentissage Q construit un tableau de n*m cases où chacune représente la “qualité” de l’action a_{m} lorsqu’on est dans l’état s_{n}.

\begin{matrix} & a_{1} & a_{2} & a_{3} & ... & a_{m}\\ s_{1} & Q(s_{1},a_{1}) & Q(s_{1},a_{2}) & Q(s_{1},a_{3}) & ... &Q(s_{1},a_{m})\\ s_{2} & Q(s_{2},a_{1}) & Q(s_{2},a_{2}) & Q(s_{2},a_{3}) & ... &Q(s_{2},a_{m})\\ s_{3} & Q(s_{3},a_{1}) & Q(s_{3},a_{2}) & Q(s_{3},a_{3}) & ... &Q(s_{3},a_{m})\\ ... & ... & ... & ... & ... & ... \\ s_{n} & Q(s_{n},a_{1}) & Q(s_{n},a_{2}) & Q(s_{n},a_{3}) & ... &Q(s_{n},a_{m})\\ \end{matrix}

Dans le cas du casse brique, si on considère qu’une image de jeu (210*160 pixels) représente 1 état et que chaque pixel possède 3 canaux (RGB) alors il existe 210*160*256^3 états différents. La méthode basique avec le tableau est donc inutilisable car il y a trop d’états possibles dans ce jeu.
Pour utiliser l’algorithme du q-learning même lorsque l’espace d’état est très grand, l’astuce est de remarquer que le tableau ci-dessus représente une fonction. Ainsi, plutôt que de stocker toutes les combinaisons possibles en fonction s_{n} et a_{m}, une solution intéressante consiste à estimer la fonction Q:s,a \longrightarrow Q(s,a). Pour illustrer mon propos, prenons un jeu avec 3 états et 2 actions où l’algorithme du q-learning converge vers les valeurs ci-dessous :

\begin{matrix} &a_{1} & a_{2} \\ s_{1} & 3 & 4 \\ s_{2} & 5 & 6 \\ s_{3} & 7 & 8 \\ \end{matrix}

Ce tableau peut être généré par la formule Q(n,m)=2n+mn et m représentent respectivement l’indice de l’état et celui de l’action, formule que devra trouver l’IA.
Le principe est le même pour le casse-brique. En effet, même si le nombre d’états possibles est très grand, seule une poignée d’informations contenues dans les images seront intéressantes :
-Distance entre la balle et le paddle
-Vitesse de la balle
-Est-ce que la balle monte ou descend?
etc.
L’IA devra donc trouver et extraire ces caractéristiques pertinentes des images pour pouvoir estimer les valeurs de la fonction Q.
Un réseau de neurones profond de type convolutionnel (CNN) sera utilisé pour approximer la fonction Q car il est spécialisé dans l’extraction de caractéristiques dans les images.
Le Deep Q Network (DQN) prendra 4 images en entrée et donnera pour les 4 actions du jeu la “qualité” de chaque action.

Si l’on donne une seule image à notre réseau de neurones, il sera incapable d’estimer la vitesse de la balle ni de connaitre sa direction et son sens. Pour cette raison, un état sera composé de 4 images : La vitesse nécessite 2 images, l’accélération 3 et avec 4 images, on atteint une meilleure précision. En définissant un état comme un couple de 4 images, on respecte la propriété de Markov dont j’ai parlé dans le cours précédent.
state_breakout

Principe de l’algorithme Deep Q Learning

Au début de l’apprentissage, notre DQN possède des poids aléatoires donc ses valeurs Q le sont elles aussi. Comment procéder afin qu’il converge vers des valeurs cohérentes?

Pour calculer les valeurs Q(s,a) on utilisera la formule:

Q(s,a)=r+\gamma \, \max_{a'}Q(s',a')

Il existe des états où les valeurs Q de leurs actions sont connues : ceux où l’on perd. Pour ces états, Q(s,a) vaut simplement la récompense : 0. Il est à noté qu’une récompense négative pour le jeu du casse-brique n’a pas montré de meilleure performance.
Intuitivement, on peut supposer qu’au cours de son apprentissage, l’agent pourra estimer de façon pertinente les valeurs Q(s,a) des états précédant une défaite puis par récurrence remonter jusqu’au début d’une partie.
Malheureusement, en procédant de la sorte, l’apprentissage sera instable : les valeurs Q pourront diverger/osciller etc. La solution est donc d’utiliser une mémoire de rejeu et un deuxième Deep Q Network appelé Target DQN. Avec ces 2 éléments, nos entraînements seront reproductibles : ils auront des courbes d’apprentissages similaires. C’est plutôt une bonne nouvelle pour vous.

Experience Replay : La mémoire de rejeu (Replay Memory)

Prenons le cas suivant : nous sommes dans la situation d’un apprentissage supervisé. Vous souhaitez créer un programme qui sépare des images en 2 classes (chats et chiens). Quels choix allez-vous sélectionner? Enverrez-vous toutes les images de chats puis toutes celles de chiens ou alternerez-vous entre les classes? Il est évident que la seconde option est la plus judicieuse. Aussi, procéderons-nous de la même façon pour éviter d’avoir un mini-batch composé de données corrélées. Un problème de corrélation surgira si l’on donne au DQN une suite d’états consécutifs. Afin de contourner cette difficulté, on prendra simplement des états du jeu au hasard piochés dans une mémoire qui regroupe notre historique de jeu : c’est la mémoire de rejeu. Maintenant, listons les informations nécessaires et suffisantes que l’on aura besoin de stocker.

Une étape de jeu suit le processus ci-dessous:
-L’agent est dans l’état s_{t}
-L’agent choisit son action a_{t} en suivant une politique \epsilon \text{-greedy}
-L’agent se trouve désormais dans l’état s_{t+1} et obtient une récompense r_{t}. L’agent récupère aussi une information l_{t} qui indique s’il a perdu la partie.
A chaque étape, on stockera en mémoire une expérience e_{t}=(s_t,a_t,s_{t+1},r_{t},l_{t}), sa taille sera limitée à 1 million d’expériences. A chaque apprentissage, on sélectionnera 32 expériences au hasard qui formeront notre mini-batch.

L’intérêt du second DQN appelé Target DQN

Le but du Deep Q Learning est de chercher les paramètres d’une fonction à deux variables \widehat{Q}. Pour trouver ses paramètres, on se place dans le cadre de l’apprentissage supervisé. Quelles sont les conditions pour pourvoir utiliser l’apprentissage supervisé? On doit fournir deux types de données : les prédictions et les valeurs “vraies”. De plus, ces dernières doivent être fixes : elles restent identiques entre le début et la fin de l’apprentissage.

Regardons maintenant ce qu’il se passe avec un seul DQN : notre réseau de neurones produit à la fois les prédictions et les valeurs “vraies”. Les prédictions sont simplement Q(s,a). Les valeurs “vraies” \widehat{Q}(s,a) sont obtenues avec la formule ci-dessous :

\widehat{Q}(s,a)=r+\gamma \, \max_{a'}Q(s',a')

Avec ces deux valeurs, le DQN est en mesure de calculer l’erreur d’apprentissage et de mettre à jour ses poids pour s’approcher de la fonction \widehat{Q}. Cependant, en procédant de la sorte, il modifie la fonction qu’il tente d’apprendre. En effet, il produit lui-même les valeurs “vraies”, donc en changeant ses poids, il modifie Q(s',a') et par conséquent, \widehat{Q}. Mais ceci induira des valeurs “vraies” trop versatiles. Dès lors, on ne se trouvera plus dans le cadre supervisé et notre DQN oscillera/divergera.

Une solution pour pallier ce problème est de rajouter un autre appelé DQN cible (target). Ce DQN sera utilisé uniquement durant l’apprentissage, il gardera ses poids fixes (pendant une certaine durée) et nous donnera la fonction \widehat{Q} indispensable au premier DQN (online) pour apprendre.

Processus d’apprentissage :
-Le premier DQN utilisera ses poids pour choisir ses actions.
-A chaque apprentissage, les valeurs du DQN primaire (online) seront utilisées pour récupérer les prédictions et le DQN cible lui fournira les valeurs “vraies”. On ajustera alors les poids du DQN primaire pour diminuer l’erreur entre les deux DQN.
-A une période définie (10000 étapes), on copiera les poids du DQN primaire dans le DQN cible.

Cette période est suffisamment longue pour éviter la divergence.

Structure du projet

Pour construire notre IA on aura besoin de 4 fichiers :
-Partie 1 : Le code d’entraînement
-Partie 2 : La classe de la mémoire de rejeu
-Partie 3 : La classe de l’agent
-Partie 4 : La classe de notre DQN

Écrivons maintenant le code d’entraînement.