# Online Optimization in Games via Control Theory: Connecting Regret, Passivity and Poincar'e Recurrence

arXiv: https://arxiv.org/abs/2106.04748 · HTML: https://mlsanity.com/paper/2106.04748/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 47 references that are in the map.
- First posted on arXiv 9 Jun 2021.

## Builds on (most cited first, 17 of 17)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [The Mechanics of n-Player Differentiable Games](https://mlsanity.com/paper/1802.05642/) (2018)
- [Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization](https://mlsanity.com/paper/1807.04252/) (2018)
- [From Poincar'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization](https://mlsanity.com/paper/2002.08456/) (2020)
- [Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascent](https://mlsanity.com/paper/1907.04392/) (2019)
- [Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Games](https://mlsanity.com/paper/1905.08396/) (2019)
- [Graphical Models for Game Theory](https://mlsanity.com/paper/1301.2281/) (2013)
- [Chaos, Extremism and Optimism: Volume Analysis of Learning in Games](https://mlsanity.com/paper/2005.13996/) (2020)
- [Poincar'e Recurrence, Cycles and Spurious Equilibria in Gradient-Descent-Ascent for Non-Convex Non-Concave Zero-Sum Games](https://mlsanity.com/paper/1910.13010/) (2019)
- [Fast and Furious Learning in Zero-Sum Games: Vanishing Regret with Non-Vanishing Step Sizes](https://mlsanity.com/paper/1905.04532/) (2019)
- [A continuous-time approach to online optimization](https://mlsanity.com/paper/1401.6956/) (2014)
- [A Passivity-Based Approach to Nash Equilibrium Seeking over Networks](https://mlsanity.com/paper/1705.02424/) (2017)
- [Passivity Analysis of Higher Order Evolutionary Dynamics and Population Games](https://mlsanity.com/paper/1609.04952/) (2016)
- [Passivity and Evolutionary Game Dynamics](https://mlsanity.com/paper/1803.07744/) (2018)
- [Passivity Analysis of Replicator Dynamics and its Variations](https://mlsanity.com/paper/1812.07164/) (2018)

## Built on by (most cited first, 3 of 3)

- [Evolutionary Dynamics and Phi-Regret Minimization in Games](https://mlsanity.com/paper/2106.14668/) (2021)
- [Swim till You Sink: Computing the Limit of a Game](https://mlsanity.com/paper/2408.11146/) (2024)
- [Smooth Quadratic Prediction Markets](https://mlsanity.com/paper/2505.02959/) (2025)

## Abstract (arXiv)

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 energy conservation and dissipation in physical systems. It has become a standard tool in analysis of general feedback systems, to which game dynamics belong. Our starting point is to show that all continuous-time Follow-the-Regularized-Leader (FTRL) dynamics, which include the well-known Replicator Dynamic, are lossless, i.e. it is passive with no energy dissipation. Interestingly, we prove that passivity implies bounded regret, connecting two fundamental primitives of control theory and online optimization. The observation of energy conservation in FTRL inspires us to present a family of lossless learning dynamics, each of which has an underlying energy function with a simple gradient structure. This family is closed under convex combination; as an immediate corollary, any convex combination of FTRL dynamics is lossless and thus has bounded regret. This allows us to extend the framework of Fox and Shamma [Games, 2013] to prove not just global asymptotic stability results for game dynamics, but Poincar'e recurrence results as well. Intuitively, when a lossless game (e.g. graphical constant-sum game) is coupled with lossless learning dynamics, their feedback interconnection is also lossless, which results in a pendulum-like energy-preserving recurrent behavior, generalizing the results of Piliouras and Shamma [SODA, 2014] and Mertikopoulos, Papadimitriou and Piliouras [SODA, 2018].