Self-Play PSRO: Toward Optimal Populations in Two-Player Zero-Sum Games

Stephen McAleer, Jb Lanier, Kevin Wang, Pierre Baldi, Roy Fox, Tuomas Sandholm

TL;DR

Policy Space Response Oracles (PSRO) find Nash equilibria by iteratively adding deterministic best responses to a population, but this process can be painfully slow in games requiring complex mixed strategies. This paper introduces Self-Play PSRO (SP-PSRO), which accelerates convergence by adding approximately optimal stochastic (mixed) policies to the population. By training this new strategy off-policy alongside the standard best response, SP-PSRO drastically reduces exploitability in just a few iterations without requiring extra environment experience.

What Problem Does This Paper Address?

Finding Nash equilibria in large, competitive two-player zero-sum games (like StarCraft or Poker) is a foundational challenge in game theory and AI. Algorithms based on the Double Oracle framework, such as PSRO and Anytime PSRO (APSRO), solve this by maintaining a population of policies and iteratively adding a pure (deterministic) best response to the opponent's current population mixture.

However, many games require players to mix over a vast number of pure strategies to remain unexploitable (e.g., Rock-Paper-Scissors). Because standard PSRO only adds one deterministic strategy at a time, it can suffer from terrible exploitability in early iterations and may need to expand almost every pure strategy in the game before converging.

Methods

SP-PSRO addresses this bottleneck by adding mixed strategies directly to the population. During each main iteration, three training processes unfold concurrently:

  1. Opponent Best Response ($\beta_{-i}$): Updates via reinforcement learning against the current population distribution.
  2. Restricted Distribution ($\pi^r_i$): A meta-solver updates the distribution over the population via a no-regret algorithm against the opponent's best response.
  3. New Stochastic Strategy ($\nu_i$): A new strategy is trained via off-policy reinforcement learning to best-respond directly to the opponent's best response.

At the end of the iteration, SP-PSRO adds two policies to the population: the standard pure best response ($\beta_i$) and the time-average of the new stochastic strategy ($\bar{\nu}_i$). Because the new strategy is trained off-policy using the exact same experience gathered during the best-response training, SP-PSRO achieves this without requiring any additional environment samples.

Figure 1: SP-PSRO. In this diagram we show how SP-PSRO works within an iteration from the perspective of the column player. The fixed population is shown in blue and the new strategy is shown in green. Every inner iteration, three things happen. (1) The opponent best response updates toward a best response to the current distribution over both the fixed population and the new strategy. (2) The new strategy updates toward a best response against the opponent best response. (3) The restricted distribution updates via no regret against the opponent best response. In the final iteration, the time-average of the new strategy and the player’s best response to the opponent’s restricted distribution (which is trained in a symmetric manner) are added to the population and the cycle starts again.

Datasets

The authors evaluate SP-PSRO across a diverse suite of competitive environments provided by the OpenSpiel framework:

  • Normal-Form Games: A 50-action "Big Rock-Paper-Scissors" game, randomly generated matrix games, and restricted game matrices extracted from AlphaStar, Connect 4, 5-3 Blotto, and Hex-3.
  • Extensive-Form Games (Tabular): Leduc Poker (9,457 states), Tiny Battleship (1,573 states), 4-Repeated Rock-Paper-Scissors (9,841 states), and Goofspiel (18,426 states).
  • Deep RL Environments: Liar's Dice, Small Battleship, and 4x Repeated RPS, evaluated using Double Deep Q-Networks (DDQN) for function approximation.

Key Insights and Ideas

  • The Power of Mixing Early: Pure strategies are easily countered. Adding a mixed strategy—even a rough approximation of one—can lower a population's exploitability far more effectively than any single deterministic strategy can.
  • Free Lunch via Off-Policy Learning: You don't need extra environment interactions to learn a mixed strategy. By training the new strategy off-policy on the replay buffer of experience generated during the opponent's best-response training, SP-PSRO gains a powerful mixed strategy for "free" in terms of sample complexity.
  • Anytime Framework Integration: Simply doing self-play isn't enough; combining it with APSRO's no-regret restricted distribution tracking ensures that the opponent's best response doesn't just exploit a static target, forcing meaningful exploration of the strategy space.

Key Results

SP-PSRO consistently outperforms both PSRO and APSRO in convergence speed and early-iteration exploitability:

  • Instant Convergence in Matrix Games: In games like Big RPS, 5-3 Blotto, and the AlphaStar restricted game, SP-PSRO drops exploitability to near zero in the very first few iterations, whereas PSRO and APSRO take dozens of iterations to slowly grind it down.
  • Tabular Superiority: In extensive-form games using tabular Q-learning (e.g., Leduc Poker), SP-PSRO shows a drastic improvement in performance starting from the first iteration.
  • Sample-Efficient Deep RL: When scaled to deep reinforcement learning with DDQN, SP-PSRO remains highly sample-efficient, outperforming baselines significantly in early-iteration exploitability on Liar's Dice and Repeated RPS.

Limitations and Future Work

  • Late-Game Plateaus: Because adding more strategies increases the action space for the no-regret meta-solver, it can become harder to learn the restricted distribution. This sometimes causes SP-PSRO to plateau at a slightly higher exploitability level than APSRO in later iterations. Currently, the authors mitigate this by manually switching to APSRO after a set number of iterations.
  • Compute Overhead: While sample complexity (environment steps) remains identical to APSRO, training the extra neural network off-policy increases the computational and wall-clock time cost.
  • Unprincipled Inner Loop: The self-play heuristic used to generate the new mixed strategy lacks formal convergence guarantees to a Nash equilibrium within that sub-step. Future work could explore integrating more rigorous regret-minimization techniques, like Monte-Carlo CFR, into the inner loop or combining SP-PSRO with extensive-form double oracle algorithms like XDO and NXDO.

Summary updated

Abstract

In competitive two-agent environments, deep reinforcement learning (RL) methods based on the \emph{Double Oracle (DO)} algorithm, such as \emph{Policy Space Response Oracles (PSRO)} and \emph{Anytime PSRO (APSRO)}, iteratively add RL best response policies to a population. Eventually, an optimal mixture of these population policies will approximate a Nash equilibrium. However, these methods might need to add all deterministic policies before converging. In this work, we introduce \emph{Self-Play PSRO (SP-PSRO)}, a method that adds an approximately optimal stochastic policy to the population in each iteration. Instead of adding only deterministic best responses to the opponent's least exploitable population mixture, SP-PSRO also learns an approximately optimal stochastic policy and adds it to the population as well. As a result, SP-PSRO empirically tends to converge much faster than APSRO and in many games converges in just a few iterations.
BibTeX
@misc{mcaleer2022self,
  author = {Stephen McAleer and JB Lanier and Kevin Wang and Pierre Baldi and Roy Fox and Tuomas Sandholm},
  title = {{Self-Play PSRO: Toward Optimal Populations in Two-Player Zero-Sum Games}},
  year = {2022},
  eprint = {2207.06541},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2207.06541},
}
Figure