# Pipeline PSRO: A Scalable Approach for Finding Approximate Nash Equilibria in Large Games

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

## Key facts

- Cited by 47 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jun 2020.

## Built on by (most cited first, 30 of 47)

- [Modelling Behavioural Diversity for Learning in Open-Ended Games](https://mlsanity.com/paper/2103.07927/) (2021)
- [Independent Natural Policy Gradient Always Converges in Markov Potential Games](https://mlsanity.com/paper/2110.10614/) (2021)
- [XDO: A Double Oracle Algorithm for Extensive-Form Games](https://mlsanity.com/paper/2103.06426/) (2021)
- [No-Press Diplomacy from Scratch](https://mlsanity.com/paper/2110.02924/) (2021)
- [Cooperative Open-ended Learning Framework for Zero-shot Coordination](https://mlsanity.com/paper/2302.04831/) (2023)
- [A Survey on Self-play Methods in Reinforcement Learning](https://mlsanity.com/paper/2408.01072/) (2024)
- [ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regret](https://mlsanity.com/paper/2206.04122/) (2022)
- [MALib: A Parallel Framework for Population-based Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2106.07551/) (2021)
- [Multi-Agent Training beyond Zero-Sum with Correlated Equilibrium Meta-Solvers](https://mlsanity.com/paper/2106.09435/) (2021)
- [Online Double Oracle](https://mlsanity.com/paper/2103.07780/) (2021)
- [Policy Space Diversity for Non-Transitive Games](https://mlsanity.com/paper/2306.16884/) (2023)
- [Unifying Behavioral and Response Diversity for Open-ended Learning in Zero-sum Games](https://mlsanity.com/paper/2106.04958/) (2021)
- [A Game-Theoretic Approach for Improving Generalization Ability of TSP Solvers](https://mlsanity.com/paper/2110.15105/) (2021)
- [NeuPL: Neural Population Learning](https://mlsanity.com/paper/2202.07415/) (2022)
- [A Game-Theoretic Framework for Managing Risk in Multi-Agent Systems](https://mlsanity.com/paper/2205.15434/) (2022)
- [Reevaluating Policy Gradient Methods for Imperfect-Information Games](https://mlsanity.com/paper/2502.08938/) (2025)
- [Tackling Cooperative Incompatibility for Zero-Shot Human-AI Coordination](https://mlsanity.com/paper/2306.03034/) (2023)
- [Self-Play PSRO: Toward Optimal Populations in Two-Player Zero-Sum Games](https://mlsanity.com/paper/2207.06541/) (2022)
- [Policy Space Response Oracles: A Survey](https://mlsanity.com/paper/2403.02227/) (2024)
- [Anytime PSRO for Two-Player Zero-Sum Games](https://mlsanity.com/paper/2201.07700/) (2022)
- [Search in Imperfect Information Games](https://mlsanity.com/paper/2111.05884/) (2021)
- [Efficient Policy Space Response Oracles](https://mlsanity.com/paper/2202.00633/) (2022)
- [Rethinking Adversarial Policies: A Generalized Attack Formulation and Provable Defense in RL](https://mlsanity.com/paper/2305.17342/) (2023)
- [Combining Tree-Search, Generative Models, and Nash Bargaining Concepts in Game-Theoretic Reinforcement Learning](https://mlsanity.com/paper/2302.00797/) (2023)
- [Learning Diverse Risk Preferences in Population-based Self-play](https://mlsanity.com/paper/2305.11476/) (2023)
- [An Empirical Study on Google Research Football Multi-agent Scenarios](https://mlsanity.com/paper/2305.09458/) (2023)
- [Distributed Deep Reinforcement Learning: A Survey and A Multi-Player Multi-Agent Learning Toolbox](https://mlsanity.com/paper/2212.00253/) (2022)
- [Neural Population Learning beyond Symmetric Zero-sum Games](https://mlsanity.com/paper/2401.05133/) (2024)
- [Improving Social Welfare While Preserving Autonomy via a Pareto Mediator](https://mlsanity.com/paper/2106.03927/) (2021)
- [Neural Auto-Curricula](https://mlsanity.com/paper/2106.02745/) (2021)

## Abstract (arXiv)

Finding approximate Nash equilibria in zero-sum imperfect-information games is challenging when the number of information states is large. Policy Space Response Oracles (PSRO) is a deep reinforcement learning algorithm grounded in game theory that is guaranteed to converge to an approximate Nash equilibrium. However, PSRO requires training a reinforcement learning policy at each iteration, making it too slow for large games. We show through counterexamples and experiments that DCH and Rectified PSRO, two existing approaches to scaling up PSRO, fail to converge even in small games. We introduce Pipeline PSRO (P2SRO), the first scalable general method for finding approximate Nash equilibria in large zero-sum imperfect-information games. P2SRO is able to parallelize PSRO with convergence guarantees by maintaining a hierarchical pipeline of reinforcement learning workers, each training against the policies generated by lower levels in the hierarchy. We show that unlike existing methods, P2SRO converges to an approximate Nash equilibrium, and does so faster as the number of parallel workers increases, across a variety of imperfect information games. We also introduce an open-source environment for Barrage Stratego, a variant of Stratego with an approximate game tree complexity of 1050. P2SRO is able to achieve state-of-the-art performance on Barrage Stratego and beats all existing bots. Experiment code is available athttps://github.com/JBLanier/pipeline-psro.