Research map / Multi-agent systems and games / Games and equilibria
Accelerate Multi-Agent Reinforcement Learning in Zero-Sum Games with Subgame Curriculum Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes SACL, a subgame curriculum learning method for MARL in zero-sum games that resets agents to buffered visited states, selects subgames via a bias-plus-variance value-change metric, and samples them with a farthest-point-sampled particle buffer on top of MAPPO.
Problem
Learning Nash equilibrium in complex zero-sum games with MARL is computationally expensive, and existing curricula only vary opponents, not the starting states of the game.
Approach
Generate a curriculum over subgames (games started from specific states) by prioritizing states with fast value change and high value uncertainty, approximating the squared distance to NE values without knowing the NE, and sampling them from a particle buffer that is kept diverse via farthest point sampling.
Key results
- In GRF, SACL achieves approximate exploitability of 0.35 on pass and shoot versus 0.48 for self-play and 0.80 for PSRO.
- In hide-and-seek quadrant, SACL produces all four emergent stages using about 50% of the samples MAPPO with self-play needs.
- On the RPS(n) toy game, the sample complexity drops from exponential to linear in n when subgames are trained in a learned order.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SACL subgame curriculum instead of SP | MAPPO · GRF pass and shoot | approximate exploitability: 0.48 -> 0.35 | Helped |
| Use SACL subgame curriculum instead of SP | MAPPO · GRF run pass and shoot | approximate exploitability: 0.68 -> 0.60 | Helped |
| Use SACL subgame curriculum instead of SP | MAPPO · GRF 3 vs 1 with keeper | approximate exploitability: 0.83 -> 0.45 | Helped |
| Add the full bias-plus-variance subgame sampling metric instead of bias-only sampling (ablation) | SACL in MPE hard predator-prey · MPE hard predator-prey | approximate exploitability | Helped |
| Add the full bias-plus-variance subgame sampling metric instead of variance-only sampling (ablation) | SACL in MPE hard predator-prey · MPE hard predator-prey | approximate exploitability | Helped |
| Replace the full bias-plus-variance metric with uniform sampling (ablation) | SACL in MPE hard predator-prey · MPE hard predator-prey | approximate exploitability | Mixed |
| Replace the particle-based sampler with GAN state generation (ablation) | SACL in MPE hard predator-prey · MPE hard predator-prey | approximate exploitability | Hurt |
| Replace the particle-based sampler with GMM state generation (ablation) | SACL in MPE hard predator-prey · MPE hard predator-prey | approximate exploitability | Hurt |
| Replace FPS buffer updates with random state retention (ablation) | SACL in MPE hard predator-prey · MPE hard predator-prey | approximate exploitability | Hurt |
| Replace FPS buffer updates with greedy highest-weight state retention (ablation) | SACL in MPE hard predator-prey · MPE hard predator-prey | approximate exploitability | Hurt |
| Use SACL instead of MAPPO self-play | MAPPO in HnS quadrant · HnS quadrant | environment samples to NE convergence: 50% fewer samples | Helped |
| Increase subgame sampling probability from too small a value to the selected mixed sampling approach (ablation) | SACL · MPE hard predator-prey | approximate exploitability | Helped |
Surprising findings
- Self-play does not converge to a near-NE policy in the hard MPE predator-prey setting due to large initial distance between predator and prey.
Limitations
- Requires the environment to be resettable to arbitrary intermediate states.
- The sampling metric is derived for zero-sum games and does not directly extend to general-sum games.
- Exploitability is approximated by training best-response policies, so it is only an approximation of the true exploitability.
Experimental setup
Datasets: Multi-Agent Particle Environment predator-prey Google Research Football academy scenarios hide-and-seek quadrant
Benchmarks: MPE predator-prey Google Research Football pass and shoot Google Research Football run pass and shoot Google Research Football 3 vs 1 with keeper hide-and-seek quadrant
Metrics: approximate exploitability samples to convergence cross-play payoff
Baselines: self-play fictitious self-play neural replicator dynamics policy-space response oracles VACL GAN-based state generator GMM-based state generator
Builds on: MAPPO self-play policy-space response oracles minimax-Q prioritized experience replay
Closest papers by meaning
- Offline Fictitious Self-Play for Competitive Games (AAAI 2026 · similarity 0.89)
- Provable Memory Efficient Self-Play Algorithm for Model-free Reinforcement Learning (ICLR 2024 · similarity 0.87)
- Foundations of Multi-Agent Learning in Dynamic Environments: Where Reinforcement Learning Meets Strategic Decision-Making (AAAI 2025 · similarity 0.87)
- A-PSRO: A Unified Strategy Learning Method with Advantage Metric for Normal-form Games (ICML 2025 · similarity 0.87)
- Sample-Efficient Multi-Agent RL: An Optimization Perspective (ICLR 2024 · similarity 0.87)
- Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.