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

• URL: http://arxiv.org/abs/2605.28273v1
• Date: Wed, 27 May 2026 10:18:33 GMT
• Title: Global Policy-Space Response Oracles for Two-Player Zero-Sum Games
• Abstract summary: Policy-Space Response Oracles scales equilibrium computation to large zero-sum games.<n>Population Exploitability measures how well a restricted strategy set represents the full game.<n>Global PSRO approximates Nash equilibria with significantly fewer policy iterations than prior PSRO methods.
• Score: 18.686097245170533
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Policy Abstraction and Nash Refinement in Tree-Exploiting PSRO [10.137357924571262]
  Policy Space Response Oracles (PSRO) interleaves empirical game-theoretic analysis with deep reinforcement learning (DRL) to solve games too complex for traditional analytic methods.<n>Tree-exploiting PSRO (TE-PSRO) is a variant of this approach that iteratively builds a coarsened empirical game model in extensive form.<n>We make two main methodological advances to TE-PSRO that enhance its applicability to complex games of imperfect information.
  arXiv  Detail & Related papers  (2025-02-05T05:48:16Z)
• Iterative Nash Policy Optimization: Aligning LLMs with General Preferences via No-Regret Learning [55.65738319966385]
  We propose a novel online algorithm, iterative Nash policy optimization (INPO)<n>Unlike previous methods, INPO bypasses the need for estimating the expected win rate for individual responses.<n>With an LLaMA-3-8B-based SFT model, INPO achieves a 42.6% length-controlled win rate on AlpacaEval 2.0 and a 37.8% win rate on Arena-Hard.
  arXiv  Detail & Related papers  (2024-06-30T08:00:34Z)
• Neural Population Learning beyond Symmetric Zero-sum Games [52.20454809055356]
  We introduce NeuPL-JPSRO, a neural population learning algorithm that benefits from transfer learning of skills and converges to a Coarse Correlated (CCE) of the game. Our work shows that equilibrium convergent population learning can be implemented at scale and in generality.
  arXiv  Detail & Related papers  (2024-01-10T12:56:24Z)
• Population-size-Aware Policy Optimization for Mean-Field Games [34.80183622480149]
  We study how the optimal policies of agents evolve with the number of agents (population size) in mean-field games. We propose Population-size-Aware Policy Optimization (PAPO), which unifies two natural options (augmentation and hypernetwork) and significantly better performance. PAPO consists of three components: i) the population-size encoding which transforms the original value of population size to an equivalent encoding to avoid training collapse, ii) a hypernetwork to generate a distinct policy for each game conditioned on the population size, andiii) the population size as an additional input to the generated policy.
  arXiv  Detail & Related papers  (2023-02-07T10:16:00Z)
• ApproxED: Approximate exploitability descent via learned best responses [61.17702187957206]
  We study the problem of finding an approximate Nash equilibrium of games with continuous action sets. We propose two new methods that minimize an approximation of exploitability with respect to the strategy profile.
  arXiv  Detail & Related papers  (2023-01-20T23:55:30Z)
• Faster Last-iterate Convergence of Policy Optimization in Zero-Sum Markov Games [63.60117916422867]
  This paper focuses on the most basic setting of competitive multi-agent RL, namely two-player zero-sum Markov games. We propose a single-loop policy optimization method with symmetric updates from both agents, where the policy is updated via the entropy-regularized optimistic multiplicative weights update (OMWU) method. Our convergence results improve upon the best known complexities, and lead to a better understanding of policy optimization in competitive Markov games.
  arXiv  Detail & Related papers  (2022-10-03T16:05:43Z)
• Self-Play PSRO: Toward Optimal Populations in Two-Player Zero-Sum Games [69.5064797859053]
  We introduce emphSelf-Play PSRO (SP-PSRO), a method that adds an approximately optimal policy to the population in each iteration. SP-PSRO empirically tends to converge much faster than APSRO and in many games converge in just a few iterations.
  arXiv  Detail & Related papers  (2022-07-13T22:55:51Z)
• Efficient Policy Space Response Oracles [61.71849698253696]
  Policy Space Response Oracle method (PSRO) provides a general solution to Nash equilibrium in two-player zero-sum games. Central to our development is the newly-introduced of minimax optimization on unrestricted-restricted (URR) games. We report a 50x speedup in wall-time, 10x data efficiency, and similar exploitability as existing PSRO methods on Kuhn and Leduc Poker games.
  arXiv  Detail & Related papers  (2022-01-28T17:54:45Z)
• Anytime Optimal PSRO for Two-Player Zero-Sum Games [17.821479538423155]
  Policy Space Response Oracles (PSRO) is a reinforcement learning algorithm for games that can handle continuous actions. AODO is a double oracle algorithm for 2-player zero-sum games that converges to a Nash equilibrium. We show that our methods achieve far lower exploitability than DO and PSRO and never increase exploitability.
  arXiv  Detail & Related papers  (2022-01-19T16:34:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.