Global Policy-Space Response Oracles for Two-Player Zero-Sum Games
For researchers computing equilibria in large zero-sum games, Global PSRO provides a more efficient population expansion method that reduces computational cost.
Global PSRO introduces a two-phase exploration-selection framework that minimizes Population Exploitability to guide strategy population expansion, achieving lower exploitability and approximating Nash equilibria with significantly fewer policy iterations than prior PSRO methods in 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.