Efficient Policy Space Response Oracles

2022-01-28 · Ming Zhou, Jingxiao Chen, Ying Wen, Weinan Zhang, Yaodong Yang, Yong Yu, Jun Wang

Policy Space Response Oracle methods (PSRO) provide a general solution to learn Nash equilibrium in two-player zero-sum games but suffer from two drawbacks: (1) the computation inefficiency due to the need for consistent meta-game evaluation via simulations, and (2) the exploration inefficiency due to finding the best response against a fixed meta-strategy at every epoch. In this work, we propose Efficient PSRO (EPSRO) that largely improves the efficiency of the above two steps. Central to our development is the newly-introduced subroutine of no-regret optimization on the unrestricted-restricted (URR) game. By solving URR at each epoch, one can evaluate the current game and compute the best response in one forward pass without the need for meta-game simulations. Theoretically, we prove that the solution procedures of EPSRO offer a monotonic improvement on the exploitability, which none of existing PSRO methods possess. Furthermore, we prove that the no-regret optimization has a regret bound of $\mathcal{O}(\sqrt{T\log{[(k^2+k)/2]}})$, where $k$ is the size of restricted policy set. Most importantly, a desirable property of EPSRO is that it is parallelizable, this allows for highly efficient exploration in the policy space that induces behavioral diversity. We test EPSRO on three classes of games, and report a 50x speedup in wall-time and 10x data efficiency while maintaining similar exploitability as existing PSRO methods on Kuhn and Leduc Poker games.

📄 PDF Abstract BibTeX arXiv:2202.00633

Code (0)

등록된 구현이 없습니다.

Tasks

Efficient Exploration

Code-Space Response Oracles: Generating Interpretable Multi-Agent Policies with Large Language Models

2026-03-10 · Daniel Hennes, Zun Li, John Schultz, Marc Lanctot arxiv

Recent advances in multi-agent reinforcement learning, particularly Policy-Space Response Oracles (PSRO), have enabled the computation of approximate game-theoretic equilibria in increasingly complex domains. However, th…

Multi-agent Reinforcement Learning Code Generation

Fusion-PSRO: Nash Policy Fusion for Policy Space Response Oracles

2024-05-31 · Jiesong Lian, Yucong Huang, Chengdong Ma, Mingzhi Wang 외

For solving zero-sum games involving non-transitivity, a useful approach is to maintain a policy population to approximate the Nash Equilibrium (NE). Previous studies have shown that the Policy Space Response Oracles (PS…

Multi-agent Reinforcement Learning

Policy Space Response Oracles: A Survey

2024-03-04 · Ariyan Bighashdel, Yongzhao Wang, Stephen Mcaleer, Rahul Savani 외

Game theory provides a mathematical way to study the interaction between multiple decision makers. However, classical game-theoretic analysis is limited in scalability due to the large number of strategies, precluding di…

Position Survey

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

Sample-Efficient Policy Space Response Oracles with Joint Experience Best Response

2026-02-06 · Ariyan Bighashdel, Thiago D. Simão, Frans A. Oliehoek arxiv

Multi-agent reinforcement learning (MARL) offers a scalable alternative to exact game-theoretic analysis but suffers from non-stationarity and the need to maintain diverse populations of strategies that capture non-trans…

Multi-agent Reinforcement Learning Offline RL