A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning

By Marc Lanctot, Vinícius Flores Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, Thore Graepel. 2017

750 citations recorded by the source corpus.

To achieve general intelligence, agents must learn how to interact with others in a shared environment: this is the challenge of multiagent reinforcement learning (MARL). The simplest form is independent reinforcement learning (InRL), where each agent treats its experience as part of its (non-stationary) environment. In this paper, we first observe that policies learned using InRL can overfit to the other agents' policies during training, failing to sufficiently generalize during execution. We introduce a new metric, joint-policy correlation, to quantify this effect. We describe an algorithm for general MARL, based on approximate best responses to mixtures of policies generated using deep reinforcement learning, and empirical game-theoretic analysis to compute meta-strategies for policy selection. The algorithm generalizes previous ones such as InRL, iterated best response, double oracle, and fictitious play. Then, we present a scalable implementation which reduces the memory requirement using decoupled meta-solvers. Finally, we demonstrate the generality of the resulting policies in two partially observable settings: gridworld coordination games and poker.

Subfields: Artificial Intelligence, Reinforcement Learning

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

In Reinforcement Learning

Citations in the corpus

AI safety via debate (2018, background): “• Existing research: Self play has produced impressive results for the games of Go [Silver et al., 2016, 2017a], chess and shogi [Silver et al., 2017b], and Dota 2 [OpenAI, 2017], and remains an area of active research [Bansal et al., 2017, Lanctot et al., 2017].”
OpenSpiel: A Framework for Reinforcement Learning in Games (2019, methodology): “Policy-Space Response Oracles (PSRO) generalizes fictitious play and the double-oracle algorithm [36, 40] by analyzing this meta-game using empirical game-theoretic analysis [74].”
Discovering Diverse Multi-Agent Strategic Behavior via Reward Randomization (2021, background): “In this framework, Nash Equilibrium (NE) (Nash, 1951), where no player could benefit from altering its strategy unilaterally, provides a general solution concept and serves as a goal for policy learning and has attracted increasingly significant interests from AI researchers (Heinrich & Silver, 2016”
The Hanabi Challenge: A New Frontier for AI Research (2019, methodology): “Several MARL algorithms have been recently proposed that learn from models of others whether by using a training regime based on cognitive hierarchies [87], by defining a learning rule that shapes the anticipated learning of other agents [88], or by training architectures that incorporate agent iden”
Learning with Opponent-Learning Awareness (2017, background): “[21] generalise the ideas of game-theoretic best-response-style algorithms, such as NFSP [17].”
Efficient Communication in Multi-Agent Reinforcement Learning via Variance Based Control (2019, background): “Worse still, each agent can easily overfit its strategy to the behaviours of other agents [11], which seriously deteriorates the overall performance.”
Machine Theory of Mind (2018, background): “…RL (Ng et al., 2000; Abbeel & Ng, 2004), Bayesian inference (Lucas et al., 2014; Evans et al., 2016), Bayesian Theory of Mind (Baker et al., 2011; Jara-Ettinger et al., 2016; Baker et al., 2017) or game theory (Camerer et al., 2004; Yoshida et al., 2008; Camerer, 2010; Lanctot et al., 2017).”
Learning Attentional Communication for Multi-Agent Cooperation (2018, background): “Moreover, policies learned using independent RL can easily overfit to the other agents’ policies [9].”
A survey and critique of multiagent deep reinforcement learning (2018, methodology): “Despite its common usage self-play can be brittle to forgetting past knowledge [180,186,275] (see Sect.”
Relational Forward Models for Multi-Agent Learning (2018, positive): “…where multiple learning agents perceive and act in a shared environment, has produced impressive results (Jaderberg et al., 2018; Pachocki et al., 2018; Leibo et al., 2017; Hughes et al., 2018; Peysakhovich & Lerer, 2017a; Lerer & Peysakhovich, 2017; Bansal et al., 2017; Lanctot et al., 2017).”
Emergent Coordination Through Competition (2019, methodology): “Other recent related approaches to multi-agent training include PSRO (Lanctot et al., 2017) and NFSP (Heinrich & Silver, 2016), which are motivated by game-theoretic methods (fictitious play and double oracle) for solving matrix games, aiming for some robustness by playing previous best response…”
Emergent Communication through Negotiation (2018, background): “Furthermore, it is well-known that, unless trained in a diverse environment, agents overﬁt to the their speciﬁc opponent or teammate (Lanctot et al., 2017).”
Open-Ended Learning Leads to Generally Capable Agents (2021, background): “The notion of generations of agents, forming a growing set (or league in Vinyals et al. (2019)) of agents lies at the core of many multi-agent learning algorithms (Balduzzi et al., 2019; Lanctot et al., 2017).”
"Other-Play" for Zero-Shot Coordination (2020, methodology): “In particular, because OP is a modification of the SP algorithm, it can be combined with many of the algorithmic innovations that have been developed to improve SP in various games (Lanctot et al., 2017; Foerster et al., 2018a; Lowe et al., 2017; Foerster et al., 2017).”
Open-ended Learning in Symmetric Zero-sum Games (2019, methodology): “Following Lanctot et al. (2017), we assume access to a subroutine, or oracle , that ﬁnds an approximate best response to any mixture i p i φ i ( w i ) of objectives.”
Deep Reinforcement Learning for Multiagent Systems: A Review of Challenges, Solutions, and Applications (2018, methodology): “This method is vulnerable to overfitting [67] and computationally expensive, and therefore the number of agents involved is limited.”
Interactive Agent Modeling by Learning to Probe (2018, methodology): “For instance, inspired by game theory, there have been approaches aiming at finding Nash equilibira in multi-agent games, where agents’ models are represented by their utilities (Littman, 1994; Hu & Wellman, 2003) and strategies (Claus & Boutilier, 1998; Tesauro, 2004; Powers & Shoham, 2005; Heinric”
Multi-agent deep reinforcement learning: a survey (2021, background): “More-over, Lanctot et al. (2017) argued that independent learners could over-fit to other agents’ policies during the training and, thus, may fail to generalize at test time.”