Q-learning

Google DeepMind a réalisé un programme informatique qui joue à des jeux vidéos Atari 2600. Pour cela, ils ont appliqué le Q-learning avec de l'apprentissage profond. Cette technique s'appelle alors le "deep reinforcement learning" or "deep Q-learning". Cela fait l'objet d'un brevet[2].

Environnement sous la forme d'une grille. Le robot se déplace de case en case. Sur une case "tête de mort" : le robot meurt et perd 100€. Sur une case "gâteau", le robot gagne 100€. Sur les autres cases, le robot perd 1€. Pour une case s, plus une flèche dans une direction a est noire, plus Q(s, a) est grand. Si les flèches sont pleines et vertes, il s'agit d'une valeur Q(s, a) maximale.

Considérons un système quelconque : par exemple, un jeu vidéo, un robot qui doit s'évader d'un labyrinthe, ou encore un robot qui doit apprendre à tenir un œuf. Un agent (programme informatique, robot) doit alors apprendre à réaliser une tâche : gagner une partie de jeu vidéo avec le plus de points, s'évader d'un labyrinthe sans se faire attraper, tenir l’œuf le plus longtemps sans le casser. Le Q-learning permet d'apprendre une stratégie, qui indique quelle action effectuer dans chaque état du système. Par exemple, le robot peut apprendre d'aller à droite quand il se trouve sur la case (2, 3), mais d'aller en haut s'il se trouve sur la case (4, 6), etc. A chaque étape, l'agent reçoit une récompense immédiate qui est un nombre réel. Typiquement, l'agent peut recevoir 100 euros s'il est sorti du labyrinthe, ou s'il a gagné le jeu. L'agent reçoit -100 euros s'il est piégé, si l’œuf est cassé. C'est le concepteur de l'environnement qui choisit ces récompenses immédiates lorsqu'il modélise le système.

Plus précisément, le Q-learning apprend une fonction de valeur notée Q. Cette fonction Q estime le gain potentiel, c'est-à-dire la somme des récompenses Q(s,a) sur le long terme, apportée par le choix d'une certaine action a dans un certain état s en suivant une politique optimale. Cette fonction Q s'appelle fonction de valeur actions-états, puisqu'elle prend comme argument un état s et une action a. Par exemple, Q( être en (2, 3), aller à droite) est une estimation de la somme des récompenses si l'agent (programme informatique, robot) est dans la case (2, 3) et décide d'aller à droite. Lorsque cette fonction de valeur Q d'actions-états est connue ou apprise par l'agent, la stratégie optimale peut être construite en sélectionnant l'action à valeur maximale pour chaque état, c'est-à-dire en sélectionnant l'action a qui maximise la valeur Q(s,a) quand l'agent se trouve dans l'état s. Autrement dit, si l'agent est dans la case (2, 3), il regarde les valeurs Q( être en (2, 3), aller à droite), Q( être en (2, 3), aller à gauche), Q( être en (2, 3), aller à haut) , Q( être en (2, 3), aller à bas) et Q( être en (2, 3), rester sur place). Il choisit alors l'action qui maximise la valeur. Par exemple si

• Q( être en (2, 3), aller à droite) = 78€
• Q( être en (2, 3), aller à gauche) = 22€
• Q( être en (2, 3), aller à haut) = -5€
• Q( être en (2, 3), aller à bas) = 12€

alors l'agent décide d'aller à droite (car 78€ est le gain maximal).

Un des points forts du Q-learning est qu'il permet de comparer les récompenses probables de prendre les actions accessibles sans avoir de connaissance initiale de l’environnement. En d'autres termes, bien que le système soit modélisé par un processus de décision markovien (fini), l'agent qui apprend ne le connaît pas et l'algorithme du Q-learning ne l'utilise pas directement : en particulier, l'algorithme n'utilise jamais l'information des probabilités de passer d'un état s' à un état s en exécutant l'action a. Le Q-learning ne fait que interagir avec l'environnement.

Cette notion d’apprentissage par récompense a été introduite à l'origine dans la thèse de Watkins en 1989[3]. C'est une variante de l'apprentissage par différence temporelle[4]. Le Q-learning converge vers une stratégie optimale, c'est-à-dire qu'il conduit à maximiser la récompense totale des étapes successives[5].

La fonction de valeur action-état dans une table est initialisée à 0 pour chaque couple action-état. Chaque cellule est mise à jour pendant l'exécution de l'algorithme Q-learning.

La situation consiste en un agent, un ensemble d'états ${\displaystyle S}$ et d'actions ${\displaystyle A}$. En réalisant une action ${\displaystyle a\in A}$, l'agent passe d'un état ${\displaystyle s}$ à un nouvel état ${\displaystyle s'}$et reçoit une récompense ${\displaystyle r}$ (c'est une valeur numérique). Le but de l'agent est de maximiser sa récompense totale. Cela est réalisé par apprentissage de l'action optimale pour chaque état. L'action optimale pour chaque état correspond à celle avec la plus grande récompense sur le long terme. Cette récompense est la somme pondérée de l'espérance mathématique des récompenses de chaque étape future à partir de l'état actuel. La pondération de chaque étape peut être ${\displaystyle \gamma ^{\Delta t}}$ où ${\displaystyle \Delta t}$ est le délai entre l'étape actuelle et future et ${\displaystyle \gamma }$ un nombre compris entre 0 et 1 (autrement dit ${\displaystyle 0\leq \gamma \leq 1}$) appelé facteur d'actualisation.

L'algorithme calcule une fonction de valeur action-état :

${\displaystyle Q:S\times A\to \mathbb {R} }$

Avant que l'apprentissage ne débute, la fonction ${\displaystyle Q}$ est initialisée arbitrairement. Ensuite, à chaque choix d'action, l'agent observe la récompense et le nouvel état (qui dépend de l'état précédent et de l'action actuelle). Le cœur de l'algorithme est une mise à jour de la fonction de valeur. La définition de la fonction de valeur est mise à jour à chaque étape de la façon suivante[6] :

${\displaystyle Q[s,a]:=(1-\alpha )Q[s,a]+\alpha \left(r+\gamma \max _{a'}Q[s',a']\right)}$

où ${\displaystyle s'}$est le nouvel état, ${\displaystyle s}$ est l'état précédent, ${\displaystyle a}$ est l'action choisie, ${\displaystyle r}$ est la récompense reçue par l’agent, ${\displaystyle \alpha }$ est un nombre entre 0 et 1, appelé facteur d'apprentissage, et ${\displaystyle \gamma }$ est le facteur d'actualisation. En d'autres termes, la valeur de ${\displaystyle Q[s,a]}$ est remplacée par une moyenne pondérée entre la précédente valeur de ${\displaystyle Q[s,a]}$ (pondérée par ${\displaystyle 1-\alpha }$) et le gain attendu ${\displaystyle r+\gamma \max _{a'}Q[s',a']}$ (pondérée par ${\displaystyle \alpha }$).

Un épisode de l'algorithme finit lorsque ${\displaystyle s_{t+1}}$ est un état final. Toutefois, le ${\displaystyle Q}$-learning peut aussi être appliqué à des tâches non épisodiques. Si le facteur d'actualisation est plus petit que 1, la valeur action-état est finie même pour ${\displaystyle \Delta t}$ infini.

N.B. : Pour chaque état final ${\displaystyle s_{f}}$, la valeur de ${\displaystyle Q(s_{f},a)}$ n'est jamais mise à jour et maintient sa valeur initiale. Généralement, ${\displaystyle Q(s_{f},a)}$ est initialisé à zéro.

Voici le pseudo-code du Q-learning.

entrée : taux d'apprentissage α > 0 et un petit ε > 0, taux γ > 0
sortie : tableau Q[., .]
initialiser Q[s, a] pour tout état s non final, toute action a de façon arbitraire, 
         et Q(état terminal, a) = 0 pour toute action a
répéter
      //début d'un épisode 
      s := état initial
      répéter
               //étape d'un épisode
               choisir une action a depuis s en utilisant la politique spécifiée par Q (par exemple ε-greedy)
               exécuter l'action a
               observer la récompense r et le nouvel état s'
               Q[s, a] := Q[s, a] + α[r + γ maxa' Q(s', a') - Q(s, a)]
               s := s'
      jusqu'à ce que s soit l'état terminal

En 1992, Watkins et Dayan ont proposé la première démonstration de convergence de l'algorithme de Q-learning[9]. Le théorème est le suivant.

On suppose que les couples état-action ${\displaystyle (s,a)}$ apparaissent une infinité de fois (cf. p. 281 de [9] ; attention, le vocabulaire utilisé est différent de celui du livre de Sutton et Barto[7] ; un épisode pour Watkins et Dayan est une observation de l'état, la sélection de l'action, l'observation de la récomposence et la mise à jour ; alors que dans le livre de Sutton et Barto, un épisode est une suite de mise à jour jusqu'à atteindre un état final). Notons ${\displaystyle n^{i}(s,a)}$ le numéro de l'étape où l'agent est dans l'état s et s'apprète à exécuter l'action a pour la ${\displaystyle i}$-ème fois. On suppose que les récompenses sont bornées, i.e. il existe une constante ${\displaystyle {\mathfrak {R}}}$ telle que la récompense ${\displaystyle r_{n}}$ à l'étape ${\displaystyle n}$ vérifie ${\displaystyle |r_{n}|\leq {\mathfrak {R}}}$. Concernant les facteurs d'apprentissage, en notant le facteur d'apprentissage ${\displaystyle \alpha _{n}}$ à l'étape ${\displaystyle n}$, on demande que :

• ${\displaystyle 0\leq \alpha _{n}<1}$
• ${\displaystyle \sum _{i=1}^{+\infty }\alpha _{n^{i}(s,a)}=+\infty }$ pour tout couple état-action ${\displaystyle (s,a)}$
• ${\displaystyle \sum _{i=1}^{+\infty }\alpha _{n^{i}(s,a)}^{2}<+\infty }$ pour tout couple état-action ${\displaystyle (s,a)}$

Le théorème dit, alors que sous ces conditions, le tableau ${\displaystyle Q_{n}}$ à l'étape ${\displaystyle n}$, converge avec probabilité 1 vers le tableau optimal ${\displaystyle Q^{*}}$.

Q-learning est off-policy, c'est-à-dire que l'on distingue :

• la politique utilisée au cours de l'apprentissage, qui est généralement une politique ε-greedy ;
• la politique utilisée dans l'équation de mise à jour ${\displaystyle Q[s,a]:=(1-\alpha )Q[s,a]+\alpha \left(r+\gamma \max _{a'}Q[s',a']\right)}$. On y note le terme ${\displaystyle \max _{a'}Q[s',a']}$, i.e. on apprend en fonction de la meilleure action a' possible en s'. Ainsi, a' n'est pas sélectionnée via la politique d'apprentissage (typiquement, la politique ε-greedy).

Un algorithme similaire à Q-learning est l'algorithme SARSA mais la mise à jour, elle, utilise la politique en train d'être apprise. Dans SARSA, l'équation de mise à jour est ${\displaystyle Q[s,a]:=(1-\alpha )Q[s,a]+\alpha \left(r+\gamma Q[s',a']\right)}$ où a' est l'action choisie depuis l'état s' par la politique en cours d'apprentissage. Q-learning apprend une politique optimale, alors que SARSA apprend une politique proche de l'optimale. L'exemple classique (du livre de Sutton et Barto) est celui d'un robot qui apprend à aller d'un point A à un point B près d'une falaise. Q-learning apprend une politique optimale qui longe la falaise, alors que SARSA apprend une politique plus sûre, où le robot est un peu plus loin du précipice. En résumé, Q-learning est plus efficace et SARSA plus sûr[12].

• SARSA, un autre algorithme d'apprentissage par renforcement mais on-policy

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Q-Learning » (voir la liste des auteurs).