Research map / Learning theory and algorithms / Submodular and game algorithms
A-PSRO: A Unified Strategy Learning Method with Advantage Metric for Normal-form Games
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 A-PSRO, a PSRO variant that uses an "advantage" metric (best-response-based value of a strategy) as the strategy-exploration objective, with a lookahead update, for normal-form zero-sum and general-sum games.
Problem
Computing Nash equilibria in large-scale normal-form games with open-ended learning (PSRO variants) is slow because existing methods lack an efficient metric for whether a new strategy improves toward equilibrium, and general-sum games have multiple equilibria with different rewards.
Approach
Defines an advantage function V_i(π_i) = U_i(π_i, best response opponent action) whose maximum is zero exactly at Nash equilibrium in symmetric zero-sum games; new strategies are generated by a lookahead step (1-d)θ + d·Δπ that maximizes this advantage, unifying zero-sum convergence and reward-maximizing equilibrium selection in general-sum games.
Key results
- In zero-sum games A-PSRO reduces exploitability by up to several orders of magnitude relative to PSRO, P-PSRO, DPP-PSRO, UDF-PSRO and PSD-PSRO (Figure 2).
- In advanced Staghunt and RSP general-sum games, A-PSRO consistently reaches the highest-reward equilibrium while baselines stagnate in suboptimal equilibria (Figure 4).
- A-PSRO reaches exploitability 1e-2 in fewer than 50 iterations in under 1 minute, and fictitious play on its population reaches 1e-4 in about 1e3 iterations versus about 1e4 directly.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use A-PSRO instead of the compared PSRO algorithms | PSRO strategy learning · Zero-sum games | exploitability | Helped |
| Use A-PSRO instead of the compared PSRO algorithms | PSRO strategy learning · General-sum games | joint reward | Helped |
| Remove the LookAhead module (ablation) | A-PSRO · Zero-sum games | exploitability | Hurt |
| Remove the diversity module (ablation) | A-PSRO · Transitive game | exploitability | Helped |
| Remove the diversity module (ablation) | A-PSRO · Games with strong non-transitive dimensions | exploitability | Hurt |
| Combine LookAhead with diversity exploration (ablation) | A-PSRO · Zero-sum games | exploitability | Helped |
Surprising findings
- Without the diversity module, A-PSRO performs better than full A-PSRO in the transitive game, and the lookahead module is shown to matter most in all games.
- A-PSRO shows higher exploitability than diversity-based baselines in early iterations because subgames do not yet cover the strategy space.
Limitations
- In general-sum games, A-PSRO must explore multiple equilibrium oracles, increasing computational cost.
- Advantage function is non-convex in general-sum games, so guarantees are only local; the neural-network approximation extension is only theoretical/preliminary.
- Early-stage exploitability is higher than diversity-based methods because subgames do not cover the strategy space.
Experimental setup
Datasets: randomly generated normal-form games AlphaStar meta-game Elo game simplified Go game advanced Staghunt advanced RSP
Benchmarks: AlphaStar meta-game transitive game Elo game with noise simplified Go advanced Staghunt advanced RSP randomly generated general-sum games multi-player zero-sum and general-sum games
Metrics: exploitability joint reward running time
Baselines: PSRO P-PSRO DPP-PSRO UDF-PSRO PSD-PSRO
Builds on: PSRO double oracle fictitious play pipeline PSRO diversity-based PSRO (PSD-PSRO, UDF-PSRO, DPP-PSRO)
Closest papers by meaning
- Global Policy-Space Response Oracles for Two-Player Zero-Sum Games (ICML 2026 · similarity 0.91)
- A Generalized Training Approach for Multiagent Learning (ICLR 2020 · similarity 0.91)
- Pipeline PSRO: A Scalable Approach for Finding Approximate Nash Equilibria in Large Games (NeurIPS 2020 · similarity 0.90)
- No-regret Learning in Harmonic Games: Extrapolation in the Face of Conflicting Interests (NeurIPS 2024 · similarity 0.87)
- Accelerate Multi-Agent Reinforcement Learning in Zero-Sum Games with Subgame Curriculum Learning (AAAI 2024 · similarity 0.87)
- From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications (NeurIPS 2025 · 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.