Learning and Evaluation in Non-Transitive Strategy Spaces

50 concepts37 papers

We naturally tend to think of skill as a ladder. If a Grandmaster defeats an intermediate player, and that intermediate player defeats a novice, we confidently predict that the Grandmaster will defeat the novice. This linear hierarchy relies on the assumption of transitivity: the idea that skill can be reduced to a single, scalar value where higher numbers consistently dominate lower ones.

Traditional competitive rating frameworks, such as the classic Elo system or the Bayesian TrueSkill model introduced by Herbrich et al. in TrueSkillTM: A Bayesian Skill Rating System, bake this transitive assumption directly into their mathematics. However, real-world strategic environments—from real-time strategy games like StarCraft II to classic board games like chess—frequently shatter this assumption. They are defined instead by non-transitive cycles, the multi-dimensional equivalent of Rock-Paper-Scissors, where Strategy A defeats Strategy B, Strategy B defeats Strategy C, but Strategy C completely dismantles Strategy A.

As Bertrand et al. demonstrate in On the Limitations of the Elo, Real-World Games are Transitive, not Additive, forcing these circular dynamics into a strict scalar hierarchy causes standard rating systems to misrank players and fail at predicting future matchups. To build robust artificial intelligence and accurately evaluate performance, we must abandon the skill ladder and learn to navigate the geometry of non-transitive spaces.

The Geometry of Strategy: The Spinning Top

How do we visualize a game where skill and style coexist? The authors of Re-evaluating evaluation proposed a geometric solution: decomposing a game's payoff matrix into two distinct components. The first is a transitive component, which represents a pure hierarchy of skill (climbing the ladder). The second is a cyclic component, which captures the non-transitive, style-based loops (the Rock-Paper-Scissors dynamics). Savani expands on this in Ordinal Potential-based Player Rating by utilizing neural network decompositions to isolate these style-based cycles while preserving ordinal win/loss relationships.

Interestingly, this cyclic structure is not uniformly distributed across all levels of play. Empirical studies of complex games like chess by Wang et al. in Measuring the Non-Transitivity in Chess and Xiangqi by Li et al. in JiangJun: Mastering Xiangqi by Tackling Non-Transitivity in Two-Player Zero-Sum Games reveal a spinning top geometry.

          ▲ Pure Transitive Skill (Elite Masters)
         / \
        /   \
       /     \
      |       |
     /         \
    |           | ◄ The Non-Transitive Bulge (Intermediate Tier)
     \         /    (Rich web of cyclic counter-strategies)
      |       |
       \     /
        \   /
         \ /
          ▼ Novices

At the very bottom of the top (novices), the game is highly transitive: players who understand the basic rules easily defeat those who do not. At the very peak (elite masters), the game narrows and becomes transitive again, as optimal play leaves little room for structural vulnerabilities.

However, at the intermediate skill levels, the strategy space bulges out dramatically. This mid-tier bulge is packed with non-transitive cycles. Intermediate players master different subsets of tactics, creating a complex web of counter-strategies where an overall "better" player can be consistently defeated by a lower-ranked opponent who happens to deploy a specific counter-style. This geometric bulge explains why human players frequently experience performance plateaus; mastering a single linear line of play is insufficient when the environment demands navigating an ocean of circular tactics.

Why Self-Play Chases Its Own Tail

In multi-agent reinforcement learning, the standard recipe for creating superhuman AI has long been self-play: letting an agent train continuously against recent versions of itself. In a purely transitive game, self-play acts as a powerful engine for optimization, sparking a continuous co-evolutionary arms race where each generation is strictly better than the last.

In a non-transitive environment, however, naive self-play fails catastrophically. Because every strategy has a potential counter, the agent simply learns to defeat its most recent incarnation. If the agent currently favors Rock, it will evolve to play Paper. Facing Paper, it will evolve to play Scissors.

As Arulkumaran et al. point out in AlphaStar: An Evolutionary Computation Perspective, this dynamic causes reinforcement learning algorithms to get trapped in infinite loops, endlessly cycling through strategies without ever achieving global improvement. The agent "forgets" how to defend against strategies it discarded dozens of iterations ago. Consequently, even if the agent achieves high performance against its immediate predecessors, it remains fragile and easily exploited by uncommon, unconventional, or "cheese" strategies that lie outside its immediate training loop, a vulnerability highlighted by Huang et al. in A Robust and Opponent-Aware League Training Method for StarCraft II.

Breaking Cycles via Population Diversity

To escape these strategic loops, modern frameworks shift the focus from optimizing a single agent to maintaining a diverse population of strategies. The foundational architecture for this approach is Policy Space Response Oracles (PSRO), formalized in this context by Balduzzi et al. in Open-ended learning in symmetric zero-sum games.

Instead of optimizing against only the latest opponent, PSRO treats the historical pool of discovered strategies as a "gamescape" (a convex polytope). It computes a meta-strategy—such as a Nash Equilibrium—over this entire population, and then trains the next generation of agents to execute a best response against this mixed distribution. This prevents the agent from chasing its own tail; it cannot switch entirely to Paper if it still has to defend against the historical presence of Scissors.

However, simply growing the size of the population is not enough. If the training algorithm generates minor variations of the same basic strategy, the population will cluster around a single node in the cycle. To prevent this, recent work introduces explicit mathematical constraints to enforce behavioral diversity:

  • Determinantal Point Processes (DPP): The authors of Modelling Behavioural Diversity for Learning in Open-Ended Games utilize DPPs to maximize the expected cardinality and geometric volume of the strategy set, ensuring that new agents actively push into unexplored regions of the behavior space.
  • Policy Hull Expansion: Rather than focusing purely on payoff outcomes, Yao et al. introduce PSD-PSRO in Policy Space Diversity for Non-Transitive Games. This method directly optimizes for expanding the "Policy Hull" in the strategy space, providing formal theoretical guarantees of convergence to a stable Nash Equilibrium even within highly non-transitive environments.

By forcing agents to confront a broad, diverse portfolio of counter-plays simultaneously, these methods anchor the learning process, ensuring that strategic breakthroughs represent genuine global progress rather than temporary local adaptations.

Evaluating Strength Without a Ladder

If skill cannot be plotted on a linear ladder, how do we evaluate whether an agent is actually improving? If Agent A defeats Agent B, and Agent B defeats Agent C, but Agent C defeats Agent A, declaring a definitive "winner" based on raw win rates is misleading. An agent could artificially inflate its score simply by racking up victories against redundant variations of a strategy it easily counters, while remaining entirely vulnerable to a single catastrophic counter-play.

To accurately evaluate progress in non-transitive spaces, researchers rely on game-theoretic solution concepts that evaluate agents relative to the entire strategy space:

  1. Nash Averaging: Introduced by Balduzzi et al. in Re-evaluating evaluation, this approach weights opponents according to their presence in the game's Nash Equilibrium. It automatically ignores redundant benchmarks and evaluates an agent based on its performance against an unexploitable meta-strategy.
  2. $\alpha$-Rank: This metric treats the payoff matrix as a landscape for an evolutionary drift process. It calculates the long-term stationary distribution of a Markov chain over the strategies, identifying which strategies act as stable "attractors" that players will naturally gravitate toward over time.

The primary bottleneck for these game-theoretic evaluations is computational complexity. Calculating a full payoff matrix for $n$ distinct strategies requires conducting $O(n^2)$ pairwise matches, which quickly becomes prohibitively expensive when evaluating complex deep reinforcement learning policies.

To resolve this challenge, Rashid et al. developed $\alpha$IG in Estimating α-Rank by Maximizing Information Gain, a Bayesian framework that uses information-theoretic sampling to focus match selection exclusively on the most consequential strategic interactions. Concurrently, Du et al. demonstrated in Estimating α-Rank from A Few Entries with Low Rank Matrix Completion that by leveraging low-rank matrix completion, the full $\alpha$-Rank profile of a massive strategy space can be accurately reconstructed using only a tiny fraction of the total possible matchup entries.

Ultimately, understanding non-transitivity changes how we view both AI training and human expertise. Progress in complex domains is not about climbing a straight ladder to higher power levels; it is about expanding one's strategic footprint to encompass, survive, and master the cycles of the environment.

Key Foundational Work

TrueSkillTM: A Bayesian Skill Rating System (2006) — contributed 1 concept elements to this direction.
Playing With Population Protocols (2008) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_non_transitive_strategy_cycles_481ebb9f,
  title = {non-transitive strategy cycles},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-transitive-strategy-cycles/rdr_481ebb9fe1904e5f99772af60cef5f52},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_non_transitive_strategy_cycles_481ebb9f_v1,
  title = {non-transitive strategy cycles},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-transitive-strategy-cycles/rdr_481ebb9fe1904e5f99772af60cef5f52/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}

See something wrong? Report a mistake