Ouvrir le menu principal

Apprentissage par renforcement

Sous domaine de l'apprentissage automatique

En intelligence artificielle, plus précisément en apprentissage automatique, l'apprentissage par renforcement consiste, pour un agent autonome (robot, etc.), à apprendre les actions à prendre, à partir d'expériences, de façon à optimiser une récompense quantitative au cours du temps. L'agent est plongé au sein d'un environnement, et prend ses décisions en fonction de son état courant. En retour, l'environnement procure à l'agent une récompense, qui peut être positive ou négative. L'agent cherche, au travers d'expériences itérées, un comportement décisionnel (appelé stratégie ou politique, et qui est une fonction associant à l'état courant l'action à exécuter) optimal, en ce sens qu'il maximise la somme des récompenses au cours du temps.

Historique et lien avec la biologieModifier

Parmi les premiers algorithmes d'apprentissage par renforcement, on compte le Temporal difference learning (TD-learning), proposé par Richard Sutton en 1988[1], et le Q-learning[2] mis au point essentiellement lors d'une thèse soutenue par Chris Watkins en 1989 et publié réellement en 1992[3].

Toutefois, l'origine de l'apprentissage par renforcement est plus ancienne. Elle dérive de formalisations théoriques de méthodes de contrôle optimal, visant à mettre au point un contrôleur permettant de minimiser au cours du temps une mesure donnée du comportement d'un système dynamique. La version discrète et stochastique de ce problème est appelée un processus de décision markovien et fut introduite par Bellman en 1957[4].

D'autre part, la formalisation des problèmes d'apprentissage par renforcement s'est aussi beaucoup inspirée de théories de psychologie animale, comme celles analysant comment un animal peut apprendre par essais-erreurs à s'adapter à son environnement. Ces théories ont beaucoup inspiré le champ scientifique de l'intelligence artificielle et ont beaucoup contribué à l'émergence d'algorithmes d'apprentissage par renforcement au début des années 1980.

En retour, le raffinement actuel des algorithmes d'apprentissage par renforcement inspire les travaux des neurobiologistes et des psychologues pour la compréhension du fonctionnement du cerveau et du comportement animal. En effet, la collaboration entre neurobiologistes et chercheurs en intelligence artificielle a permis de découvrir qu'une partie du cerveau fonctionnait de façon très similaire aux algorithmes d'apprentissage par renforcement tels que le TD-learning[5]. Il semblerait ainsi que la nature ait découvert, au fil de l'évolution, une façon semblable à celles trouvées par des chercheurs pour optimiser la façon dont un agent ou organisme peut apprendre par essais-erreurs. Ou plutôt, les chercheurs en intelligence artificielle ont redécouvert en partie ce que la nature avait mis des millions d'années à mettre en place. En effet, la zone du cerveau qui montre des analogies avec les algorithmes d'apprentissage par renforcement s'appelle les ganglions de la base, dont une sous-partie appelée la substance noire émet un neuromodulateur, la dopamine, qui renforce chimiquement les connexions synaptiques entre les neurones. Ce fonctionnement des ganglions de la base a été identifié comme existant chez l'ensemble des vertébrés[6], et on retrouve le même genre de résultats en imagerie médicale chez l'homme[7].

Enfin, la boucle d'échange scientifique entre neurobiologistes, psychologues et chercheurs en intelligence artificielle n'est pas terminée puisque actuellement, des chercheurs prennent inspiration du cerveau pour raffiner les algorithmes d'apprentissage par renforcement et essayer ainsi de mettre au point des robots plus autonomes et adaptatifs que ceux existants[8]. En effet, même si la nature et les chercheurs semblent avoir trouvé séparément une même solution pour résoudre certains types de problèmes tels que ceux décrits au paragraphe précédent, on se rend bien compte que l'intelligence des robots actuels est encore bien loin de celle de l'homme ou même de celle de nombreux animaux tels que les singes ou les rongeurs. Une voie prometteuse pour pallier cela est d'analyser plus en détail comment le cerveau biologique paramétrise et structure anatomiquement des processus tels que l'apprentissage par renforcement, et comment il intègre ces processus avec d'autres fonctions cognitives telles que la perception, l'orientation spatiale, la planification, la mémoire, et d'autres afin de reproduire cette intégration dans le cerveau artificiel d'un robot[9].

FormalismeModifier

 
Le scenario typique d'apprentissage par renforcement: un agent effectue une action sur l'environnement, cette action est interprétée en une récompense et une représentation du nouvel état, et cette nouvelle représentation est transmise à l'agent.

Formellement, la base du modèle d'apprentissage par renforcement consiste en :

1. un ensemble d'états S de l'agent dans l'environnement ;
2. un ensemble d'actions A que l'agent peut effectuer ;
3. un ensemble de valeurs scalaires "récompenses" R que l'agent peut obtenir.

À chaque pas de temps t de l'algorithme, l'agent perçoit son état   et l'ensemble des actions possibles  . Il choisit une action   et reçoit de l'environnement un nouvel état   et une récompense   (qui est nulle la plupart du temps et vaut classiquement 1 dans certains états clefs de l'environnement). Fondé sur ces interactions, l'algorithme d'apprentissage par renforcement doit permettre à l'agent de développer une politique   qui lui permette de maximiser la quantité de récompenses. Cette dernière s'écrit   dans le cas des processus de décision markoviens (MDP) qui ont un état terminal, et   pour les MDPs sans état terminal (où   est un facteur de dévaluation compris entre 0 et 1 et permettant, selon sa valeur, de prendre en compte les récompenses plus ou moins loin dans le futur pour le choix des actions de l'agent).

Ainsi, la méthode de l'apprentissage par renforcement est particulièrement adaptée aux problèmes nécessitant un compromis entre la quête de récompenses à court terme et celle de récompenses à long terme. Cette méthode a été appliquée avec succès à des problèmes variés, tels que le contrôle robotique[10],[11], le pendule inversé[12], la planification de tâches, les télécommunications, le backgammon[13] et les échecs[14],[15].

AlgorithmeModifier

On donne ici une version algorithmique basique de l'apprentissage par renforcement, particulièrement du TD-learning. Cette version a pour but de permettre au lecteur intéressé de faire une rapide implémentation informatique de l'algorithme afin de mieux comprendre son fonctionnement itératif. On se place ici dans le cas le plus simple où on ne cherche pas à améliorer le comportement (ou politique) de l'agent, mais on cherche à évaluer une politique donnée lorsqu'elle est mise en œuvre par un agent dans un environnement donné.

On initialise V(s) aléatoirement, qui est la valeur que l'agent attribuera à chaque état s.
On initialise la politique π à évaluer.
On répète (pour chaque épisode) :
On initialise s
On répète (à chaque pas de temps de l'épisode) :
a ← action donnée par π pour s
L'agent effectue l'action a; on observe la récompense r et l'état suivant s'
V(s) ← V(s) + α [r + γV(s') - V(s)]
s ← s'
Jusqu'à ce que s soit terminal

Pour plus de détails concernant l'implémentation de cet algorithme, ou concernant la version algorithmique du Q-learning, se référer au livre de Sutton et Barto publié en 1998[16].

ApplicationsModifier

 
Jeux Ataris. Hessel et al. ont montré que l'apprentissage par renforcement donne des programmes meilleurs que les humains.
 
Jeu de go. AlphaGo Zero sont des programmes qui ont appris à jouer grâce à l'apprentissage par renforcement.

L'apprentissage par renforcement est utilisé dans plusieurs applications : robotique, gestion de ressources[17], vol d'hélicoptères[18], chimie[19].

En 2015, Mnih et al.[20] ont montré que l'apprentissage par renforcement permet de créer un programme qui joue à des jeux Atari. En 2018, Hessel et al.[21] ont combiné plusieurs techniques pour améliorer les performances. AlphaGo Zero est une nouvelle technique d'apprentissage par renforcement où l'agent apprend en étant son propre professeur[22].

RéférencesModifier

  1. Sutton, R.S. (1988). Learning to predict by the method of temporal differences. Machine Learning, 3:9-44.
  2. Voir Machine Learning, pp. 373-380
  3. Watkins, C.J.C.H. & Dayan, P. (1992). Q-learning. Machine Learning, 8:279-292.
  4. Bellman, R.E. (1957). A Markov decision process. Journal of Mathematical Mech., 6:679-684.
  5. Houk, J.C., Adams, J.L. & Barto, A.G. (1995). A Model of how the Basal Ganglia generate and Use Neural Signals That Predict Reinforcement. In Houk et al. (Eds), Models of Information Processing in the Basal Ganglia. The MIT Press, Cambridge, MA.
  6. Redgrave, P., Prescott, T.J. & Gurney, K. (1999). The basal ganglia: a vertebrate solution to the selection problem? Neuroscience, 89, 1009-1023.
  7. O’Doherty, J., Dayan, P., Schultz, J., Deichmann, R., Friston, K. & Dolan, R. (2004). Dissociable Roles of Dorsal and Ventral Striatum in Instrumental Conditioning. Science, 304:452-454.
  8. Khamassi, M., Lachèze, L., Girard, B., Berthoz, A. & Guillot, A. (2005). Actor-critic models of reinforcement learning in the basal ganglia: From natural to artificial rats. Adaptive Behavior, Special Issue Towards Artificial Rodents, 13(2):131-148.
  9. Meyer, J.-A., Guillot, A., Girard, B., Khamassi, M., Pirim, P. & Berthoz, A. (2005). The Psikharpax project: Towards building an artificial rat. Robotics and Autonomous Systems, 50(4):211-223.
  10. (en) J. Andrew (Drew) Bagnell et J. Schneider, « Autonomous helicopter control using reinforcement learning policy search methods », ICRA-01,‎
  11. Ng, A and al. (2004). Autonomous helicopter flight via reinforcement learning. In NIPS 16
  12. (en) Donald Michie et Roger A. Chambers, Machine Intelligence 2, North-Holland, Elsevier and Michie D. (Eds.), , « BOXES : An experiment in adaptive control »
  13. (en) Gerry Tesauro, Machine Learning, , partie 8, chap. 3-4 (« Practical issues in temporal difference learning »)
  14. (en) Arthur Samuel, « Some studies in machine learning using the game of checkers », IBM Journal of Research and Development,‎ , p. 210-229
  15. (en) Arthur Samuel, « Some studies in machine learning using the game of checkers II - Recent Progress », IBM Journal of Research and Development,‎ , p. 609-615
  16. Sutton, R.S. & Barto, A.G. (1998). Reinforcement Learning:An Introduction. The MIT Press Cambridge, MA.
  17. Hongzi Mao, Mohammad Alizadeh, Ishai Menache et Srikanth Kandula, « Resource Management with Deep Reinforcement Learning », Proceedings of the 15th ACM Workshop on Hot Topics in Networks, ACM, série HotNets '16,‎ , p. 50–56 (ISBN 978-1-4503-4661-0, DOI 10.1145/3005745.3005750, lire en ligne, consulté le 8 décembre 2019)
  18. Pieter Abbeel, Adam Coates, Morgan Quigley et Andrew Y. Ng, « An Application of Reinforcement Learning to Aerobatic Helicopter Flight », Proceedings of the 19th International Conference on Neural Information Processing Systems, MIT Press, série NIPS'06,‎ , p. 1–8 (lire en ligne, consulté le 8 décembre 2019)
  19. Zhenpeng Zhou, Xiaocheng Li et Richard N. Zare, « Optimizing Chemical Reactions with Deep Reinforcement Learning », ACS Central Science, vol. 3, no 12,‎ , p. 1337–1344 (ISSN 2374-7943, PMID 29296675, PMCID PMC5746857, DOI 10.1021/acscentsci.7b00492, lire en ligne, consulté le 8 décembre 2019)
  20. (en) Volodymyr Mnih, Koray Kavukcuoglu, David Silver et Andrei A. Rusu, « Human-level control through deep reinforcement learning », Nature, vol. 518, no 7540,‎ , p. 529–533 (ISSN 1476-4687, DOI 10.1038/nature14236, lire en ligne, consulté le 8 novembre 2019)
  21. « Hessel », sur www.aaai.org (consulté le 8 novembre 2019)
  22. « AlphaGo Zero: Starting from scratch », sur Deepmind (consulté le 8 novembre 2019)

BibliographieModifier

  • (en) Tom M. Mitchell, Machine Learning, McGraw-Hill International Editions, [détail des éditions], chap. 13 Reinforcement Learning, p. 367-390

Liens externesModifier