Source-linked AI summary
Open-ended Learning in Symmetric Zero-sum Games
David Balduzzi, Marta Garnelo, Yoram Bachrach, Wojciech M. Czarnecki, Julien Perolat, Max Jaderberg, Thore Graepel
TL;DR
In nontransitive games, self-play can cycle without improving overall strength, and there may be no clear opponent against which to measure progress. The paper develops a geometric framework for population objectives and a niching algorithm, PSROrN. In two resource-allocation games, PSROrN outperforms existing alternatives.
Problem
In nontransitive games, self-play can cycle without improving overall strength, so the objective for agent learning is unclear.
Source: §1 · p. 1, §2.1 · p. 3Method
The paper uses gamescapes to formulate population-level objectives and presents PSROrN, which adaptively constructs game-theoretic niches to amplify strategic diversity.
Source: §1 · p. 2Results
In Colonel Blotto and differentiable Lotto, PSROrN outperforms PSRON; both greatly outperform self-play, while PSROU performs comparably to PSRON.
Source: §1 · p. 2Takeaways & Limitations
The framework makes population performance analyzable in nontransitive games and supports learning goals of discovering and mastering underlying strategic components.
Source: §1 · p. 2, §6 · p. 8Without further assumptions about game structure, a finite population’s empirical gamescape cannot support strong conclusions about the full functional gamescape.
Source: §3 · p. 5
Abstract
from arXiv · showhide
Zero-sum games such as chess and poker are, abstractly, functions that evaluate pairs of agents, for example labeling them `winner' and `loser'. If the game is approximately transitive, then self-play generates sequences of agents of increasing strength. However, nontransitive games, such as rock-paper-scissors, can exhibit strategic cycles, and there is no longer a clear objective -- we want agents to increase in strength, but against whom is unclear. In this paper, we introduce a geometric framework for formulating agent objectives in zero-sum games, in order to construct adaptive sequences of objectives that yield open-ended learning. The framework allows us to reason about population performance in nontransitive games, and enables the development of a new algorithm (rectified Nash response, PSRO_rN) that uses game-theoretic niching to construct diverse populations of effective agents, producing a stronger set of agents than existing algorithms. We apply PSRO_rN to two highly nontransitive resource allocation games and find that PSRO_rN consistently outperforms the existing alternatives.
1. Introduction
In nontransitive games, self-play can cycle without improving overall strength, leaving unclear what objectives agents should pursue. The paper formulates population progress geometrically and introduces PSROrN, which outperforms existing alternatives in two resource-allocation games.
1. Introduction
- The paper proposes algorithms that continually pose useful objectives for open-ended learning in two-player zero-sum games, a setting that includes function optimization as a special case.This addresses the under-studied task of generating useful opponents, including opponents with unfamiliar behaviors.Source: §1 · p. 1
- Self-play can cycle through agents without improving overall strength in nontransitive games, because improving against one opponent can worsen performance against another.The paper develops a mathematical framework and algorithms to uncover and solve latent game problems.Source: §1 · p. 1
- Gamescapes represent game interactions geometrically; population performance increases transitively as the polytope expands, reframing learning as growing the gamescape rather than finding one best agent.The framework also measures diversity in effective behaviors, excluding policy differences that do not change outcomes and agents that lose in novel ways.Source: §1 · pp. 1–2
- PSROrN adaptively constructs game-theoretic niches to amplify strategic diversity, complementing PSRON’s objective of training against a Nash-equilibrium mixture.Both algorithms are presented as ways to grow the gamescape.Source: §1 · p. 2
- PSROrN outperforms PSRON in Colonel Blotto and differentiable Lotto; both greatly outperform self-play, while PSROU performs comparably to PSRON.These resource-allocation games are highly nontransitive.Source: §1 · p. 2
- Related work connects adaptive objectives to novelty search and open-ended learning, while distinguishing this work from multiobjective optimization and excluding asymmetric GANs.Novelty search continually changes its target objective; the paper is concerned with generating as well as optimizing objectives.Source: §1 · p. 2
2. Functional-form games (FFGs)
Functional-form games model pairwise outcomes between parametrized agents as antisymmetric evaluations. Their transitive and cyclic components explain why self-play suits some games but may fail in games with strategic cycles.
2. Functional-form games (FFGs)
- A functional-form game evaluates pairs of parametrized agents with an antisymmetric function; higher evaluations favor the first agent, and the parametrization is folded into the game.The paper renders wins, losses, and ties as positive, negative, and zero evaluations, respectively.Source: §2 · p. 2
- The FFG toolkit turns a two-player game into agent objectives, provides approximate best responses, and evaluates populations with antisymmetric matrices and Nash equilibria.The Nash equilibrium is taken from the zero-sum matrix game specified by the population evaluation matrix.Source: §2 · pp. 2–3
- Every functional-form game decomposes, under a suitably defined inner product, into transitive and cyclic components.Few games are purely one component, but understanding both cases matters for general algorithms.Source: §2 · p. 3
2.1. Transitive games
- In transitive games, a rating function expresses performance as rating differences; monotonic games generalize this structure, with Elo modeling win probabilities through a sigmoid.Elo’s model is used in Chess, Go, and other games.Source: §2.1 · p. 3
- Against a fixed opponent, a much weaker opponent can yield vanishing gradients under Elo’s model, while training against a sequence of increasingly strong opponents avoids that skill-gap problem.For transitive games, the choice of fixed opponent does not change the solution.Source: §2.1 · p. 3
- Self-play poses and masters successive objectives, but assumes that local wins imply global improvement; this assumption fails in nontransitive games.In those games, improvement against one agent does not guarantee improvement against others.Source: §2.1 · p. 3
2.2. Cyclic games
- Cyclic games counterbalance wins against some agents with losses against others, as in strategic cycles found in rock-paper-scissors, poker, and StarCraft.The disc-game example varies the strength of rock-paper-scissors interactions across a family of games.Source: §2.2 · pp. 3–4
- For general functional-form games, the challenge is to find practical substitutes for repeated local improvement and a transitive measure of progress.Without a transitive measure, a sequence of local improvements may yield no overall improvement.Source: §2.2 · p. 4
3. Functional and Empirical Gamescapes
Gamescapes represent strategic interactions geometrically, shifting the objective from finding a best agent to growing a population’s strategic span. The section defines population performance and effective diversity to describe progress and effective coverage.
3. Functional and Empirical Gamescapes
- The EGS represents convex mixtures of evaluation-matrix rows, and its dimension is determined by matrix rank; 40-agent examples had one- or two-dimensional representations.The FGS represents possible interactions, while the EGS is a tractable proxy based on observed agents.Source: §3 · p. 4
- A finite-population EGS cannot support strong conclusions about the full FGS without additional assumptions, since unobserved strategic cycles may remain.Training against randomized opponent distributions could uncover unobserved dimensions.Source: §3 · p. 5
3.1. Population performance
- In cyclic games, an agent’s performance is misleading because beating one opponent entails losing to another, motivating a population-level measure based on Nash play.The measure compares two populations using a Nash equilibrium of their cross-population evaluation matrix.Source: §3.1 · p. 5
- If hull(P) ⊂ hull(Q), Q performs at least as well as P against any population R, making gamescape expansion a transitive progress criterion.The population-performance measure is independent of the choice of Nash equilibrium, and in monotonic games it compares the populations’ best agents.Source: §3.1 · p. 5
3.2. Effective diversity
- Effective diversity measures how Nash-supported agents exploit one another; it is zero when a dominant agent exists.It measures the volume spanned by Nash-supported agents, and larger gamescapes in the illustrated disc game yield more diverse, better exploiters.Source: §3.2 · p. 6
4. Algorithms
The algorithms build sequences of local training objectives that yield transitive population-level progress by expanding the gamescape. PSRO_N responds to a Nash mixture, while PSRO_rN uses Nash-supported niches to amplify agents’ strengths.
4. Algorithms
- The algorithms construct fruitful local objectives whose solved responses add up to transitive population-level progress, and output populations rather than single agents.They are presented as specializations of policy space response oracles.Source: §4 · p. 6
4.1. Response to the Nash (PSRON)
- PSRO_N generates approximate best responses to the current population’s Nash mixture, degenerating to self-play in transitive games.If a response has positive Nash-weighted payoff against the population, adding it strictly enlarges the empirical gamescape.Source: §4.1 · p. 6
- PSRO_N stops expanding the gamescape when the game’s Nash equilibrium is already contained in the empirical gamescape, because no best response to it exists.The disc-game example motivates using niching to continue meaningful expansion after finding the full-game Nash equilibrium.Source: §4.1 · p. 6
4.2. Response to the rectified Nash (PSROrN)
- PSRO_rN trains each Nash-supported agent against the Nash-weighted mixture of agents it beats or ties, an objective shown to produce effective diversity.The approach aims to amplify strengths while ignoring weaknesses.Source: §4.2 · p. 7
- A pathological PSRO_rN mode arises when highly local exploits fail to generalize, producing many specialized agents as the gamescape grows.The algorithm amplifies positive coordinates of Nash-supported agents in their evaluation-matrix rows.Source: §4.2 · p. 7
- In rock-paper-scissors, PSRO_rN gradients that amplify strengths expand the gamescape, whereas optimizing agents to reduce losses contracts it.The contrasting gradients illustrate why targeting weaknesses does not create diverse niches.Source: §4.2 · p. 7, Figure 3 · p. 7
5. Experiments
Across two highly nontransitive resource-allocation games, PSRO_rN outperforms the alternatives across compute budgets. The experiments also track how each method’s population expands its gamescape.
Experimental setups
- The experiments compare self-play, PSROU, PSRO_N, and PSRO_rN under fixed oracle-query budgets using relative population performance.Computing evaluation matrices, which costs O(n^2), is excluded from the computational model; relative evaluation and oracle-query costs depend on the game.Source: §5 · p. 8
- Blotto uses 3 areas and 10 coins; Differentiable Lotto uses 9 customers sampled uniformly in the square [-1, 1]^2, with gradient ascent as its oracle.Blotto is not differentiable, so its best-response oracle uses maximum a posteriori policy optimization.Source: §5 · pp. 7–8
Results
- Across both games, PSRO_rN outperforms alternatives across compute budgets; PSROU and PSRO_N perform comparably, while population-upgraded self-play remains worst in Lotto but slightly beats both in Blotto.The standard self-play comparison uses only its final agent; tracking all generated agents narrows its margin in Lotto.Source: §5 · p. 8
- In Differentiable Lotto, PSRO_rN expands the gamescape more uniformly through ladder-like trajectories and is the only method increasing hull area at every iteration.All algorithms increase hull area overall.Source: §5 · p. 8, Figure 5 · p. 8
6. Conclusion
The paper proposes a gamescape framework and PSRO_rN for open-ended learning in differentiably parameterized, symmetric zero-sum games. Its appendices clarify the interaction data represented and equivalences between row- and column-based gamescapes.
6. Conclusion
- The framework aims to discover the strategic components of a game and master each, using gamescapes to represent latent objectives; PSRO_rN is empirically validated for uncovering strategic diversity.The authors frame these algorithms as foundations for combining gradient and reinforcement-based learning with game-theoretic adaptive objectives.Source: §6 · p. 8
A. Behaviorism
- The paper operationalizes an agent through all its possible interactions, with functional gamescapes covering possible interactions and empirical gamescapes covering observed ones.The analysis restricts itself to the pairwise-interaction facet reported by φ; richer statistics may require instance-specific analysis.Source: A. Behaviorism · p. 10
B. Convex geometry
- For both empirical and functional gamescapes, using column mixtures instead of row mixtures yields the same polytope or functions up to sign.The functional version exchanges φ(•, w) for φ(w, •).Source: B. Convex geometry · p. 10
C. Proof of theorem 1
The section extends combinatorial Hodge theory to antisymmetric flows, setting up tools later generalized to functions.
C. Proof of theorem 1
- The authors generalize results from combinatorial Hodge theory to flows represented by antisymmetric functions.Earlier formulations use antisymmetric matrices on finite graphs.Source: C. Proof of theorem 1 · p. 10, §C.1 · p. 10
C.1. Combinatorial Hodge theory
- In the finite-graph setting, a flow assigns a value to each directed edge, with the reverse direction taking the opposite value.The passage relates graph flows to vector fields on manifolds.Source: §C.1 · p. 10
- The combinatorial gradient turns a vertex-valued vector into edge flows, while divergence assigns each vertex its contribution as a source.The curl records the flow around a three-vertex cycle.Source: §C.1 · pp. 10–11
C.2. Functional Hodge theory
The section extends combinatorial Hodge tools to flows over a compact probability space and proves a functional-setting variant of Hodge decomposition.
C.2. Functional Hodge theory
- The functional setting represents flow between points in a compact probability space with an antisymmetric function.The finite combinatorial setting is a special case when the space is finite.Source: §C.2 · p. 11
- The section defines functional gradient, divergence, and curl operators and establishes identities connecting them.For zero-expectation functions, divergence composed with gradient returns the function, and curl composed with gradient is zero.Source: §C.2 · p. 11
- The authors prove a variant of Hodge decomposition for flows in the functional setting.The cited combinatorial result decomposes flows into gradient flows and curl-free flows.Source: §C.2 · p. 11
- Theorem 1 states that the vector space of games admits an orthogonal decomposition.The supplied theorem statement does not specify the decomposition's components.Source: §C.2 · p. 11
D. Proofs of propositions
The propositions characterize gamescape equivalence and dimension, population-level performance, and when adding an agent expands a gamescape.
D. Proofs of propositions
- A population is redundant relative to another when each of its agents is empirically indistinguishable from a mixture of agents in the other population.The proposition states that adding such a redundant population yields equivalent gamescapes.Source: D. Proofs of propositions · p. 12
- Equivalent gamescapes can represent the same polytope across dimensions through projection and recovery.The proof establishes this equivalence for the matrices A and B.Source: D. Proofs of propositions · p. 12
- A population's empirical gamescape can be represented in R^r, where r is the rank of its evaluation matrix.The proof constructs an isomorphic polytope in that rank-dimensional space.Source: D. Proofs of propositions · p. 12
- Population performance is independent of the chosen Nash equilibrium, and under monotonicity it compares the populations' best agents.If one population's hull is contained in another's, its performance against the other population is at most zero, and its performance against any third population is no better.Source: D. Proofs of propositions · p. 12
- Adding an agent that beats the Nash distribution strictly enlarges the population's gamescape.The proposition's condition is that the agent's expected payoff against that distribution is positive.Source: D. Proofs of propositions · p. 13
Proof of proposition 7
The proposition establishes effective diversity as the objective constructed by rectified Nash response.
Proof of proposition 7
- Rectified Nash response constructs an objective identified as effective diversity.The passage refers to the algorithm's rectified Nash response objectives.Source: Proof of proposition 7 · p. 13
E.1. Nash reweighting of evaluation matrices
The Nash-reweighted evaluation matrix remains antisymmetric and has zero row and column sums. The section also expresses population diversity as a matrix norm.
E.1. Nash reweighting of evaluation matrices
- For an antisymmetric evaluation matrix A and any Nash equilibrium p, the Nash-reweighted matrix is antisymmetric with every row and column summing to zero.The statement allows p to be non-unique.Source: §E.1 · p. 13
- The zero-sum row and column property follows from antisymmetry and the Nash equilibrium condition.The proof establishes nonnegative row sums whose total is zero, and applies the same argument to columns.Source: §E.1 · p. 13
E.2. Diversity as a matrix norm
- Population diversity can be rewritten as the matrix norm ℓ_1,1, with the second equality following from antisymmetry of φ.Source: §E.2 · p. 13
E.3. Reduction to the rock-paper-scissors
This section reduces a population game to a rock-paper-scissors meta-game and surveys explicit functional-form game constructions. It also describes the embedding procedures used to visualize game structure and training trajectories.
E.3. Reduction to the rock-paper-scissors
- Grouping a Nash-reweighted evaluation matrix into rock, paper, and scissors blocks yields a meta-game with equal positive cyclic payoffs.The construction forms mixture agents and sums entries within each block; the resulting payoff parameter satisfies α = β = γ and α > 0.Source: §E.3 · p. 14
F. Examples of functional-form games
- Functional-form games include parametrized two-player zero-sum games whose payoffs and approximate best responses can be estimated, including with reinforcement learning.The section presents explicit mathematical constructions of such games.Source: F. Examples of functional-form games · p. 14
F.1. Symplectic games
- Symplectic examples include transitive, cyclic, and mixed games, with the mixed construction combining transitive and cyclic structure in a cigar-shaped game.In the mixed case, the first two coordinates provide transitive structure and the remaining coordinates provide cyclic structure.Source: §F.1 · pp. 14–15
- Other symplectic constructions include sparse-vector images, deformed differentiable games, and long cycles whose payoff-matrix rank is n − 2 for even n and n − 1 for odd n.The sparse-vector construction has most entries near zero.Source: §F.1 · p. 15
F.2. Variants of Colonel Blotto
- The resource-allocation examples include continuous and differentiable Lotto variants, with parametrized families such as mixtures of Dirac or Gaussian distributions.Source: §F.2 · p. 15
F.3. Comparison with GANs
- Unlike functional-form games, GANs are asymmetric: their generator and discriminator have different roles and their losses have different semantics.Source: §F.3 · p. 15
G. Details of 2D embedding procedure
- Figure 6 compares Schur, PCA, SVD, and t-SNE embeddings; the t-SNE perplexity was 9, and tested alternatives did not capture gamescape structure more meaningfully.Embeddings use two dimensions; the figure colors agents by average payoff against the population and depicts transitive and cyclic empirical gamescapes with distinct shapes.Source: G. Details of 2D embedding procedure · pp. 15–16, Figure 6 · p. 17
- Figure 7 tracks Differentiable Blotto training in 2D Schur space, marking the initial policy, population hulls, and PSROrN hull area over iterations.Source: Figure 7 · p. 18