Pipeline PSRO: A Scalable Approach for Finding Approximate Nash Equilibria in Large Games
This addresses the scalability problem for researchers and practitioners in game theory and AI, offering a general solution for large games like Barrage Stratego with a complexity of approximately 10^50, though it builds incrementally on prior PSRO methods.
The paper tackles the challenge of finding approximate Nash equilibria in large zero-sum imperfect-information games by introducing Pipeline PSRO (P2SRO), a scalable method that parallelizes training with convergence guarantees, achieving state-of-the-art performance on Barrage Stratego and beating all existing bots.
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.