# Anytime PSRO for Two-Player Zero-Sum Games

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

## Key facts

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

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning](https://mlsanity.com/paper/1711.00832/) (2017)
- [OpenSpiel: A Framework for Reinforcement Learning in Games](https://mlsanity.com/paper/1908.09453/) (2019)
- [Open-ended Learning in Symmetric Zero-sum Games](https://mlsanity.com/paper/1901.08106/) (2019)
- [Solving Imperfect-Information Games via Discounted Regret Minimization](https://mlsanity.com/paper/1809.04040/) (2018)
- [Pipeline PSRO: A Scalable Approach for Finding Approximate Nash Equilibria in Large Games](https://mlsanity.com/paper/2006.08555/) (2020)
- [XDO: A Double Oracle Algorithm for Extensive-Form Games](https://mlsanity.com/paper/2103.06426/) (2021)
- [Stable-Predictive Optimistic Counterfactual Regret Minimization](https://mlsanity.com/paper/1902.04982/) (2019)
- [Iterative Empirical Game Solving via Single Policy Best Response](https://mlsanity.com/paper/2106.01901/) (2021)
- [Evaluating Strategy Exploration in Empirical Game-Theoretic Analysis](https://mlsanity.com/paper/2105.10423/) (2021)

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

- [A Survey on Self-play Methods in Reinforcement Learning](https://mlsanity.com/paper/2408.01072/) (2024)
- [Self-Play PSRO: Toward Optimal Populations in Two-Player Zero-Sum Games](https://mlsanity.com/paper/2207.06541/) (2022)
- [Robust Multi-Objective Controlled Decoding of Large Language Models](https://mlsanity.com/paper/2503.08796/) (2025)
- [Simplex Neural Population Learning: Any-Mixture Bayes-Optimality in Symmetric Zero-sum Games](https://mlsanity.com/paper/2205.15879/) (2022)
- [Fictitious Cross-Play: Learning Global Nash Equilibrium in Mixed Cooperative-Competitive Games](https://mlsanity.com/paper/2310.03354/) (2023)
- [ApproxED: Approximate exploitability descent via learned best responses](https://mlsanity.com/paper/2301.08830/) (2023)
- [Composing Efficient, Robust Tests for Policy Selection](https://mlsanity.com/paper/2306.07372/) (2023)
- [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 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.