Anytime PSRO for Two-Player Zero-Sum Games

2022-01-19 · Stephen Mcaleer, Kevin Wang, John Lanier, Marc Lanctot, Pierre Baldi, Tuomas Sandholm, Roy Fox

Policy space response oracles (PSRO) is a multi-agent reinforcement learning algorithm that has achieved state-of-the-art performance in very large two-player zero-sum games. PSRO is based on the tabular double oracle (DO) method, an algorithm that is guaranteed to converge to a Nash equilibrium, but may increase exploitability from one iteration to the next. We propose anytime double oracle (ADO), a tabular double oracle algorithm for 2-player zero-sum games that is guaranteed to converge to a Nash equilibrium while decreasing exploitability from one iteration to the next. Unlike DO, in which the restricted distribution is based on the restricted game formed by each player's strategy sets, ADO finds the restricted distribution for each player that minimizes its exploitability against any policy in the full, unrestricted game. We also propose a method of finding this restricted distribution via a no-regret algorithm updated against best responses, called RM-BR DO. Finally, we propose anytime PSRO (APSRO), a version of ADO that calculates best responses via reinforcement learning. In experiments on Leduc poker and random normal form games, we show that our methods achieve far lower exploitability than DO and PSRO and decrease exploitability monotonically.

📄 PDF Abstract BibTeX arXiv:2201.07700

Code (0)

등록된 구현이 없습니다.

Tasks

Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)Vocal Bursts Valence Prediction

Self-Play PSRO: Toward Optimal Populations in Two-Player Zero-Sum Games

2022-07-13 · Stephen Mcaleer, JB Lanier, Kevin Wang, Pierre Baldi 외

In competitive two-agent environments, deep reinforcement learning (RL) methods based on the \emph{Double Oracle (DO)} algorithm, such as \emph{Policy Space Response Oracles (PSRO)} and \emph{Anytime PSRO (APSRO)}, itera…

Deep Reinforcement Learning Reinforcement Learning (RL)

Team-PSRO for Learning Approximate TMECor in Large Team Games via Cooperative Reinforcement Learning

2023-09-21 · NeurIPS 2023 11

Recent algorithms have achieved superhuman performance at a number of two-player zero-sum games such as poker and go. However, many real-world situations are multi-player games. Zero-sum two-team games, such as bridge an…

A Generalized Training Approach for Multiagent Learning

2019-09-27 · ICLR 2020 1 · Paul Muller, Shayegan Omidshafiei, Mark Rowland, Karl Tuyls 외

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 …

MuJoCo

Self-adaptive PSRO: Towards an Automatic Population-based Game Solver

2024-04-17 · Pengdeng Li, Shuxin Li, Chang Yang, Xinrun Wang 외

Policy-Space Response Oracles (PSRO) as a general algorithmic framework has achieved state-of-the-art performance in learning equilibrium policies of two-player zero-sum games. However, the hand-crafted hyperparameter va…

Hyperparameter Optimization

Global Policy-Space Response Oracles for Two-Player Zero-Sum Games

2026-05-27 · Junyu Zhang, Feihong Yang, Jian Wang, Chao Wang 외 arxiv

The Policy-Space Response Oracles (PSRO) framework scales equilibrium computation to large zero-sum games by iteratively expanding a restricted strategy set using deep reinforcement learning (DRL). A central challenge is…

Reinforcement Learning