Evolutionary Dynamics of Multi-Agent Learning: A Survey
By Daan Bloembergen, Karl Tuyls, Daniel Hennes, Michael Kaisers. 2015
347 citations recorded by the source corpus.
The interaction of multiple autonomous agents gives rise to highly dynamic and nondeterministic environments, contributing to the complexity in applications such as automated financial markets, smart grids, or robotics. Due to the sheer number of situations that may arise, it is not possible to foresee and program the optimal behaviour for all agents beforehand. Consequently, it becomes essential for the success of the system that the agents can learn their optimal behaviour and adapt to new situations or circumstances. The past two decades have seen the emergence of reinforcement learning, both in single and multi-agent settings, as a strong, robust and adaptive learning paradigm. Progress has been substantial, and a wide range of algorithms are now available. An important challenge in the domain of multi-agent learning is to gain qualitative insights into the resulting system dynamics. In the past decade, tools and methods from evolutionary game theory have been successfully employed to study multi-agent learning dynamics formally in strategic interactions. This article surveys the dynamical models that have been derived for various multi-agent reinforcement learning algorithms, making it possible to study and compare them qualitatively. Furthermore, new learning algorithms that have been introduced using these evolutionary game theoretic tools are reviewed. The evolutionary models can be used to study complex strategic interactions. Examples of such analysis are given for the domains of automated trading in stock markets and collision avoidance in multi-robot systems. The paper provides a roadmap on the progress that has been achieved in analysing the evolutionary dynamics of multi-agent learning by highlighting the main results and accomplishments.
Subfields: Artificial Intelligence, Economics and Econometrics, Management Science and Operations Research, Reinforcement Learning, Evolutionary Computation
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Sergey Levine
- Yoshua Bengio
- Pieter Abbeel
- Ruslan Salakhutdinov
- Mohit Bansal
- Quoc V. Le
- Yuxi Li
- Percy Liang
In Economics and Econometrics
- R´emi Munos
- Marc Lanctot
- David Silver
- Marc G. Bellemare
- Karl Tuyls
- Julien Pérolat
- Neil Burch
- Dustin Morrill
In Management Science and Operations Research
- Karl Tuyls
- David Silver
- Marc G. Bellemare
- Marc Lanctot
- R´emi Munos
- Pablo Hernandez-Leal
- Jakob N. Foerster
- Julien Pérolat
In Reinforcement Learning
- Sergey Levine
- Pieter Abbeel
- Shimon Whiteson
- Jakob N. Foerster
- Yuxi Li
- Marc G. Bellemare
- Karl Tuyls
- R´emi Munos
In Evolutionary Computation
- Peter Stone
- Lacra Pavel
- Hugo Larochelle
- Georgios Piliouras
- Panayotis Mertikopoulos
- Marc Lanctot
- Karl Tuyls
- Bolin Gao
Citations in the corpus
- OpenSpiel: A Framework for Reinforcement Learning in Games (2019, background): “Visualization of Evolutionary and Policy Learning Dynamics One common visualization tool in the multiagent learning literature (especially in games) is a phase portrait that shows a vector field and/or trajectories of particle the depict local changes to the policy under specific update dynamics [64”
- Multi-agent Reinforcement Learning in Sequential Social Dilemmas (2017, background): “, [13, 15], rather than on designing new learning algorithms.”
- The Hanabi Challenge: A New Frontier for AI Research (2019, background): “Several years of work on MARL gave rise to many algorithms, extensions, and analyses [59, 60, 61, 62, 63].”
- Lenient Multi-Agent Deep Reinforcement Learning (2017, background): “Multiagent reinforcement learning (MA-RL) is known for being challenging even in environments with only two implicit learning agents, lacking the convergence guarantees present in most single-agent learning algorithms [3, 18].”
- A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning (2017, background): “For a more elaborate introduction to replicator dynamics, and their relationship with RL, we refer to [7].”
- Neural Replicator Dynamics (2019, neutral): “…MARL have been primarily identified between the Replicator Dynamics (RD), a standard model in EGT, and simple policy iteration algorithms such as Cross Learning and Learning Automata [4, 5, 65], value-iteration algorithms such as Q-learning in stateless cases [27, 63], and no-regret learning [29].”
- Learning against sequential opponents in repeated stochastic games (2017, background): “Learning to act in multiagent systems has received attention mainly from game theory, focused on algorithms that converge to the Nash equilibrium [2, 6, 7]; and from reinforcement learning, focused on acting optimally in stochastic scenarios with limited a priori information but online observations…”
- On the Properties of the Softmax Function with Application in Game Theory and Reinforcement Learning (2017, background): “It has been known that stateless multi-agent reinforcement learning that utilizes the softmax selection rule has close connections with the field of evolutionary game theory [9], [10], [22], [23], [54], [20], [58].”
- Tight last-iterate convergence rates for no-regret learning in multi-player games (2020, background): “In turn, a substantial body of work (e.g., [CBL06, DP09, EDMN09, CD11, VZ13, KKDB15, BTHK15, MP17, MZ18, KBTB18]) has focused on establishing for which classes of games or learning algorithms this convergence to a CCE can be strengthened, such as to convergence to a Nash equilibrium (NE) .”
- Algorithms for computing strategies in two-player simultaneous move games (2016, neutral): “For surveys of the relevant previous work in multiagent reinforcement learning and game theory (including the zero-sum case), see [30, 31, 32].”
- Artificial Intelligence, Algorithmic Pricing, and Collusion (2020, methodology): “But the observation of supra-competitive prices is not, per se, genuine proof of collusion, as high prices could be due to the algorithms’ failure to learn the competitive equilibrium.(8) If”
- Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games (2020, background): “…to the following fundamental question in game-theoretical learning [Cesa-Bianchi and Lugosi, 2006, Shoham and Leyton-Brown, 2008, Viossat and Zapechelnyuk, 2013, Bloembergen et al., 2015, Monnot and Piliouras, 2017]: Would OGD learning, and more broadly no-regret learning, lead to Nash equilibiria?”
- From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization (2020, background): “In zero-sum sequential imperfect information games, the policy can cycle around the minimax equilibrium without ever converging, even in simple single-state games (Piliouras & Shamma, 2014; Mertikopoulos et al., 2018; Singh et al., 2000; Bloembergen et al., 2015; Bailey & Piliouras, 2018).”
- Multi-objective multi-agent decision making: a utility-based analysis and survey (2019, background): “Recent works have surveyed multiagent decision making from a variety of different perspectives, including: the evolutionary dynamics of multi-agent learning [20], non-stationarity in multi-agent environments [66], modelling other agents in MAS [3], and deep reinforcement learning in MAS [67,109].”
- A Survey of Learning in Multiagent Environments: Dealing with Non-Stationarity (2017, background): “Finally, a recent survey analysed methods from evolutionary game theory and its relation with multiagent learning (Bloembergen et al., 2015).”
- Deep Reinforcement Learning for Multiagent Systems: A Review of Challenges, Solutions, and Applications (2018, background): “social dilemma (MGSD) that has been applied to various phenomena in social science and biology [22], [52], [94].”
- Cooperative Multi-agent Control Using Deep Reinforcement Learning (2017, background): “Learning to cooperate between several interacting agents has been well studied [39, 30, 6].”