The Game Theory & Multi-Agent team at DeepMind studies several aspects of multi-agent learning ranging from computing approximations to fundamental concepts in game theory to simulating social dilemmas in rich spatial environments and training 3-d humanoids in difficult team coordination tasks. A signature aim of our group is to use the resources and expertise made available to us at DeepMind in deep reinforcement learning to explore multi-agent systems in complex environments and use these benchmarks to advance our understanding. Here, we summarise the recent work of our team and present a taxonomy that we feel highlights many important open challenges in multi-agent research.
T.Anthony, T.Eccles, A.Tacchetti, J.Kramár, I.Gemp, T.Hudson, N.Porcel, M.Lanctot, J.Pérolat, R.Everettet al., Learning to play no-press diplomacy with best response policy iteration, Advances in Neural Information Processing Systems33 (2020), 17987–18003.
2.
T.W.Anthony, Expert iteration, PhD thesis, UCL (University College London), 2021.
3.
K.J.Arrow, Some mathematical models of race discrimination in the labor market, Racial discrimination in economic life (1972), 187–204.
4.
Y.Bachrach, R.Everett, E.Hughes, A.Lazaridou, J.Z.Leibo, M.Lanctot, M.Johanson, W.M.Czarnecki and T.Graepel, Negotiating team formation using deep reinforcement learning, Artificial Intelligence288 (2020), 103356. doi:10.1016/j.artint.2020.103356.
5.
Y.Bachrach, I.Gemp, M.Garnelo, J.Kramar, T.Eccles, D.Rosenbaum and T.Graepel, A neural network auction for group decision making over a continuous space, in: Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI) Demonstrations Track, 2021.
6.
A.Bakhtin, D.Wu, A.Lerer and N.Brown, No-press diplomacy from scratch, Advances in Neural Information Processing Systems34 (2021).
7.
M.A.Bakker, R.Everett, L.Weidinger, I.Gabriel, W.S.Isaac, J.Z.Leibo and E.Hughes, Modelling Cooperation in Network Games with Spatio-Temporal Complexity, 2021, CoRR, arXiv:2102.06911.
8.
J.Balaguer, R.Köster, C.Summerfield and A.Tacchetti, The good shepherd: An oracle agent for mechanism design, in: ICLR Workshop on Gamification and Multiagent Solutions, 2022.
9.
J.Balaguer, R.Köster, A.Weinstein, L.Campbell-Gillingham, C.Summerfield, M.Botvinick and A.Tacchetti, HCMD-zero: Learning value aligned mechanisms from data, in: ICLR Workshop on Gamification and Multiagent Solutions, 2022.
10.
D.Balduzzi, K.Tuyls, J.Perolat and T.Graepel, Re-evaluating evaluation, Advances in Neural Information Processing Systems31 (2018).
11.
D.Bloembergen, K.Tuyls, D.Hennes and M.Kaisers, Evolutionary dynamics of multi-agent learning: A survey, J. Artif. Intell. Res.53 (2015), 659–697. doi:10.1613/jair.4818.
12.
T.Börgers and R.Sarin, Learning through reinforcement and replicator dynamics, Journal of Economic Theory77(1) (1997), 1–14. doi:10.1006/jeth.1997.2319.
13.
G.W.Brown, Iterative solution of games by fictitious play, activity analysis of production and, allocation13(1) (1951), 374–376.
14.
T.Cabannes, M.Lauriere, J.Perolat, R.Marinier, S.Girgin, S.Perrin, O.Pietquin, A.M.Bayen, E.Goubault and R.Elie, Solving N-player dynamic routing games with congestion: A mean field approach, 2021, arXiv preprint arXiv:2110.11943.
15.
A.Calhamer, Diplomacy, Board Game, Avalon Hill (1959).
16.
R.Carmona, J.-P.Fouque and L.-H.Sun, Mean field games and systemic risk, Communications in Mathematical Sciences13(4) (2015), 911–933. doi:10.4310/CMS.2015.v13.n4.a4.
17.
M.Carroll, R.Shah, M.K.Ho, T.Griffiths, S.Seshia, P.Abbeel and A.Dragan, On the utility of learning about humans for human-ai coordination, Advances in neural information processing systems32 (2019).
18.
R.Chaabouni, F.Strub, F.Altché, E.Tarassov, C.Tallec, E.Davoodi, K.W.Mathewson, O.Tieleman, A.Lazaridou and B.Piot, Emergent Communication at Scale, International Conference on Learning Representations, 2021.
19.
W.M.Czarnecki, G.Gidel, B.Tracey, K.Tuyls, S.Omidshafiei, D.Balduzzi and M.Jaderberg, Real world games look like spinning tops, Advances in Neural Information Processing Systems33 (2020), 17443–17454.
20.
A.Dafoe, Y.Bachrach, G.Hadfield, E.Horvitz, K.Larson and T.Graepel, Cooperative AI: Machines Must Learn to Find Common Ground, Nature Publishing Group, 2021.
21.
A.Dafoe, E.Hughes, Y.Bachrach, T.Collins, K.R.McKee, J.Z.Leibo, K.Larson and T.Graepel, Open problems in cooperative ai, 2020, arXiv preprint arXiv:2012.08630.
22.
J.Deng, W.Dong, R.Socher, L.-J.Li, K.Li and L.Fei-Fei, Imagenet: A large-scale hierarchical image database, in: 2009 IEEE Conference on Computer Vision and Pattern Recognition, Ieee, 2009, pp. 248–255. doi:10.1109/CVPR.2009.5206848.
23.
C.Dogbé, Modeling crowd dynamics by the mean-field limit approach, Mathematical and Computer Modelling52(9–10) (2010), 1506–1520. doi:10.1016/j.mcm.2010.06.012.
24.
A.M.Donati, G.Quispe, C.Ollion, S.L.Corff, F.Strub and O.Pietquin, Learning natural language generation from scratch, in: Conference of the North American Chapter of the Association for Computational Linguistics, 2022.
T.Eccles, Y.Bachrach, G.Lever, A.Lazaridou and T.Graepel, Biases for emergent communication in multi-agent reinforcement learning, Advances in neural information processing systems32 (2019).
27.
R.Élie, E.Hubert, T.Mastrolia and D.Possamaï, Mean–field moral hazard for optimal energy demand response management, Mathematical Finance31(1) (2021), 399–473. doi:10.1111/mafi.12291.
28.
R.Elie, E.Hubert and G.Turinici, Contact rate epidemic control of COVID-19: An equilibrium view, Mathematical Modelling of Natural Phenomena15 (2020), 35. doi:10.1051/mmnp/2020022.
29.
R.Elie, J.Perolat, M.Laurière, M.Geist and O.Pietquin, On the convergence of model free learning in mean field games, in: Proc. of AAAI, 2020.
30.
M.Geist, J.Pérolat, M.Laurière, R.Elie, S.Perrin, O.Bachem, R.Munos and O.Pietquin, Concave utility reinforcement learning: The mean-field game viewpoint, in: Proc. of AAMAS, 2022.
31.
I.Gemp, K.R.McKee, R.Everett, E.A.Duéñez-Guzmán, Y.Bachrach, D.Balduzzi and A.Tacchetti, D3C: Reducing the Price of Anarchy in Multi-Agent Learning, 2020, arXiv preprint arXiv:2010.00575.
32.
I.Gemp, B.McWilliams, C.Vernade and T.Graepel, Eigengame: PCA as a nash equilibrium, 2020, arXiv preprint arXiv:2010.00554.
33.
I.Gemp, B.McWilliams, C.Vernade and T.Graepel, EigenGame Unloaded: When playing games is better than optimizing, 2021, arXiv preprint arXiv:2102.04152.
34.
I.Gemp, R.Savani, M.Lanctot, Y.Bachrach, T.Anthony, R.Everett, A.Tacchetti, T.Eccles and J.Kramár, Sample-based approximation of Nash in large many-player games via gradient descent, in: Proceedings of the 21st International Conference on Autonomous Agents and MultiAgent Systems, AAMAS ’22, International Foundation for Autonomous Agents and Multiagent Systems, 2022.
35.
S.Ginsburg and E.Jablonka, Evolutionary transitions in learning and cognition, Philosophical Transactions of the Royal Society B376(1821) (2021), 20190766. doi:10.1098/rstb.2019.0766.
36.
J.Gray, A.Lerer, A.Bakhtin and N.Brown, Human-level performance in no-press diplomacy via equilibrium search, 2020, arXiv preprint arXiv:2010.02923.
37.
A.Gruslys, M.Lanctot, R.Munos, F.Timbers, M.Schmid, J.Perolat, D.Morrill, V.Zambaldi, J.-B.Lespiau, J.Schultz, M.G.Azar, M.Bowling and K.Tuyls, The Advantage Regret-Matching Actor-Critic, 2020.
38.
J.Heinrich, M.Lanctot and D.Silver, Fictitious self-play in extensive-form games, in: Proceedings of the 32nd International Conference on Machine Learning (ICML 2015), 2015.
39.
J.Heinrich and D.Silver, Deep Reinforcement Learning from Self-Play in Imperfect-Information Games, 2016, CoRR arXiv:1603.01121.
40.
D.Hennes, D.Morrill, S.Omidshafiei, R.Munos, J.Perolat, M.Lanctot, A.Gruslys, J.-B.Lespiau, P.Parmas, E.Duenez-Guzman and K.Tuyls, Neural replicator dynamics, in: Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2020.
41.
M.Huang, R.P.Malhamé and P.E.Caines, Large population stochastic dynamic games: Closed-loop McKean-Vlasov systems and the Nash certainty equivalence principle, Communications in Information & Systems6 (2006).
42.
E.Hughes, T.W.Anthony, T.Eccles, J.Z.Leibo, D.Balduzzi and Y.Bachrach, Learning to resolve alliance dilemmas in many-player zero-sum games, 2020, arXiv preprint arXiv:2003.00799.
43.
E.Hughes, J.Z.Leibo, M.Phillips, K.Tuyls, E.Dueñez-Guzman, A.García Castañeda, I.Dunning, T.Zhu, K.McKee, R.Kosteret al., Inequity aversion improves cooperation in intertemporal social dilemmas, Advances in neural information processing systems31 (2018).
44.
N.Jaques, A.Lazaridou, E.Hughes, C.Gulcehre, P.Ortega, D.Strouse, J.Z.Leibo and N.De Freitas, Social influence as intrinsic motivation for multi-agent deep reinforcement learning, in: International Conference on Machine Learning, PMLR, 2019, pp. 3040–3049.
45.
A.Kalinowska, E.Davoodi, F.Strub, K.Mathewson, T.Murphey and P.Pilarski, Situated Communication: A Solution to over-Communication Between Artificial Agents, Emergent Communication Workshop at ICLR 2022, 2022.
46.
K.Kopparapu, E.A.Duéñez-Guzmán, J.Matyas, A.S.Vezhnevets, J.P.Agapiou, K.R.McKee, R.Everett, J.Marecki, J.Z.Leibo and T.Graepel, Hidden Agenda: A Social Deduction Game with Diverse Learned Equilibria, 2022, arXiv preprint arXiv:2201.01816.
47.
R.Köster, D.Hadfield-Menell, R.Everett, L.Weidinger, G.K.Hadfield and J.Z.Leibo, Spurious normativity enhances learning of compliance and enforcement behavior in artificial agents, Proceedings of the National Academy of Sciences119(3) (2022).
48.
A.Krizhevsky, I.Sutskever and G.E.Hinton, Imagenet classification with deep convolutional neural networks, Advances in neural information processing systems25 (2012).
49.
M.G.Lagoudakis and R.Parr, Least-squares policy iteration, The Journal of Machine Learning Research4 (2003), 1107–1149.
50.
M.Lanctot, E.Lockhart, J.-B.Lespiau, V.Zambaldi, S.Upadhyay, J.Pérolat, S.Srinivasan, F.Timbers, K.Tuyls, S.Omidshafiei, D.Hennes, D.Morrill, P.Muller, T.Ewalds, R.Faulkner, J.Kramár, B.D.Vylder, B.Saeta, J.Bradbury, D.Ding, S.Borgeaud, M.Lai, J.Schrittwieser, T.Anthony, E.Hughes, I.Danihelka and J.Ryan-Davis, OpenSpiel: A Framework for Reinforcement Learning in Games, 2019, CoRR, arXiv:1908.09453.
51.
M.Lanctot, V.Zambaldi, A.Gruslys, A.Lazaridou, K.Tuyls, J.Perolat, D.Silver and T.Graepel, A unified game-theoretic approach to multiagent reinforcement learning, in: Neural Information Processing Systems (NIPS), 2017.
52.
M.Lanctot, V.Zambaldi, A.Gruslys, A.Lazaridou, K.Tuyls, J.Perolat, D.Silver and T.Graepel, A unified game-theoretic approach to multiagent reinforcement learning, in: Advances in Neural Information Processing Systems, 2017.
53.
J.-M.Lasry and P.-L.Lions, Mean field games, Jpn. J. Math. (2007). doi:10.1007/s11537-007-0657-8.
54.
M.Laurière, S.Perrin, S.Girgin, P.Muller, A.Jain, T.Cabannes, G.Piliouras, J.Pérolat, R.Élie, O.Pietquinet al., Scalable Deep Reinforcement Learning Algorithms for Mean Field Games, 2022, arXiv preprint arXiv:2203.11973.
55.
J.Z.Leibo, E.A.Dueñez-Guzman, A.Vezhnevets, J.P.Agapiou, P.Sunehag, R.Koster, J.Matyas, C.Beattie, I.Mordatch and T.Graepel, Scalable evaluation of multi-agent reinforcement learning with melting pot, in: International Conference on Machine Learning, PMLR, 2021, pp. 6187–6199.
56.
J.Z.Leibo, E.Hughes, M.Lanctot and T.Graepel, Autocurricula and the emergence of innovation from social interaction: A manifesto for multi-agent intelligence research, 2019, arXiv preprint arXiv:1903.00742.
57.
J.Z.Leibo, J.Perolat, E.Hughes, S.Wheelwright, A.H.Marblestone, E.Duéñez-Guzmán, P.Sunehag, I.Dunning and T.Graepel, Malthusian reinforcement learning, in: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, 2019, pp. 1099–1107.
58.
J.Z.Leibo, V.F.Zambaldi, M.Lanctot, J.Marecki and T.Graepel, Multi-agent Reinforcement Learning in Sequential Social Dilemmas, 2017, CoRR arXiv:1702.03037.
59.
G.Lever, J.Merel, N.Heess, S.Tunyasuvunakool, S.Liu and T.Graepel, Emergent Coordination Through Competition, 2019.
60.
S.Liu, G.Lever, Z.Wang, J.Merel, S.Eslami, D.Hennes, W.M.Czarnecki, Y.Tassa, S.Omidshafiei, A.Abdolmalekiet al., From motor control to team play in simulated humanoid football, 2021, arXiv preprint arXiv:2105.12196.
61.
S.Liu, L.Marris, D.Hennes, J.Merel, N.Heess and T.Graepel, NeuPL: Neural population learning, in: International Conference on Learning Representations, 2022, https://openreview.net/forum?id=MIX3fJkl_1.
62.
E.Lockhart, M.Lanctot, J.Pérolat, J.-B.Lespiau, D.Morrill, F.Timbers and K.Tuyls, Computing approximate equilibria in sequential adversarial games by exploitability descent, in: Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), 2019.
63.
L.Marris, P.Muller, M.Lanctot, K.Tuyls and T.Graepel, Multi-agent training beyond zero-sum with correlated equilibrium meta-solvers, in: Proceedings of the 38th International Conference on Machine Learning, M.Meila and T.Zhang, eds, Proceedings of Machine Learning Research, Vol. 139, PMLR, 2021, pp. 7480–7491, http://proceedings.mlr.press/v139/marris21a.html.
64.
K.R.McKee, I.Gemp, B.McWilliams, E.A.Duéñez-Guzmán, E.Hughes and J.Z.Leibo, Social diversity and social preferences in mixed-motive reinforcement learning, 2020, arXiv preprint arXiv:2002.02325.
65.
H.B.McMahan, G.J.Gordon and A.Blum, Planning in the presence of cost functions controlled by an adversary, in: Proceedings of the 20th International Conference on Machine Learning (ICML-03), 2003, pp. 536–543.
66.
P.Milgrom and P.R.Milgrom, Putting Auction Theory to Work, Cambridge University Press, 2004.
67.
P.Moreno, E.Hughes, K.R.McKee, B.A.Pires and T.Weber, Neural Recursive Belief States in Multi-Agent Reinforcement Learning, 2021, https://arxiv.org/abs/2102.02274arXiv:arXiv. doi:10.48550/ARXIV.2102.02274.
68.
P.Muller, S.Omidshafiei, M.Rowland, K.Tuyls, J.Perolat, S.Liu, D.Hennes, L.Marris, M.Lanctot, E.Hughes, Z.Wang, G.Lever, N.Heess, T.Graepel and R.Munos, A generalized training approach for multiagent learning, in: Proceedings of the Eighth International Conference on Learning Representations (ICLR), 2020.
R.Munos, J.Perolat, J.-B.Lespiau, M.Rowland, B.D.Vylder, M.Lanctot, F.Timbers, D.Hennes, S.Omidshafiei, A.Gruslys, M.G.Azar, E.Lockhart and K.Tuyls, Fast computation of Nash equilibria in imperfect information games, in: Proceedings of the International Conference on Machine Learning (ICML), 2020.
C.H.Papadimitriou and G.Piliouras, From Nash equilibria to chain recurrent sets: An algorithmic solution concept for game theory, Entropy20(10) (2018), 782. doi:10.3390/e20100782.
73.
P.Paquette, Y.Lu, S.S.Bocco, M.Smith, S.Ortiz-Gagné, J.K.Kummerfeld, J.Pineau, S.Singh and A.C.Courville, No-press diplomacy: Modeling multi-agent gameplay, Advances in Neural Information Processing Systems32 (2019).
74.
R.Patel, M.Garnelo, I.Gemp, C.Dyer and Y.Bachrach, Game-theoretic vocabulary selection via the Shapley value and Banzhaf index, in: Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 2021, pp. 2789–2798.
75.
J.Perolat, J.Z.Leibo, V.Zambaldi, C.Beattie, K.Tuyls and T.Graepel, A multi-agent reinforcement learning model of common-pool resource appropriation, Advances in Neural Information Processing Systems30 (2017).
76.
J.Perolat, R.Munos, J.-B.Lespiau, S.Omidshafiei, M.Rowland, P.Ortega, N.Burch, T.Anthony, D.Balduzzi, B.D.Vylder, G.Piliouras, M.Lanctot and K.Tuyls, From Poincaré recurrence to convergence in imperfect information games: Finding equilibrium via regularization, in: Proceedings of the Thirty-Eighth International Conference on Machine Learning (ICML), 2021.
77.
J.Perolat, S.Perrin, R.Elie, M.Laurière, G.Piliouras, M.Geist, K.Tuyls and O.Pietquin, Scaling up Mean Field Games with Online Mirror Descent, 2021, arXiv preprint arXiv:2103.00623.
78.
S.Perrin, M.Laurière, J.Pérolat, R.Élie, M.Geist and O.Pietquin, Generalization in mean field games by learning master policies, 2021, arXiv preprint arXiv:2109.09717.
79.
S.Perrin, M.Laurière, J.Pérolat, M.Geist, R.Élie and O.Pietquin, Mean field games flock! the reinforcement learning way, 2021, arXiv preprint arXiv:2105.07933.
80.
S.Perrin, J.Pérolat, M.Laurière, M.Geist, R.Elie and O.Pietquin, Fictitious play for mean field games: Continuous time analysis and applications, in: Proc. of NeurIPS, 2020.
81.
J.W.Rae, S.Borgeaud, T.Cai, K.Millican, J.Hoffmann, F.Song, J.Aslanides, S.Henderson, R.Ring, S.Younget al., Scaling language models: Methods, analysis & insights from training gopher, 2021, arXiv preprint arXiv:2112.11446.
82.
M.Rita, F.Strub, J.-B.Grill, O.Pietquin and E.Dupoux, On the role of population heterogeneity in emergent communication, in: International Conference on Learning Representations, 2021.
83.
D.Silver, J.Schrittwieser, K.Simonyan, I.Antonoglou, A.Huang, A.Guez, T.Hubert, L.Baker, M.Lai, A.Bolton, Y.Chen, T.P.Lillicrap, F.Hui, L.Sifre, G.van den Driessche, T.Graepel and D.Hassabis, Mastering the game of Go without human knowledge, Nat.550(7676) (2017), 354–359. doi:10.1038/nature24270.
84.
S.Srinivasan, M.Lanctot, V.Zambaldi, J.Pérolat, K.Tuyls, R.Munos and M.Bowling, Actor-critic policy optimization in partially observable multiagent environments, in: Advances in Neural Information Processing Systems (NeurIPS), 2018.
85.
D.Strouse, K.McKee, M.Botvinick, E.Hughes and R.Everett, Collaborating with humans without human data, Advances in Neural Information Processing Systems34 (2021).
86.
P.Sunehag, G.Lever, S.Liu, J.Merel, N.Heess, J.Z.Leibo, E.Hughes, T.Eccles and T.Graepel, Reinforcement learning agents acquire flocking and symbiotic behaviour in simulated ecosystems, in: ALIFE 2019: The 2019 Conference on Artificial Life, MIT Press, 2019, pp. 103–110. doi:10.1162/isal_a_00148.
87.
E.Szathmáry and J.M.Smith, The Major Transitions in Evolution, WH Freeman Spektrum, Oxford, UK, 1995.
88.
A.Tacchetti, D.Strouse, M.Garnelo, T.Graepel and Y.Bachrach, Learning truthful, efficient, and welfare maximizing auction rules, in: ICLR Workshop on Gamification and Multiagent Solutions, 2022.
89.
C.G.I.Team, A.Bhoopchand, B.Brownfield, A.Collister, A.D.Lago, A.Edwards, R.Everett, A.Frechette, Y.G.Oliveira, E.Hugheset al., Learning Robust Real-Time Cultural Transmission without Human Data, 2022, arXiv preprint arXiv:2203.00715.
90.
K.Tuyls, D.Heytens, A.Nowé and B.Manderick, Extended replicator dynamics as a key to reinforcement learning in multi-agent systems, in: Machine Learning: ECML 2003, 14th European Conference on Machine Learning, Proceedings, Cavtat-Dubrovnik, Croatia, September 22–26, 2003, N.Lavrac, D.Gamberger, L.Todorovski and H.Blockeel, eds, Lecture Notes in Computer Science, Vol. 2837, Springer, 2003, pp. 421–431. doi:10.1007/978-3-540-39857-8_38.
91.
K.Tuyls, S.Omidshafiei, P.Muller, Z.Wang, J.Connor, D.Hennes, I.Graham, W.Spearman, T.Waskett, D.Steelet al., Game plan: What AI can do for football, and what football can do for AI, Journal of Artificial Intelligence Research71 (2021), 41–88. doi:10.1613/jair.1.12505.
92.
K.Tuyls, K.Verbeeck and T.Lenaerts, A selection-mutation model for q-learning in multi-agent systems, in: The Second International Joint Conference on Autonomous Agents & Multiagent Systems, AAMAS 2003, Proceedings, Melbourne, Victoria, Australia, July 14–18, 2003, ACM, 2003, pp. 693–700. doi:10.1145/860575.860687.
93.
A.Vezhnevets, Y.Wu, M.Eckstein, R.Leblond and J.Z.Leibo, Options as responses: Grounding behavioural hierarchies in multi-agent reinforcement learning, in: International Conference on Machine Learning, PMLR, 2020, pp. 9733–9742.
94.
E.Vinitsky, R.Köster, J.P.Agapiou, E.Duéñez-Guzmán, A.S.Vezhnevets and J.Z.Leibo, A learning agent that acquires social norms from public sanctions in decentralized multi-agent settings, 2021, arXiv preprint arXiv:2106.09012.
J.X.Wang, E.Hughes, C.Fernando, W.M.Czarnecki, E.A.Duéñez-Guzmán and J.Z.Leibo, Evolving intrinsic motivations for altruistic behavior, 2018, arXiv preprint arXiv:1811.05931.
97.
J.Yang, A.Li, M.Farajtabar, P.Sunehag, E.Hughes and H.Zha, Learning to incentivize other learning agents, Advances in Neural Information Processing Systems33 (2020), 15208–15219.
