Online Optimization in Games via Control Theory: Connecting Regret,
  Passivity and Poincar\'e Recurrence
  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].
