Online Optimization in Games via Control Theory: Connecting Regret, Passivity and Poincaré 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].
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
On the incremental form of dissipativity
Following the seminal work of Zames, the input-output theory of the 70s acknowledged that incremental properties (e.g. incremental gain) are the relevant quantities to study in nonlinear feedback system analysis. Yet, no…
FormLyapunov equations: a (fixed) point of view
The Lyapunov equation is the gateway drug of nonlinear control theory. In these notes we revisit an elegant statement connecting the concepts of asymptotic stability and observability, to the solvability of Lyapunov equa…
Towards convergence to Nash equilibria in two-team zero-sum games
Contemporary applications of machine learning in two-team e-sports and the superior expressivity of multi-agent generative adversarial networks raise important and overlooked theoretical questions regarding optimization …
Vocal Bursts Valence PredictionSmooth markets: A basic mechanism for organizing gradient-based learners
With the success of modern machine learning, it is becoming increasingly important to understand and control how learning algorithms interact. Unfortunately, negative results from game theory show there is little hope of…
BIG-bench Machine LearningOnline Monotone Games
Algorithmic game theory (AGT) focuses on the design and analysis of algorithms for interacting agents, with interactions rigorously formalized within the framework of games. Results from AGT find applications in domains …
Reinforcement LearningReinforcement Learning (RL)