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
Nontransitive zero-sum games lack a clear single objective because strategic cycles can make self-play fail to improve overall strength. The paper introduces gamescapes and adaptive objectives, including PSROrN, and finds that PSROrN outperforms existing alternatives in two highly nontransitive resource-allocation games. The framework supports population-level analysis and the construction of diverse effective agents.
Problem
Nontransitive games can cycle strategically, so improving against one opponent does not guarantee improvement against others and the appropriate objective is unclear.
Method
The paper uses gamescapes to formulate adaptive objectives and proposes PSROrN, which uses game-theoretic niching to uncover strategic diversity.
Results
PSROrN outperforms PSRON and self-play in Colonel Blotto and differentiable Lotto, while PSROU performs comparably to PSRON.
Takeaways & Limitations
Learning in these games should discover and master the strategic components underlying the game rather than seek a single best agent.
Takeaways & Limitations
PSRON can stop expanding a population when its empirical gamescape contains the full game's Nash equilibrium.
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
The paper addresses how to formulate useful learning objectives in multi-agent domains where self-play can fail because games are nontransitive. It introduces gamescapes and adaptive algorithms for open-ended learning, including PSROrN, which outperforms alternatives in two resource-allocation games.
- Deep learning often solves packaged objectives, but many multi-agent domains lack a clear objective to optimize.
- Learning in games requires generating stronger, unfamiliar opponents as well as defeating known opponents.
- Self-play can cycle in nontransitive games because improving against one opponent may worsen performance against another.
- Functional-form games model zero-sum games played by parametrized agents, and their decomposition separates transitive and cyclic components.
- Gamescapes represent objectives and population performance geometrically, with nontransitive games requiring potentially high-dimensional representations.
- PSRON responds to Nash mixtures, while PSROrN adaptively creates game-theoretic niches that promote strategically diverse effective agents.
- PSROrN outperforms PSRON and self-play in Colonel Blotto and differentiable Lotto, while PSROU performs comparably to PSRON.
- The paper relates its adaptive-objective framework to novelty search, open-ended evolution, curiosity, learning in games, and multiobjective optimization.
2. Functional-form games (FFGs)
Functional-form games represent parametrized-agent interactions with antisymmetric evaluations, allowing transitive and cyclic structure to be analyzed. Self-play is effective under transitivity but can fail in cyclic games, motivating broader tools and objectives.
- 2. Functional-form games (FFGs): A functional-form game evaluates pairs of parametrized agents with an antisymmetric function φ(v, w) = −φ(w, v).
- 2. Functional-form games (FFGs): The agent parametrization and environment are folded together into φ, so the game combines agent architecture with the environment.
- 2. Functional-form games (FFGs): Win probabilities can be converted into antisymmetric evaluations, and approximate best-response oracles can use gradients, reinforcement learning, or evolutionary algorithms.
- 2. Functional-form games (FFGs): An evaluation matrix for a population supports Nash-equilibrium analysis, while every functional-form game decomposes into transitive and cyclic components.
- 2.1. Transitive games: In transitive games, performance is represented by differences in a rating function, with Elo providing a sigmoid win-probability model.
- 2.1. Transitive games: Training against a much weaker opponent can produce vanishing gradients under Elo’s model, whereas self-play maintains opponents of increasing strength.
- 2.1. Transitive games: Self-play poses and masters sequential objectives, but its assumption that local improvement implies global improvement fails in nontransitive games.
- 2.2. Cyclic games: Cyclic games counterbalance wins against some agents with losses against others, as in rock-paper-scissors-like interactions.
3. Functional and Empirical Gamescapes
Gamescapes provide a geometric framework for representing strategic objectives and measuring population progress in zero-sum games, including nontransitive games where no single best agent exists. The framework distinguishes functional possibilities from empirically observed interactions and motivates population growth through performance and effective diversity.
- Functional and Empirical Gamescapes: Rather than seeking a single dominant agent, the framework seeks populations that cover the strategic dimensions of a zero-sum game.This population-level view supports conservative Nash responses while preserving strategies useful for exploiting new opponents.
- Functional and Empirical Gamescapes: Gamescapes represent mixtures of objectives implicit in a functional-form game, while empirical gamescapes provide a tractable proxy based on observed population interactions.The functional gamescape covers possible interactions, whereas the empirical gamescape captures interactions represented by a finite evaluation matrix.
- Functional and Empirical Gamescapes: In transitive or monotonic games, the gamescape reduces to a one-dimensional landscape, whereas cyclic components require higher-dimensional representations.Optimization landscapes are a special case in which improving an agent reduces to increasing a single objective function.
- Functional and Empirical Gamescapes: Redundant agents do not change the empirical gamescape, so geometrically equivalent populations can represent the same strategic structure despite different evaluation-matrix sizes.Two matrices with rock-paper-scissors structure, including one with duplicated scissors, produce equivalent triangular gamescapes.
- Functional and Empirical Gamescapes: 40 agents can yield one- or two-dimensional empirical gamescapes, whose dimension is determined by the evaluation matrix rank.In general, an n-agent empirical gamescape can be represented in R^r, where r = rank(A_P) ≤ n.
- Functional and Empirical Gamescapes: Empirical gamescapes may miss strategic dimensions present in the full functional gamescape, so finite-population observations cannot by themselves establish the game’s complete structure.The paper connects this gap to exploration and suggests randomized opponent distributions as one way to uncover unobserved dimensions.
- Population performance: Population performance increases when a population’s gamescape polytope expands, providing a transitive progress measure even when individual-agent performance is nontransitive.The measure is independent of the selected Nash equilibrium and agrees with best-agent comparison in monotonic games.
- Effective diversity: Effective diversity measures how Nash-supported agents exploit one another; larger concentric gamescapes contain more diverse and better exploiting agents.If a population has a dominant agent, effective diversity is zero.
4. Algorithms
The paper develops PSRON and PSROrN to construct objectives and populations that expand gamescapes in nontransitive games. PSROrN uses game-theoretic niches to amplify strengths, while PSRON can stop expanding once the population contains the Nash equilibrium.
- Algorithms: The algorithms construct local objectives whose approximate solutions iteratively expand empirical gamescapes and output populations rather than single agents.They assume an oracle that finds an approximate best response to a mixture of agents.
- Response to Nash (PSRON): PSRON trains approximate best responses to the Nash mixture of the current population, extending double oracle and reducing to self-play in transitive games.A proposition states that a positive-mass response strictly enlarges the empirical gamescape.
- Response to Nash (PSRON): PSRON can fail when the population’s gamescape contains the full-game Nash equilibrium, because no epsilon-better response exists there.The paper motivates PSROrN as a niching method that can continue growing the gamescape in this case.
- Response to uniform distribution (PSROU): PSROU trains approximate best responses to the uniform distribution over the current population, but its effect on the gamescape is not understood.The paper relates PSROU to fictitious self-play.
- Response to rectified Nash (PSROrN): PSROrN trains each Nash-supported agent against the Nash-weighted mixture of agents it beats or ties, amplifying strengths while ignoring weaknesses.This objective is identified as effective diversity; in the disc game, its gradients point outside the polytope and expand the gamescape.
- Response to rectified Nash (PSROrN): Training agents against opponents they lose to produces inward-pointing gradients that contract the gamescape rather than creating diverse niches.In rock-paper-scissors, training rock against paper makes it more like scissors, with analogous cycling for the other agents.
5. Experiments
The experiments evaluate self-play, PSROU, PSRON, and PSROrN under fixed oracle-query budgets in two highly nontransitive resource-allocation games. PSROrN outperforms the alternatives and is the only method that consistently expands the empirical gamescape throughout training.
- Experimental setup: The experiments study Colonel Blotto and differentiable Lotto, two highly nontransitive resource-allocation games.Blotto uses three areas, ten coins, and 1,000 games; differentiable Lotto uses nine randomly chosen customers over 500 games.
- Results: The differentiable Lotto trajectories show PSROrN expanding the convex hull through consistent ladder-like movements.The visualization uses a two-dimensional Schur embedding of the empirical gamescape.
- Experimental setup: Performance comparisons track relative population performance under a fixed computational budget measured by oracle queries.The reported population-performance measure compares the populations produced by the algorithms.
- Results: PSROrN outperforms PSRON, PSROU, and self-play across a wide range of allowed compute budgets.PSROU and PSRON perform comparably, while self-play performs worst in the primary comparison.
- Results: PSROrN grows the gamescape more uniformly than the other algorithms and is the only method that increases convex-hull area at every iteration.All algorithms increase area overall, but only PSROrN does so at every iteration.
6. Conclusion
The paper presents gamescapes as a framework for open-ended learning in symmetric zero-sum games and proposes PSROrN to uncover strategic diversity. It positions the algorithms as foundations for combining game-theoretic adaptive objectives with gradient- and reinforcement-based learning.
- Conclusion: The paper proposes gamescapes to represent latent objectives and PSROrN to uncover strategic diversity in functional-form games.The framework targets two-player symmetric zero-sum games with differentiable agent parametrizations.
- Future scope: The algorithms are described as simple and generic foundations for unifying modern gradient and reinforcement-based learning with game-theoretic adaptive objectives.The paper identifies more complex games as a direction for future work.
- Scope and framing: The paper adopts a behaviorist characterization in which an agent is defined by all ways it can interact with other agents.Functional gamescapes capture possible interactions, while empirical gamescapes capture observed interactions.
- Scope and framing: The analysis restricts interactions to the pairwise facet reported by φ, although richer statistics could be examined in specific instances.Examples include which units are built or which pieces are taken.
- Related settings: The framework differs from GANs and much co-evolution work because those settings often involve asymmetric agents or interactions with different role semantics.The paper notes that asymmetric semantics are richer but more difficult to analyze.
D. Proof of theorem 1
The appendix extends combinatorial Hodge-theoretic tools from finite antisymmetric flows to functional games. It defines functional gradient, divergence, and curl operators and establishes the ingredients for a functional Hodge decomposition.
- Functional extension: The paper generalizes combinatorial Hodge-theory results from antisymmetric matrices to antisymmetric functions on agent spaces.The finite combinatorial setting appears when the compact agent space is finite.
- Functional setting: A functional game is an antisymmetric flow φ(v,w) specifying the flow from agent v to agent w.The agent space W is compact and equipped with a probability measure.
- Operators: The functional gradient maps a zero-mean function on agents to a flow, while divergence maps a flow back to a function on agents.The appendix defines curl as a three-agent operator on flows.
- Operator properties: The operators satisfy div ◦ grad(f) = f for zero-mean f and curl ◦ grad(f) ≡ 0.The divergence of every flow is also zero-mean.
- Hodge decomposition: The functional Hodge decomposition separates game space into orthogonal gradient-flow and curl-free components.The result is presented as a functional analogue of the Helmholtz decomposition.
E. Proofs of propositions
The propositions establish geometric properties of gamescapes, including equivalence under redundancy, low-dimensional representations, Nash-equilibrium geometry, and monotonic population performance.
- Proposition 2: Redundant populations have equivalent gamescapes when their added agents are empirically indistinguishable from mixtures of existing agents.Equivalence is expressed through mutually inverse projection and lifting maps between the polytopes.
- Proposition 3: The empirical gamescape of a population can be represented in R^r, where r = rank(AP).For antisymmetric evaluation matrices, a Schur decomposition constructs an isomorphic polytope in the rank-dimensional space.
- Propositions 4–5: Because antisymmetric games have value zero, empirical Nash equilibria are characterized geometrically through the associated linear-program solution.The value p⊺Aq is independent of the choice of Nash equilibrium, supporting a well-defined population-level performance measure.
- Proposition 5: If hull(P) ⊂ hull(Q), then v(P,Q) ≤ 0 and Q performs at least as well as P against any population R.Every mixture available to P is also available to Q, which yields the population-performance comparison.
- Proposition 6: Adding an agent that beats the Nash distribution strictly enlarges the empirical gamescape.Such an agent cannot be a convex combination of the existing population because any such combination would tie or lose to the Nash distribution.
Proof of proposition 7
The rectified Nash response objective is identified with effective diversity, linking the algorithm’s objective to coverage of the gamescape.
- Proposition 7: The objective constructed by rectified Nash response is effective diversity.The result connects PSRO_rN’s objective to the paper’s diversity-based geometric analysis.
F.1. Nash reweighting of evaluation matrices
Nash reweighting preserves antisymmetry while producing a matrix whose rows and columns all sum to zero.
- Nash reweighting: The Nash-reweighted matrix p ⊙ A ⊙ p is antisymmetric and has zero row and column sums.The construction uses an antisymmetric evaluation matrix and a Nash equilibrium with zero game value.
F.2. Diversity as a matrix norm
Effective diversity can be expressed as a particular matrix norm, providing an algebraic characterization of population coverage.
- Diversity as a matrix norm: Effective diversity is a matrix norm ℓp,q with p = q = 1.The paper notes that alternative norms, including Frobenius and spectral norms, remain an open direction for further study.
F.3. Reduction to the rock-paper-scissors
The paper constructs a rock-paper-scissors meta-game by reducing a Nash-supported population to three mixture agents, then proves their evaluation matrix has the standard cyclic form.
- Assumptions: The construction assumes a Nash equilibrium with support on at least three agents; two-agent support instead implies their pairwise payoff is zero.The three-agent reduction therefore targets equilibria with genuinely nontrivial support.
- Rock-paper-scissors reduction: The reduction constructs weight vectors and corresponding mixture agents representing rock, paper, and scissors.Mixture-agent evaluations are computed by weighting pairwise payoffs between the original agents.
- Rock-paper-scissors reduction: The resulting three-agent population forms a rock-paper-scissors meta-game.Its evaluation matrix is antisymmetric, with cyclic interactions among the three reduced agents.
- Rock-paper-scissors reduction: The proof establishes that the matrix parameters satisfy α > 0 and α = β = γ.Thus, the three cyclic matchups have equal positive strength in the reduction.
- Functional-form games: The broader framework treats parametrized-agent interactions as functional-form games, whose payoffs and approximate best responses may be estimated through reinforcement learning.The construction is presented among explicit mathematical examples of functional-form games.
- Functional-form games: The paper gives transitive, cyclic, and mixed symplectic examples, including a high-dimensional cyclic game and a mixed game with transitive and cyclic coordinates.The mixed construction has a transitive first-coordinate structure and cyclic structure in the remaining coordinates.
- Game constructions: The paper also describes long cycles and resource-allocation games, including Colonel Blotto and Continuous Lotto, as examples of nontransitive game structures.Differentiable Lotto provides additional differentiable symmetric zero-sum functional-form games.
- Embedding procedure: For visualization, the paper generates antisymmetric payoff matrices and compares Schur, PCA, SVD, and t-SNE embeddings of their game structures.The figures use two-dimensional embeddings and color agents by average payoff against the population.