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:
- Opponent Best Response ($\beta_{-i}$): Updates via reinforcement learning against the current population distribution.
- 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.
- 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.
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