Global Policy-Space Response Oracles for Two-Player Zero-Sum Games
Junyu Zhang, Feihong Yang, Jian Wang, Chao Wang, Xudong Zhang · 2026
Read Global Policy-Space Response Oracles for Two-Player Zero-Sum Games by Junyu Zhang, Feihong Yang, Jian Wang, Chao Wang, Xudong Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-28273.txt.
Introduction
Zhang and colleagues find game equilibria in big zero-sum games by growing strategy pools toward overall quality, not just best replies. Their Global PSRO setup scores small pools by how exploitable they stay, then probes and picks new moves to shrink that gap. On several two-player games it hit near-Nash play in far fewer rounds than older methods.
Catalog record
| CREATOR | Junyu Zhang, Feihong Yang, Jian Wang, Chao Wang, Xudong Zhang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 98513 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.28273
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Global Policy-Space Response Oracles for Two-Player Zero-Sum Games Junyu Zhang, Feihong Yang, Jian Wang, Chao Wang, Xudong Zhang Abstract 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 . 1 Introduction Computing equilibria in large-scale games is challenging due to enormous strategy spaces and the intractability of exhaustive analysis ( 17 ; 2 ) . The Policy-Space Response Oracle (PSRO) framework improves scalability by iteratively solving restricted games over a growing strategy population, where best responses (BR) are often learned via deep reinforcement learning (DRL) ( 7 ) . A central difficulty in PSRO lies in strategy population construction : how to assemble, under limited computational budgets, a small set of strategies whose induced restricted game faithfully represents the strategic structure of the full game. In standard PSRO, each iteration adds a BR to a meta-strategy computed by a meta-strategy solver (MSS), typically the Nash equilibrium (NE) of the current restricted game. Since the restricted game is only a local approximation, a BR to its equilibrium can be locally strong yet contribute little to improving the approximation quality of the full game, leading to inefficient expansion. Many PSRO variants modify the MSS to encourage exploration or reduce overfitting ( 7 ; 19 ; 18 ; 20 ; 8 ) , but they still rely primarily on restricted-game payoffs and do not explicitly evaluate whether an expansion improves full-game approximation; in the worst case, such restricted-game-based expansions may require adding essentially the entire strategy space to converge (Sec. 3.1 ). Methods that incorporate extra global information, such as Anytime PSRO ( 13 ) , aim to find meta-strategies that are hard for full-game opponents to exploit, yet still expand by responding to a single current meta-strategy without directly assessing the population after expansion. We instead make expansion decisions by explicitly optimizing population quality after adding a candidate strategy. This is directly aligned with the primary goal of PSRO-style methods, namely constructing a small population whose induced game approximates a full game equilibrium. We measure population quality with Population Exploitability (PE), the minimum exploitability achievable by mixtures supported on the population against full-game opponents. This leads to a two-phase exploration–selection framework. In the exploration phase, we generate a batch of candidate responses by training against multiple meta-strategies given by different kinds of MSSs. In the selection phase, we evaluate the PE of each post-expansion population obtained by hypothetically adding a candidate strategy, and select the candidate that minimizes this post-expansion PE. This directly aligns the expansion with improving population-level equilibrium approximation. Furthermore, the PE estimation procedure naturally yields a BR to the selected population mixture in the full game. We also add the BR to the population, which corresponds to executing one standard Anytime-PSRO expansion alongside the selected candidate. Overall, two strategies are obtained in the selection phase to expand the restricted game. We instantiate this framework as Global PSRO , a practical DRL-based algorithm for large-scale two-player zero-sum games. To make multi-candidate training and PE-based selection feasible, we use parameter sharing with conditional policy models for candidate generation and PE estimation, and adopt a regularized PE-based score to make selection robust to PE estimation errors. Experiments across several benchmark games show that Global PSRO reaches substantially better equilibrium approximations than existing PSRO variants under matched interaction budgets. Our contributions can be summarized as follows: • We analyze existing PSRO meta-strategy solvers from the perspective of global information utilization, and show that relying solely on restricted-game information can lead to highly inefficient population expansion. • We formulate strategy population construction as an explicit optimization problem that is directly aligned with the primary objective of PSRO, namely minimizing the PE of the expanded population after each addition, and propose an exploration–selection framework that ranks candidates by their estimated post-expansion PE. • We introduce Global PSRO, a scalable DRL-based instantiation with parameter-shared candidate generation and regularized PE estimation for practical multi-candidate selection, and empirically demonstrate superior iteration and sample efficiency across a range of two-player zero-sum games. 2 Preliminaries 2.1 Games We consider finite n -player normal-form games. A game is defined by a tuple \mathcal{G}=(\mathcal{N},\{\Pi_{i}\}_{i=1}^{n},\{U_{i}\}_{i=1}^{n}) , where \mathcal{N}=\{1,\dots,n\} denotes the set of players, \Pi_{i} is the pure strategy set of player i , and U_{i}:\Pi_{1}\times\cdots\times\Pi_{n}\rightarrow\mathbb{R} is the payoff function. We focus on two-player zero-sum games, where U_{1}=-U_{2} . A two-player game is symmetric if \Pi_{1}=\Pi_{2}=\Pi and the payoff functions are identical up to player exchange, i.e., U_{1}(\pi_{i},\pi_{j})=U_{2}(\pi_{j},\pi_{i}) for all \pi_{i},\pi_{j}\in\Pi . A mixed strategy \sigma_{i}\in\Delta(\Pi_{i}) is a probability distribution over \Pi_{i} , and \sigma=(\sigma_{1},\sigma_{2}) denotes a joint mixed strategy. For \pi_{i}\in\Pi_{i} , we write \sigma_{i}(\pi_{i}) for its probability and \operatorname{supp}(\sigma_{i})=\{\pi_{i}\in\Pi_{i}:\sigma_{i}(\pi_{i})>0\} for the support. The expected payoff to player i under \sigma is denoted by U_{i}(\sigma) . Given an opponent strategy \sigma_{-i} , a (pure) BR of player i is defined as \mathcal{B}_{i}(\sigma_{-i})=\arg\max_{\pi_{i}\in\Pi_{i}}U_{i}(\pi_{i},\sigma_{-i}). (1) 2.2 Restricted Games and Meta-Games PSRO operates by maintaining, for each player i , a restricted strategy set \Pi_{i}^{r}\subseteq\Pi_{i} . The Cartesian product \Pi^{r}=\Pi_{1}^{r}\times\Pi_{2}^{r} induces a restricted game , whose payoff matrix is defined by evaluating U_{i} on strategy profiles in \Pi^{r} . Solving the restricted game yields a meta-strategy \sigma\in\Delta(\Pi^{r}) , typically computed by a MSS such as a NE solver. This restricted game, together with its meta-strategy, is often referred to as the meta-game . Importantly, the meta-game is only an approximation of the full game, and its quality depends entirely on the choice of the restricted strategy set \Pi^{r} . In each iteration of PSRO, new strategies are generated by computing (approximate) BRs to the current meta-strategy, commonly using DRL. These strategies are then added to \Pi^{r} , and the meta-game is recomputed. 2.3 Exploitability and Population Exploitability The exploitability of a joint mixed strategy \sigma is defined as \epsilon(\sigma)=\frac{1}{|\mathcal{N}|}\sum_{i\in\mathcal{N}}\max_{\pi_{i}\in\Pi_{i}}\big[U_{i}(\pi_{i},\sigma_{-i})-U_{i}(\sigma)\big]. (2) A strategy \sigma^{\star} is a NE if and only if \epsilon(\sigma^{\star})=0 . Exploitability is a property of an individual mixed strategy. In contrast, the primary goal of PSRO is to construct restricted strategy populations that approximate the full game well. To measure the approximation quality of a restricted strategy set \Pi^{r} as an approximation of the full game, a commonly used population-level quantity is PE, defined as \mathcal{PE}(\Pi^{r};\mathcal{G})=\min_{\sigma\in\Delta(\Pi^{r})}\epsilon(\sigma). (3) PE measures the smallest exploitability attainable by any mixed strategy whose support