CoChat
Sign Up
PreprintCited by 3Artificial Intelligence in GamesEvolutionary Algorithms and ApplicationsReinforcement Learning in Robotics

The DOI matches its DataCite record.

Pick Your Battles: Interaction Graphs as Population-Level Objectives for Strategic Diversity

Open access
Garnelo, Marta, Czarnecki, Wojciech Marian, Liu, Siqi, Tirumala, Dhruva, Oh, Junhyuk, Gidel, Gauthier, van Hasselt, Hado, Balduzzi, David·2021·arXiv
DOI 10.48550/arxiv.2110.04041arXiv 2110.04041
Open this paper in CoChat — free accountOpen PDF

Abstract

Strategic diversity is often essential in games: in multi-player games, for example, evaluating a player against a diverse set of strategies will yield a more accurate estimate of its performance. Furthermore, in games with non-transitivities diversity allows a player to cover several winning strategies. However, despite the significance of strategic diversity, training agents that exhibit diverse behaviour remains a challenge. In this paper we study how to construct diverse populations of agents by carefully structuring how individuals within a population interact. Our approach is based on interaction graphs, which control the flow of information between agents during training and can encourage agents to specialise on different strategies, leading to improved overall performance. We provide evidence for the importance of diversity in multi-agent training and analyse the effect of applying different interaction graphs on the training trajectories, diversity and performance of populations in a range of games. This is an extended version of the long abstract published at AAMAS.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2110.04041

Cites

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • SP may cause cycles in the strategy space when agents forget how to play against previous versions of their policy.

    “However, SP may cause cycles in the strategy space when agents forget how to play against previous versions of their policy (Garnelo et al., 2021).”

    From MAESTRO: Open-Ended Environment Design for Multi-Agent Reinforcement Learning (2023) · cites this paper as Garnelo et al., 2021

    Section 7.3 (p. 10) reports that agents trained with the self-play interaction graph cycled throughout training, supporting the claim that self-play may cause cycles in strategy space. The passage does not say that agents cycled because they forgot how to play against earlier versions of their policies. (LLM, conf=0.88)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

No references could be resolved yet.

Research works printed but not linked: 26

  1. [1][1] David Balduzzi, Marta Garnelo, Yoram Bachrach, Wojciech M Czarnecki, Julien Perolat, Max Jaderberg, and Thore Graepel. Open-ended learning in symmetric zero-sum games. International Conference on Machine Learning , 2019. -
  2. [2][2] David Balduzzi, Sebastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Graepel. The mechanics of n-player differentiable games. arXiv preprint arXiv:1802.05642 , 2018. - · arXiv
  3. [3][3] David Balduzzi, Karl Tuyls, Julien Perolat, and Thore Graepel. Re-evaluating evaluation. In Advances in Neural Information Processing Systems , pages 3268-3279, 2018. -
  4. [4][4] Rafaglyph[suppress] l Dre˙ zewski. A model of co-evolution in multi-agent system. In International Central and Eastern European Conference on Multi-Agent Systems , pages 314-323. Springer, 2003. -
  5. [5][5] Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity is all you need: Learning skills without a reward function. International Conference on Learning Representations , 2018. -
  6. [6][6] Sevan G Ficici and Jordan B Pollack. A game-theoretic memory mechanism for coevolution. In Genetic and Evolutionary Computation Conference , pages 286-297. Springer, 2003. -
  7. [7][7] Chelsea Finn, Tianhe Yu, Tianhao Zhang, Pieter Abbeel, and Sergey Levine. One-shot visual imitation learning via meta-learning. In Conference on Robot Learning , pages 357-368, 2017. -
  8. [8][8] Carlos Florensa, Yan Duan, and Pieter Abbeel. Stochastic neural networks for hierarchical reinforcement learning. International Conference on Learning Representations , 2016. -
  9. [9][9] Kevin Frans, Jonathan Ho, Xi Chen, Pieter Abbeel, and John Schulman. Meta learning shared hierarchies. arXiv preprint arXiv:1710.09767 , 2017. - · arXiv
  10. [10][10] Marta Garnelo, Wojciech Marian Czarnecki, Siqi Liu, Dhruva Tirumala, Junhyuk Oh, Gauthier Gidel, Hado van Hasselt, and David Balduzzi. Pick your battles: Interaction graphs as population-level objectives for strategic diversity. In Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems , pages 1501-1503, 2021. -
  11. [11][11] Karol Gregor, Danilo Jimenez Rezende, and Daan Wierstra. Variational intrinsic control. International Conference on Learning Representations , 2017. -
  12. [12][12] Carlos Guestrin, Michail Lagoudakis, and Ronald Parr. Coordinated reinforcement learning. In ICML , volume 2, pages 227-234. Citeseer, 2002. -
  13. [13][13] Karol Hausman, Jost Tobias Springenberg, Ziyu Wang, Nicolas Heess, and Martin Riedmiller. Learning an embedding space for transferable robot skills. International Conference on Learning Representations , 2018. -
  14. [14][14] Max Jaderberg, Wojciech M Czarnecki, Iain Dunning, Luke Marris, Guy Lever, Antonio Garcia Castaneda, Charles Beattie, Neil C Rabinowitz, Ari S Morcos, Avraham Ruderman, et al. Humanlevel performance in 3d multiplayer games with population-based reinforcement learning. Science , 364(6443):859-865, 2019. -
  15. [15][15] Michael Kearns, Michael L Littman, and Satinder Singh. Graphical models for game theory. arXiv preprint arXiv:1301.2281 , 2013. - · arXiv
  16. [16][16] Marc Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien P´ erolat, David Silver, and Thore Graepel. A unified game-theoretic approach to multiagent reinforcement learning. In Advances in Neural Information Processing Systems , pages 4190-4203, 2017. -
  17. [17][17] Da Li, Yongxin Yang, Yi-Zhe Song, and Timothy M Hospedales. Learning to generalize: Meta-learning for domain generalization. In Thirty-Second AAAI Conference on Artificial Intelligence , 2018. -
  18. [18][18] Siqi Liu, Guy Lever, Josh Merel, Saran Tunyasuvunakool, Nicolas Heess, and Thore Graepel. Emergent coordination through competition. International Conference on Learning Representations , 2018. -
  19. [19][19] Kevin R. McKee, Ian Gemp, Brian McWilliams, Edgar A. Du´ e˜ nez-Guzm´ an, Edward Hughes, and Joel Z. Leibo. Social diversity and social preferences in mixed-motive reinforcement learning. arXiv preprint arXiv:2002.02325 , 2020. - · arXiv
  20. [20][20] Jason Morrison and Franz Oppacher. A general model of co-evolution for genetic algorithms. In Artificial Neural Nets and Genetic Algorithms , pages 262-268. Springer, 1999. -
  21. [21][21] Frans A Oliehoek, Edwin D De Jong, and Nikos Vlassis. The parallel nash memory for asymmetric games. In Proceedings of the 8th annual conference on Genetic and evolutionary computation , pages 337-344, 2006. -
  22. [22][22] Jan Paredis. Coevolutionary computation. Artificial life , 2(4):355-375, 1995. -
  23. [24][24] David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science , 362(6419):1140-1144, 2018. -
  24. [25][25] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. Nature , 550(7676):354-359, 2017. -
  25. [26][26] Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Micha¨ el Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature , 575(7782):350-354, 2019. -
  26. [27][27] Oriol Vinyals, Timo Ewalds, Sergey Bartunov, Petko Georgiev, Alexander Sasha Vezhnevets, Michelle Yeo, Alireza Makhzani, Heinrich K¨ uttler, John Agapiou, Julian Schrittwieser, et al. Starcraft ii: A new challenge for reinforcement learning. arXiv preprint arXiv:1708.04782 , 2017. · arXiv

Cited by

Sorted by citations

Metadata

Authors
Garnelo, M., Czarnecki, W. M., Liu, S., Tirumala, D., Oh, J., Gidel, G., van Hasselt, H., & Balduzzi, D.
Affiliations
Google DeepMind (United Kingdom) (GB)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2021
Pages
1501-1503
ISSN
1548-8403 (ISSN-L)
DOI
10.48550/arxiv.2110.04041
arXiv
2110.04041
OpenAlex
W3176176644
Cited by
3
References
0
Citations by year
2025: 1 · 2024: 1 · 2022: 1
FWCI
0.23
Type
conference paper
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • Adaptive Agents and Multi-Agents Systems (publishedVersion)
  • arXiv (Cornell University) (publishedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Artificial Intelligence in Games
  • Physical Sciences › Computer Science › Artificial Intelligence › Evolutionary Algorithms and Applications
  • Physical Sciences › Computer Science › Artificial Intelligence › Reinforcement Learning in Robotics
Keywords
strategic diversity, interaction graphs, multiplayer games, agent diversity, training trajectories

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review