Policy Space Diversity for Non-Transitive Games

Jian Yao, Weiming Liu, Haobo Fu, Yaodong Yang, Stephen McAleer, Qiang Fu, Wei Yang

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.

  1. 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.
  2. 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.
  3. 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.
  4. 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

Abstract

Policy-Space Response Oracles (PSRO) is an influential algorithm framework for approximating a Nash Equilibrium (NE) in multi-agent non-transitive games. Many previous studies have been trying to promote policy diversity in PSRO. A major weakness with existing diversity metrics is that a more diverse (according to their diversity metrics) population does not necessarily mean (as we proved in the paper) a better approximation to a NE. To alleviate this problem, we propose a new diversity metric, the improvement of which guarantees a better approximation to a NE. Meanwhile, we develop a practical and well-justified method to optimize our diversity metric using only state-action samples. By incorporating our diversity regularization into the best response solving of PSRO, we obtain a new PSRO variant, \textit{Policy Space Diversity} PSRO (PSD-PSRO). We present the convergence property of PSD-PSRO. Empirically, extensive experiments on single-state games, Leduc, and Goofspiel demonstrate that PSD-PSRO is more effective in producing significantly less exploitable policies than state-of-the-art PSRO variants.
BibTeX
@inproceedings{yao2023policy,
  author = {Jian Yao and Weiming Liu and Haobo Fu and Yaodong Yang and Stephen McAleer and Qiang Fu and Wei Yang},
  title = {{Policy Space Diversity for Non-Transitive Games}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=PRgvdEbhdH},
}
Figure