Q-learning

En intelligence artificielle, plus précisément en apprentissage automatique, le Q-learning est un algorithme d'apprentissage par renforcement. Il ne nécessite aucun modèle initial de l'environnement. La lettre 'Q' désigne la fonction qui mesure la qualité d'une action exécutée dans un état donné du système^[1].

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

L'article doit être débarrassé d'une partie de son jargon (janvier 2023).

Sa qualité peut être largement améliorée en utilisant un vocabulaire plus directement compréhensible. Discutez des points à améliorer en page de discussion.

Dans le *Q-learning*, l'agent exécute une action a en fonction de l'état s et d'une fonction Q. Il perçoit alors le nouvel état s' et une récompense r de l'environnement. Il met alors à jour la fonction Q. Le nouvel état s' devient alors l'état s, et l'apprentissage continue.

Applications

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].

Description

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^[pas clair] 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].

Algorithme

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 $S$ et d'actions $A$ . En réalisant une action $a\in A$ , l'agent passe d'un état $s$ à un nouvel état $s'$ et reçoit une récompense $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 $\gamma ^{\Delta t}$ où $\Delta t$ est le délai entre l'étape actuelle et future et $\gamma$ un nombre compris entre 0 et 1 (autrement dit $0\leq \gamma \leq 1$ ) appelé facteur d'actualisation.

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

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

Avant que l'apprentissage ne débute, la fonction $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] :

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

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

Un épisode de l'algorithme finit lorsque $s_{t+1}$ est un état final. Toutefois, le $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 $\Delta t$ infini.

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

Pseudo-code

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 + γ max_a' Q(s', a') - Q(s, a)]

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

Influence des variables sur l'algorithme

Facteur d'apprentissage

Le facteur d'apprentissage $\alpha$ détermine à quel point la nouvelle information calculée surpassera l'ancienne. Si $\alpha$ = 0, l'agent n'apprend rien. A contrario, si $\alpha$ = 1, l'agent ignore toujours tout ce qu'il a appris jusqu'à présent et ne considérera que la dernière information.

Dans un environnement déterministe, la vitesse d'apprentissage $\alpha _{t}(s,a)=1$ est optimale. Lorsque le problème est stochastique, l'algorithme converge sous certaines conditions dépendant de la vitesse d'apprentissage. En pratique, souvent cette vitesse correspond à $\alpha _{t}(s,a)=0.1$ pour toute la durée du processus^[7].

Facteur d'actualisation

Le facteur d'actualisation $γ$ détermine l'importance des récompenses futures. Un facteur $γ$ = 0 rendrait l'agent myope en ne considérant seulement les récompenses courantes, alors qu'un facteur $γ$ proche de 1 ferait aussi intervenir les récompenses plus lointaines. Si le facteur d'actualisation $γ$ est proche ou égal à 1, la valeur de $Q$ peut diverger^[8].

Convergence

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 $(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 $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 $i$ -ème fois. On suppose que les récompenses sont bornées, i.e. il existe une constante ${\mathfrak {R}}$ telle que la récompense $r_{n}$ à l'étape $n$ vérifie $|r_{n}|\leq {\mathfrak {R}}$ . Concernant les facteurs d'apprentissage, en notant le facteur d'apprentissage $\alpha _{n}$ à l'étape $n$ , on demande que :

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

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

Extensions et variantes

Double Q-learning

Comme le Q-learning utilise l'estimateur max, le Q-learning surestime la valeur des actions et de fait, dans des environnements bruités, l'apprentissage est lent. Ce problème est résolu dans la variante appelée double Q-learning^[10] qui utilise deux fonctions d'évaluation $Q^{A}$ et $Q^{B}$ apprises sur deux ensembles d'expériences différents. La mise à jour se fait de façon croisée :

Q_{t+1}^{A}(s_{t},a_{t})=Q_{t}^{A}(s_{t},a_{t})+\alpha _{t}(s_{t},a_{t})\left(r_{t}+\gamma ~Q_{t}^{B}\left(s_{t+1},\mathop {\operatorname {arg~max} } _{a}Q_{t}^{A}(s_{t+1},a)\right)-Q_{t}^{A}(s_{t},a_{t})\right)

, et

Q_{t+1}^{B}(s_{t},a_{t})=Q_{t}^{B}(s_{t},a_{t})+\alpha _{t}(s_{t},a_{t})\left(r_{t}+\gamma ~Q_{t}^{A}\left(s_{t+1},\mathop {\operatorname {arg~max} } _{a}Q_{t}^{B}(s_{t+1},a)\right)-Q_{t}^{B}(s_{t},a_{t})\right).

Comme la valeur estimée est évaluée en utilisant une autre politique, le problème de la surestimation est résolu. L'apprentissage de l'algorithme à ensemble peut être effectué en utilisant des techniques d'apprentissage profond, ce qui donne les réseaux DQN (deep Q-networks, réseaux profonds Q). On peut alors avoir le Double DQN, pour obtenir de meilleures performances qu'avec l'algorithme DQN original^[11].

Comparaison avec d'autres algorithmes

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 $Q[s,a]:=(1-\alpha )Q[s,a]+\alpha \left(r+\gamma \max _{a'}Q[s',a']\right)$ . On y note le terme $\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 $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].

Voir aussi

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

Notes et références

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

↑ Tambet Matiisen, « Demystifying Deep Reinforcement Learning | Computational Neuroscience Lab », sur neuro.cs.ut.ee, 19 décembre 2015 (consulté le 6 avril 2018)
↑ « Methods and Apparatus for Reinforcement Learning, US Patent #20150100530A1 », US Patent Office, 9 avril 2015 (consulté le 28 juillet 2018)
↑ C. J. Watkins, Learning from delayed rewards, Kings College, Cambridge, mai 1989
↑ (en) George F Luger, Artificial intelligence : Structures and strategies for complex problem solving. 5e édition., Addison Wesley, 2005, 903 p. (ISBN 0-321-26318-9, lire en ligne), p. 448
↑ Watkins et Dayan, Q-learning.Machine Learning, 1992
↑ (en) David L. Poole et Alan K. Mackworth, Artificial Intelligence, Cambridge University Press, 2009 (ISBN 978-0-511-79479-7, DOI 10.1017/CBO9780511794797, lire en ligne), p. 469.
↑ ^{a et b} Reinforcement Learning: An Introduction, Richard Sutton et Andrew Barto, MIT Press, 1998.
↑ (en) Stuart J. Russell et Peter Norvig, Artificial Intelligence : A Modern Approach, Prentice Hall, 2010, Third éd., 1132 p. (ISBN 978-0-13-604259-4), p. 649.
↑ ^{a et b} (en) Christopher J. C. H. Watkins et Peter Dayan, « Q-learning », Machine Learning, vol. 8, n^o 3,‎ 1^er mai 1992, p. 279–292 (ISSN 1573-0565, DOI 10.1007/BF00992698, lire en ligne, consulté le 17 février 2023).
↑ Hado van Hasselt, « Double Q-learning », Advances in Neural Information Processing Systems, vol. 23,‎ 2011, p. 2613–2622 (lire en ligne [PDF]).
↑ Hado van Hasselt, Arthur Guez et David Silver, « Deep reinforcement learning with double Q-learning », AAAI Conference on Artificial Intelligence,‎ 2015, p. 2094–2100 (lire en ligne [PDF]).
↑ « Machine Learning : L'apprentissage par renforcement », sur www-igm.univ-mlv.fr (consulté le 9 mai 2022).

Portail de l’éducation

[:0-1] Tambet Matiisen, « Demystifying Deep Reinforcement Learning | Computational Neuroscience Lab », sur neuro.cs.ut.ee, 19 décembre 2015 (consulté le 6 avril 2018)

[2] « Methods and Apparatus for Reinforcement Learning, US Patent #20150100530A1 », US Patent Office, 9 avril 2015 (consulté le 28 juillet 2018)

[3] C. J. Watkins, Learning from delayed rewards, Kings College, Cambridge, mai 1989

[4] (en) George F Luger, Artificial intelligence : Structures and strategies for complex problem solving. 5e édition., Addison Wesley, 2005, 903 p. (ISBN 0-321-26318-9, lire en ligne), p. 448

[5] Watkins et Dayan, Q-learning.Machine Learning, 1992

[6] (en) David L. Poole et Alan K. Mackworth, Artificial Intelligence, Cambridge University Press, 2009 (ISBN 978-0-511-79479-7, DOI 10.1017/CBO9780511794797, lire en ligne), p. 469.

[:2-7] {a et b} Reinforcement Learning: An Introduction, Richard Sutton et Andrew Barto, MIT Press, 1998.

[8] (en) Stuart J. Russell et Peter Norvig, Artificial Intelligence : A Modern Approach, Prentice Hall, 2010, Third éd., 1132 p. (ISBN 978-0-13-604259-4), p. 649.

[:1-9] {a et b} (en) Christopher J. C. H. Watkins et Peter Dayan, « Q-learning », Machine Learning, vol. 8, n^o 3,‎ 1^er mai 1992, p. 279–292 (ISSN 1573-0565, DOI 10.1007/BF00992698, lire en ligne, consulté le 17 février 2023).

[10] Hado van Hasselt, « Double Q-learning », Advances in Neural Information Processing Systems, vol. 23,‎ 2011, p. 2613–2622 (lire en ligne [PDF]).

[11] Hado van Hasselt, Arthur Guez et David Silver, « Deep reinforcement learning with double Q-learning », AAAI Conference on Artificial Intelligence,‎ 2015, p. 2094–2100 (lire en ligne [PDF]).

[12] « Machine Learning : L'apprentissage par renforcement », sur www-igm.univ-mlv.fr (consulté le 9 mai 2022).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]