Open-ended Learning in Symmetric Zero-sum Games

Abstract

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.

ICML 2019, final version

References in corpus (3)

• Human-level performance in first-person multiplayer games with population-based deep reinforcement learning
• Flows and Decompositions of Games: Harmonic and Potential Games
• Paired Open-Ended Trailblazer (POET): Endlessly Generating Increasingly Complex and Diverse Learning Environments and Their Solutions

Cited by in corpus (23)

• Dota 2 with Large Scale Deep Reinforcement Learning
• Learning Agile Soccer Skills for a Bipedal Robot with Deep Reinforcement Learning
• Game-Theoretic Multiagent Reinforcement Learning
• OpenSpiel: A Framework for Reinforcement Learning in Games
• Adversarial Policies: Attacking Deep Reinforcement Learning
• TStarBot-X: An Open-Sourced and Comprehensive Study for Efficient League Training in StarCraft II Full Game
• A Generalized Training Approach for Multiagent Learning
• Learning to Play No-Press Diplomacy with Best Response Policy Iteration
• Using a thousand optimization tasks to learn hyperparameter search strategies
• Discovering Diverse Multi-Agent Strategic Behavior via Reward Randomization
• TLeague: A Framework for Competitive Self-Play based Distributed Multi-Agent Reinforcement Learning
• Options as responses: Grounding behavioural hierarchies in multi-agent RL
• Pipeline PSRO: A Scalable Approach for Finding Approximate Nash Equilibria in Large Games
• Real World Games Look Like Spinning Tops
• Arena: A General Evaluation Platform and Building Toolkit for Multi-Agent Intelligence
• Fast and Furious Learning in Zero-Sum Games: Vanishing Regret with Non-Vanishing Step Sizes
• Calibration of Shared Equilibria in General Sum Partially Observable Markov Games
• ${\alpha }^{\alpha }$-Rank: Practically Scaling $\alpha$-Rank through Stochastic Optimisation
• Consensus Multiplicative Weights Update: Learning to Learn using Projector-based Game Signatures
• A Limited-Capacity Minimax Theorem for Non-Convex Games or: How I Learned to Stop Worrying about Mixed-Nash and Love Neural Nets
• A Game-Theoretic Approach for Improving Generalization Ability of TSP Solvers
• Constants of Motion: The Antidote to Chaos in Optimization and Game Dynamics
• Complex Momentum for Optimization in Games