Chaos, Extremism and Optimism: Volume Analysis of Learning in Games

Yun Kuen Cheung, Georgios Piliouras

In multi-agent reinforcement learning and AI applications like Generative Adversarial Networks (GANs), training algorithms often fail to converge to a stable equilibrium. Instead, they frequently exhibit cyclic, divergent, or chaotic behavior. For instance, standard regret-minimizing dynamics like Multiplicative Weights Updates (MWU) diverge in simple zero-sum games, while game-theoretically inspired tweaks like Optimistic MWU (OMWU) manage to converge.

This paper seeks a unified, principled mathematical framework to understand why these discrete-time learning algorithms behave so differently across various types of games (e.g., zero-sum versus coordination games). Instead of relying on tedious, case-by-case analysis or potential functions that break down near boundaries, the authors introduce a generalizable tool to predict algorithmic stability and chaos: volume analysis.

Methods: Tracking Volume in Dual Space

The authors employ volume analysis, a tool borrowed from dynamical systems theory, and apply it to discrete-time learning algorithms.

  • Dual Space Analysis: Instead of analyzing the algorithms in the standard "primal space" (the simplex of action probabilities), they map the dynamics to a "dual space" representing aggregate cumulative payoffs.
  • Tracking Volume: They track how the volume (Lebesgue measure) of a set of initial conditions evolves over time when pushed forward by the algorithm. If the volume expands exponentially, the system is "Lyapunov chaotic"—highly sensitive to initial conditions and exhibiting the butterfly effect. If it contracts, the system tends toward stability.
Evolution and deformation of a volume of initial conditions over time.
  • ODE Analogue for OMWU: Because OMWU's update rule depends on both the current and previous time steps, standard volume analysis is difficult to apply directly. To solve this, the authors derive a novel continuous-time Ordinary Differential Equation (ODE) analogue. They show that OMWU is essentially an online Euler discretization of this ODE, allowing them to apply volume analysis cleanly.

Key Insights: The "No Free Lunch" of Game Dynamics

A central finding of the paper is that algorithm stability is highly dependent on the game type; there is no universally stable algorithm.

While MWU expands volume (and is thus chaotic) in zero-sum games, it actually contracts volume in coordination games. OMWU does the exact opposite: it stabilizes zero-sum games but becomes chaotic in coordination games.

Extremism and Unavoidability

The authors introduce a concept from control theory called unavoidability: if a region of "good" states is volume-expanding (which they term "uncontrollable"), the system cannot stay there forever. Because the volume grows too large to be contained, the system is mathematically guaranteed to eventually escape into "bad" states.

In zero-sum games, MWU's volume expansion leads to bizarre, highly unstable behavior termed extremism. Even if the game has a perfectly balanced, fully-mixed Nash equilibrium (like Rock-Paper-Scissors), MWU will inevitably push players to a state where they almost exclusively play a single strategy for long periods, repeatedly cycling through these extreme edges.

Divergent, chaotic trajectories typical of MWU in zero-sum games.

Key Mathematical Results

  • Proof of Extremism: The authors prove that for almost all zero-sum games, MWU with a sufficiently small step size will eventually drive the system to an "extremal domain." In this domain, players concentrate their gameplay on a single strategy with a probability of $\ge 1 - \delta$ (where $\delta$ is arbitrarily small).
  • OMWU Chaos in Coordination Games: They prove that OMWU in non-trivial coordination games expands volume exponentially at a rate of $1 + \Omega(\epsilon^2)$ per step. This makes it Lyapunov chaotic, with a predictable Lyapunov time bound of $\mathcal{O}((n+m)/(\epsilon^2 \delta^2 \alpha_1^2))$.
  • Continuous Analogue Derivation: The authors successfully derived a standard ODE system that perfectly mirrors OMWU via backward finite-difference and Euler discretization, bridging discrete algorithmic updates with continuous dynamical systems theory.

Limitations and Future Work

The paper is heavily theoretical and focuses primarily on two-player normal-form games (specifically zero-sum and coordination games). The proofs also assume a sufficiently small learning step size ($\epsilon$) for the volume analysis to hold.

While the authors do not explicitly outline a dedicated future work section, the natural next steps implied by their methodology would involve extending this volume analysis framework to more complex, high-dimensional settings. This could include general-sum games with more than two players, deep multi-agent reinforcement learning dynamics, or empirical validations of volume expansion and contraction in large-scale GAN training.

Summary updated

Abstract

We perform volume analysis of Multiplicative Weights Updates (MWU) and its optimistic variant (OMWU) in zero-sum as well as coordination games. Our analysis provides new insights into these game/dynamical systems, which seem hard to achieve via the classical techniques within Computer Science and Machine Learning. First, we examine these dynamics not in their original space (simplex of actions) but in a dual space (aggregate payoffs of actions). Second, we explore how the volume of a set of initial conditions evolves over time when it is pushed forward according to the algorithm. This is reminiscent of approaches in evolutionary game theory where replicator dynamics, the continuous-time analogue of MWU, is known to preserve volume in all games. Interestingly, when we examine discrete-time dynamics, the choices of the game and the algorithm both play a critical role. So whereas MWU expands volume in zero-sum games and is thus Lyapunov chaotic, we show that OMWU contracts volume, providing an alternative understanding for its known convergent behavior. Yet, we also prove a no-free-lunch type of theorem, in the sense that when examining coordination games the roles are reversed. Using these tools, we prove two novel, rather negative properties of MWU in zero-sum games. (1) Extremism: even in games with a unique fully-mixed Nash equilibrium, the system recurrently gets stuck near pure-strategy profiles, despite them being clearly unstable from game-theoretic perspective. (2) Unavoidability: given any set of good states (with a rather relaxed interpretation of “good” states), the system cannot avoid bad states indefinitely.
BibTeX
@inproceedings{cheung2020chaos,
  author = {Yun Kuen Cheung and Georgios Piliouras},
  title = {{Chaos, Extremism and Optimism: Volume Analysis of Learning in Games}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=WgDaFW4dfQn},
}
Figure