The Evolution of Uncertainty of Learning in Games

Yun Kuen Cheung, Georgios Piliouras, Yixin TaoICLR 2022 · OpenReview

Introduction

In the study of multi-agent learning, researchers typically ask a standard question: will a learning algorithm eventually settle into a stable state, such as a Nash equilibrium? However, this traditional framing assumes we know the exact starting point of every agent. In reality, machine learning models and game-theoretic systems operate under "initial uncertainty." We rarely know an agent's private initial beliefs, environmental measurements are often noisy, and system initializations are drawn from dataset distributions.

This paper addresses a fundamental gap in the literature by shifting the focus from single-point convergence to the evolution of distributions. Specifically, it asks: Does initial uncertainty shrink (indicating stability) or grow (indicating chaos and unpredictability) as agents learn? While previous work has used "volume analysis" to show that sets of initial conditions can expand, this research provides a rigorous, information-theoretic treatment to quantify exactly how unpredictable these systems become over time.

Measuring Uncertainty with Differential Entropy

To measure this evolving unpredictability, the researchers employ Differential Entropy (DE), the continuous analog of Shannon entropy. Their analysis centers on the Jacobian matrix of the dynamical systems created by standard learning algorithms, particularly focusing on the popular Multiplicative Weights Update (MWU) and its variant, Optimistic MWU (OMWU).

Instead of analyzing the dynamics in the standard strategy simplex, the authors map the system to the cumulative payoff space, which proves mathematically more tractable. They demonstrate that if the determinant of the Jacobian matrix is greater than 1, the "volume" of the probability distribution expands. This expansion directly correlates to an increase in differential entropy, formally capturing the system's growing unpredictability.

The Linear Growth of Chaos and the "Grand Escape"

The study yields several striking insights into the behavior of learning dynamics in games, particularly two-player zero-sum games, coordination games, and one-population evolutionary games.

First, the authors discover that uncertainty in these systems grows exceptionally fast. In a simple system with random payoffs, uncertainty typically grows at a logarithmic rate ($O(\log T)$). However, for any non-trivial zero-sum game using MWU, the differential entropy increases linearly with time ($O(T)$). This means these learning-in-games systems become unpredictable much faster than simple random walks.

This linear growth leads to the paper's most significant conceptual takeaway: The "Grand Escape." Because entropy cannot increase indefinitely within a bounded space, the system must eventually "escape" the regions that produce high entropy growth. The authors mathematically prove that agents will inevitably drift away from interior Nash equilibria, pushing toward the boundaries of the strategy space.

Evolution of a probability distribution over time, illustrating the expansion of uncertainty and formation of vortices.

Previous volume analyses showed it was merely possible to reach chaotic states. By applying an entropy-based approach, this paper reveals how probable these states are, showing that probability density often concentrates in complex "vortices" far from equilibrium, as visualized in the system's evolving probability distributions.

Robustness and Broader Implications

The findings are remarkably robust. The authors demonstrate that even if a game's payoffs are slightly perturbed by noise in each round, the linear growth of uncertainty persists. Furthermore, the framework extends beyond standard zero-sum games; for instance, using OMWU in coordination games also results in linear entropy growth. In biological parallels (one-population games), if a species is rewarded more for intra-species play than inter-species play, uncertainty is guaranteed to grow.

Limitations and Future Directions

While theoretically profound, the current framework has some limitations. Stronger conclusions like the "grand escape" require the initial distribution to have "bounded support" (not spreading to infinity at the start), and the mathematical proofs often rely on the learning step-size being sufficiently small.

Looking forward, the authors suggest these results likely extend to the broader family of Follow-the-Regularized-Leader (FTRL) algorithms. A particularly exciting natural next step is applying this entropy framework to Generative Adversarial Networks (GANs)—which are essentially complex zero-sum games where training instability and unpredictable dynamics remain major practical hurdles.

Summary updated

Abstract

Learning in games has become an object of intense interest for ML due to its connections to numerous AI architectures. We study standard online learning in games but from a non-standard perspective. Instead of studying the behavior of a single initial condition and whether it converges to equilibrium or not, we study the behavior of a probability distribution/measure over a set of initial conditions. This initial uncertainty is well-motivated both from a standard game-theoretic perspective (e.g. a modeler's uncertainty about the agents' initial beliefs) as well as from a ML one (e.g. noisy measurements, system initialization from a dataset distribution). Despite this, little is formally known about whether and under what conditions uncertainty is amplified or reduced in these systems. We use the popular measure of differential entropy to quantify the evolution of uncertainty. We find that such analysis shares an intimate relationship with volume analysis, a technique which was recently used to demonstrate the occurrence of Lyapunov chaos when using Multiplicative Weights Update (MWU) or Follow-the-Regularized-Leader (FTRL) algorithms in zero-sum games. This allows us to show that the differential entropy of these learning-in-game systems increases linearly with time, formalizing their increased unpredictability over time. We showcase the power of the framework by applying it in the study of multiple related systems, including different standard online optimization algorithms in numerous games and dynamics of evolutionary game theory.
BibTeX
@inproceedings{cheung2022evolution,
  author = {Yun Kuen Cheung and Georgios Piliouras and Yixin Tao},
  title = {{The Evolution of Uncertainty of Learning in Games}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=Fza94Y8VS4a},
}
Figure