Open-ended Learning in Symmetric Zero-sum Games

By David Balduzzi, Marta Garnelo, Yoram Bachrach, Wojciech M. Czarnecki, Julien Pérolat, Max Jaderberg, Thore Graepel. 2019

201 citations recorded by the source corpus.

Zero-sum games such as chess and poker are, abstractly, functions that evaluate pairs of agents, for example labeling them `winner' and `loser'. If the game is approximately transitive, then self-play generates sequences of agents of increasing strength. However, nontransitive games, such as rock-paper-scissors, can exhibit strategic cycles, and there is no longer a clear objective -- we want agents to increase in strength, but against whom is unclear. In this paper, we introduce a geometric framework for formulating agent objectives in zero-sum games, in order to construct adaptive sequences of objectives that yield open-ended learning. The framework allows us to reason about population performance in nontransitive games, and enables the development of a new algorithm (rectified Nash response, PSRO_rN) that uses game-theoretic niching to construct diverse populations of effective agents, producing a stronger set of agents than existing algorithms. We apply PSRO_rN to two highly nontransitive resource allocation games and find that PSRO_rN consistently outperforms the existing alternatives.

Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning, Game & Decision Theory

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 Management Science and Operations Research

In Reinforcement Learning

In Game & Decision Theory

Citations in the corpus

OpenSpiel: A Framework for Reinforcement Learning in Games (2019, neutral): “[31, 63] Counterfactual Regret Minimization (CFR) Tabular [78, 47] (Tabular) Exploitability Tabular [78] External sampling Monte Carlo CFR Tabular [34, 35] Outcome sampling Monte Carlo CFR Tabular [34, 35] Q-learning Tabular [67] Value Iteration Tabular [67] Advantage Actor-Critic (A2C) RL [42] Deep”
Dota 2 with Large Scale Deep Reinforcement Learning (2019, background): “[60] for a discussion of cyclic strategies in games with simultaneous-turns and/or imperfect information).”
Discovering Diverse Multi-Agent Strategic Behavior via Reward Randomization (2021, neutral): “…(Robinson, 1951; Monderer & Shapley, 1996; Heinrich & Silver, 2016; Kamra et al., 2019; Han & Hu, 2019), double-oracle (McMahan et al., 2003; Lanctot et al., 2017; Wang et al., 2019; Balduzzi et al., 2019) and regularized self-play (Foerster et al., 2018; Perolat et al., 2020; Bai & Jin, 2020).”
Open-Ended Learning Leads to Generally Capable Agents (2021, background): “Iterative notions of improvements have been used, particularly in multiagent systems, either explicitly by targeting the goal with respect to known opponents (Balduzzi et al., 2019; McMahan et al., 2003), implicitly by using internal ranking between agents (Jaderberg et al.”
Adversarial Policies: Attacking Deep Reinforcement Learning (2019, methodology): “Consequently, we urge caution when using methods such as self-play that assume transitivity, and would recommend more general methods where practical (Balduzzi et al., 2019; Brown et al., 2019).”
Grandmaster level in StarCraft II using multi-agent reinforcement learning (2019, methodology): “Self-play algorithms, similar to those used in chess and Go 18 , learn rapidly but may chase cycles (for example, where A defeats B, and B defeats C, but A loses to C) indefinitely without making progress 19 .”
Arena: A General Evaluation Platform and Building Toolkit for Multi-Agent Intelligence (2019, methodology): “Rock, Paper, and Scissors in normal-form game [63] and Cyclic Game in [4] are both special cases of F CP ; see Lemmas 2 and 3 in the supplementary material [2].”
Minimax Theorem for Latent Games or: How I Learned to Stop Worrying about Mixed-Nash and Love Neural Nets (2020, methodology): “The function oracle ( f, F , ˜ ϕ ) is a black box oracle similar to the one described in Balduzzi et al. (2019) that gives an improvement for the mappings f within the class F using the approximate payoff ˜ ϕ .”
Options as responses: Grounding behavioural hierarchies in multi-agent RL (2019, background): “Flat agents are not capable of separating these two signals and are likely to cycle between different strategies, as discussed in [5].”
Multi-objective multi-agent decision making: a utility-based analysis and survey (2019, background): “competitive), or even creating populations of agents that develop effective behaviours against a large range of opponents [2].”
Unifying Behavioral and Response Diversity for Open-ended Learning in Zero-sum Games (2021, methodology): “The empirical gamescape is introduced by [2] to represent the expressiveness of a population P i in the reward outcome level given the opponent population P − i : Deﬁnition 2.”