Q-learning

technique d'Intelligence Artificielle d'apprentissage par renforcement

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

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

modifier

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

modifier
 
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

modifier
 
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   et d'actions  . En réalisant une action  , l'agent passe d'un état   à un nouvel état  et reçoit une récompense   (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    est le délai entre l'étape actuelle et future et   un nombre compris entre 0 et 1 (autrement dit  ) appelé facteur d'actualisation.

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

 

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

 

 est le nouvel état,   est l'état précédent,   est l'action choisie,   est la récompense reçue par l’agent,   est un nombre entre 0 et 1, appelé facteur d'apprentissage, et   est le facteur d'actualisation. En d'autres termes, la valeur de   est remplacée par une moyenne pondérée entre la précédente valeur de   (pondérée par  ) et le gain attendu   (pondérée par  ).

Un épisode de l'algorithme finit lorsque   est un état final. Toutefois, le  -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   infini.

N.B. : Pour chaque état final  , la valeur de   n'est jamais mise à jour et maintient sa valeur initiale. Généralement,   est initialisé à zéro.

Pseudo-code

modifier

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

Influence des variables sur l'algorithme

modifier

Facteur d'apprentissage

modifier

Le facteur d'apprentissage   détermine à quel point la nouvelle information calculée surpassera l'ancienne. Si   = 0, l'agent n'apprend rien. A contrario, si   = 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   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 à   pour toute la durée du processus[7].

Facteur d'actualisation

modifier

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   peut diverger[8].

Convergence

modifier

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

  •  
  •   pour tout couple état-action  
  •   pour tout couple état-action  

Le théorème dit, alors que sous ces conditions, le tableau   à l'étape  , converge avec probabilité 1 vers le tableau optimal  .

Extensions et variantes

modifier

Double Q-learning

modifier

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  et   apprises sur deux ensembles d'expériences différents. La mise à jour se fait de façon croisée :

 , et
 

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

modifier

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  . On y note le terme  , 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   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

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

Notes et références

modifier
  1. Tambet Matiisen, « Demystifying Deep Reinforcement Learning | Computational Neuroscience Lab », sur neuro.cs.ut.ee, (consulté le )
  2. « Methods and Apparatus for Reinforcement Learning, US Patent #20150100530A1 », US Patent Office, (consulté le )
  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, , 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, (ISBN 978-0-511-79479-7, DOI 10.1017/CBO9780511794797, lire en ligne), p. 469.
  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, , Third éd., 1132 p. (ISBN 978-0-13-604259-4), p. 649.
  9. a et b (en) Christopher J. C. H. Watkins et Peter Dayan, « Q-learning », Machine Learning, vol. 8, no 3,‎ , p. 279–292 (ISSN 1573-0565, DOI 10.1007/BF00992698, lire en ligne, consulté le ).
  10. Hado van Hasselt, « Double Q-learning », Advances in Neural Information Processing Systems, vol. 23,‎ , 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,‎ , p. 2094–2100 (lire en ligne [PDF]).
  12. « Machine Learning : L'apprentissage par renforcement », sur www-igm.univ-mlv.fr (consulté le ).