Source-linked AI summary
A Survey on Self-play Methods in Reinforcement Learning
Ruize Zhang, Zelai Xu, Chengdong Ma, Chao Yu, Wei-Wei Tu, Wenhao Tang, Shiyu Huang, Deheng Ye, Wenbo Ding, Yaodong Yang, Yu Wang
TL;DR
Self-play has achieved notable success in complex non-cooperative domains, but MARL lacks a comprehensive perspective capturing its breadth and depth. This survey organizes the field through a unified framework and classification of self-play algorithms, while highlighting unresolved theoretical and scalability challenges.
Problem
Despite self-play’s success in non-cooperative domains, a comprehensive perspective capturing its breadth and depth remains lacking in MARL.
Method
The survey presents a unified framework and categorizes existing self-play algorithms into four main categories.
Results
Self-play has demonstrated remarkable success in non-cooperative domains including Go, chess, poker, and complex video games.
Takeaways & Limitations
The survey provides a structured roadmap for understanding self-play methods and their applications across non-cooperative domains.
Takeaways & Limitations
Convergence or optimality remains difficult to formally characterize within standard game-theoretic frameworks.
Abstract
from arXiv · showhide
Self-play, a learning paradigm where agents iteratively refine their policies by interacting with historical or concurrent versions of themselves or other evolving agents, has shown remarkable success in solving complex non-cooperative multi-agent tasks. Despite its growing prominence in multi-agent reinforcement learning (MARL), such as Go, poker, and video games, a comprehensive and structured understanding of self-play remains lacking. This survey fills this gap by offering a comprehensive roadmap to the diverse landscape of self-play methods. We begin by introducing the necessary preliminaries, including the MARL framework and basic game theory concepts. Then, it provides a unified framework and classifies existing self-play algorithms within this framework. Moreover, the paper bridges the gap between the algorithms and their practical implications by illustrating the role of self-play in different non-cooperative scenarios. Finally, the survey highlights open challenges and future research directions in self-play.
1 Introduction
Non-cooperative MARL is difficult because agents have conflicting objectives and lack the shared rewards that support centralized training, worsening non-stationarity. Self-play addresses these challenges by iteratively improving policies against evolving opponents, motivating this survey’s systematic roadmap of methods, applications, and open problems.
- Non-cooperative MARL is harder than cooperative settings because conflicting objectives remove shared rewards and aggravate non-stationarity.The absence of a shared reward prevents effective centralized training, which can mitigate non-stationarity in cooperative settings.
- Self-play trains agents against evolving opponents, including historical or concurrent versions of themselves or other agents.Vanilla self-play specifically uses the latest version of the agent, while the broader paradigm permits opponent distributions.
- Self-play has succeeded in non-cooperative domains including Go, chess, poker, and complex video games, developing strategies that surpass human expertise.
- Self-play remains limited by potential convergence to suboptimal strategies and significant computational requirements.
- Existing surveys provide valuable algorithmic, PSRO-specific, or theoretical perspectives but do not comprehensively cover self-play’s breadth and depth.This survey addresses that gap with a systematic roadmap of self-play algorithms in non-cooperative MARL.
- The survey introduces MARL and game-theory preliminaries, proposes a unified four-category framework, analyzes applications, and identifies open challenges and future directions.Its application analysis connects self-play algorithms with different non-cooperative scenarios.
2 Preliminaries
The preliminaries formulate MARL through partially observable Markov games and introduce game-theoretic representations and strategic relationships relevant to self-play.
- 2.1 MARL Framework: Partially observable Markov games model multiple agents receiving individual observations while interacting through shared states, actions, transitions, rewards, and discounting.
- 2.1 MARL Framework: Agents select actions from stochastic policies, receive rewards after environment transitions, and seek to maximize expected discounted cumulative rewards.
- 2.2 Game Theory: Normal-form games encode strategies and payoffs directly, whereas extensive-form games represent sequential decisions, information availability, and game-tree structure.
- 2.2 Game Theory: Meta-games abstract interactions over entire policies, with players choosing policies and meta-strategies assigning mixed strategies over the policy population.
- 2.2 Game Theory: The survey distinguishes transitive strategy orderings from non-transitive cyclic relationships, restricting its analysis to two-player zero-sum symmetric games.
3 Algorithms
The algorithms section organizes self-play methods through a unified framework designed to express diverse algorithmic families and support comparison and future design.
- 3 Algorithms: The proposed framework aims to provide greater expressivity and generalization capabilities while remaining illustrated for symmetric games.
- 3 Algorithms: Self-play algorithms are categorized into traditional self-play, PSRO, ongoing-training-based, and regret-minimization-based series.
- 3 Algorithms: The survey compares representative classic algorithms within the framework and analyzes classification rationale, prior frameworks, and design insights for future research.
3.1 Framework Definition
The unified framework represents self-play through policy populations, opponent-sampling interactions, oracle updates, evaluation, and meta-strategy revision.
- 3.1 Framework Definition: The framework maintains a policy population and interaction matrix, repeatedly trains policies against sampled opponents, evaluates the population, and updates opponent sampling.
- 3.1 Framework Definition: Policy populations use lazy initialization with placeholders or immediate initialization with real random or pretrained policies.
- 3.1 Framework Definition: The interaction matrix stores opponent-policy distributions, can be viewed as directed interaction graphs in two-player settings, and initially receives zero entries before updates.
- 3.1 Framework Definition: The framework separates standard and ongoing training and accommodates optional evaluation, buffers, and meta-strategy updates across multiple epochs.
- 3.1 Framework Definition: The oracle abstracts policy improvement through best-response, approximate best-response, or specialized diversity-oriented procedures, with RL, evolution, and regret-minimization implementations.
- 3.1 Framework Definition: Evaluation produces policy-performance representations such as Elo ratings or payoff tensors, which a meta-strategy solver maps into a new interaction matrix.
3.2 Traditional Self-Play Algorithms
Traditional self-play improves policies by repeatedly training against current or historical versions, with variants differing in how opponents are sampled and retained.
- Traditional self-play repeatedly trains agents against themselves or policies from different iterations, enabling strategy exploration and more robust decision-making.
- Integration into Our Framework: The framework models traditional self-play with a growing policy population, lazy initialization, no policy conditioning, and generally simple interaction matrices.Only inactive policies are trained in each iteration, while K bounds the number of active policies.
- Integration into Our Framework: Under the two-player symmetric-game assumption, traditional self-play produces a lower triangular interaction matrix because policy m trains only against already-trained policies n≤m.
- Vanilla Self-Play: Vanilla self-play is effective in transitive games but can cycle in non-transitive games, create nonstationarity, and become trapped in a local optimum.
- Vanilla Self-Play: Off-policy self-play reuses samples generated by earlier policies, helping leverage past experience and maintain more stationary training.
3.3 PSRO Series
The PSRO series expands a policy population with response oracles and uses increasingly sophisticated meta-strategy solvers to represent strategic solutions across games.
- PSRO gradually expands the policy space by adding oracle policies that approximate optimal responses to opponents’ current meta-strategies.
- Integration into Our Framework: The framework represents PSRO with a growing population and opponent-sampling strategies, while PSRO interaction matrices remain lower triangular under the shared assumption.
- Double Oracle: Double Oracle computes best responses to restricted-game Nash equilibria and can theoretically reach the full-game Nash equilibrium in two-player normal-form games.
- Double Oracle: In rock-paper-scissors, Double Oracle adds best responses until the final Nash equilibrium is uniform over the three policies, indicating convergence.
- PSRO Extensions: PSRO uses more sophisticated meta-strategy solvers than traditional self-play to capture game structure, but this comes at higher computational cost.
- PSRO Extensions: PSRO variants target faster convergence, computational tractability, policy diversity, and broader game settings through alternative equilibria, parallelization, and diversity mechanisms.Examples include CE/CCE-based solvers, mean-field PSRO, α-PSRO, JPSRO, Pipeline PSRO, and diversity-oriented variants.
3.4 Ongoing-Training-Based Series
Ongoing-training methods repeatedly update active policies rather than training only newly added policies, producing denser interactions and supporting transfer across a population.
- Ongoing-training methods address truncated response quality and redundant relearning by repeatedly training all active policies.
- Framework Properties: Because policies can train against already updated peers, their interaction matrix is generally not lower triangular.
- Applications: FTW trains multiple policies in parallel, sampling teammates and adversaries from the population, which creates a densely connected interaction graph.
- NeuPL: NeuPL uses a unified conditional network adjusted to meta-game mixture strategies, enabling transfer learning across policies.
- Simplex-NeuPL: Simplex-NeuPL extends NeuPL toward any-mixture optimality by conditioning policies on strategies sampled from a population simplex, enhancing robustness.
3.5 Regret-Minimization-Based Series
Regret-minimization self-play minimizes cumulative regret, offers strong guarantees in two-player zero-sum games, and includes CFR variants for improving scalability and convergence.
- Regret-minimization methods minimize cumulative regret over time and are especially supported by theory in two-player zero-sum games.
- Framework Properties: Their interaction matrix is a unit lower shift matrix because each iteration trains against the latest strategy.
- Regret Matching: Regret matching with strategy averaging is proven to converge to a Nash equilibrium in two-player zero-sum games.
- CFR Variants: CFR decomposes extensive-form regret minimization across information sets, while CFR+ and sampling variants reduce update or traversal costs.
- CFR Limitations: Vanilla CFR is limited by full game-tree traversal and substantial storage for counterfactual regrets, especially in large games.
- CFR Variants: Sampling methods such as MCCFR shorten iterations by sampling histories while matching vanilla CFR’s counterfactual regrets in expectation.
3.6 Reassessment of the Framework
The survey reassesses self-play through a unified framework that distinguishes algorithmic categories, integrates regret minimization, and exposes design directions beyond oracle and meta-strategy selection.
- Framework scope: The framework unifies existing self-play algorithms into four categories and supports their comparison, evaluation, and future development.It is presented as more general than prior frameworks and is intended to organize algorithm design and evaluation.
- Algorithmic categories: The four categories differ in population growth, policy updating, and training regime, including traditional self-play, PSRO, ongoing training, and regret minimization.Traditional and PSRO methods generally expand populations, ongoing training follows a different paradigm, and regret minimization optimizes performance across time.
- Algorithmic categories: PSRO uses more complex meta-strategy solvers for game-theoretic tasks, whereas traditional self-play can reduce the computational cost of those solvers.α-PSRO is cited as an example for multiplayer general-sum games.
- Limitations: Regret-minimization methods suit extensive-form imperfect-information games but require substantial memory and lack comparable equilibrium guarantees beyond two-player zero-sum settings.Tracking regret at every information set creates memory overhead, while convergence guarantees to Nash equilibrium remain limited in scope.
- Framework comparison: The framework generalizes NeuPL by separating opponent sampling σ^[k] from the policy condition h(k), increasing expressiveness.σ^[k] specifies how opponents are sampled for policy k, while h(k) conditions the policy more generally than NeuPL.
- Framework novelty: It is the first surveyed self-play framework to integrate regret-minimization-based methods with other self-play paradigms.The survey presents this integration as a significant extension of the framework’s coverage.
- Cross-category integration: Combining regret minimization with PSRO can reduce oracle cost while preserving convergence and rationality in supported settings.ODO’s MWU oracle need not compute a full Nash equilibrium, yet it provably converges in two-player zero-sum normal-form games.
- Future directions: The framework highlights future directions including cross-category hybrids, selective policy retraining, and transferring auxiliary knowledge across agents.Suggested mechanisms include bandit-based oracle scheduling and learnable history kernels that propagate knowledge without external intervention.
4 Empirical Analysis
The survey examines self-play across board, card, and video games, showing how methods adapt to perfect or imperfect information and real-time multi-agent settings.
- Application scope: Self-play applications are organized into board games, card games, and video games according to information structure and interaction dynamics.Board games are typically turn-based and perfect-information, card games usually involve imperfect information, and video games feature real-time actions.
- Board games: AlphaGo, AlphaZero, and MuZero demonstrate self-play’s effectiveness in board games, with MuZero also achieving state-of-the-art Atari performance.The methods progressively reduce reliance on expert data and predefined game rules while combining learned networks with MCTS.
- Board games: DeepNash reaches third place among professional Gravon Stratego players using neural R-NaD and an approximate fixed-point policy.Its four-headed network separately supports value prediction, deployment, piece selection, and displacement.
- Card games: Regret minimization is well suited to imperfect-information card games, although non-regret self-play methods can also perform well.The survey illustrates these settings through Texas Hold’em, DouDiZhu, and Mahjong.
- Card games: DeltaDou achieves expert-level performance in DouDizhu, while LuckyJ reaches 10 dan in Mahjong and defeats human professionals.Suphx also reaches a performance level comparable to expert human players, including 10 dan on Tenhou.
4.3 Video Games
In video games, self-play supports strong performance across real-time strategy, MOBA, and football environments by combining policy populations, exploiters, curricula, and cross-play.
- StarCraft II: AlphaStar dominates 1v1 StarCraft II competitions and defeats professional players using hierarchical self-play with main agents and exploiters.Its league maintains a population of past agents, with different agent types training against complementary opponents.
- MOBA games: OpenAI Five defeats the world champion team in a simplified 17-hero Dota 2 setting using a mixture of vanilla self-play and quality-based opponent sampling.The training mixture uses vanilla self-play with 80% probability and PFSP-like sampling with 20% probability.
- MOBA games: Curriculum self-play learning enables a 40-hero Honor of Kings system to defeat professional teams after staged training and policy distillation.The stages train fixed lineups, distill multiple teachers, and then resume self-play with randomly selected lineups.
- Football: League-style self-play wins the simplified GRF Kaggle competition, and TiZero improves TrueSkill over TiKick while avoiding expert-data reliance.WeKick initializes its opponent pool with reinforcement-learning and GAIL strategies; TiZero combines curriculum learning with FP and PFSP.
- Football: FXP achieves a win rate of over 94% by separating main and counter populations with asymmetric cross-play roles.Counter policies train only against the main population, while main policies play against both populations.
5 Open Problems and Future Work
Self-play methods achieve strong results across games, language models, and simulated real-world tasks, but open problems remain in theoretical guarantees, non-stationarity, scalability, and deployment.
- Theoretical Guarantees: Formal guarantees for convergence or optimality remain limited for successful methods such as AlphaGo, AlphaStar, and OpenAI Five [7] under realistic computational and exploration constraints.Computing even approximate Nash equilibria can be difficult in larger games, motivating alternatives such as correlated equilibrium and α-rank.
- Non-stationarity: Evolving opponent strategies create non-stationary environments, motivating robust self-play that adapts to changing conditions through tools such as opponent modeling.The same strategy can produce different outcomes over time as opponents evolve.
- Scalability and Training Efficiency: Scaling self-play to more teams and players increases interaction complexity, computation, and storage demands for policy pools and regret values.The iterative training process drives computational cost, while regret-minimization methods additionally store regrets for information sets and actions.
- Real-world Applications: Real-world deployment remains constrained because iterative trial-and-error is expensive and can produce impractical or unsafe behavior outside controlled environments.Most recent work therefore uses simulators, while sample-efficient online training is proposed to reduce reliance on elaborate Sim2Real pipelines.
6 Conclusion
The survey presents self-play as iterative policy refinement against historical or concurrent agents and organizes its methods through a unified taxonomy. It connects this taxonomy to applications across games while identifying persistent challenges.
- Self-play iteratively refines policies through interaction with historical or concurrent versions of agents or other evolving agents.
- The survey introduces MARL and game-theory foundations, then classifies self-play algorithms into four main categories within a unified framework.
regret-minimization-based series.
The survey integrates four self-play groups within a common framework and compares them to derive design insights. It also connects these methods to applications while highlighting unresolved challenges and future directions.
- regret-minimization-based series.: The four self-play groups are integrated into a common framework and compared to draw design insights for future research.
- regret-minimization-based series.: The survey analyzes self-play across board games, card games, and video games, linking algorithmic organization with practical scenarios.
- regret-minimization-based series.: Despite broad successes, convergence to suboptimal strategies and substantial computational demands remain challenges, alongside opportunities involving LLMs and real-world applications.
- regret-minimization-based series.: The survey positions self-play as a source of insights and tools for developing advanced AI systems and as a guide for researchers and practitioners.