A Generalized Training Approach for Multiagent Learning

Abstract

This paper investigates a population-based training regime based on game-theoretic principles called Policy-Spaced Response Oracles (PSRO). PSRO is general in the sense that it (1) encompasses well-known algorithms such as fictitious play and double oracle as special cases, and (2) in principle applies to general-sum, many-player games. Despite this, prior studies of PSRO have been focused on two-player zero-sum games, a regime wherein Nash equilibria are tractably computable. In moving from two-player zero-sum games to more general settings, computation of Nash equilibria quickly becomes infeasible. Here, we extend the theoretical underpinnings of PSRO by considering an alternative solution concept, $\alpha$-Rank, which is unique (thus faces no equilibrium selection issues, unlike Nash) and applies readily to general-sum, many-player settings. We establish convergence guarantees in several games classes, and identify links between Nash equilibria and $\alpha$-Rank. We demonstrate the competitive performance of $\alpha$-Rank-based PSRO against an exact Nash solver-based PSRO in 2-player Kuhn and Leduc Poker. We then go beyond the reach of prior PSRO applications by considering 3- to 5-player poker games, yielding instances where $\alpha$-Rank achieves faster convergence than approximate Nash solvers, thus establishing it as a favorable general games solver. We also carry out an initial empirical validation in MuJoCo soccer, illustrating the feasibility of the proposed approach in another complex domain.

References in corpus (13)

• Learning to Communicate with Deep Multi-Agent Reinforcement Learning
• Human-level performance in first-person multiplayer games with population-based deep reinforcement learning
• A Survey and Critique of Multiagent Deep Reinforcement Learning
• Counterfactual Multi-Agent Policy Gradients
• Multiagent Bidirectionally-Coordinated Nets: Emergence of Human-level Coordination in Learning to Play StarCraft Combat Games
• Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observability
• Bayes' Bluff: Opponent Modelling in Poker
• Emergent Coordination Through Competition
• Multiplicative Weights Update with Constant Step-Size in Congestion Games: Convergence, Limit Cycles and Chaos
• Multiagent Soft Q-Learning
• Open-ended Learning in Symmetric Zero-sum Games
• Evolutionary Reinforcement Learning for Sample-Efficient Multiagent Coordination
• Multiagent Evaluation under Incomplete Information

Cited by in corpus (6)

• Distributed Deep Reinforcement Learning: A Survey and A Multi-Player Multi-Agent Learning Toolbox
• Navigating the Landscape of Multiplayer Games
• Mis-spoke or mis-lead: Achieving Robustness in Multi-Agent Communicative Reinforcement Learning
• ${\alpha }^{\alpha }$-Rank: Practically Scaling $\alpha$-Rank through Stochastic Optimisation
• A Game-Theoretic Approach for Improving Generalization Ability of TSP Solvers
• Search in Imperfect Information Games