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

Abstract

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 $10^{50}$. 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.

arXiv commentSM and JL contributed equally

References in corpus (9)

• Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor
• Dota 2 with Large Scale Deep Reinforcement Learning
• Human-level performance in first-person multiplayer games with population-based deep reinforcement learning
• Deep Reinforcement Learning: An Overview
• Soft Actor-Critic for Discrete Action Settings
• Deep Reinforcement Learning from Self-Play in Imperfect-Information Games
• Open-ended Learning in Symmetric Zero-sum Games
• DREAM: Deep Regret minimization with Advantage baselines and Model-free learning
• The Advantage Regret-Matching Actor-Critic

Cited by in corpus (6)

• Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learning
• Distributed Deep Reinforcement Learning: A Survey and A Multi-Player Multi-Agent Learning Toolbox
• An Empirical Study on Google Research Football Multi-agent Scenarios
• XDO: A Double Oracle Algorithm for Extensive-Form Games
• Modelling Behavioural Diversity for Learning in Open-Ended Games
• Search in Imperfect Information Games