Résumé

L’apprentissage par renforcement profond est un domaine de recherche récent mais très actif qui réunit les atouts de l’apprentissage profond (usage de réseaux de neurones) et de l’apprentissage par renforcement (résolution de tâches séquentielles de décision). Dans cette approche, on cherche à développer une politique optimale (un comportement) pour régir un agent actif dans un environnement précis, et on confie aux réseaux de neurones profonds une fonction d’approximation (par exemple, pour la fonction de valeur). Jusqu’ici, on a obtenu des résultats exceptionnels lorsqu’il s’agissait de dépasser les performances humaines dans certaines activités, comme les jeux Atari [11] ou encore le go, avec le désormais célèbre tournoi opposant DeepMind et Lee Sedol [12]. Résultat : une multiplication spectaculaire du nombre d’applications qui exploitent cette technique, en particulier dans le domaine des jeux vidéo et de la robotique. 

Or, à ce jour, la recherche sur l’apprentissage par renforcement profond s’est concentrée sur les environnements comportant un agent unique. Ainsi, dans les jeux Atari, il n’y a qu’un joueur virtuel à commander. Des travaux récents ont toutefois relancé la mise : on explore désormais des approches multiagents, dans des environnements où se déroulent plusieurs apprentissages simultanés. En présence d’agents multiples, tant l’environnement que les agents eux-mêmes deviennent plus dynamiques, ce qui rend la tâche beaucoup plus complexe. 

L’approche multiagent s’est distinguée dans des jeux tels que DOTA 2 [14] ou Quake III Arena en mode Capture the flag (conquête du drapeau) [21], où de nombreux agents apprennent simultanément à combattre ou à coopérer dans un même environnement. Mais il reste de nombreux défis à relever. Cet article vise (i) à présenter clairement les tendances actuelles en matière d’apprentissage multiagent par renforcement profond, et (ii) à montrer, par des exemples et les leçons qu’on a pu en tirer, comment on peut allier des méthodes et algorithmes d’apprentissage par renforcement profond et d’apprentissage multiagent pour résoudre les problèmes de ce nouveau domaine de recherche.

De l’apprentissage multiagent à l’apprentissage multiagent par renforcement profond

Il y a près de 20 ans, les travaux fondateurs de Stone et Veloso ont dégagé des exemples très intuitifs et pratiques [1] qui ont contribué à définir le cadre des systèmes multiagents et les problèmes à résoudre dans le contexte de l’apprentissage machine :

Les chercheurs en IA en sont arrivés au stade où ils peuvent examiner comment des agents autonomes multiples interagiront dans le monde réel. En fait, une telle étude est même devenue incontournable. On prévoit l’avènement de la voiture autonome; il faut donc envisager qu’il y en aura plus qu’une en action. Et même si chaque véhicule parvient à se conduire tout seul, il faudra déterminer, sur l’autoroute, comment leurs comportements s’influenceront mutuellement.

Quelque dix ans plus tard, Shoham, Powers et Grenager [2] ont souligné le nombre croissant de publications sur l’apprentissage des systèmes multiagents, déclarant qu’il n’était déjà plus possible de recenser tous les articles pertinents. Dans la décennie qui a suivi, les articles sur l’apprentissage multiagents ont continué de se multiplier, considérant la discipline sous tous les angles, des rouages fondamentaux aux principales difficultés rencontrées [3], en passant par toute une série de sous-questions (comme les réglages coopératifs ou la dynamique évolutive de l’apprentissage multiagent) [4-10].

Ces recherches ont abouti à un certain nombre de réussites, d’abord dans les jeux Atari à un seul joueur [11], puis plus récemment dans les jeux à deux agents [12-13], comme le go, le poker et les compétitions entre deux équipes.

L’apprentissage par renforcement profond [15] est au cœur de ces travaux et s’est associé à d’autres techniques d’IA, telles que la recherche arborescente Monte-Carlo, la planification et, tout récemment, les systèmes multiagents. C’est ainsi qu’est apparu l’apprentissage multiagent par renforcement profond. 

L’apprentissage dans un contexte multiagent est d’une nature plus complexe, soulevant de nouveaux problèmes [3-10] tels que :

•    La non-stationnarité : si tous les agents apprennent simultanément, la dynamique se complexifie et échappe à de nombreuses hypothèses admises en apprentissage par renforcement.

•    La malédiction de la dimensionnalité : la croissance de l’espace état-action devient exponentielle quand un agent tient compte de toutes les actions menées par ses pairs.

•    La répartition du mérite entre plusieurs agents : il s’agit de déterminer comment les agents estiment leur contribution lorsqu’ils sont constitués en équipes; par exemple, si une récompense est accordée à une équipe alors que le gros du travail repose sur un agent en particulier, ses pairs peuvent devenir « indolents » – exactement comme dans la vie!

En dépit de ces facteurs complexes, dans tous les congrès majeurs sur l’intelligence artificielle (AAAI, AAMAS, ICLR, IJCAI, NIPS, etc.), on a présenté des réussites de l’apprentissage multiagent par renforcement profond. La place réservée à cette approche par les grands congrès nous a convaincus de la pertinence de proposer une revue des travaux récents dans le domaine, et une analyse de leur relation avec les travaux antérieurs.

Pour ce faire, nous avons établi quatre catégories essentielles, illustrées ci-dessous. 

Catégorisation des travaux sur l’apprentissage multiagent par renforcement profond. (a) Analyse des comportements émergents : évaluation des algorithmes d’apprentissage par renforcement profond dans les scénarios multiagents. (b) Apprentissage de la communication : les agents apprennent par leurs actions et l’échange de messages. (c) Apprentissage de la coopération : les agents apprennent à coopérer à partir des actions et des observations locales, exclusivement. (d) Agents modélisant d’autres agents : les agents accomplissent leurs tâches en fonction du comportement des autres agents (coopération ou compétition).

(i) Analyse des comportements émergents:

 

(ii) Apprentissage de la coopération

 

(iii) Apprentissage de la communication

 

(iv) Agents modélisant d’autres agents

 

Réunir les forces de l’apprentissage multiagent et de l’apprentissage par renforcement profond

Notre article fournit aussi des orientations en exposant les méthodes et les algorithmes issus de l’apprentissage par renforcement profond et de l’apprentissage multiagent qui peuvent se compléter pour résoudre les problèmes soulevés par l’apprentissage multiagent par renforcement profond. Cette solution s’impose, par exemple, dans : 

•    Le problème de la non-stationnarité.

•    Le problème de la répartition du mérite entre plusieurs agents.

Nous présentons aussi des leçons générales tirées de ces travaux, notamment à l’égard des éléments suivants :

•    Mémoire de reprise de l’expérience en apprentissage multiagent par renforcement profond – une composante clé de nombreux travaux sur l’apprentissage par renforcement profond. Ces conteneurs constituent une forme de mémoire explicite qui stocke les interactions permettant aux agents d’améliorer leurs comportements.

•    Réseaux de neurones récurrents (p. ex. réseaux récurrents à mémoire court et long terme). Ces réseaux servent de mémoire implicite améliorant les performances, notamment dans les environnements partiellement observables.

•    Apprentissage centralisé avec exécution décentralisée. Les agents sont entraînés par un contrôleur central qui accède à la fois à leurs actions et à leurs observations, mais à l’étape du déploiement, ils n’accèdent qu’aux observations.

•    Partage de paramètres. Pour de nombreuses tâches, il s’avère utile de partager les couches internes d’un réseau, même en présence de nombreuses sorties.

Dans la dernière partie de l’article, nous réfléchissons à certains enjeux et défis qui restent ouverts :

•    En ce qui concerne les récompenses rares et différées

Les concours et environnements récents de systèmes d’apprentissage multiagent (p. ex. Pommerman [24], Capture the flag [21], MarLÖ, Starcraft II et Dota 2) proposent des scénarios complexes, où de nombreuses actions doivent être effectuées avant qu’un signal de récompense devienne disponible. Cette difficulté existe d’emblée dans l’apprentissage par renforcement [16]; dans l’apprentissage multiagent par renforcement profond, le problème s’accentue, car les agents doivent apprendre non seulement des comportements de base (comme en apprentissage par renforcement profond), mais aussi un volet stratégique (compétitif ou collaboratif) incorporé dans la configuration multiagent. 

•    En ce qui concerne la partie contre soi-même.

La partie contre soi-même (tous les agents utilisent le même algorithme d’apprentissage) est une clé qui permet à l’apprentissage multiagent d’atteindre des performances impressionnantes [17-19]. Malgré les résultats significatifs obtenus également par l’apprentissage multiagent par renforcement profond, les travaux récents ont démontré qu’une partie contre soi-même ordinaire n’est pas l’approche la plus productive [20, 21]. 

•    En ce qui concerne la nature combinatoire de l’apprentissage multiagent par renforcement profond.

La recherche arborescente Monte-Carlo a permis des avancées majeures pour AlphaGo et AlphaGo Zero, qui utilisent tous deux cette technique conjointement avec l’apprentissage par renforcement profond. Cependant, dans les scénarios multiagents, il faut aussi gérer la croissance exponentielle des espaces d’actions pour l’ensemble des agents, lorsqu’on tient compte des méthodes centralisées. En empruntant la voie des planificateurs plus évolutifs [22, 23], on ouvre un nouvel axe qui combine les planificateurs fondés sur la recherche arborescente Monte-Carlo avec des techniques d’apprentissage par renforcement profond dans les scénarios multiagents. 

Conclusion

Bien qu’il existe plusieurs publications intéressantes relatives à l’apprentissage par renforcement profond et à l’apprentissage multiagent par renforcement profond qui exposent des avancées importantes en IA, nous constatons que les techniques à agent unique et à agents multiples exigent encore énormément de recherche. Notre article vise à inciter les chercheurs à s’appuyer sur l’abondante littérature existante dans ces deux domaines (apprentissage par renforcement profond et apprentissage multiagent) et à unir leurs efforts pour améliorer l’efficacité de la recherche sous le thème des agents multiples.

Article complet : https://arxiv.org/abs/1810.05587

Références

[1] P. Stone, M. M. Veloso, Multiagent Systems - A Survey from a Machine Learning Perspective., Autonomous Robots 8 (2000) 345–383.
[2] Y. Shoham, R. Powers, T. Grenager, If multi-agent learning is the answer, what is the question?, Artificial Intelligence 171 (2007) 365–377. 
[3] K. Tuyls, G. Weiss, Multiagent learning: Basics, challenges, and prospects, AI Magazine 33 (2012) 41–52. 
[4] L. Busoniu, R. Babuska, B. De Schutter, A Comprehensive Survey of Multiagent Reinforcement Learning, IEEE Transactions on Systems, Man and Cybernetics, Part C (Applications and Reviews) 38 (2008) 156–172. 
[5] A. Nowé, P. Vrancx, Y.-M. De Hauwere, Game theory and multi-agent reinforcement learning, in: Reinforcement Learning, Springer, 2012, pp. 441–470. 
[6] L. Panait, S. Luke, Cooperative Multi-Agent Learning: The State of the Art, Autonomous Agents and Multi-Agent Systems 11 (2005).
[7] L. Matignon, G. J. Laurent, N. Le Fort-Piat, Independent reinforcement learners in cooperative Markov games: a survey regarding coordination problems, Knowledge Engineering Review 27 (2012) 1–31. 
[8] D. Bloembergen, K. Tuyls, D. Hennes, M. Kaisers, Evolutionary Dynamics of Multi-Agent Learning: A Survey., Journal of Artificial Intelligence Research 53 (2015) 659–697. 
[9] P. Hernandez-Leal, M. Kaisers, T. Baarslag, E. Munoz de Cote, A Survey of Learning in Multiagent Environments - Dealing with Non-Stationarity (2017). arXiv:1707.09183.
[10] S. V. Albrecht, P. Stone, Autonomous agents modelling other agents: A comprehensive survey and open problems, Artificial Intelligence 258 (2018) 66–95. 
[11] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, S. Petersen, C. Beattie, A. Sadik, I. Antonoglou, H. King, D. Kumaran, D. Wierstra, S. Legg, D. Hassabis, Human-level control through deep reinforcement learning, Nature 518 (2015) 529–533. 
[12] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. van den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbrenner, I. Sutskever, T. Lillicrap, M. Leach, K. Kavukcuoglu, T. Graepel, D. Hassabis, Mastering the game of Go with deep neural networks and tree search, Nature 529 (2016) 484–489. 
[13] M. Moravčík, M. Schmid, N. Burch, V. Lisý, D. Morrill, N. Bard, T. Davis, K. Waugh, M. Johanson, M. Bowling, DeepStack: Expert-level artificial intelligence in heads-up no-limit poker, Science 356 (2017) 508–513. 
[14] Open AI Five, https://blog.openai.com/openai-five, 2018. [Accès en ligne le 7 septembre 2018]. 
[15] K. Arulkumaran, M. P. Deisenroth, M. Brundage, A. A. Bharath, A Brief Survey of Deep Reinforcement Learning (2017). arXiv:1708.05866v2.
[16] R. S. Sutton, A. G. Barto, Introduction to reinforcement learning, volume 135, MIT press Cambridge, 1998.
[17] J. Hu, M. P. Wellman, Nash Q-learning for general-sum stochastic games, Journal of Machine Learning Research 4 (2003) 1039–1069. 
[18] M. Bowling, Convergence and no-regret in multiagent learning, in: Advances in Neural Information Processing Systems, Vancouver, Canada, 2004, pp. 209–216. 
[19] J. Heinrich, D. Silver, Deep Reinforcement Learning from Self-Play in Imperfect-Information Games (2016). arXiv:1603.01121
[20] T. Bansal, J. Pachocki, S. Sidor, I. Sutskever, I. Mordatch, Emergent Complexity via Multi-Agent Competition., in: International Conference on Machine Learning, 2018.
[21] M. Jaderberg, W. M. Czarnecki, I. Dunning, L. Marris, G. Lever, A. G. Castañeda, C. Beattie, N. C. Rabinowitz, A. S. Morcos, A. Ruderman, N. Sonnerat, T. Green, L. Deason, J. Z. Leibo, D. Silver, D. Hassabis, K. Kavukcuoglu, T. Graepel, Human-level performance in first-person multiplayer games with population based deep reinforcement learning (2018).
[22] C. Amato, F. A. Oliehoek, et al., Scalable planning and learning for multiagent POMDPs., in: AAAI, 2015, pp. 1995–2002. 
[23] G. Best, O. M. Cliff, T. Patten, R. R. Mettu, R. Fitch, Dec-MCTS: Decentralized planning for multi-robot active perception, The International Journal of Robotics Research (2018)
[24] Resnick, C., Eldridge, W., Ha, D., Britz, D., Foerster, J., Togelius, J., Cho, K. and Bruna, J., 2018. Pommerman: A Multi-Agent Playground. arXiv preprint arXiv:1809.07124..