Q-learning

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
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.

En intelligence artificielle, plus précisément en apprentissage automatique, le Q-learning est une technique d'apprentissage par renforcement. Cette technique 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].

Description[modifier | modifier le code]

Cette méthode d'apprentissage peut être appliquée pour trouver une suite d'actions associées à des états (politique) d'un processus de décision markovien (fini) quelconque. Cela fonctionne par l'apprentissage d'une fonction de valeur d'état qui permet de déterminer le potentiel bienfait (récompense) de prendre une certaine action dans un certain état en suivant une politique optimale.

La politique est la règle de sélection des actions successives d'un agent dans l'état actuel du système. Lorsque cette fonction de valeur d'action-état est connue, la politique optimale peut être construite en sélectionnant l'action à valeur maximale pour chaque état. Un des points forts du -learning est qu'il permet de comparer les récompenses probables de prendre les actions accessibles sans avoir de connaissance initiale de l’environnement. 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]. Par la suite, il a été prouvé, que -learning converge vers une politique optimale, à comprendre dans le sens de maximiser la récompense totale des étapes successives[4].

Algorithme[modifier | modifier le code]

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. L'exécution d'une action dans un état spécifique fournit à l'agent une récompense (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 une 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 entre 0 et 1 (autrement dit ) appelé le facteur d'actualisation.

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

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). Ainsi, est mis à jour. Le cœur de l'algorithme est une mise à jour de la fonction de valeur. La définition de la fonction de valeur est corrigée à chaque étape de la façon suivante[5] :

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.

Un épisode de l'algorithme finit lorsque est un état final. Toutefois, le -learning peut aussi apprendre dans une tâche non épisodique. 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.

Influence des variables sur l'algorithme[modifier | modifier le code]

Facteur d'apprentissage[modifier | modifier le code]

Le facteur d'apprentissage détermine à quel point la nouvelle information calculée surpassera l'ancienne. Un facteur de 0 ne ferait rien apprendre à l'agent en question, alors qu'un facteur de 1 ne ferait considérer à l'agent 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[6].

Facteur d'actualisation[modifier | modifier le code]

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

Extensions et variantes[modifier | modifier le code]

Double Q-learning[modifier | modifier le code]

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. C'est pourquoi une variante appelée Double Q-learning a été proposée[8]. En pratique, il y a deux fonctions d'évaluation et qui utilise un ensemble d'expériences différentes. La mise à jour s'effectue comme suit :

, and

Maintenant, la valeur estimée est évaluée en utilisant une autre politique, ce qui résout le problème de la surestimation. L'algorithme a ensemble été combiné avec de l'apprentissage profond, comme dans l'algorithme DQN, et donne le Double DQN qui est meilleur que l'algorithme DQN original[9].

Notes et références[modifier | modifier le code]

  1. Tambet Matiisen, « Demystifying Deep Reinforcement Learning | Computational Neuroscience Lab », sur neuro.cs.ut.ee, (consulté le 6 avril 2018)
  2. C. J. Watkins, Learning from delayed rewards, Kings College, Cambridge, mai 1989
  3. (en) George F Luger, Artificial intelligence: Structures and strategies for complex problem solving. 5e édition., Addison Wesley, (ISBN 0 321 26318 9), p. 448
  4. Watkins et Dayan, Q-learning.Machine Learning, 1992
  5. (en) David L. Poole et Alan K. Mackworth, Artificial Intelligence, Cambridge University Press, (ISBN 9780511794797, DOI 10.1017/CBO9780511794797, lire en ligne), p. 469
  6. Reinforcement Learning: An Introduction, Richard Sutton et Andrew Barto, MIT Press, 1998.
  7. (en) Stuart J. Russell et Peter Norvig, Artificial Intelligence: A Modern Approach, Prentice Hall, (ISBN 978-0136042594), p. 649
  8. Hado van Hasselt, « Double Q-learning », Advances in Neural Information Processing Systems, vol. 23,‎ , p. 2613–2622 (lire en ligne [PDF])
  9. 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])