Q-learning

Cette méthode d'apprentissage permet d'apprendre une stratégie, qui indique quelle action effectuer dans chaque état du système. Elle fonctionne par l'apprentissage d'une fonction de valeur état-action notée Q qui permet de déterminer le gain potentiel, c'est-à-dire la récompense sur le long terme, Q(s,a) , apportée par le choix d'une certaine action a dans un certain état s en suivant une politique optimale. Lorsque cette fonction de valeur d'action-état 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.

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.

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

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[5] :

${\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. On note le terme ${\displaystyle \max _{a'}Q[s',a']}$, i.e. on apprend en fonction de la meilleure action a' possible en s'. C'est pourquoi on dit que Q-learning est off-policy.

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.

initialiser Q[s, a] pour tout état s, toute action a de façon arbitraire, mais Q(état terminal, a) = 0 pour toute action a

répéter
      //début d'un épisode 
      initialiser l'état s
      
      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 l'état s'

               Q[s, a] := Q[s, a] + α[r + γ maxa' Q(s', a') - Q(s, a)]

               s := s'
               a := a'
      jusqu'à ce que s soit l'état terminal

Q-learning est off-policy. 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)}$, il n'y a pas de référence à la politique en train d'être apprise. 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'une 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[10].

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

• Portail de l’éducation