Global Policy-Space Response Oracles for Two-Player Zero-Sum Games

The Policy-Space Response Oracles (PSRO) framework scales equilibrium computation to large zero-sum games by iteratively expanding a restricted strategy set using deep reinforcement learning (DRL). A central challenge is to construct, under limited computational budgets, a small strategy population whose induced game well approximates the full game. Existing PSRO variants typically expand the population using best responses to meta-strategies computed from restricted-game payoffs, which can lead to inefficient expansions that provide limited global improvement. We propose to guide population expansion by directly evaluating the post-expansion population quality. Specifically, we adopt Population Exploitability (PE) to measure how well a restricted strategy set represents the full game, and introduce a two-phase exploration--selection framework that explicitly minimizes PE during expansion. We instantiate this framework as Global PSRO, a practical DRL-based algorithm that efficiently generates candidate responses and estimates PE via parameter-sharing conditional neural networks. Experiments across multiple two-player zero-sum games show that Global PSRO achieves lower exploitability and approximates Nash equilibria with significantly fewer policy iterations than prior PSRO methods. The experimental code is available at https://github.com/Zhangjy1997/GlobalPSRO.

Imagine teaching an AI to play a difficult competitive game. It cannot learn every possible tactic at once, so it builds a toolbox of strategies step by step. The usual approach is to add a strategy that works best against the AI’s current toolbox of strategies. But this view can be too narrow: a strategy that works well against the current toolbox may not do much to make the toolbox as a whole stronger. Our paper proposes a more forward-looking way to grow that toolbox. It generates several possible new strategies, estimates how strong the toolbox would become after adding each one, and keeps the one that most strengthens the collection as a whole. Across a range of competitive games, this approach helps the AI build stronger strategy sets more efficiently than previous methods.