Passivity, No-Regret, and Convergent Learning in Contractive Games

Hassan Abdelraouf, Georgios Piliouras, Jeff S. Shamma · 2025

Read Passivity, No-Regret, and Convergent Learning in Contractive Games by Hassan Abdelraouf, Georgios Piliouras, Jeff S. Shamma (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-22850.txt.

Introduction

Hassan Abdelraouf, Georgios Piliouras, and Jeff Shamma study when learning rules in games settle down and keep regret low, in a paper from 2025. The setting is continuous time play in games where strategies pull toward each other. The bridge they use is a passivity condition from control theory.

When a learning rule meets that condition, its regret stays finite. The authors show the condition holds for many standard rules and their higher order versions. Those versions can reach stable play where the plain rules cannot, while keeping regret finite. Examples show rules that break the condition can lose the finite regret property. A final sorting of rules by passivity type frames future analysis.

Catalog record

CREATORHassan Abdelraouf, Georgios Piliouras, Jeff S. Shamma
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE46 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-22850

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Passivity, No-Regret, and Convergent Learning in Contractive Games Hassan Abdelraouf, Georgios Piliouras, Jeff S. Shamma Abstract We investigate the interplay between passivity, no-regret, and convergence in contractive games for various learning dynamic models and their higher-order variants. Our setting is continuous time. Building on prior work for replicator dynamics, we show that if learning dynamics satisfy a passivity condition between the payoff vector and the difference between its evolving strategy and any fixed strategy, then it achieves finite regret. We then establish that the passivity condition holds for various learning dynamics and their higher-order variants. Consequentially, the higher-order variants can achieve convergence to Nash equilibrium in cases where their standard order counterparts cannot, while maintaining a finite regret property. We provide numerical examples to illustrate the lack of finite regret of different evolutionary dynamic models that violate the passivity property. We also examine the fragility of the finite regret property in the case of perturbed learning dynamics. Continuing with passivity, we establish another connection between finite regret and passivity, but with the related equilibrium-independent passivity property. Finally, we present a passivity-based classification of dynamic models according to the various passivity notions they satisfy, namely, incremental passivity, δ \delta -passivity, and equilibrium-independent passivity. This passivity-based classification provides a framework to analyze the convergence of learning dynamic models in contractive games. I INTRODUCTION No-regret online learning algorithms have become powerful tools in designing adaptive and efficient decision-making strategies within dynamic, uncertain, and competitive environments. These algorithms enable agents to make sequential decisions while minimizing their regret, defined as the difference between the cumulative reward of the algorithm and that of the best fixed action in hindsight [ 1 ] . Among the most well-known no-regret algorithms are Follow-The-Regularized-Leader (FTRL) [ 2 ] , which includes Multiplicative-Weights-Update (MWU) [ 3 ] as a special case, and Online-Mirror-Descent (OMD) [ 4 ] . By appropriately selecting a decreasing step size, these algorithms can achieve O(\sqrt{T}) regret. The intersection of online learning and game theory, often referred to as learning in games, explores how rational agents learn through repeated interactions in strategic settings, where each agent seeks to maximize its own utility while considering the strategies of others. In this framework, no-regret algorithms allow agents to learn and adapt from past interactions and, for some games, converge to equilibrium strategies without centralized coordination [ 5 ] . Indeed, fundamental connections have been established between no-regret learning and game-theoretic solution concepts [ 3 , 6 , 7 ] . Passivity is a fundamental input-output property of dynamical systems that abstracts the principles of energy conservation and dissipation in mechanical and electrical systems [ 8 ] . In the online learning context, learning algorithms can be viewed as an input-output operator where the input is the stream of payoffs and the output is the stream of strategies. This perspective enables the application of passivity theory to both analyze and design learning algorithms. For instance, [ 9 ] introduced the notion of \delta -passivity to study the convergence of learning dynamics to Nash equilibria in contractive games, showing that the implementation of a learning dynamic model in a game can be viewed as a feedback interconnection between the learning operator (with payoff as input and strategy as output) and the game operator (with strategy as input and payoff as output). Moreover, as demonstrated in [ 10 ] , if a learning dynamic model fails to satisfy a suitable passivity property, it is possible to construct a higher-order game that results in instability. Recent works [ 11 , 12 ] have further employed equilibrium-independent passivity to analyze convergence in zero-sum games and to design higher-order variants of learning dynamic models that converge in games where their standard counterparts do not. In this work, we adopt an alternative notion of passivity—specifically, passivity from the payoff vector to the difference between the output strategy and any fixed strategy—which is directly linked to the no-regret property of learning dynamics [ 13 ] . The main contributions of this paper are summarized as: • We show that the strategic higher-order variants of learning dynamic models that have finite regret not only improve convergence in zero-sum games, where their standard counterparts fail to converge, but also preserve the finite regret property (Section IV ). • Numerical examples are provided, illustrating that several evolutionary dynamic models used in population games lack the finite regret property (Section IV ). • The finite regret property of a learning dynamic model is shown to be fragile under payoff perturbations (Section V ). • A connection is established between finite regret and equilibrium-independent passivity (Section VI ). • Incremental passivity is shown to be a generalized notion of passivity that implies both equilibrium-independent passivity and \delta -passivity (Section VII ). • We utilize these results, along with existing \delta -passivity results for various evolutionary dynamic models [ 9 , 14 ] , to construct a passivity-based classification of learning dynamic models according to the passivity notions they satisfy: incremental passivity, \delta -passivity, and equilibrium-independent passivity (Section VII ). • We demonstrate that learning dynamic models that have finite regret converge globally to the unique Nash equilibrium in strictly contractive games. Moreover, our passivity-based classification provides a comprehensive framework for analyzing the convergence of learning dynamic models in contractive games (Section VIII ). II NOTATION We denote by \mathbb{R}_{+} the set of nonnegative real numbers. For a given vector x\in\mathbb{R}^{n} , x_{i} denotes its i -th entry. [x]_{+} denotes the nonnegative part of x , such that its i -th component is given by [x_{i}]_{+}=\max(x_{i},0) . \text{diag}(x) denotes n\times n diagonal matrix whose i -th diagonal entry is x_{i} for all i=1,\dots,n . I_{n}\in\mathbb{R}^{n\times n} is the identity matrix. \mathbf{1}_{n}\in\mathbb{R}^{n} is the vector of all ones and \mathbf{0}_{n} is the vector of all zeros. For two vectors x,y\in\mathbb{R}^{n} , the inner product is defined as \langle x,y\rangle=x^{T}y and the Euclidean norm is denoted by \|x\|_{2} . The probability simplex in \mathbb{R}^{n} is denoted by \Delta_{n} and is defined as \{s\in\mathbb{R}^{n}:s_{i}\geq 0\;\forall\;i=1,\dots,n\text{ and }\mathbf{1}^{T}s=1\}. \text{Int}(\Delta_{n}) denotes the interior of the probability simplex. e_{i}\in\Delta_{n} denotes the i -th vertex of the simplex \Delta_{n} , i.e., the vector whose i -th component equals 1 and all other components equal 0 . The tangent space of \Delta_{n} is denoted by T\Delta_{n} where T\Delta_{n}=\{y\in\mathbb{R}^{n}:\mathbf{1}_{n}^{T}y=0\} . The normal cone to \Delta_{n} at a point x\in\Delta_{n} is given by N\Delta_{n}(x)=\{y\in\mathbb{R}^{n}:y^{T}(x^{\prime}-x)\leq 0\;\forall\;x^{\prime}\in\Delta_{n}\}. For a closed convex set C\subset\mathbb{R}^{n} , \Pi_{C}(x) denotes the projection of x\in\mathbb{R}^{n} onto the set C and is given by \Pi_{C}(x)=\argmin_{s\in C}\|x-s\|_{2}. \sigma:\mathbb{R}^{n}\to\text{Int}(\Delta_{n}) denotes the softmax function such that \sigma(x)=\exp(x)/\sum_{i=1}^{n}\exp(x)_{i} . The space of square integrable functions over finite intervals is denoted by \mathbb{L}_{e} . i.e., \mathbb{L}_{e}=\left\{f:\mathbb{R}_{+}\to\mathbb{R}^{n}:\int_{0}^{T}f(t)^{T}f(t)dt<\infty\;\;\forall\;T\in\mathbb{R}_{+}\right\}. For f,g\in\mathbb{L}_{e} , the truncated inner produced is defined as \langle f,g\rangle_{T}=\int_{0}^{T}f(t)^{T}g(t)dt . III Background III-A Online Learning and Regret III-A 1 Continuous-time learning dynamics In this paper, we consider continuous-time learning dynamics where the payoff vector p(\cdot):\mathbb{R}_{+}\to\mathbb{R}^{n} is assumed to be a continuously differentiable function of time. In continuous-time (FTRL) dynamics, the process starts at time t=0 and for any t>0 , the learner computes the cumulative payoff as z(t)=z(0)+\int_{0}^{t}p(\tau)d\tau . The mixed strategy x(t)\in\Delta_{n} is then computed as x(t)=C(z(t)) where C(z)=\argmax_{y\in\Delta_{n}}y^{T}z-h(y), and h(y) is a differentiable

Read the complete text