Online Optimization in Games via Control Theory: Connecting Regret, Passivity and Poincaré Recurrence

Yun Kuen Cheung, Georgios Piliouras

Introduction

This research establishes a formal bridge between online optimization and control theory, demonstrating that popular learning algorithms—specifically Follow-the-Regularized-Leader (FTRL) dynamics—function as "lossless" physical systems. By reframing regret minimization through the lens of passivity, the study explains why multi-agent learning dynamics often exhibit perpetual, pendulum-like cycles (Poincaré recurrence) in zero-sum games rather than converging to a static Nash Equilibrium.

Problem Statement: The Disconnect in Multi-Agent Learning

In multi-agent systems, understanding how agents adapt over time is critical. Historically, two fields have approached this from different perspectives:

  1. Online Optimization focuses on "regret"—the measure of how much better an agent could have performed in hindsight.
  2. Control Theory focuses on "passivity" and "stability"—how a system manages energy and maintains control under feedback.

Despite their overlap, the mathematical link between regret and passivity has remained elusive. This gap is particularly evident in biology and economics, where the Replicator Dynamic (a form of FTRL) fails to settle in zero-sum games like Rock-Paper-Scissors, instead orbiting the equilibrium indefinitely. This paper provides a unified language to explain these energy-preserving behaviors.

Methodology: Learning as a Control System

The authors employ a control-theoretic framework, specifically Passivity Theory, to model the learning process. They treat learning as an input-output system where the input is the stream of payoffs and the output is the agent's strategy.

Feedback interconnection of a learning operator ($S_1$) and a game operator ($S_2$).

The methodology relies on three core components:

  • Storage Functions: In control theory, these act as energy meters. A "passive" system does not produce its own energy, while a "lossless" system conserves it perfectly.
  • Convex Analysis: The authors use the "convex conjugate" of regularizer functions to derive energy-like storage functions for FTRL.
  • Feedback Interconnection: As shown in the figure above, a game is modeled as two connected blocks: a learning operator ($S_1$) and a game operator ($S_2$). Analyzing the energy flow between these blocks determines the stability of the entire system.

Key Insights: The Physics of Learning

The central contribution of this work is the mapping of optimization concepts onto physical principles. The paper proves that all continuous-time FTRL dynamics (including Gradient Descent and Replicator Dynamics) are "lossless" systems. They do not dissipate payoff information; instead, they store it perfectly in their internal state.

Analogy between lossless learning dynamics and physical systems like gravity.

Key theoretical breakthroughs include:

  • Passivity $\implies$ Bounded Regret: The authors prove that if a learning dynamic is "finitely passive" (its energy has a lower bound), it is mathematically guaranteed to have constant regret. This provides a physical intuition for algorithmic performance.
  • The "Mix-and-Match" Property: The family of lossless learning dynamics is closed under convex combination. A hybrid of Replicator Dynamics and Online Gradient Descent remains lossless and maintains bounded regret.
  • Recurrence over Convergence: In constant-sum games, system energy is conserved. Because energy cannot dissipate, the system cannot settle into a Nash Equilibrium (a low-energy state). Instead, it must return near its starting point infinitely often—a phenomenon known as Poincaré recurrence.

Results and Implications

The theoretical framework was validated through several key theorems and simulations:

  • Theorems 7 & 8: Established the formal equivalence between finite passivity and constant regret.
  • Theorem 19: Demonstrated that in graphical constant-sum games with a fully-mixed Nash Equilibrium, agents using these dynamics exhibit recurrent, non-convergent behavior.
  • Numerical Validation: Simulations of Rock-Paper-Scissors and Cyclic Matching Pennies confirmed the theory, showing that the distance to the starting state periodically drops to near-zero ($10^{-3}$), even when mixing different learning styles.

Limitations and Future Directions

While this work provides a robust continuous-time analysis, most real-world algorithms operate in discrete steps. Extending passivity theory to discrete-time learning is a primary area for future research. Additionally, the authors suggest applying this framework to "active" or "dissipative" learning systems—those that intentionally manipulate "energy" to achieve faster convergence or increased robustness in non-zero-sum environments.

Summary updated

Abstract

We present a novel control-theoretic understanding of online optimization and learning in games, via the notion of passivity. Passivity is a fundamental concept in control theory, which abstracts e...
BibTeX
@inproceedings{cheung2021online,
  author = {Yun Kuen Cheung and Georgios Piliouras},
  title = {{Online Optimization in Games via Control Theory: Connecting Regret, Passivity and Poincaré Recurrence}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=m6A4yQGa4io},
}
Figure