Source-linked AI summary
A Generalized Training Approach for Multiagent Learning
Paul Muller, Shayegan Omidshafiei, Mark Rowland, Karl Tuyls, Julien Perolat, Siqi Liu, Daniel Hennes, Luke Marris, Marc Lanctot, Edward Hughes, Zhe Wang, Guy Lever, Nicolas Heess, Thore Graepel, Remi Munos
TL;DR
Prior PSRO work focused on two-player zero-sum games, while Nash computation and equilibrium selection constrain its use in general games. This paper uses α-Rank and a preference-based response oracle to study PSRO in broader settings. It reports competitive performance in two-player poker and application to general-sum, many-player games.
Problem
Prior PSRO studies focused on settings where Nash equilibria are tractable, although Nash computation and equilibrium selection limit its use in general games.
Source: §1 · pp. 1–2Method
The paper studies PSRO with α-Rank as its meta-solver and introduces preference-based best response to align policy expansion with α-Rank.
Source: §2 · p. 3, §3 · p. 4, §4.2 · p. 5Results
α-Rank-based PSRO was competitive with Nash-based PSRO in zero-sum games and was reported to scale to general-sum, many-player games.
Source: §7 · p. 10Takeaways & Limitations
The authors conclude that their theoretical and empirical results support scaling multiagent training in general settings.
Source: §7 · p. 10Without a novelty-bound oracle, some multi-population games do not yield even partial convergence to an SSCC, and the α-Rank–Nash link in general games remains for future work.
Source: §4.3 · pp. 6–7
Abstract
from arXiv · showhide
This paper investigates a population-based training regime based on game-theoretic principles called Policy-Spaced Response Oracles (PSRO). PSRO is general in the sense that it (1) encompasses well-known algorithms such as fictitious play and double oracle as special cases, and (2) in principle applies to general-sum, many-player games. Despite this, prior studies of PSRO have been focused on two-player zero-sum games, a regime wherein Nash equilibria are tractably computable. In moving from two-player zero-sum games to more general settings, computation of Nash equilibria quickly becomes infeasible. Here, we extend the theoretical underpinnings of PSRO by considering an alternative solution concept, $\alpha$-Rank, which is unique (thus faces no equilibrium selection issues, unlike Nash) and applies readily to general-sum, many-player settings. We establish convergence guarantees in several games classes, and identify links between Nash equilibria and $\alpha$-Rank. We demonstrate the competitive performance of $\alpha$-Rank-based PSRO against an exact Nash solver-based PSRO in 2-player Kuhn and Leduc Poker. We then go beyond the reach of prior PSRO applications by considering 3- to 5-player poker games, yielding instances where $\alpha$-Rank achieves faster convergence than approximate Nash solvers, thus establishing it as a favorable general games solver. We also carry out an initial empirical validation in MuJoCo soccer, illustrating the feasibility of the proposed approach in another complex domain.
1 INTRODUCTION
PSRO grows populations of player policies by repeatedly analyzing matchups and training new policies against a meta-game distribution. This paper investigates α-Rank as an alternative to Nash-based policy selection, whose computational and selection difficulties constrain PSRO in general games.
1 INTRODUCTION
- PSRO iteratively simulates policy matchups, selects a distribution over existing policies, and trains new policies against that distribution.This population-based approach includes fictitious play, double oracle, and independent reinforcement learning as instances in two-player zero-sum games.Source: §1 · pp. 1–2
- Nash-based policy selection limits PSRO in general games because Nash equilibria can be intractable to compute and suffer from equilibrium selection.The paper identifies α-Rank, which applies readily to general games, as an alternative whose PSRO behavior needs theoretical and empirical study.Source: §1 · p. 2
- The paper establishes convergence guarantees for α-Rank-based PSRO in several game classes and studies links between α-Rank, Nash equilibria, and Projected Replicator Dynamics.It also introduces a best-response notion intended to guarantee convergence to the α-Rank distribution, tested empirically in randomly generated general-sum games.Source: §1 · p. 2
- Evaluations cover two-player Kuhn and Leduc Poker, 3- to 5-player poker, and preliminary MuJoCo soccer experiments using reinforcement-learning oracles.The paper reports competitive performance against Nash-based PSRO in the two-player poker variants and extends evaluation to settings beyond prior PSRO applications.Source: §1 · p. 2
2 PRELIMINARIES
The preliminaries describe how PSRO builds and analyzes a meta-game of policy matchups. They introduce Nash equilibrium and α-Rank as meta-solver concepts, with α-Rank deriving a unique stationary distribution from a perturbed response-graph walk.
2 PRELIMINARIES
- Nash equilibrium requires each player's strategy to be a best response to the others, while NASHCONV measures distance from equilibrium.Prior PSRO instances use Projected Replicator Dynamics as an approximate Nash meta-solver.Source: §2 · p. 2
- α-Rank walks the response graph, whose edges represent unilateral payoff-improving deviations, with small-probability backward transitions ensuring a unique stationary distribution.That distribution places its mass on sink strongly connected components of the response graph.Source: §2 · p. 3
- An oracle computes policies with specified properties, such as a best response, and its choice affects PSRO's convergence rate and final solution concept.Approximate best-response oracles can use reinforcement learning against a fixed distribution over opponents' policies.Source: §2 · p. 3
- Empirical game-theoretic analysis constructs a meta-game by simulating joint policy matchups and recording expected utilities, enabling game-theoretic analysis over policies rather than atomic actions.The text distinguishes sink strongly connected components of the underlying game from those of the PSRO meta-game.Source: §2 · p. 3
3 POLICY-SPACE RESPONSE ORACLES: NASH AND BEYOND
PSRO alternates between completing a policy meta-game, solving it for a policy distribution, and expanding populations with new policies. The solver and oracle choices define the PSRO variant.
3 POLICY-SPACE RESPONSE ORACLES: NASH AND BEYOND
- PSRO initializes policy populations and iterates through complete, solve, and expand phases.The complete phase fills missing meta-game payoffs through simulations; the solve phase computes a policy profile, and the expand phase adds policies returned by an oracle.Source: §3 · p. 4
- The meta-solver may compute a Nash, α-Rank, or uniform distribution, while the oracle returns at least one new policy for each player.PSRO(M, O) denotes the variant using meta-solver M and oracle O.Source: §3 · p. 4
- Prior PSRO investigations focused on Nash solvers and best-response oracles, with theory centered on two-player zero-sum games.The text says those guarantees do not hold beyond that regime, motivating study of alternative solvers and oracles.Source: §3 · p. 4
4 GENERALIZING PSRO THEORY
The theory section shows why standard best responses may fail to recover α-Rank components and introduces preference-based best response (PBR) to align policy expansion with α-Rank. It establishes convergence guarantees under stated conditions while identifying limitations and links to Nash and preference-based reinforcement learning.
4.1 ESTABLISHING CONVERGENCE TO α-RANK
- Standard best-response PSRO can terminate without discovering the game's sink strongly connected component, even when α-Rank concentrates on that component.The counterexample's single-population run ends with strategies A, B, C, and D rather than X.Source: §4.1 · p. 5
4.2 A NEW RESPONSE ORACLE
- PBR selects strategies aligned with α-Rank's response-graph dynamics, and the counterexample shows it can recover the missing sink strategy X.The example gives X a PBR score of 1, higher than the competing strategies' scores.Source: §4.2 · p. 5
- For multiple populations, PBR returns a new strategy for each player in every meta-game SSCC, diversifying strategies across subsets of prior strategies.The text relates this diversification to rectified-Nash best response, which also seeks diversity but only in two-player zero-sum games.Source: §4.2 · pp. 5–6
4.3 α-PSRO: THEORY, PRACTICE, AND CONNECTIONS TO NASH
- With a novelty-bound PBR oracle, α-PSRO fully converges to at least one sink strongly connected component; without that bound, it partially converges if its population contains a member of an SSCC.In single-population games, α-PSRO partially converges to the unique SSCC; some multi-population games without novelty-bounding do not partially converge to any SSCC.Source: §4.3 · p. 6
- Although exact PBR is computable in small normal-form games, the paper considers classes where standard reinforcement-learning agents may approximate it.The stated motivation is that best-response and PBR objectives can be incompatible in some games.Source: §4.3 · p. 7
- PBR and standard best response are compatible in two-player single-population win-loss games and in single-population monotonic games.The win-loss result assumes constant-sum payoffs in {0, 1}; monotonicity is defined through a non-decreasing function of strategy scores.Source: §4.3 · p. 7
- In symmetric win-loss games with deterministic outcomes between deterministic strategies, preference-based reinforcement learning optimizes the PBR objective exactly.The paper identifies implementing PBR with preference-based reinforcement learning as a direction for broader game classes.Source: §4.3 · p. 7
- In symmetric two-player zero-sum games, Nash-equilibrium support is contained within α-Rank support under equal-magnitude off-diagonal payoffs, and some Nash equilibrium has support contained within α-Rank support more generally.The paper leaves a more complex description of the α-Rank–Nash link in general games to future work.Source: §4.3 · p. 7
5 EVALUATION
The evaluation compares PSRO oracles and meta-solvers on randomly generated general-sum games and poker benchmarks. α-Rank is competitive with Nash in two-player poker and converges fastest in three-player Leduc, while PBR captures more α-Rank support than BR across tested strategy-space sizes.
Meta-solver comparisons
- The evaluation extends prior two-player zero-sum PSRO studies to general-sum games and poker domains with more than two players.Figure 4 reports poker results for domains with more than two players.Source: §5 · pp. 7, 9, Figure 4 · p. 9
Oracle comparisons
- For all tested |Sk| values, PBR discovers a larger proportion of α-Rank support than BR, supporting the theoretical results.The oracle comparisons use randomly generated 4- and 5-player games; the figure’s top and bottom rows correspond to those player counts, respectively.Source: §5 · pp. 7–8, Figure 2 · p. 8
Meta-solver comparisons
- In Kuhn poker, α-Rank, Nash, and PRD converge at essentially the same rate toward zero NASHCONV, unlike the slower Uniform and Rectified PRD solvers and plateauing Rectified Nash.The authors attribute Rectified Nash’s cycling through the same policies to its design for symmetric games, unlike the asymmetric poker domains.Source: §5 · p. 8, Figure 3 · p. 8
- In 3-player Leduc, α-Rank converges fastest; in all tested Kuhn instances it and PRD have competitive convergence rates.Exact Nash is omitted from the greater-than-two-player experiments because it is intractable in these instances.Source: §5 · p. 9, Figure 4 · p. 9
6 RELATED WORK
Related work situates PSRO among population-based learning, other multiagent learning approaches, and evolutionary solution concepts. It also describes α-Rank as an alternative for analyzing general-sum, many-player interactions.
PSRO-based research
- PSRO unifies approaches including fictitious play, independent reinforcement learning, and double oracle.Parallel Nash Memory incrementally grows strategy spaces using a search heuristic rather than exact best responses.Source: §6 · p. 9
Multiagent learning
- Other multiagent methods include MADDPG, COMA, DIAL, and several deep-RL approaches for continuous control.The passage also points readers to a survey of recent deep multiagent RL approaches.Source: §6 · p. 10
Evolutionary dynamics
- α-Rank was introduced as a scalable dynamic alternative to Nash for general-sum, many-player games that captures underlying multiagent evolutionary dynamics.Related work also uses evolutionary dynamics, including replicator dynamics, to examine multiagent interactions through meta-games.Source: §6 · pp. 9–10
7 DISCUSSION
The discussion concludes that α-Rank-based PSRO is competitive with Nash-based PSRO in zero-sum games and scales to general-sum, many-player games. The authors identify using uncertainty in the meta-solver distribution to guide new-strategy selection as future work.
Discussion
- α-Rank-based PSRO is competitive with Nash-based PSRO in zero-sum games and scales to general-sum, many-player games.The authors propose studying how uncertainty in the meta-solver distribution could inform selection of strategies to add to populations.Source: §7 · p. 10
ACKNOLWEDGEMENTS
The authors acknowledge Bart De Vylder for helpful feedback on the paper draft.
Acknowledgements
- Bart De Vylder provided helpful feedback on the paper draft.Source: ACKNOLWEDGEMENTS · p. 10
APPENDICES
The appendices illustrate BR- and PBR-oracle iterations, give counterexamples distinguishing α-Rank support from equilibrium support, and establish several convergence and oracle-compatibility results for α-PSRO.
A.2 EXAMPLE BEHAVIOR OF PSRO(NASH, BR)
- In both examples, the PSRO(Nash, BR) run can terminate without discovering a strategy needed to recover the full α-Rank distribution.Examples 4 and 5 show this failure in a symmetric game and a two-player zero-sum game, respectively.Source: §A.2 · p. 16
A.3 COUNTEREXAMPLES: α-RANK VS. NASH SUPPORT
- Chicken's α-Rank support omits the mixed-Nash support, while in Prisoner's Dilemma it is disjoint from correlated-equilibrium support.The Chicken example retains only the two pure Nash profiles; the Prisoner's Dilemma example places α-Rank weight only on (D,D).Source: §A.3 · pp. 16–17
A.4 SINGLE-POPULATION α-CONV
- A single-population α-CONV variant is introduced using a single-population PBR-Score, whose maximization is over pure strategies.Source: §A.4 · p. 17
B.1 PROOF OF PROPOSITION 1
- Single-population α-PSRO α-partially converges to an SSCC if its population contains a member of that SSCC.The proof uses the induced meta-SSCC and the PBR oracle to show the process cannot terminate before encountering a member of the underlying SSCC.Source: §B.1 · p. 18
B.2 PROOF OF PROPOSITION 2
- With a novelty-bound PBR oracle, α-PSRO α-fully converges to at least one game SSCC.At convergence, the meta-SSCC contains every strategy profile in its corresponding underlying-game SSCC.Source: §B.2 · p. 18
B.3 PROOF OF PROPOSITION 3
- Single-population α-PSRO cannot terminate before encountering the game's SSCC, because an SSCC member has maximal PBR score against a population without one.The proof gives that score as 1 and bounds population-member scores below 1.Source: §B.3 · p. 18
B.4 PROOF OF PROPOSITION 4
- Without a novelty-bound oracle, multi-population α-PSRO can terminate before reaching an SSCC, as a weak intermediate joint strategy blocks coordinated changes.The counterexample's unique SSCC is the singleton profile (3,2,3), which the algorithm fails to reach.Source: §B.4 · pp. 18–19
B.5 PROOF OF PROPOSITION 5
- In two-player single-population win-loss games, BR is compatible with PBR.The proof identifies the final manipulated best-response objective with the single-population PBR objective.Source: §B.5 · p. 19
B.6 PROOF OF PROPOSITION 6
The appendices establish conditions linking best-response methods, PBR, and α-Rank, then describe the poker and normal-form game procedures used in experiments. They also specify the scope of additional oracle comparisons.
B.6 PROOF OF PROPOSITION 6
- In monotonic symmetric two-player games, BR is compatible with PBR; the toy example shows BR’s sole solution N is among PBR’s valid solutions.The example assumes a strictly increasing σ; any strategy dominating the current population is valid for PBR.Source: §B.6 · pp. 19, 21
B.7 PROOF OF PROPOSITION 7
- In symmetric win-loss games with deterministic outcomes between deterministic strategies, preference-based RL that maximizes win probability against a strategy distribution exactly optimizes PBR.Source: §B.7 · p. 22
B.8–B.9 PROOFS OF PROPOSITIONS 8–9
- In symmetric two-player zero-sum games, every NE support lies within α-Rank support when off-diagonal payoffs have equal magnitude; without that condition, at least one such NE exists.Source: §B.8 · p. 22, §B.9 · p. 23
C.1 EXPERIMENTAL PROCEDURES
- Poker experiments used OpenSpiel Kuhn and Leduc implementations, 100 simulations per strategy pair, and deterministic subsequent PSRO updates from estimated mean-payoff matrices.Reported averages use 2 runs, primarily to capture machine-specific rounding differences.Source: §C.1 · p. 24
C.2.1–C.2.2 GAME GENERATION AND POKER
- Normal-form comparisons combine generated transitive and cyclic payoff components, while K-player Kuhn uses K+1 cards and Leduc has two betting rounds with a public card.Source: §C.2.1 · pp. 24–25, §C.2.2 · p. 25
C.3 PBR COMPUTATION IN NORMAL FORM GAMES
- PBR-SCORE and PCS-SCORE assess convergence like NASHCONV, but these scores and NASHCONV are intractable generally and useful in small tractable games.PBR scores candidate strategies by their probability of outperforming current joint strategies, then selects the highest-scoring strategy.Source: §C.3 · p. 25
C.4 ADDITIONAL ORACLE COMPARISON RESULTS
- Figure C.9 compares oracles on randomly generated normal-form games across strategy-space sizes, with rows corresponding to two- through five-player games.Source: Figure C.9 · p. 26
C.5 NOTES ON RECTIFIED NASH PERFORMANCE
The appendix explains why Rectified Nash performs poorly in the evaluated poker domains: it can repeat existing responses and restrict further policy discovery. It also details α-Rank’s response-graph random walk and limiting distribution.
C.5 NOTES ON RECTIFIED NASH PERFORMANCE
- Rectified Nash loops by iteration 3, leaving Player 1 responding only to Player 2’s random policy and preventing Player 2 from adding novel policies.The resulting population is deadlocked.Source: §C.5 · p. 27
- Rectified Nash and Rectified PRD each discover 5 distinct policies in the illustrated evaluation, while Rectified Nash generally discovers fewer policies and plateaus at low NASHCONV.In a few rare seeds with around 10 simulations per payoff entry, Rectified Nash reached low exploitability; the authors leave the relationship between payoff noise, diversity, and exploitability for future work.Source: §C.5 · p. 27, Figure C.10 · p. 27
- Rectified PRD performs better than Rectified Nash in NASHCONV, but payoff noise plus PRD’s intrinsic noise does not deterministically yield 0 exploitability.The authors conjecture that noisier behavior may help Rectified PRD escape deadlocks and discover more policies, leaving further analysis for future work.Source: §C.5 · p. 27
D α-RANK IN DETAIL
- α-Rank forms a directed response graph over pure strategy profiles and ranks profiles by the masses in the random walk’s unique invariant distribution.The walk allows small-probability backward transitions to ensure irreducibility.Source: D α-RANK IN DETAIL · p. 31
- The α-Rank transition matrix permits transitions only between profiles differing in one player’s strategy, with transition probabilities determined by payoff differences.As α tends to infinity, only profiles in sink strongly connected components can receive positive mass.Source: D α-RANK IN DETAIL · p. 31
E TOWARDS THEORETICAL GUARANTEES FOR THE PROJECTED REPLICATOR DYNAMICS
The section examines theoretical grounding for projected replicator dynamics and introduces single-mutation PRD as a related constrained variant. It also outlines initial MuJoCo soccer experiments and their training setup.
E TOWARDS THEORETICAL GUARANTEES FOR THE PROJECTED REPLICATOR DYNAMICS
- PRD heuristically encourages exploration by projecting strategy distributions into a lower-bounded simplex, but this projection may sever its connection to Nash equilibria.Theoretical game-theoretic properties of PRD were left open.Source: E TOWARDS THEORETICAL GUARANTEES FOR… · p. 32
- The paper takes a first step toward PRD guarantees by highlighting a possible connection between α-Rank and single-mutation PRD, while leaving formal investigation for future work.The connection is described as informal and potentially worthy of further investigation.Source: E TOWARDS THEORETICAL GUARANTEES FOR… · p. 32
- Simulating PRD or s-PRD may be costly, and their dynamics can be chaotic even in simple two-player, two-strategy games, complicating convergence-time estimates.α-Rank does not rely on such simulations.Source: E TOWARDS THEORETICAL GUARANTEES FOR… · p. 32
F MUJOCO SOCCER EXPERIMENT
- The MuJoCo soccer experiments are an initial investigation of α-Rank-based PSRO with function-approximation policies in a complex domain.The paper frames these experiments as preliminary groundwork rather than conclusive evaluation.Source: F MUJOCO SOCCER EXPERIMENT · p. 33
F.1 TRAINING PROCEDURE
- The training procedure uses 32 reinforcement-learning agents, forms homogeneous teams, and evaluates pairwise team matchups in a two-player team-versus-team meta-game.Payoffs are average team win rates.Source: §F.1 · p. 33
- Meta-game payoff estimates use an adaptive number of simulations, averaging 10 to 100 per entry, while the final evaluation matrix uses 100 per entry.The procedure adds three policies per PSRO iteration per player, corresponding to the 10% best RL agents.Source: §F.1 · p. 33
F.2 RESULTS
In 3-vs.-3 MuJoCo soccer, α-Rank-based PSRO significantly outperforms uniform-meta-solver PSRO in the reported comparison. The section also describes a separate comparison with self-play and cautions that broader analysis is needed.
F.2 RESULTS
- PSRO(α-Rank, RL) significantly outperforms PSRO(Uniform, RL) in the reported 3-vs.-3 team comparison.The figure shows win probabilities for each pipeline’s best eight agents and the α-Rank distribution over their induced meta-game.Source: §F.2 · p. 33, Figure F.13 · p. 34
- A second experiment compares α-PSRO training with self-play training in 2-vs.-2 games to gauge improvement associated with PSRO.The supplied passages do not report the outcome of this comparison.Source: §F.2 · pp. 33–34, Figure F.14 · p. 35
- The authors characterize the soccer results as preliminary and say more extensive research and analysis are needed to make them conclusive.They identify extensive ablation studies as future work.Source: §F.2 · p. 34