TL;DR
This paper introduces Policy Space Diversity PSRO (PSD-PSRO), a new framework for solving complex non-transitive games. By shifting the focus from diversifying payoffs to diversifying the actual policy space (the "Policy Hull"), the authors provide a mathematically grounded approach that guarantees convergence to a Nash Equilibrium where previous methods often stalled.
What Problem Does This Paper Address?
In "non-transitive" games, strategies follow cyclic patterns—think Rock-Paper-Scissors, where no single strategy is king. To solve these, researchers use Policy-Space Response Oracles (PSRO), an algorithm that iteratively grows a population of strategies to find a Nash Equilibrium (NE).
The challenge is that standard PSRO often gets stuck in "cycles" or fails to explore the strategy space effectively. While previous work tried to fix this by encouraging "diversity," they usually defined diversity based on payoffs (the "gamescape"). The authors of this paper prove a frustrating reality: a population that looks diverse in terms of payoffs isn't necessarily closer to a Nash Equilibrium. In fact, enlarging the payoff space can be "deceptive," leading the algorithm away from the optimal solution.
Methods
The authors propose a shift in perspective from the payoff space to the Policy Hull (PH)—the set of all possible mixed strategies that can be formed from the current population.
- Population Exploitability (PE): They introduce a new metric to quantify a population's strength. Unlike standard exploitability, PE measures the best possible performance a player can achieve by choosing any mixture of their current strategies.
- Policy Space Diversity (PSD): They develop a diversity regularizer that explicitly encourages the algorithm to find new strategies that are far away from the current Policy Hull.
- Sequence-Form Representation: To make this practical, they represent policies using "sequence-form," which maps a policy to the probability of reaching specific state-action pairs. This representation is a "fine" representation (a bijection), ensuring that if two representations are different, the policies are truly different.
- Optimization: They integrate this diversity term into the Reinforcement Learning (RL) process used to find "Best Responses." The final objective for the RL agent is a weighted sum of the expected payoff and the distance (measured via KL-divergence) from the existing policy population.
Datasets
The researchers evaluated PSD-PSRO on a variety of benchmarks representing different types of strategic challenges:
- AlphaStar888: An empirical game matrix generated from 888 professional-level StarCraft II agents.
- Non-Transitive Mixture Game: A synthetic 2D game involving 7 Gaussian "humps" where agents must navigate a cyclic landscape.
- Leduc Poker: A standard benchmark for imperfect-information games.
- Goofspiel: A complex, multi-stage simultaneous move card game (tested with 5-card and 8-card variants).
- Disc Game: A geometric game used primarily for visualizing how the Policy Hull expands over time.
Key Insights and Ideas
- The "Gamescape" Trap: The paper’s most significant theoretical contribution is proving that enlarging the "gamescape" (payoff vectors) is neither sufficient nor necessary for reducing exploitability. You can add a strategy that makes your payoff matrix look "diverse" while actually making your overall population weaker.
- Policy Hull > Gamescape: Expanding the Policy Hull (the space of strategies) is a much more reliable proxy for progress. A larger Policy Hull is mathematically guaranteed to lead to lower Population Exploitability.
- Convergence Guarantee: The authors prove that if PSD-PSRO converges, it is guaranteed to have found a full-game Nash Equilibrium. This is a major step up from previous diversity-enhancing variants like $PSRO_{rN}$, which can converge to sub-optimal points.
Key Results
- Lower Exploitability: Across all games, PSD-PSRO consistently reached lower exploitability levels than the original PSRO and other state-of-the-art variants (like Pipeline-PSRO or DPP-PSRO).
- Dominance in Goofspiel: In the 8-card Goofspiel tournament, PSD-PSRO achieved a 62% average win rate against all other competing algorithms.
- Efficiency: In AlphaStar888, PSD-PSRO converged significantly faster and to a much more stable Nash Equilibrium than its predecessors.
- Low Overhead: Despite the extra math, the diversity calculation only accounted for about 7.9% of the total computational time in Leduc Poker.
Limitations and Future Work
- Hyperparameter Sensitivity: The algorithm relies on a diversity weight ($\lambda$). If $\lambda$ is too high, the agent ignores payoffs; if it's too low, it doesn't diversify. Currently, this requires manual tuning.
- Scaling to Massive Games: While it works on Goofspiel and Leduc Poker, the authors suggest that future work is needed to scale the sequence-form representation to "extra-large" games like full-scale Mahjong or Chess.
- Adaptive Diversity: The authors suggest using "online bandits" to automatically tune the diversity weight during training as a promising future direction.
Summary updated