L’équipe Borealis AI (de gauche à droite): Matt Taylor, Chao Gao, Pablo Hernandez-Leal et Bilal Kartal.

L’environnement Pommerman [1] est basé sur le jeu classique Bomberman sur console Nintendo. Il a été mis sur pied par un groupe de chercheurs en apprentissage machine afin d’explorer l’apprentissage multiagent et de repousser les limites de la technologie par des jeux de compétition fondés sur l’apprentissage par renforcement.

La compétition par équipe a eu lieu le 8 décembre 2018 pendant le congrès NeurIPS à Montréal. Elle regroupait 25 participants de partout dans le monde. L’équipe de Borealis AI, formée des chercheurs d’Edmonton Chao Gao, Pablo Hernandez-Leal et Bilal Kartal, ainsi que du directeur de recherche Matt Taylor, a remporté la deuxième place dans la catégorie des agents d’apprentissage et la cinquième place au classement général, qui comprend les agents heuristiques (sans apprentissage). En guise de récompense, nous avons rapporté à la maison un superbe processeur graphique NVIDIA Titan V édition CEO. Voici comment nous avons accompli nos exploits.

1. Règles d’engagement

La compétition Pommerman regroupe quatre agents de bombardement placés aux coins d’une planche de jeu symétrique de 11 x 11. Le jeu oppose deux équipes de deux agents.

Les règles sont les suivantes: 

  • À chaque pas de temps, chaque agent peut effectuer l’une des six actions suivantes: se déplacer vers l’un ou l’autre des quatre points cardinaux, rester sur place ou poser une bombe. 

  • Chaque cellule de la planche de jeu peut être utilisée comme un passage (l’agent peut la franchir), un mur rigide (elle ne peut pas être détruite) ou une planche de bois (elle peut être détruite avec une bombe). 

  • Le jeu effectue le mappage des fonctions générées de façon aléatoire aux échelons individuels. Il existe toujours un chemin possible entre les agents, de sorte que les mappages générés par les procédures peuvent toujours être exploités durant la partie.

  • Quand un agent pose une bombe, celle-ci explose après 10 pas de temps et produit des flammes qui durent pendant deux pas de temps. Les flammes détruisent le bois et tuent les agents qui se trouvent dans le rayon d’action des bombes quand elles explosent. Quand une paroi de bois est détruite, les débris révèlent un passage ou un pouvoir additionnel (voir ci-dessous). 

  • Les pouvoirs additionnels augmentent les capacités des joueurs au cours d’une partie et peuvent prendre trois formes: i) augmentation du rayon d’action des bombes; ii) augmentation du nombre de bombes qu’un joueur peut poser; iii) capacité pour un joueur de botter des bombes. 

  • Chaque partie dure 800 pas de temps. Une partie peut prendre fin de deux façons: une équipe gagne la partie avant la fin de la période de jeu, ou la partie est déclarée nulle après 800 pas de temps.

 

Exemple de partie du jeu en équipe Pommerman.

2. Défis

La compétition Pommerman est un niveau de référence très exigeant pour les méthodes d’apprentissage par renforcement. Voici pourquoi:

  • Récompenses peu nombreuses et différées: Les agents ne reçoivent aucune récompense avant la fin de la partie, qui peut durer jusqu’à 800 pas de temps. La récompense individuelle est de +1 ou -1. Si les deux agents meurent durant le même pas de temps, chacun obtient la cote -1, ce qui accroît le niveau de difficulté du problème d’attribution de crédits temporels [2]. Le problème d’attribution de crédits concerne la reconnaissance des actions atomiques par des récompenses rares et différées. 
  • Récompenses erronées: Les récompenses peuvent être erronées en raison des suicides potentiels. Prenons un scénario simplifié où deux agents seulement s’affrontent : notre agent d’apprentissage et un adversaire. Nous considérons qu’un faux positif survient lorsque notre agent obtient une récompense de +1 à la suite du suicide de l’adversaire (et non parce qu’il a neutralisé son adversaire grâce à ses aptitudes au combat), et qu’un faux négatif survient quand notre agent obtient une récompense de -1 en raison de son propre suicide. Les épisodes de faux négatif constituent un important goulot d’étranglement pour l’apprentissage de comportements raisonnables avec exploration pure dans l’apprentissage par renforcement sans modèle. En outre, les épisodes de faux positif peuvent récompenser les agents pour des politiques arbitraires (passives), comme le fait de « camper » plutôt que de chercher activement l’affrontement avec l’adversaire. 

Exemple de planche remplie avec quatre agents.

Exemples de vues partielles pour chaque agent.

  • Observabilité partielle: Les agents ne peuvent voir que leur voisinage immédiat. Cela soulève plusieurs problèmes. Par exemple, un agent peut mourir sans même avoir aperçu la bombe si le rayon d’action de cette dernière est supérieur au champ de vision de l’agent. Un autre problème se présente lorsqu’une bombe est bottée par un agent. La bombe devient alors un projectile qui, combiné à la chaîne d’explosions, confère un caractère très stochastique à l’environnement.  
  • Vaste espace de recherche: Étant donné les six actions possibles pour chacun des quatre agents et la capacité de jeu simultané, le nombre d’actions possibles dans l’espace de recherche conjoint atteint 1 296 opérations. Comme une partie de Pommerman peut durer jusqu’à 800 pas de temps, on peut évaluer le niveau de complexité de l’espace de recherche à (1 296)^800 ≈ 10^2 400, c’est-à-dire beaucoup plus grand que dans le jeu de Go.
  • Absence de simulateur d’avance rapide: La compétition exige de prendre des décisions en temps quasi réel, c’est-à-dire en moins de 100 ms par action. Cependant, le module de simulation en aval est plutôt lent. Par conséquent, les algorithmes de recherche standards sont inefficaces. Il faut alors modifier les algorithmes standards, comme dans le cas de l’agent de recherche hybride [3] qui a remporté la première compétition. On pourrait citer également l’agent de recherche en arborescence Monte Carlo personnalisé (non inscrit à la compétition) utilisé dans notre autre recherche en cours, qui sera présentée durant l’atelier sur les jeux d’apprentissage par renforcement du congrès de l’AAAI de 2019, en janvier [4]. 
  • Difficulté d’apprendre à poser une bombe: Comme ils doivent poser des bombes afin d’éliminer leurs adversaires, les agents doivent absolument acquérir cette compétence pour remporter le jeu. Cependant, un agent se tue souvent lui-même pendant son exploration. Il peut ainsi apprendre à ne pas poser de bombe du tout et à se comporter en poltron [1]. Les agents doivent acquérir un large éventail de compétences applicables à des planches de jeu et des adversaires randomisés. 

 

Aux premières étapes de son apprentissage, un agent se suicide plusieurs fois.

 

Après un certain apprentissage, l’agent sait comment poser des bombes près de ses adversaires et se mettre ensuite à l’abri de l’explosion.


  • Défis multiagents [5]: Chaque équipe inscrite à la compétition compte deux agents. L’un des problèmes qui surviennent dans cet environnement est la coordination des actions des deux agents, qui n’ont pas le droit de partager le même contrôleur. Un deuxième problème est lié à la nature de l’environnement: les membres de l’équipe ne disposent d’aucun renseignement sur les agents qu’ils sont sur le point d’affronter. Un troisième défi a trait à l’attribution des crédits multiagents: dans cet environnement d’équipe, les deux agents de l’équipe reçoivent la même récompense pour chaque partie. Aucune information n’est disponible sur la contribution particulière de chacun des agents.
  • Défi de généralisation des adversaires: Le simulateur Pommerman comprend un agent contrôlé par script (fondé sur des règles) appelé SimpleAgent et qui peut être utilisé comme adversaire pour entraîner les agents de l’équipe. SimpleAgent récolte des pouvoirs additionnels en cours de partie et pose des bombes lorsqu’il se trouve près d’un adversaire. Il est relativement habile à éviter le souffle des bombes qui explosent et applique l’algorithme de Dijkstra à chaque pas de temps. Le comportement de SimpleAgent est stochastique et peut changer selon les pouvoirs additionnels qu’il récolte. Par exemple, si l’agent a recueilli plusieurs munitions, il peut poser trop de bombes et déclencher des explosions en chaîne, ou encore se suicider plus fréquemment. Dans le cadre d’une expérience préliminaire, nous avons entraîné des agents d’apprentissage par renforcement avec SimpleAgent. Nos agents entraînés ont appris à gagner la partie en exploitant les vulnérabilités de leurs adversaires.

 

Notre agent d’apprentissage (en blanc) est très fort contre SimpleAgent. Il sait éviter les explosions et a même appris à mener SimpleAgent à se suicider afin de gagner la partie sans poser de bombe.

Lorsque nous avons examiné le comportement de notre agent vis-à-vis de SimpleAgent, nous avons découvert qu’il avait appris à le forcer à se suicider. Cela a commencé quand SimpleAgent a d’abord posé une bombe puis s’est déplacé vers la cellule adjacente X. Notre agent, après avoir observé ce comportement de son adversaire, a décidé de se rendre simultanément à la cellule X. Suivant le fonctionnement du modèle aval du moteur du jeu, les deux agents ont alors été retournés à leur emplacement d’origine au pas de temps suivant. En d’autres termes, notre agent a découvert une faille dans le comportement de SimpleAgent et appris à l’exploiter afin de gagner la partie en forçant son adversaire à se suicider. La méthode se répétait jusqu’à ce que la bombe explose et supprime SimpleAgent. Cette politique est optimale contre SimpleAgent, mais elle ne peut pas être généralisée aux autres adversaires, car ces agents ont appris à cesser de poser des bombes et à agir comme des cibles faciles à exploiter.  

Remarque: La généralisation des politiques relatives aux adversaires est extrêmement importante pour le traitement des environnements multiagents dynamiques. Des problèmes semblables ont été observés dans Laser Tag [6]. 

Dans les tâches ne mettant en jeu qu’un seul agent, on a aussi observé des comportements défaillants (et étranges) [7]. Un agent d’apprentissage par renforcement entraîné pour CoastRunners a découvert une étape du jeu où, en raison d’un défaut d’appariement entre la récompense maximale possible et le comportement voulu, il pouvait obtenir des pointages plus élevés, au lieu de finir la partie. 

3. Notre équipe Skynet

Une équipe Skynet est composée d’un réseau neuronal unique et repose sur cinq modules de base: 

  1. Partage de paramètres [10] 
  2. Modelage de récompenses [12] 
  3. Filtre d’actions
  4. Apprentissage de curriculum d’adversaire [14]
  5. Algorithme efficace d’apprentissage par renforcement [13]

Nous utilisons le mécanisme de partage de paramètres, c’est-à-dire que nous autorisons les agents à partager les paramètres d’un seul réseau. Cela permet d’entraîner le réseau à partir de l’expérience des deux agents. Les agents peuvent tout de même adopter des comportements différents, car chaque agent fait des observations différentes. 

Nous avons ajouté des récompenses denses afin d’améliorer le rendement des agents sur le plan de l’apprentissage. Nous nous sommes inspirés du mécanisme de récompenses différentielles dans le but de fournir aux agents une contribution plus importante pour leurs comportements, par opposition à l’attribution d’une récompense globale unique.

Notre troisième module, le filtre d’actions, est construit de manière à fournir à l’agent des connaissances préalables, qui lui indiquent ce qu’il ne doit pas faire, puis à lui permettre de découvrir ce qu’il doit faire par essais et erreurs (c’est-à-dire en suivant un processus d’apprentissage). Cette approche comporte deux avantages: 1) elle simplifie le problème de l’apprentissage; 2) elle permet à l’agent d’acquérir parfaitement les compétences superficielles, comme l’évitement des flammes ou la fuite pour s’éloigner des bombes dans des cas simples. 

Il est utile de mentionner que le filtre d’actions mentionné ci-dessus est extrêmement rapide et ne ralentit pas tellement l’apprentissage par renforcement. Combinée à l’évaluation du réseau neuronal, l’exécution de chaque action n’exige que quelques millisecondes de plus, une vitesse presque égale à l’inférence aval pure dans un réseau neuronal. Rappelons que le délai maximal d’exécution de chaque action pendant la compétition est de 100 ms. 

Le réseau neuronal est entraîné par $\mathit{PPO}$ qui minimise l’objectif suivant: 

\begin{equation}
\begin{split}
    o(\theta;\mathcal{D}) & = \sum_{(s_t, a_t, R_t) \in \mathcal{D}} \Bigg[ -\mathit{clip}(\frac{\pi_\theta(a_t|s_t)}{\pi_\theta^{old}(a_t|s_t)}, 1-\epsilon, 1+\epsilon) A(s_t, a_t) + \\ 
    & \frac{\alpha}{2} \max\Big[ (v_\theta(s_t) -R_t)^2, (v_\theta^{old}(s_t) + \mathit{clip}(v_\theta(s_t) - v_\theta^{old}(s_t), -\epsilon, \epsilon)-R_t)^2 \Big] \Bigg], 
\end{split}
\end{equation}

où $\theta$ est le réseau neuronal, $\mathcal{D}$ fait l’objet d’un échantillonnage par $\pi_\theta^{old}$, $\epsilon$ est un paramètre de mise au point. Reportez-vous à l’article sur l’optimisation de la politique proximale (PPO) pour plus de détails. 

Notre équipe a lutté contre un ensemble d’adversaires de curriculum:   

  • Équipes d’adversaires immobiles: les adversaires ne changent pas de position et ne posent pas de bombe.    
  • Répartition intelligente aléatoire sans bombes: les adversaires ne posent pas de bombe, mais ils suivent une « répartition intelligente aléatoire », c’est-à-dire qu’ils utilisent le filtre d’actions décrit ci-dessus.

Nous avons permis aux adversaires de ne pas poser de bombe parce que nous avons constaté que le réseau neuronal pouvait alors se concentrer sur l’acquisition de véritables compétences de pose de bombes, et non sur une compétence exclusivement fondée sur le comportement suicidaire des adversaires. En outre, cette stratégie évite l’entraînement à partir de signaux de récompense liés à de « faux positifs » causés par le suicide involontaire de l’adversaire.

Comme le montre le schéma ci-dessous, l’architecture répète d’abord quatre couches de convolution, suivies de deux instances relatives aux politiques et aux valeurs, respectivement.

Au lieu de recourir à un module LSTM pour suivre l’historique d’observations, nous avons utilisé un « tableau rétrospectif » pour suivre la valeur la plus récente de chaque case de la planche de jeu. Dans le cas des cases hors de la portée d’un agent, le moteur remplissant le « tableau rétrospectif » remplace les éléments non observés de la planche par les derniers éléments observés. La fonction d’entrée compte au total 14 plans. Les 10 premiers plans sont extraits des observations courantes des agents, tandis que les quatre plans restants proviennent du « tableau rétrospectif ». 

 

Exemple d’une partie entre l’équipe Skynet (rouge) et une équipe composée de deux agents SimpleAgent (bleu).

4. Compétition

La compétition par équipe Pommerman était fondée sur une procédure à double élimination. Les trois agents qui ont obtenu les meilleurs résultats ont utilisé des méthodes de recherche en arborescence, c’est-à-dire qu’ils ont activement utilisé le modèle d’analyse en aval afin de vérifier à l’avance l’effet de chaque décision en appliquant des méthodes heuristiques. Durant la compétition, ces agents semblaient botter plus souvent les bombes, ce qui augmentait leurs chances de survie.

Comme mentionné dans l’introduction, notre équipe Skynet a remporté la deuxième place dans la catégorie des agents d’apprentissage et la cinquième au classement général, qui comprend les agents heuristiques (sans apprentissage). Il importe de noter que les agents fondés sur des scripts ne figuraient pas parmi les meilleurs joueurs durant cette compétition, qui a fait ressortir la grande qualité des méthodes de recherche en arborescence et d’apprentissage. 

Une autre des équipes que nous avions inscrites, CautiousTeam, était constituée d’agents SimpleAgent et, fait intéressant, s’est hissée à la septième position du classement général. Nous avions inscrit l’équipe CautiousTeamprincipalement pour vérifier qu’un agent SimpleAgent qui ne pose pas de bombe pourrait obtenir des résultats comparables (ou même meilleurs) que le gagnant [3] de la première compétition disputée en juin, soit un scénario sans règles entièrement observable. Les résultats obtenus lors de la compétition semblent confirmer notre intuition. 

5. Leçons apprises et suite des travaux

En plus de constituer un environnement intéressant et (surtout) amusant, le simulateur Pommerman a été conçu comme modèle de référence pour l’apprentissage multiagent. Nous étudions actuellement des méthodes d’apprentissage multiagent par renforcement profond [5] en utilisant l’environnement Pommerman comme banc d’essai.

  • L’une des avenues que nous explorons est de combiner des agents de recherche et des agents d’apprentissage dans un cadre d’apprentissage par imitation. Par exemple, des algorithmes de planification peuvent fournir en continu des trajectoires expertes que les agents d’apprentissage par renforcement peuvent imiter afin d’accélérer leur apprentissage [4]. Nous avons mentionné précédemment que les méthodes de recherche ordinaires sont trop lentes pour être déployées dans un environnement de jeu en temps réel; elles peuvent tout de même être mises à profit durant l’entraînement, particulièrement dans les méthodes d’apprentissage par renforcement distribué.
  • Une autre avenue que nous envisageons d’explorer est d’utiliser l’inférence bayésienne pour détecter les adversaires. Nous avons donné une présentation à ce sujet lors de l’atelier sur l’utilisation de LatinX en IA (LatinX in AI) du congrès NeurIPS 2018 [8]. Le principe consiste à réutiliser des politiques (compétences) de façon intelligente en identifiant rapidement l’adversaire que l’on affronte.
  • Enfin, la compétition nous a permis de constater que le problème de la coopération dans le jeu Pommerman n’est toujours pas résolu. Nous étudions des méthodes d’apprentissage multiagent profond qui pourraient permettre aux agents de coopérer plus efficacement pour exécuter les tâches.

Remerciements

Nous désirons remercier les créateurs du banc d’essai Pommerman, les organisateurs de la compétition et la communauté Pommerman toujours plus nombreuse sur Discord. Nous serons heureux de prendre part à d’autres compétitions à l’avenir.

Références

[1] Cinjon Resnick, Wes Eldridge, David Ha, Denny Britz, Jakob Foerster, Julian Togelius, Kyunghyun Cho et Joan Bruna, « Pommerman: A multiagent playground », prépublication arXiv, arXiv:1809.07124, 2018.

[2] Richard S. Sutton et Andrew G. Barto, Reinforcement learning: An introduction, MIT Press, 2018.

[3] Zhou Hongwei et coll., « A hybrid search agent in Pommerman », actes de la 13e International Conference on the Foundations of Digital Games, ACM, 2018.

[4] Bilal Kartal, Pablo Hernandez-Leal et Matthew E. Taylor, « Using Monte Carlo Tree Search as a Demonstrator within Asynchronous Deep RL », prépublication arXiv, arXiv:1812.00045(2018).

[5] Pablo Hernandez-Leal, Bilal Kartal et Matthew E Taylor, « Is multiagent deep reinforcement learning the answer or the question? A brief survey », prépublication arXiv, arXiv:1810.05587, 2018.

[6] Marc Lanctot et coll., « A unified game-theoretic approach to multiagent reinforcement learning », Advances in Neural Information Processing Systems, 2017.

[7] Open AI, « Faulty Reward Functions in the Wild », https://blog.openai.com/faulty-reward-functions/.

[8] Pablo Hernandez-Leal, Bilal Kartal et Matthew E. Taylor, « Skill Reuse in Partially Observable Multiagent Environments », atelier « LatinX in AI » du congrès NeurIPS 2018.

[9] Yann LeCun, Yoshua Bengio et Geoffrey Hinton, « Deep learning », Nature, vol. 521, 2015, p. 436-444.

[10] J. N. Foerster, Y. M. Assael, N. De Freitas et S. Whiteson, « Learning to communicate with deep multi-agent reinforcement learning », Advances in Neural Information Processing Systems, 2016.

[11] J. N. Foerster, N. Nardelli, G. Farquhar, T. Afouras, P. H. S. Torr, P. Kohli et S. Whiteson, « Stabilising Experience Replay for Deep Multi-Agent Reinforcement Learning », actes de l’International Conference on Machine Learning, 2017.

[12] Sam Devlin et coll., « Potential-based difference rewards for multiagent reinforcement learning », actes de l’International Conference on Autonomous Agents and Multi-Agent Systems, 2014.

[13] John Schulman et coll., « Proximal policy optimization algorithms », prépublication arXiv, arXiv:1707.06347, 2017.

[14] Trapit Bansal et coll., « Emergent complexity via multi-agent competition », prépublication arXiv, arXiv:1710.03748, 2017.

Annexe

Nous fournissons ici plus de détails sur certains concepts évoqués plus haut.

Récompense différentielle: La récompense différentielle est une méthode permettant de surmonter le problème de l’attribution des crédits dans les équipes. Si l’on s’en tient à la procédure de récompense externe, les deux agents de l’équipe reçoivent la même récompense (récompense globale), sans égard à la contribution de chacun. Une telle politique entrave l’apprentissage multiagent, car des actions douteuses peuvent être récompensées à l’occasion, et certains agents peuvent apprendre à exécuter le gros du travail tandis que les autres deviennent paresseux. À l’inverse, l’approche de la récompense différentielle [14] propose de calculer la contribution individuelle de chaque agent sans compromettre la coordination. Le principe général est simple : on calcule la récompense individuelle de chaque agent en soustrayant de la récompense globale externe toute récompense contre-factuelle à laquelle ne correspond aucune action de la part de l’agent. Ainsi, les membres de l’équipe sont incités à la fois à améliorer le rendement global de l’équipe et à optimiser leur propre contribution. Aucun agent n’apprend à être paresseux. 

Entraînement centralisé et exécution décentralisée: Même si le scénario de jeu en équipe comprend une exécution partiellement observable, seul le mode d’entraînement permet de « pirater » le simulateur de jeu afin d’accéder à l’état complet. L’accès à l’état complet permet d’entraîner une fonction de valeur centralisée utilisée pendant l’entraînement afin de définir des réglages critiques pour les acteurs. Cependant, lorsqu’ils sont déployés, les agents n’utilisent que le réseau de politiques, ce qui signifie qu’ils sont entraînés à partir d’observations partielles.

Récompenses denses: Il peut arriver qu’un agent se suicide et que son coéquipier parvienne à lui seul à éliminer l’équipe adverse. Dans le cas le plus simple, les deux membres de l’équipe obtiennent alors la récompense +1, ce qui renforce le comportement de l’agent qui s’est suicidé! Pour résoudre ce problème, nous avons modifié la récompense externe de base de l’agent qui s’est suicidé afin que ce dernier reçoive une récompense moindre que celle attribuée au membre survivant de l’équipe. Cette technique a aidé notre agent à améliorer son rendement durant le jeu, mais elle s’accompagne de certaines conséquences, tant prévisibles qu’imprévues. Par exemple, dans ce contexte, il est impossible de faire en sorte qu’un des agents se sacrifie (dans une configuration où il supprime en même temps un ennemi) pour permettre à l’équipe de gagner, ou d’attribuer moins de crédits à un agent qui a supprimé un adversaire mais est mort en tentant de vaincre l’autre.

Filtre d’actions: Notre filtre d’actions comptait deux catégories.

Pour l’évitement du suicide 

  • Ne pas se rendre sur des cases qui seront remplies de flammes à la prochaine étape. 
  • Ne pas se rendre sur des cases qui sont « condamnées » par des bombes. Les cases condamnées par une bombe $b$ peuvent être déterminées en tenant compte de la force, de la portée et de la durée de l’explosion de la bombe, ainsi que de la situation locale sur la planche de jeu, à l’aide d’une procédure de programmation dynamique dans $O(l^2)$ où $l$ représente la portée (le rayon d’action) de l’explosion.   

Pour la pose de bombes

  • Ne pas poser de bombe si le coéquipier se trouve à proximité. 
  • Ne pas poser de bombe si la case occupée par l’agent est menacée par une autre bombe.