# Efficient Policy Space Response Oracles

arXiv: https://arxiv.org/abs/2202.00633 · HTML: https://mlsanity.com/paper/2202.00633/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 45 references that are in the map.
- First posted on arXiv 28 Jan 2022.

## Builds on (most cited first, 19 of 19)

- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Dota 2 with Large Scale Deep Reinforcement Learning](https://mlsanity.com/paper/1912.06680/) (2019)
- [Reinforcement Learning with Deep Energy-Based Policies](https://mlsanity.com/paper/1702.08165/) (2017)
- [A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning](https://mlsanity.com/paper/1711.00832/) (2017)
- [Mean Field Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1802.05438/) (2018)
- [Open-ended Learning in Symmetric Zero-sum Games](https://mlsanity.com/paper/1901.08106/) (2019)
- [Distilling Policy Distillation](https://mlsanity.com/paper/1902.02186/) (2019)
- [Real World Games Look Like Spinning Tops](https://mlsanity.com/paper/2004.09468/) (2020)
- [α-Rank: Multi-Agent Evaluation by Evolution](https://mlsanity.com/paper/1903.01373/) (2019)
- [Pipeline PSRO: A Scalable Approach for Finding Approximate Nash Equilibria in Large Games](https://mlsanity.com/paper/2006.08555/) (2020)
- [A Deterministic Linear Program Solver in Current Matrix Multiplication Time](https://mlsanity.com/paper/1910.11957/) (2019)
- [Modelling Behavioural Diversity for Learning in Open-Ended Games](https://mlsanity.com/paper/2103.07927/) (2021)
- [XDO: A Double Oracle Algorithm for Extensive-Form Games](https://mlsanity.com/paper/2103.06426/) (2021)
- [Diverse Auto-Curriculum is Critical for Successful Real-World Multiagent Learning Systems](https://mlsanity.com/paper/2102.07659/) (2021)
- [Online Double Oracle](https://mlsanity.com/paper/2103.07780/) (2021)
- [Iterative Empirical Game Solving via Single Policy Best Response](https://mlsanity.com/paper/2106.01901/) (2021)
- [αα-Rank: Practically Scaling α-Rank through Stochastic Optimisation](https://mlsanity.com/paper/1909.11628/) (2019)
- [Evaluating Strategy Exploration in Empirical Game-Theoretic Analysis](https://mlsanity.com/paper/2105.10423/) (2021)
- [Q-Mixing Network for Multi-Agent Pathfinding in Partially Observable Grid Environments](https://mlsanity.com/paper/2108.06148/) (2021)

## Built on by (most cited first, 8 of 8)

- [A Survey on Self-play Methods in Reinforcement Learning](https://mlsanity.com/paper/2408.01072/) (2024)
- [Policy Space Diversity for Non-Transitive Games](https://mlsanity.com/paper/2306.16884/) (2023)
- [Policy Space Response Oracles: A Survey](https://mlsanity.com/paper/2403.02227/) (2024)
- [An Empirical Study on Google Research Football Multi-agent Scenarios](https://mlsanity.com/paper/2305.09458/) (2023)
- [Fusion-PSRO: Nash Policy Fusion for Policy Space Response Oracles](https://mlsanity.com/paper/2405.21027/) (2024)
- [Computing Ex Ante Equilibrium in Heterogeneous Zero-Sum Team Games](https://mlsanity.com/paper/2410.01575/) (2024)
- [NePPO: Near-Potential Policy Optimization for General-Sum Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2603.06977/) (2026)
- [Global Policy-Space Response Oracles for Two-Player Zero-Sum Games](https://mlsanity.com/paper/2605.28273/) (2026)

## Abstract (arXiv)

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 O(√Tlog[(k2+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.