Multi-Agent Learning under Uncertainty: Recurrence vs. Concentration
Authors: Kyriakos Lotidis
Panayotis Mertikopoulos
Nicholas Bambos
Jose Blanchet
Venue: NeurIPS 2025 spotlight ()
Keywords: game theory
Nash equilibrium
uncertainty
regularized learning
Primary area: theory
TL;DR: We describe where multi-agent learning concentrates in the presence of randomness and uncertainty

Abstract: In this paper, we examine the convergence landscape of multi-agent learning under uncertainty. Specifically, we analyze two stochastic models of regularized learning in continuous games—one in continuous and one in discrete time—with the aim of characterizing the long run behavior of the induced sequence of play. In stark contrast to deterministic, full-information models of learning (or models with a vanishing learning rate), we show that the resulting dynamics do not converge in general. In lieu of this, we ask instead which actions are played more often in the long run, and by how much. We show that, in strongly monotone games, the dynamics of regularized learning may wander away from equilibrium infinitely often, but they always return to its vicinity in finite time (which we estimate), and their long-run distribution is sharply concentrated around a neighborhood thereof. We quantify the degree of this concentration, and we show that these favorable properties may all break down if the underlying game is not strongly monotone—underscoring in this way the limits of regularized learning in the presence of persistent randomness and uncertainty

Multi-Agent Learning under Uncertainty:
Recurrence vs. Concentration
Kyriakos Lotidis Stanford University #lotidi@@stanford.o edu
Panayotis Mertikopoulos
Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP
LIG 38000 Grenoble, France panayotis.. panayotis. mww.iioooooooosoaaaaggaoooooo fr
Nicholas Bambos
Jose Blanchet Stanford University
Stanford University
Dambos@stanford.edt
jose. bww.bcchettttanford....
Abstract
In this paper, we examine the convergence landscape of multi-agent learning under uncertainty. Specifically, we analyze two stochastic models of regularized learning in continuous games-one in continuous and one in discrete time-with the aim characterizing the long-run behavior of the induced sequence of play. In stark contrast to deterministic, full-information models of learning (or models with a vamishing learning rate), we show that the resulting dynamics do not converge general. In lieu of this, ask instead which actions are played more often in the long run, and by how much. We show that, in strongly monotone games, the dynamics of regularized learning may wander away from equilibrium infinitely often, but they always return to its vicinity in finite time (which we estimate), and their long-run distribution is sharply concentrated around neighborhood thereof. We quantify the degree this concentration, and we show that these favorable properties may all break down if the underlying game is not strongly monotone-underscoome in this way the limits of regularized learning in the presence of persistent randomness and uncertainty.
Introduction
In its most abstract form, the standard model for online learning in games unfolds as follows: (i) at each stage of the process, every participating agent selects an action; (ii) the agents receive a reward determined by their chosen actions and their individual payoff functions; (iii) the agents update their actions, and the process repeats. In this general context, the agents have contend with various- and of uncertainty: (a) uncertainty about the game, the strategic interests of other players, and/or who else is involved in the game; (b) uncertainty about the outcomes of their actions, and which update directions may lead to better outcomes; and (c) uncertainty stemming from the environment, manifesting as random shocks to the players' payoffs and/ other disturbances. this regard, uncertainty could be either endogenous exogenous; but, in either case, it leads to players having to take decisions with very limited information at their disposal.
Our goal in this paper is to quantify the impact of uncertainty on multi-agent learning- and, more precisely, understand the differences that arise the players' long-run behavior when such uncertainty is present versus when it is not. A natural framework for exploring this question is within the greater setting of no-regret learning and, in particular, the family of folloo--he--egularicee leader" (FTRL) algorithms and dynamics [38, 64, 65]. This class contains several mainstay learning methods like online gradient descent (or, our case, ascent) [74], the exponential multiplicative
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

weights (EW) algorithm and its variants (HEDGE, ExP3, etc.) [1, 2, 40, 69I, and many others so it has become practically synonymous with the notion of online learning in games. Accordingly, we seek to answer the following questions:
What is the long- run distribution of regularized learning under uncertainty? Which actions are played more often, and by how much? Do the dynamies concentrate- and, if so, where?
Our contributions in the context of related work. Needless to say, the interpretation of these questions is context-specific, and it depends on the particular learning setting at hand. In this paper, motivated by applications to machine learning, signal processing and data science (which typically involve continuous action spaces and rewards), we focus on continuous games, and we consider two models of regularized learning, one in continuous time, and one in discrete time.
In continuous time, we model the dynamics of FTRL in the presence of uncertainty as a stochastic differential equation (SDE) perturbed by general Itō diffusion process, i.e., continuous-time martingale with possibly colored and/or correlated components. In the context of finite games, models of this type have been studied by, among others, Bravo & Mertikopoulos [10], Foster & Young [20], Fudenberg Harris [21] and Mertikopoulos & Moustakas [43, 44], the first two in an evolutionary setting, the latter as continuous- time model of the EW algorithm in the presence of random disturbances. Follow-up works in this direction include [10-12, 18, 25, 28, 49] on finite games, while [33-35, 47] considered a regularized learning model in convex minimization problems. The model which is closest to our own is that of [46, 48], who study the regret properties and guarantees of stochastic version of the dual averaging dynamics of Nesterov [57].
At a high level, our findings reveal crisp dichotomy between games that are null- moll-montt (like bilinear min-max games or zero-sum bimatrix games), and strongly monotone games (like Kelly auctions, Cournot competitions, joint signal covariance optimization problems, etc.). Specifically:
1. In null-monoo mull-monotone games, uncertainty induces a persistent drift away from equilibrium: the dynamics reach greater distances from equilibrium in finite time (which we estimate) and they require, on average, infinite time to return. In particular. if the game admits an interior equilibrium, the dynamics diffuse away esscping in the mean toward infinity or to the boundary of the game's action space-and they exhibit no concentration in any region of interior actions.
In strongly monotone games, uncertainty still induces a persistent outward drift, but this is now partially countered by the dynamics' deterministic component. Thus, in stark contrast to the null-monotone case, the players' learning trajectories end up a near-equilibrium region whose size scales with the level of uncertainty, and we estimate both the size of this region and the time required to reach it. Somewhat paradoxically, the dynamics return with probability 1 arbitrarily close to where they started, infinitely often, in way reminiscent of Poincaré recurrence in bimatrix min-max games [52, 59]; however, these returns can be exceedingly far apart, so there is no antinomy.
In discrete time, we consider standard implementation of FTRL with constant learning rate and stochastic first-order oracle feedback. Variants with a vanishing learning rate have been studied extensively in the stochastic approximation literature, and they are known to exhibit favorable convergence guarantees in, among others, strongly monotone games, cf. [50, 54] and references therein. At the same time however, these properties typically come at the expense of the algorithm slowing down to a crawl; for this reason, owing to their simplicity, robustness, and superior empirical performance, constant/ non- vanishing learning rate schedules are much more common in practice.
On the downside, the long-run behavior of FTRL is much less understood in this case. To the best of our knowledge, the most relevant results come from recent works by Loizou et al. [41] and Huang & Zhang [27], who established upper bounds on the mean distance to equilibrium for stochastic gradient descent/ / ascent in strongly monotone games, and Vlatakis et al. [68], who studied the ergodic properties of constant step-size variants of the stochastic extragradient and stochastic gradient descent-ascent algorithms for weakly quasi-strongly monotone variational inequalities. Dually to this, in the mull-monotone regime, Cauvin et al. [12] showed that FTRL exhibits a similar tendency to escape from interior equilibria in finite min-max and harmonic games; our continuous-tin analysis is, in this view, an extension of the corresponding result of [12].

---

One reason that results about the statistics of the long-run behavior of FTRL are particularly scarce in the literature is that, in discrete time, even the most basic tools of stochastic analysis are often inapplicable; for an illustration of the difficulties involved, see e.g., Azizian et al. [3, 4] and references therein. Nevertheless, based no small part on the insights gained by our continuous- we manage to establish the following version of the strong-null dichotomy in discrete time:
analysis,
1. In null-monotone games with an unbounded action space, the sequence of play under FTRL drifts away to infinity on average (though not necessarily with probability 1).
2. In strongly monotone games, we show that the mean time required to reach a given distance from the game's s equílibrium finite, and we provide an explicit estimate thereof. If the game's equilibrium is interior, we also show that FTRL converges strongly to unique invariant measure, which is concentrated in a certain region around the game's 's equilibrium, which we also estimate.
We find these results particularly appealing as they provide the first glimpse into the distributional properties of multi-agent regularized learning under uncertainty.
2 Preliminaries
2.1. Continuous games. Throughout the sequel, we consider games with a finite number of players and continuum of actions per player. Formally, players will be indexed by E .N' = (1..... N) and, during play, each player will be selecting an action x; from a closed convex subset X; of some d,-dimensional normed space V; Aggregating over all players, we will write X' 11: Xr for the space of the players' joint action profiles x = (XI,..., .N) and d = Σi d; for the dimension of the ambient space V [1 V/. Finally, we will use the shorthand
(xz;x-;) when want to highlight the action of player i E N against the action profile x = (xx) jæi of all other players-and, in similar notation, X-; J X2 for the space thereof.
The reward of each player i E N in a given action profile will be determined by an associated payoff function u, X - R, assumed here be individually concave in the sense that (x)xx) is concave in xy for all x- E X- We will further assume that each u, is B-Lipschitz smooth, and we will write respectively
0x(x) = V,,,;(X;X--) and v(x) = (x)......, UN (x))
for the individual gradient field of each player and the ensemble thereof.' !
The tuple G G(V,X,,) will be referred to concave game [62]. Mainstay examples of such games include (mixed extensions of) finite games, resource allocation problems, Kelly auctions, Cournot competitions, etc.; for completeness, we detail some of these applications in Appendix A.
2.2. Nash equilibrium. The leading solution concept in game theory is that of a Nash equilibrium, defined here as an action profile x" E X' which discourages unilateral deviations, i.e.,
(x(x") (xx; for all x; E X; and all i E N.
(NE)
A concave game always admits a Nash equilibrium if X' is compact, and it admits a unique equilibrium if the game is strongly monotone in the sense of Definition below:
Definition 1. A game g G(V, u) is called a-monotone if there exists some 2 0 Ouch that
(u(x') - uxx),x'' <-al|x' x11 for all x,x' E X.
(Mon)
If (Mon) holds for some > O, the game will be called strongly monotone; otherwise. if (Mon) only holds for a = O, 9 will be called merely monotone (or simply monotone when the distinction is not important). Finally, if (Mon) binds for 0 and all x,x' E X't is, (u(x') v(x)),x x) = for all x E X' the game will be called monoonoe.
Remark 1. Merely monotone games could be viewed as "hybrid" between null and strictly monotone games: generically, at any given action profile of merely monotone game, there would be directions of motion where the (symmetrized) Jacobian of the players' gradient field has a zero eigenvalue, and directions with positive eigenvalues; either set (but not both) could be empty, the former corresponding to the mull-monotone directions, the latter corresponding to the "strongly monotone" ones.
We are tacitly assuming here that the players' payoff functions are defined in an open neighborhood of X in V: this assumption is done only for convenience, and it does not affect any of results.
3

---

Remark 2. A weighted variant of (Mon) is sometimes called diagonal (strict / strong) concavity, in reference the work of Rosen [62]; for pointed version of these conditions known as variational stability [26, 50, 54] or coherence [53, 73]. These variants will not be important for our purposes. T
2.3. Regularized learning. In the rest of our paper, we will consider a family of online learning schemes adhering the following model of "regularized learning": players aggregate gradient feedback on their payoff functions over time and, at each instance of play, they choose the action which is most closely aligned to this aggregate. We provide detailed description of this model in Sections 3 and i-nn continuous and discrete time respectively- and only describe here the core idea.
At high level, the common denominator of these schemes is the way that players choose their actions based on the accumulation of payoff gradients over time. Formally, we will treat payoff gradients as dual vectors and we will write } V for the dual space of V; and y Π.. )i V for the ensemble thereof. Then, given an aggregate of gradient steps yi E 3/. we will assume that the i-th player chooses action via a "generalized projection" general form
mirror map 2 > X of the
Qi(yr) arg maxx, x() (xx)) for all yr Vi. In the above h4: 2, - i continuous K,-strongly convex function, that is, 1))
(,x; + (1 1)x,) S (x; (1- ()),)x(xx) -
(3)
for all x;,,/e E X; and all A [0, 1j. This function is known as the regularizer of the method and it acts as a penalty term that smooths out the "hard" arg max correspondence yi + arg max; max,(y..x)) xi). This regularization scheme has very long and rich history in game theory and optimization, where Q is often referred to as a "quuantal" or "regularized" best response operator, cf. [38, 42, 50, 64, 67] and references therein. For concreteness, we describe below the two leading examples of this regularization setup (suppressing in both cases the player index i E N for notational clarity):
Example 1 (Euclidean regularization). Let h(x) 11x1112 Then (B.12) boils down to the Euclidean projection map
( (g) = arg max x112- Thus, in particular, if X = V. we readily recover the identity map Q(y) = y.
Example 2 (Entropic regularization), Let X' = fx E R4 Σ X = 1} be the unit simplex of Rd and let h(x) >% Xx log.x denote the (negative) entropy on X. Then (B.12) yields the logit map (xpoly)))....pp((())) Q A(y) exp(y))
exp(ya)
This map forms the basis of the seminal HEDGE and EXP3 algorithms in online learning, cf. [1, 2. 13, 38, 40, 64] and references therein.
To ease notation in the sequel, we will write h(x) = Ei hx,x, for the players' aggregate regularizer, K := min; K; for the strong convexity modulus of h, and Q = 1I; 2; y - X for the resulting ensemble mirror map. In the next sections, we describe detail how this regularization setup is used in learning context.
3 Learning under uncertainty in continuous time
To set the stage for the sequel, we begin with two simple games that will serve as "minimal working examples" for the more general model and results presented in the sections to come. We focus for the moment on continuous
interactions; the discrete-time setting is presented in Section 4.
3.1. A gentle start. Consider the following 2-player, convex-concave min-max games: for x1, R. xx)x -u2 = x3//2 x3/2 for R. (6b)
(a) Bilinear saddle:
xx)x = -42 xx1
(6a)
(b) Quadratic saddle:
Both games are monotone and they admit a unique Nash equilibrium at the origin. Their gradient fields are xx) (-x2,x)) and v(x).x2) x2) respectively, so the first game null- monotone and the second one is I-strongly monotone. Accordingly, if each player follows their individual payoff gradient increase their rewards, we obtain the gradient descent/ ascent dynamics
(a) x(t) (1)) and (b) x(1) (x)((),x22()))
(GDA)

---

for the bilinear and quadratic games (6a) and (6b) respectively. It is then trivial to see that, in the bilinear case, (GDA) cycles periodically a constant distance from the game's s equilibrium, whereas, in the quadratic case, the dynamics converge to the game's s equilibrium at geometrie rate.
To model uncertainty in this setting, will consider the stochastic gradient dynamics
dx =(X(r) dr or dW(r)
(S-GDA)
where W(1) (I) W2(()) a Brownian motion in R² and or > 0 the magnitude of the noise entering the process. Intuitively, this SDE should be viewed as a rigorous formulation of the informal model (t) ((x(1)) "noise", with the Brownian term W(1) capturing all sources of randomness and uncertainty in the players' environment. Consequently, understand the impact of uncertainty in each case of (GDA), we will examine the following quantities:
1. The distance ( 2 of X(r) from the game's equilibrium (that is, the origin of R²).
2. The time T, in (z 0: ||x(r))l2 $ r) at which X()) gets within of the game's s equilibrium.
3. The density t) of ( (nd) if it exists, its long-run limit (w) lim P)x,
When it exists, Poo is known as the stationary-or invariant-distriinn related to the occupation measure H4, of the process, defined here as
of X, and it is closely
1 S ((X(s) E B} ds for every Borel B C X. (B) = -
(7)
Under mild ergodicity conditions [30, Cor. 25.9], we have lim H4 (B) = L/3 Peo so, concretely, Pa. measures the fraction of time that (r) spends in given subset of X' in the long run.
Taken together, these metries provide fairly complete picture of the statistics of X(r) so, in the rest of this section, we analyze them in the context of (S-GDA) applied to the games (6a) and (6b).
Case 1: Bilinear saddles. In this case, by a direct application of Itô's formula- chain rule of stochastic calculus [58, Chap. 4e readily obtain
d ((Ix()) 2x(r) dx(r)= + dx(1) dx(()= 20 dt + o X(1) dW(r).
(8)
This suggests that, on average. (X increases as @ Building on this observation, we show in Appendix D that the dynamics (S-GDA) for the bilinear game (6a) enjoy the following properties:
Proposition 1. Suppose that (S-GDA) is run on the game (6a) with initial condition xo e RR. Then:
1. lim E.,, [1
i.e., X()) escapes infinity in mean square.
[x,[T,]= 0o r < ||x0||. i.e., X(1) takes infinite time on average to get closer to equilibrium.
3. The limit (x) = li (xx,() does not exist, i.e., X does not admit an invariant distribution.
Proposition shows that, in the presence of uncertainty, the periodicity of the deterministic dynamics (GDA) is completely destroyed. In fact, despite random fluctuations that occasionally bring X(r) closer equilibrium, (S-GDA) exhibits consistent drift away from equilibrium, escaping any compact set in finite time and requiring infinite time to return on average. As result, X(r) becomes infinitely spread out in the long run, exhibiting no measurable concentration in any region of R², For partial illustration of this wehic we view as antithetical to convergence cf. Fig. 1. "
Case 2: Quadratic saddles. We now proceed to examine the behavior of (S-GDA) in the quadratic min-max problem (6b), where (S-GDA) gives
dx(r) -(() di dW(1).
As is well known [36, Chap. 7.4], this SDE describes the 2-dimensional Ornstein-UUllebber (OU) process
(()) = X' + + L ((-s) dW(s).
(OU)
Hence, by unfolding the stochastic integral in (OU), we can draw the following conclusions:
Proposition 2. Suppose that (S-GDA) is run the game (6b) with initial condition xo E R². Then:
For primer SDEs, [36, 58]; for completeness, also present some basic definitions in Appendix C.
5

---

1. limy- Exi [IX([]]] =o² i.e., the dynamics fluctuate at mean distance o from equilibrium.
2. The mean time required to get within distance of the game's 's equilibrium is bounded
1 ||xoll2 ,²
Ex [T,[T] 1 2 22 02
for all o < ||xoll2.
(10)
3. The density of X(1) is 1)x,1) = [TO² - e - exp 1xx-e- xoll?
(1-c- ")r In particular, X(1) con-
verges in distribution to Gaussian random variable centered at 0, viz.
(x) = lim, P(x, r) 1/(xo2) e -- -
(1I)
Proposition 2 shows that the geometric convergence properties of the deterministic dynamics (GDA) are again destroyed in the presence of uncertainty. However, in stark contrast to Proposition I for the bilinear case, X()) now exhibits a consistent drift toward equilibrium, and it ends up being sharply concentrated at distance of ((r²) from equilibrium. This interplay between recurrence and concentration will play a crucial role in the sequel, and our aim in the rest of this section will be to quantify the extent to which it holds in a more general setting.
3.2. Learning in continuous time. We now proceed to describe our general model for multi-agent learning under uncertainty, hinging on the stochastic
-eeadeeeeddled"r" template
dr, (x()(()) di (1,
= ((1)=)(()()))
(S-FTRL)
In the above, (i) (r) )i is "score" variable that tracks the aggregation of individual payoff gradients in Vú; (it) M;(1) E }/: is a continuous -quare-integrable martingale acting as a catch-all, "colored noise" disturbance term; and (iti 3/ X; is the regularized mirror map of player E NN, as per (B. In this regard, (S-FTRL) represents a noisy "stimulus-response" mechanism, where each player V tracks the aggregation of payoff gradients under uncertainty-the "stimulus"-and "responds" to this aggregate via their individual regularized mirror map Q--
The terminology scheme in the context of online convex optimization discrete time. This family of algorithms and dynamics has been widely studied in the literature; we provide more details on this in Appendix B. T
Remark 3.
saalllowthe-rguulriizeeed leaderr" is due to [64, 65], who first studied this
For concreteness, we will assume that the noise term M(1) (M:(O)ieN in (S-FTRL) is of the form
dM(r) = (X(r)) dW(r) or, more explicitly dM2(1) = o, (X(()) dW(r)
(12)
where W(r) = (WI (t) is a standard Brownian motion in IR" and o = (x)) is an ensemble of state-dependent diffusion matrices o;: X; - R4 i 3 Importantly, the model (12) allows for correlated uncertainty between different components of the process- e.g., accounting for random disturbances shared road segments in a congestion game-so so it will be the base model for our analysis. Our only standing assumption will be that or: X - Raxm= is bounded and Lipschitz continuous, which ensures that (S-FTRL) is well-posed, i.e., it admits unique strong solution that exists for all time and for every initial condition Y(O) < E y (cf. Appendix C).
Remark 4. To connect the above with Section 3.1, note that (S-GDA) is recovered from (S-FTRL) by taking. X; R, (1) = o (r), and (x;x)) = x 2 for = 1, 2 (so (y))) yt by Example 1).
3.3. Analysis and results. We now proceed to describe our main results for the stochastic dynamics (S-FTRL) which, as we show shortly, reflect the dichotomy between bilinear and quadratic saddle- point problems that we noted in Section 3.1. To state them, it will be convenient to introduce a "primal- dual"gena generalization of the Euclidean distance that is more closely aligned with the regularization setup underlying the players' response scheme. Deferring the details to Appendix B, we define here the Fenchel coupling induced by the regularizer h, of player i N as
F. 91) h.(p)) (1:))) (u),,;) for all i N,, and all p; X, y: 3/
(13)
'The representation (12) of (1) via Brownian integrator is not an assumption per se, but a consequence of the martingale representation theorem, which allows us to express any homogeneous equare-integrale martingale in this form [58, Thm. 4.3.4). Under this light, the loss in generality is negligible in our case.

---

where (v:) == e xy), - h,(xx)) denotes the convex conjugate of h, For example, in the unconstrained Euclidean case (Example 1), we recover the Euclidean distance squared, viz. Fi yr) 1 (y) pill:: by comparison, under entropic regularization on the simplex (Ex- ample 2), we get a "dualized" version of the Kullback-Leible divergence, cf. Appendix B. In all cases, F; is positive-semideefiite in the sense that (p 9:) 2 0 for all yi V/, with equality if and ony if Qu()i) P:. In view of this, the total coupling F(x. y) == En Pi y:) is a valid measure of "divergence" between p E X and y E y, and we will use it freely in the sequel as such.
The last ingredient that we will need is two measures of the amount of randomness in (S-FTRL), viz.
2 = min Amin ((x)) and o max xaxxeX Amax (E(x))
(14)
min
where Σ = T denotes the quadratic covariation matrix of the martingale (1), and Amin (resp. max)) denotes the minimum (resp. maximum) eigenvalue thereof.
With all this in hand, we will focus on two broad classes of games, null-monotone and strongly monotone, of which the bilinear and quadratic examples of Section 3.1 are archetypal examples. To state our results, we will assume that (S-FTRL) is initialized at xo < Q(yo) E ri for some yo E y and we will write F, F(x", y())) where x" is equilibrium of the game. We then have:
Theorem 1 (Null-monotonn games). Suppose that (S-FTRL) is run with smooth mirror map Q null- mull-monotone game Suppose further that the game admits an interior equilibrium x², and consider the hitting times _ == (n > 0 F, s Fo E\ and T == inf > 0: F, 2 Fo E). If o² min" > O and & > is small enough, then
Ex oo and Fm & 2 (K o min)
(15)
for some constant K Kg 0; addition, X(1) does not admit limiting distribution in this case.
Theorem (Strongly monotone games). Suppose that (S-FTRL) is run in an a-strongly monotone
game G, and consider the hitting time
T == in > 0: x(1) E Bx()))
(16)
where (x') (x -----xx1 $ r) is a ball of radius r centered on the (necessarily unique) equilibrium x" of G. Then:
Exp [T, (Fooa)/(12211)) (ra) for all r To,
(17)
where To == (max/ /2Ka.. If. in addition, Jmin > 0 and x" is interior, X() admits an invariant distribution concentrated in a ball of radius ( around x", and we have
lo Mr (B, (x*))
/22 for all Ta.
(18)
Remark 5. The bounds depend implicitly on the regularizer through its strong convexity modulus K and they indicate trade-off between the degree of concentration of the process around the radius beyond which the noise dominates the drift, and the time required to hit this region.
Remark 6. The result of Theorem 2 holds for radius of concentration not sharper than O(or). This coincides with the special case of Proposition 2, indicating that our bound is tight in this regard.
Conceptually, Theorems and reflect the dichotomy between the bilinear and quadratic examples studied in detail in Section 3.1. Indeed, we see that:
In mall-monotone games, the stochastic dynamics (S-FTRL) exhibit a consistent drift away from equilibrium, moving to greater distances in finite time, and requiring infinite time to return. As a result, if the game has an interior equilibrium, X(r) becomes infinitely spread out the long run, exhibiting concentration in any region of X' other than, possibly, its boundary (if X' is constrained).
2. In strongly monotone games, the dynamics drift toward equilibrium, and they end up being concentrated around the game's (necessarily unique) equilibrium. However, the players' learning trajectories continue to fluctuate at a distance which scales as ( and, with probability 1, they return arbitrarily close where they started, infinitely often.
These properties paint a sharp separation between null- and strongly monotone games, with uncer- tainty carrying drastically different consequences in each case; for an illustration, see Fig. I.
7

---

The proof of Theorems 1 and 2 is detailed in Appendix D. From a technical standpoint, our analysis hinges on the use of the Fenchel coupling (13) as a "mean" energy function for the dynamics. In the null-monotone case, the hitting time estimates (15) rely on an application of Dynkin's formula [58, Chap. 7.4], coupled with an eigenvalue estimation for the growth of F. Then, by descending to specific quotient of )' that compactifies the sublevel sets of F, we are able to leverage the fact that [T>] = oo for r < Fo to show that the dynamics are not positively recurrent-and and hence, they do not admit an invariant distribution. The analysis for the strongly monotone case has the same starting point, but then branches out almost immediately: the hitting time estimate (17) is again obtained via Dynkin's 's stopping time formula, but positive recurrence can no longer be established in X. because the infinitesimal generator of ( is not uniformly elliptic (that is, its eigenvalues work directly with the infinetisimal generator of the
are not bounded away from zero). Instead, score process Y(/) whose generator is uniformly elliptic after taking a specific quotient in y. This allows us deduce positive recurrence in V, which we then push forward to A' via Q, and leverage the convergence of the occupation measures to the invariant distribution of the process to derive the concentration bound (18). We detail these steps in series of technical lemmas in Appendix D. Remark 7. If the game is neither null- nor strongly monotone, our analysis suggests that (S-FTRL) would tend to "wander around" the null-monotone directions, and be carried along the strongly monotone directions toward the game's m set of equilibria. However, obtaining precise version of such a result is quite involved, so we defer it to future work.
4 Learning under uncertainty in discrete time
We now turn to the discrete-time setting, which is of more direct algorithmic relevance. Compared to Section 3, the analysis here is considerably more involved due to the lack of closed-fore form solutions and the limited upplicability of liffusion-based methods. Nevertheless, as we shall see later in this section, the structural insights gained from the continuous-time analysis remain highly valuable as they form the foundation of the tools and techniques developed here.
4.1. Learning in discrete time. In discrete time, the most widely used implementation of the FTRL template unfolds for 1 0, I.... as
Y1,++1 = Yr, + y0g,r Xi,++1 = 2i(Y,r+1).
(FTRL)
In addition to the notions already introduced and discussed in Section 3.2, (i) it. denotes here a stochastic estimate of the player's 's payoff gradient vector at Xt.r: and (ii) y > 0 step-size parameter, interchangeably referred to as the learning rate of the process. We discuss these two new elements below.
The feedback process. In terms of feedback, we assume that, at every round / = 0, l...., each player E E receives stochastic gradient feedback of the form
0j,r = v,, or, aggregating over all players 0, = V(X;;o)))))
(19)
where 0, (8ir and v(x; = (V, is stochastic first-order oracle for v(x), viz.
v(x: = o(x) U(x;
(SFO)
In the above, wr. 0, l.... is an i.i.d. sequence of random seeds drawn from some complete probability space 2 and w(); is random y-valued vector satisfying the standard assumptions
E, 0 and E [|]U(x;; [I]] s o
(20)
1, for some o > 0. In this way. letting F,, 0, I...., denote the history of the process up to time
and writing U, = w() for the noise in the players' gradient feedback at time 1, we get
6, = uXx) U, with E[U, F,] 0 and E[ 1
(21)
Following standard practice in the field-sec e.g., [68, 71] and references therein-we further assume that the probability distribution Vx of U(x) decomposes as yx = r + v where: (a) v is singular relative to the Lebesgue measure dy on V: (b) vf is absolutely continuous relative to dy; and (c) the density Px (t) of v is jointly continuous in and y. and it satisfies infyek Pa (y) > 0 for every compact set K. S X and all y E y. This last assumption is relatively mild and ensures that the noise retains a non-degenerate, smooth component across X,, much like the assumption m > 0 for the diffusion matrix of (S-FTRI) in Section 3.4
*This condition is trivially satisfied by most continuous error distributions in practice, and it can always be enforced by injecting small uniform Gaussian noise component into the process, technique which is widely
8

---

Figure 1: Trajectories and statistics of play under (FTRI)) with entropic regularization in two min-max games over [0. IJ², .,a a bilinear and a quadratic one (left vs, right half respectively). Deterministic orbits are plotted in red and stochastic trajectories in shades of blue, with darker hues indicating later points in time; the density plots depict the resulting visitation frequency in X. In tune with Theorems 3 and 4, we see that learning in mull-monotone games drifts toward the extremes of X:; by contrast, in strongly monotone games, learning orbits drift toward equilibrium, but continue to fluctuate around More details are provided in Appendix F.
The algorithm's learning rate. The second feature which sets the discrete-time framework apart the method's s learning rate y. Here and throughout, we consider constant learning rate schedule; this should be contrasted to the stochastic approximation literature [6, 9, 37, 50, 54], where (FTRL) run with a vanishing step-size Yt - 0, typically satisfying some form of the summability conditions Σ, Yr- 00, Σ, y c0.
In many cases, the of vanishing step-size enables convergence of the algorithm because dampens the impact of the noise over time [50]; at the same time however, in many applied settings, algorithms are implemented with constant-orf -r, the very least, non-vanishing- www--aiinnn--te--siiiiiii step-sizze This choice is largely driven by practical considerations: constant step-size schedules are easier to calibrate and maintain, particularly in large-scale systems where adaptivity and simplicity are critical. Moreover, vanishing step-size schedules often exhibit prolonged transient phases and converge slowly toward equilibrium neighborhoods; by contrast, constant step-size methods tend to reach near-stationn star-stationary regions much faster, even within 0. 1% accuracy or lower [16]. This behavior underlies their widespread use in modern machine learning pipelines, where learning rates are kept effectively constant throughout training, even for models trained over billions of samples and/or hundreds of billions of tokens| [15].
4.2. Analysis and results. We now have the necessary machinery place to present our results for (FTRL). Before doing so, we should only stress that the discrete-time analysis is, by necessity, more qualitative than the more explicit, continuous-time results presented in Section This gap difficult to avoid: in continuous time, the rules of stochastic calculus comprise a very sharp set of tools with which to obtain closed-form estimates for the processes involved; on the other hand, discrete time, even the most basic tools of stochastic analysis like Dynkin's 's formula are dulled down because of measurability and subsampling issues.
As before, we split our focus between null- and strongly monotone games.
The null-monotone regime. A key take-away from the analysis of Section 3 is that, in null- monotone games, uncertainty causes the dynamics of regularized learning to spread out, diverging to infinity on average, without concentrating at any region of X' other than its boundary. Our first result below shows that a version of this tenet continues to hold in discrete time:
Theorem 3 (Null-monotone games). Suppose that (FTRL) is run in a null- mull-monotone game G, and let x" be equilibrium of G. Suppose further that h' is strongly convex, and let F, F(x", Y,). where is the induced Fenchel coupling (B.22). Then lim, E[F,] co.
This result shows that (FTRL) drifts away to infinity average- though, of course, as in the continuous- time case, this does not mean that this occurs with probability 1. What is missing from Theorem 3 relative to Theorem is bound the mean time required for F, to increase decrease by 8. In the absence of a consistent drift component, our continuous-time estimates were only made possible through the use of stochastic calculus. In discrete time however, X, evolves in discrete, driftless jumps, introducing overshoots and upcrossings that render this question significantly harder.
used in both optimization and reinforcement learning to promote sufficient exploration and avoid degeneracy issues and saddle- saddle-points [6, 22, 39, 70J. In such cases, the density of the absolutely continuous component is strictly positive everywhere and independent of E X, so the uniform lower bound condition holds trivially.

---

We conjecture that similar bounds do hold in discrete time, but we leave this open as a conjecture. [We only note here for completeness that a similar result holds for any decaying step-size sequence y, with E, y = oo.]
The strongly monotone regime. We now turn to the long-run behavior of (FTRL) in strongly monotone games. Based no small part on the continuous goal will be to understand the distributional properties of the dynamics, with particular focus on (a) the existence and uniqueness of an invariant measure; and (b) the extent to which this measure is concentrated around the game's mqulibriummwhiee in turn, quantifies the long-run proximity of the iterates of (FTRL) to equilibrium. With all this in mind, our results can be stated as follows:
analysis of the previous section, our
Theorem 4 (Strongly monotone games). Suppose that (FTRL) is run in a-strongly monotone game G, and consider the hitling time
Tr = in O: X(1) B,(x")
(22)
where (x)) fx -1-- s r) is a ball of radius r centered on the (necessarily unique) equilibrium x² G. Then, for all r > ro == vr(o² + (a)) we have
Fo
if Xo IB, (x*),
E S ay(r2 -25)
( + aryp2
(23)
if Xo B,(x",
where Fo = F(x,,Y)) If. addition, x² interior. X, admits a unique invariant distribution to which it converges in total variation, and we have
lim Σ 1(x (14))11-12)
(24)
s=0
for all r > fo such that (xxx)) 5 rr.
Remark. Unlike the continuous-time setting of Section 3, we must treat the cases Xo Xo & B,, separately. This distinction arises only in discrete time, because the iterates may exhibit large jumps-so, so, returning to B, (xx) is not guaranteed, even if the process is initialized within. T
(x") and
We prove Theorem 4 in Appendix E following the strategy outlined below. First, shadowing the continuous-ting time analysis of Section 3, we reduce the dynamics to a suitable quotient space of y. eliminating redundant directions and ensuring that the process evolves in a minimal, non-degenerate domain. Building on this, we then show that the induced dynamics are Lebesgue-irreducible i.e., every measurable set with positive Lehesgue measure is reachable with positive probability under the transition kernel of the process. Moreover, invoking (23), we further deduce that P(T, < oo) = for any initial condition, implying that BB (x*) is visited infinitely often. Finally, we also show that (x')') satisfies minorization condition, meaning that the transition kernel from any point in the ball dominates fixed reference measure. In turn, this implies that, upon returning to B, (x*), the process has nonzero chance of "forgetting" its past, allowing us to construct regeneration structure via a coupling argument. Then, leveraging the continuity of F(x", .)), we obtain a uniform bound on the expected return times [E[T,] over any initialization in (x",,), which allows us to conclude that the process Y, positive Harris recurrent. As result, can be shown that the iterates of (FTRL) converge to a unique invariant measure, and we obtain quantitative control over their long-run concentration by means of our previous estimates.
Concluding remarks
Our aim in this paper was quantify the impact of noise and uncertainty on the dynamics of multi-agent regularized learning. Our findings reveal a sharp separation between games that are null-monotone (like bilinear min-max games), and strongly monotone games (like Kelly auctions or Cournot competitions). In the former case, the quasi-periodis profile of the deterministic dynamics destroyed, and learning under uncertainty drifts away on average toward extreme points (or escapes to infinity); in the latter, the sharp convergence guarantees of the deterministic dynamics are diluted by noise, and the resulting dynamics end up concentrated in a region around the game's equilibrium (which we estimate). This paves the way for further explorations of the long-run statistics of regularized learning in games-aaeeeee especiall pertaining to the invariant measure of the process- topic which we find particularly promising for advancing our understanding of the field.
10

---

Acknowledgments and Disclosure of Funding
Jose Blanchet gratefully acknowledges support from the Department of Defense through the Air Force Office of Scientific Research (Award FA9550-20-1-0397 and the Office of Naval Research (Grant 1398311), 1), as well as from the National Science Foundation (Grants 2229012, 2312204, and 2403007). Panayotis Mertikopoulos also a member of Archimedes/Athenaa RC and acknowledges financial support by the French National Research Agency (ANR) in the framework of the PEPR IA FOUNDRY project (ANR-23-PEJA-0000
the project IRGA-SPICE (G7H-IRG24E90) and project MIS 5154714 of the National Recovery and Resilience Plan Greece 2.0, funded by the European Union under the NextGenerationEUU Program.
References
[1] Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. E. Gambling in a rigged casino: The adversarial multi-armed bandit problem. In Proceedings of the 36th Annual Symposiun on Foundations of Computer Science, 1995.
[2] Auer, P., Cesa-Bianchi, N., Freund, Y.. and Schapire, E. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48-77, 2002.
[3] Azizian, W., lutzeler, F,, Malick, J., and Mertikopoulos, P. What is the long-rum run distribution of stochastic gradient descent? A large deviations analysis. In JCML '24: Proceedings of the 41st International Conference on Machine Learning, 2024.
[4] Azizian, W., lutzeler, F., Malick, J., and Mertikopoulos, The global convergence time of stochastic gradient descent in non-convex landscapes: Sharp bounds via large deviations. https://arxiis org/ aba/ 2503.1 12211663 16398, 2025.
[5] Belmega, V., Lasaulce, S., and Debbah, M. Power allocation games for MIMO multiple access channels with coordination. IEFE Trans. Wireless Commun., 3(5):3182-3192 June 2009.
[6] Benaïm, M. Dynamics of stochastic approximation algorithms. In Azéma, J., Émery, M., Ledoux, M., and Yor, M. (eds.), Séminaire de Probabilité' XXXIII, volume 1709 of Lecture Notes in Mathematics, pp. 1-68. Springer Berlin Heidelberg, 1999.
[7] Bertsekas, D. P. Convex optimization algorithms. Athena Scientific, 2015.
[8] Bhattacharya, R. N. Criteria for recurrence and existence of invariant measures for multidimensional diffusions. The Annals of Probability, 6:541-553, 1978.
[9] Borkar, S. Stochastic Approximation: Dynamical Systems Viewpoins. Cambridge University Press and Hindustan Book Agency, 2008
[10] Bravo, M. and Mertikopoulos, P. On the robustness of learning in games with stochastically perturbed payoff observations. Games and Economic Behavior, 103(John Nash Mcmorial issuc))41-66, May 2017.
[11] Cabrales, A. Stochastic replicator dynamics. International Economic Review, (1):4551-81, May 2000.
[12] Cauvin, P.-L., Legacci, D., and Mertikopoulos, P. The impact of uncertainty on regularized learning in games. In ICML 225: Proceedings of the 42nd International Conference on Machine Learning, 2025.
[13] Cesa-Bianchi N. and Lugosi, G. Prediction, Learning, and Games. Cambridge University Press, 2006.
[14] Chen, and Teboulle, M. Convergence analysis of proximal- like minimization algorithm using Bregman functions. SIAM Journal on Optimization, 3(3):538-554 August 1993.
[15] DeepSeek-Ar Al and many other authors that you can see in the arxiv link below. Deepseek-v3 v3 technical report, 2025. URL https:/ /arxivvvvoooo org//bs.////.......o....... aa////////// /2//24122222 19437.
[16] Diculeveut, A., Durmus, A., and Bach, F. Bridging the gap between constant step size stochastic gradient descent and markov chains, The Annals of Statistics, 2017, URL https:/ ptttpp:///pl..eee http:////p...semamee aep..ssmaaticcchollt org/ /or//osoDD
[17] Douc, Moulinss, E., Priouret, P., and Soulier, P. Markov chains. Operation research and financial engi- neering.Sprrngeeee Springer, 2018. doi: 10. 10000/978-33311-977777
URL httpa:/ ptttpa://hhl.. /hal. scwence/eeaaaaaaee 02022651.
[18] Engel, M. and Piliouras, G. A stochastic variant of replicator dynamics in zero-sum games and its invariant measures. Physica D: Nonlinear Phenomena, 456: 133940, December 2023.
[19] Folland, G. B. Real Analysis. Iinee--nterscieece, 2 edition. 1999.
[20] Foster, D. and Young, H. Stochastic evolutionary game dynamics. Theoretical Population Biology, 38: 219-232, 1990.
[21] Fudenberg, D. and Harris, C. Evolutionary dynamics with aggregate shocks. Journal of Economic Theory. 57(2):420 441, August 1992.

---

[22] Ge, R., Huang, F., Jin. C., and Yuan, Y. Escaping from saddle points - Online stochastic gradient for tensor decomposition. In COLT 15: Proceedings of the 28th Annual Conference on Learning Theory, 2015.
[23] Femnnndez-Lermi O. and Lasserre, J.-B. Markov Chains and Invariant Probabilities. Birkhäuser Basel, 2003, doi: 10.1007/978-3-03000 8024-4.
[24]
Hiriart-Urutyy J.-B. and Lemaréchal, C. Fundamentals of Convex Analysis. Springer, Berlin, 2001.
[25] Hofbauer, J. and Imhof, L. A. Time averages, recurrence and transience in the stochastic replicator
dynamics. The Annals of Applied Probability, 19(4):1347-1368. 2009.
[26] Hsich, Y.G., Antonakopoulos, K., and Mentikopoulos, P. Adaptive learning in continuous games: Optimal regret bounds and convergence to Nash equilibrium. In COLT '21: Proceedings of the 34th Annual Conference on Learning Theory, 2021.
[27] Huang. K. and Zhang, S. New first-order algorithms for stochastic variational inequalities. SIAM Journal on Optimization, 32 (2(4):2745-277 2022.
[28] Imhof. L. A. The long-run run behavior of the stochastic replicator dynamics. The Annals of Applied Probability, 1((1B):0019-104 2005.
[29] 1tō, K. Stochastic integral. Proceedings of the Imperial Academy of Tokyo, 20:519-524, 1944.
[30] Kallenberg, O. Foundations of modern probability. Probability and its Applications (New York). Springer- Verlag, New York, 2002. ISBN 0-387-953133
[31] Karatzas, and Shreve, S. Brownian Motion and Stochastic Calculus. Springer-Verlag, Berlin, 1998. [32] Khasminskii, R. Z. Stochastic Stability of Differential Equations. Number 66 Stochastic Modelling and Applied Probability. Springer- Berlin, 2 edition, 2012.
[33] Krichene, W. Continuous and discrete dynamics for online learning and convex optimization. PhD thesis, Department of Electrical Engineering and Computer Scienees, University of California, Berkeley, 2016.
[34] Krichene, W. and Bartlett, P. Acceleration and averaging in stochastic descent dynamies. In NIPS '1: Proceedings of the 31 International Conference on Neural Information Processing Systems, 2017.
[35] Krichene, W., Drighès, B., and Bayen, A. M. Online learning of Nash equilibria in congestion games.
SIAM Journal on Control and Optimization, 53(2):1056- 1081, 2015.
[36] Kuo, H.-H. Introduction to Stochastic Integration. Springer, Berlin, 2006.
[37] Kushner, H. and Clark, D. Stochastic Approximation Methods for Constrained and Unconstrained Systems. Springer, 1978.
[38] Lattimore. T. and Szepesvári, C. Bandit Algorithms. Cambridge University Press, Cambridge, UK, 2020.
[39] Lillicrap. T. P., Hunt, J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., and Wierstra, D. Continuous control with deep reinforcement learning. In 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016.
[40] Littlestone, N. and Warmuth, M. K. The weighted majority algorithm. Information and Computation, 108
(2):212-266 261, 1994.
[41] Loizou, N., Berard, H., Gidel, G., Mitliagkas, I,, and Lacoste-Julien, S. Stochastic gradient descent-ascent and consensus optimization for smooth games: Convergence analysis under expected co-coercivity. In NeurlPS '21: Proceedings of the 35th International Conference on Neural Information Processing Systems, 2021.
[42] McKelvey, R. D. and Palfrey. T. R. Quantal response equilibria for normal form games. Games and Economic Behavior, 10(6);6 38, 1995.
[43] Mertikopoulos, P. and Moustakas, A. L. Learning in the presence of noise. In GameNets '09: Proceedings of the 1st International Conference on Game Theory for Nenworks, 2009.
[44] Mertikopoulos, P. and Moustakas, A. L.. The emergence rational behavior in the presence of stochastic perturbations. The Annals of Applied Probability. 20(4):1359- 1388, July 2010.
[45] Mertikopoulos, P. and Sandholm, W. H. Learning in games via reinforcement and regularization. Mathe- matics of Operations Research, 41(4):1277-1224 November 2016.
[46] Mertikopoulos, P. and Staudigl, M. Convergence Nash equilibrium in continuous games with noisy first-order feedback. CDC '17 Proceedings of the 56th IEEE Annual Conference on Decision and Control, 2017.
[47] Mertikopoulos, P. and Staudigl, M. On the convergence of gradient- like flows with noisy gradient input. SIAM Journal on Optimization, 2831):163-11 197, January 2018
[48] Mertikopoulos, P. and Staudigl, M. Stochastic mirror descent dynamics and their convergence in monotone variational inequalities. Journal of Optimization Theory and Applications, 179(3):838-888) 8677 December 2018.
[49] Mertikopoulos. P. and Viossat, Y. Imitation dynamics with payoff shocks. International Journal of Game Theory, 45(1-2):22 (112)2221112222 March 2016.
12

---

[50] Mertikopoulos, P. and Zhou, Z. Learning in games with continuous action sets and unknown payoff functions. Mathematical Programming, 173(1-2)4455-07, January 2019.
[51] Mertikopoulos, P., Belmega, V., Negrel, R., and Sanguinetti, Distributed stochastic optimization via matrix exponential learning. JEEE Trans. Signal Process. 65(9):2277-2290, May 2017.
[52] Mertikopoulos, P., Papadimitriou, C. H., and Piliouras, G. Cycles in adversarial regularized learning. In SODA '18: Proceedings of the 29th annual ACM-SIAM Symposium on Discrete Algorithmss, 2018
[53] Mertikopoulos. P., Lecouat, B., Zenati, H., Foo, C.-S., Chandrasekhar, V., and Piliouras, G. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In ICLR '19; Proceedings of the 2019 International Conference on Learning Representations, 2019.
[54] Mertikopoulos, P., Hsich, Y.-P. and Cevher, V. A unified stochastic approximation framework for learning in games. Mathematical Programming, 203:559-609, January 2024.
[55] Meyn, S., Tweedie, R. L.. and Glyan, P. W. Markov Chains and Stochastic Stability. Cambridge Mathematical Library. Cambridge University Press, 2 edition, 2009.
[56] Michel, D. and Pardoux, É. An introduction to Malliavin calculus and some of its applications. In Recent advances in stochastic calculus, pp. 65 1044 Springer, 1990.
[57] Nesterov, Y. Primal-dual subgradient methods for convex problems. Mathematical Progranming, 120(1): 221-259, 2009.
[58]
Øksendal, B. Stochastic Differential Equations. Springer-Verlee Verlag, Berlin, 6 edition, 2013.
[59] Piliouras, G. and Shamma, J. S. Optimization despite chaos: Convex relaxations to complex limit sets via Poincaré recurrence. In SODA '1:: Proceedings the 25th annual ACM-SIAM Symposium on Discrete Algorithms, 2014.
[60]
Rockafellar, R. T. Convex Analysis. Princeton University Press, Princeton, NI, 1970.
[61] Rockafellar, R. T. and Wets, R. J. B. Variational Analyxis, volume 317 of A Series of Comprehensive Peringer-Verlage Berlin, 1998.
Studies in Mathematics.
[62] Rosen, J. B. Existence and uniqueness of equilibrium points for concave N- N-person games. Econometrica. 33(3):520-534, 1965.
[63] Scutari, G., Facchinei, F., Palomar, D. P., and Pang. J.S. Convex optimization, game theory, and variational inequality theory in multiuser communication systems. IEEE Signal Process. Mag., 27(3)335-49, May 2010.
[64] Shalev-Shwartz S. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2):107-194, 2011.
[65] Shalev-Shwartz, and Singer, Y. Convex repeated games and Fenchel duality. In NIPS' 06: Proceedings of the 19th Annual Conference on Neural Information Processing Systems, pp. 1265-1272. MIT Press, 2006.
[66] Telatar, E, Capacity of multi-antenna Gaussian channels. European Transactions on Telecommunications and Related Technologies, (06))585-556, 1999.
[67] van Damme, F. Stability and perfection of Nash equilibria. Springer-Verlee Verla,, Berlin, 1987.
[68] Vlatakis, E. V., Giannou, A., Chen, Y., and Xie, Q. Stochastic methods in variational inequalities: Ergodicity, bias and refinements. In Proceedings of The 27th International Conference Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pp. 4123-4131. PMLR, 02 04 May 2024.
[69] Vovk, V. G. Aggregating strategics. In COLT '90: Proceedings of the 3rd Workshop on Computational Learning Theory, pp. 371 371-383, 1990.
[70] Welling, M. and Teh, Y. W. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th International Conference International Conference on Machine Learning, ICML'11, pp. 031-688,22 2011.
[71] Yu, L., Balasubramanian, K., Volgushev, S., and Erdogdu, M. A. An analysis of constant step size sgd in the non-convex regime: asymptotic normality and bias. NIPS '21, Red Hook, NY, USA, 2021. Curran Associates Inc. ISBN
[72] Yu, W., Rhee, W., Boyd, S. P., and Cioffi, J. M. Iterative water-filling for Gaussian vector multiple-access channels. IEEE Trans. Inf. Theory, 50(1):145-15) 2004.
[73] Zhou, Z., Mertikopoulos, P., Bambos, N., Boyd, S. P., and Glynn, P. W. On the convergence of mirror descent beyond stochastic convex programming. SIAM Journal on Optimization, 30(1):687-716 2020.
[74] Zinkevich, M. Online convex programming and generalized infinitesimal gradient ascent. In ICML '03: Proceedings of the 20th International Conference on Machine Learning, pp. 928-936, 2003.
13

---

A Examples
In this appendix, we present several examples of games satisfying the standing assumptions we outlined in Section 2. Overall, these assumptions are quite standard the study of online learning and games with continuous action spaces, and most of the positive results in the literature hinge on precisely these assumptions or close variants thereof.
To provide some context, the monotonicity assumption (cf. Definition 1) provides an amenable "convex structure", which is essential for establishing the existence and characterization of equilibria via first-order variational condtions. Without a structural characteriztion of this type, even defining a meaningful solution concept becomes unclear, and global convergence cannot be expected least in general. In sense, these assumptions parallel the convex/non-come convex separation in optimization but with the added challenge that, in non-convex games, equilibria may fail exist altogether, unlike minimizers (either local or global) in non-convex minimization problems.
Our regularity assumptions- standard in practice and, as such, nearly universal in the literature. They could be relaxed, for instance, by assuming local or relative smoothness, Hölder continuity, or something of the sort-though the resulting analysis would be considerably more involved. Relaxing monotonicity, however, is considerably trickier: some of our results would go through as long as the game's 's equilibrium admits global variational characterization, e.g., in the spirit of variational stability or Minty-type condition, cf. [50, 53, 73] and references therein. If, however, the game admits distinct components of equilibria, all bets are off: in that case, FTRL could transit in perpetuity between the game's s different equilibrium components, and characterizing the mean sojourn and transition times of the process would only be possible in very special cases.
action sets, Lipschitz smoothness, etc.-are largely technical,
All in all, the set of assumptions that consider represents certain "sweet spot" between theoretical tractability and practical relevance, which explains their prevalence in the literature. The examples below illustrate the range of settings where these assumptions arise naturally.
Example A.1 (Zero-sum bimatrix games). bimatrix game consists of two players, each with a finite set of actions A, i = 1.2, and min-max objective function I.: Ai x A - IR, typically encoded matrix M E R-AixAA with MaB I.(a., (3) for all a E AI, A2. The first player is cast in the role of the minimizer and the second player in that of the maximizer, so their corresponding payoff functions are defined as #1 = = 12.
In the mixed extension of the game, each player can mix their actions by selecting a probability distribution mixed strategy- over Ar, that is, an element x; of the probability simplex X; A(AA) (x; R ||жи|| = 1}. Accordingly, in matrix notation, the players' corresponding mixed payoffs are given by
(x1, x2) = - Mx² = -22(x1x22)
(A.1)
so their individual gradient fields can be expressed as
in (x).)2)) = - and
02(11,)2) = M M'xi x1
(A.2)
for all X1 E Xi and all x2 E X2
By definition, a mixed-strategy Nash equilibrium of a bimatrix zero-sum game satisfies
L(x x(x S L(x),x)) for all E x2 E Xzz
(A.3)
If, in addition, x xx,x; both have full support support-that thap is, xf ri and x E ri ri we also have the "equalizing payoffs" condition
x(x L(x1xx)) for all x E X2, E X₂
(A.4)
which means that (A.3) binds identically. In this case, we readily get
(01(x).22) - xx) (12 x²²) #i (x1, - in (x(, + (2(x)xx)) (2(x1,x;) = =0
(A.5)
for all x E Xi, x2 E X2 i.e., the game null-monotone the sense of Definition 1.
14

---

Example A.2 (Cournot competition). In the standard Cournot competition model, there is a finite set of firms, indexed by i E N = (I.....N) NN, each providing the market with quantity x; E [0, B,] of some good (or service) up to the firm's production budget B,. Following the law of supply and demand, this good is priced following the simple linear model P(x) a - En Xi, i.e., as a linearly decreasing function of the total supply. Accordingly, in this model, the utility of firm i is given by
My (x) x, P(x) c;x; a b EJeN ci xi
(A.6)
where e; represents the marginal production cost of firm
By a straightforward derivation, the players' individual payoff gradients are given by
iy (x)
a (a-bbe
DEN - ci)
bx;
(A.7)
Oxy
and hence, the Hessian matrix of the game will be
Pug - -öij (x)(x) = 2 0xx; 2 0x,0x,
pu:
(A.8)
where dij is the standard Kronecker delta. Since H is circulant, standard linear algebra considerations show that its cigenvalues are b and -NN+ 1)b (with multiplicity N - 1 and respectively), so it follows by a well-known second-order criterion that the Cournot competition game is b-strongly monotone [50, 62).
Example A.3 (Signal covariance optimization). Consider a vector Gaussian channel of the form
y Σ H +
(A.9)
iEA
where x; E C is the (complex-valued) signal transmitted by the i-th user of the channel, H e C" the transfer matrix of the channel, E C" the noise in the channel (assumed zero-mean Gaussian and, without loss of generality, with unit covariance), and E C" is the aggregate signal output of the channel [72]. In this context, each user i E N controls the covariance matrix X; = E[x;x/] subject to the power constraint tr(X,) || s Pt. where Pj denotes the user's maximum transmit power. In this case, by the celebrated Shannon-Telatar formula [66]. and assuming a single-user decoding scheme at the receiver, the achievable rate of the i-th user is
": X,; X-,) = log det [1 Σ, H,X,H log der (I+ Σj H,
(A.10)
Putting everything together, this defines a continuous game with players i E N (I....,N). spectrahedral action sets of the form
2 = (X, E Cm.xmm :X; > 0 and Xr Pt}
(A.11)
for all i E N, and payoff functions given by (A. By calculation of Belmega et al. [5], it is known that this game is concave and monotone and, in fact, strongly monotone if the linear mapping (X....., ~ Σ, H is not rank-deficient.
Examples that are closer to signal processing and data science include distributed metric learning, multimedia classification, etc. For a range of applications along these lines, we refer the reader to [51, 63) and references therein.
B Mirror maps and regularization
In this appendix, we collect some background material, properties and examples regarding the regularization machinery underlying (FTRL) and (S-FTRL). To lighten notation essecially with respect the player index i WW-we base everything in this appendix subset of some d'dimensional vector space, which could either be X; or X, depending on the context.
abstract closed convex
The results presented below (or version thereof) are known in the literature; nevertheless, we provide detailed proofs for completeness and to resolve any conflicts or ambiguities with different conventions in the literature.
15

---

B.1. Preliminaries. Let V be a d-dimensional normed space, let )'= V denote the (algebraic) dual of V. and let (y.x) denote the canonical bilinear pairing between x V and y V". If ||||| a norm on V/ will also write
|lyll = max (y,,) ||x||| = 1}
(B.1)
for the induced dual norm on Vi Ky.x)| ||*|||ll| for all x V and all y by construction.
Given a closed convex subset C of V2 we also define:
1. The tangent cone to C at C' as
TC(p) cl(z E V p + E for some 1 > 0}
(B.2)
i.c., as the closure of the of rays emanating from p and meeting C in least one other point.
The dual cone to C at p as
TC" (p) {w E y (w, z) 2 0 for all : TC(p))
(B.3)
3. The polar cone to C at E as
PC(p) {w y: (w, z) & 0 for all z TC(p))
(B.4)
Following standard conventions in the field [60], convex functions will be allowed to take values in the extended real line R U {oo), and we will denote the effective domain of convex function f: V - RU {oo} as
dom f= E V: f(x) <o)
(B.5)
When there is danger of confusion, will identify convex function f: V R with its restriction on dom f; in other words, we will treat of interchangeably as a function on dom f with values R, or function on V with values in U {oa} (and finite on dom f).
Throughout the sequel, we will assume that functions under study are proper, that is, dom f # Ø. Then, given proper function f: V.V- R U {co}, the subdifferential of f at E dom f is defined
0f(x) = E f(x) f(x) + (y.x' -x) for allx's E EV
(B.6)
and we denote the domain of subdifferenticability of f as
dom f (x E V 0f(x) # 0).
(B.7)
With all this in hand, a regularizer on a closed convex subset of V is a continuous function h: - IR which is strongly convex, i.e., there exists some
such that
h(1x (1 1)x') z rh(x) + (1 -1 ())((x))) - =2 -0Ilx'xxxlx x
A(1
(B.8)
for all x E C and for all A E [0. 1]. By standard arguments [7, 61]. this immediately implies that
K J|x' x|| for x, X,
h(x') 2 h(x) 0h(x:'' + 2
(B.9)
where
0h(x;x' - x) lim [4(x + 0(x' x)) - h(x)]/0 0-0-
(B.
denotes the one-sided directional derivative of h at along the direction of x xx In addition, also define the following objects associated to h:
1. The prox-domain of h:
C₁= dom dh
(B.11)
2. The mirror map Q: y X induced by h:
Q(y) == arg max (y. - h(x)) xEX
for all y e )
(B.12)
The convex conjugate h": of h:
h (y)
max (y. h(x)) x
for all y V.
(B.13)
16

---

The proposition below provides some basic properties linking all the above: Proposition B.1. Let h be a K K-strongly convex regularizer on Then:
(a) Q is single-valued on y.
(b) For all x Cn and all y y, we have
x=) if and only if ah(x).
(B.14)
(c) The image im Q of Q is equal to the prox-domain of h. and we have
riC = im Cr C.
(B.15)
(d) The convex conjugate h::: y - R of h is differentiable and satisfies ( = Vh (y) for all y V.
(B.16)
(e) Q is (ipshiiipschitzz continuous, that is, ( & (1/K)ly ull. for all y E y.
(B.17)
(f) Fix some y E y and let = Q(y). Then, for all x' E X we have:
0h(x;x' - x) 2 xy x).
(B.18)
(g) Fix some y E V, and let x = QQy). Then Q + w) = x for all w E PC(x).
Proof. For the most part, these properties are well known in the literature (except possibly the last one), so we only provide pointer short sketch for most of them.
(a) This readily follows from the fact that h is strongly convex, so the arg max in (B.12) is attained and is unique for all y V.
(b) By Fermat's rule [60, Chap. 26], we readily see that solves (B. 12) if and only ( O, that is, if and only if E åh(x). Since this implies that oh, our claim follows.
(c) By 14.,4), we readily get im Q Cs. As for the second part of our claim, follows from basic properties of the subdifferential, ef. Rockafellar [60, Chap. 26).
(d) This is simply Danskin's theorem, e.g., Bertsekas [7, Proposition 5.4.8, Appendix B].
(e) This is a consequence the fact that is (1/S)-Lipschitz smooth, cf. Rockafellar Wets [61, Theorem 12.60(b)).
(f) Since y e 0h(x) by (B.14), we readily get that h(x 0(x' x)) 2 l(x) 0'y for all 0 [0, 1] Hence, by rearranging and taking the limit 0 - 0+, we conclude that
(B.19)
h(x + 0(x' x)) h(x) (y.x' x)
0h(x;x' - lim 8-00
(B.20)
0
as claimed.5
(g) By (B.14) it suffices to show that + w dh(x) for all w e PC(x). However, if w e PC(x), we also have (w,x' - x) s for all x' X, and hence, with y e 0h(x), we readily get
h(x') 2 h(x) + (y.x' - 2 h(x) (y + w, x) for all x' e X.
(B.21)
This shows that y ah(x) and completes proof.
Following [45, 50], we also define the Fenchel coupling associated to as
F(p.y) = h(() + h (y) - (y. p) for all p E X, y y.
(B.22)
The next proposition shows that the Fenchel coupling can be seen as a "primal-dual" measure of divergence between p C and y E Y:
'The existence of the limit is guaranteed by elementary convex analysis arguments, cf. Bertsekas App. B].
17

---

Proposition B.2. Let h be a K K-strongly convex regularizer on C. Then, all E X and all e y, we have:
(a) y(p.y) with equality if and only if Q(y).
(B.23a)
(b) y(p.y) 2 - -plp.
(B.23b)
Proof. These properties are known in the literature, but we provide quick proof for completeness.
(a) By the Fenchel-Yourr Young inequality, equality if and only if y E @h(p). Our claim then follows from (B.14).
have h(p) h' hy) 2 (y. p) for all p X. y V, with
(b) Let Qy) so y 0h(x) by (B.14). Then, by the definition of F, we have
F(p.y) h(p) h²( (y. p)
h(p) + (y.x) h(xx) () h(p) h(x) -ah(x;p - x)
since y E 0h(x) # by Proposition B.1
K pll
by (B.8)
so proof is complete.
Our last result at this point a useful differentiation formula for the Fenchel coupling:
Lemma B.1. For all p e X and all y V, we have:
vyF(p.)) = Q
(B.24)
Proof. The proof follows immediately from Danskin's 's theorem, cf. Eq. (B.16) of Proposition B.I.
B.2. Update lemmas. Moving forward, we note that the basic update step of (FTRL) can be written
y and x² =(y")
(B.25)
for some y, V. With this in mind, state below series of identities and estimates for the Fenchel coupling before and after an update of the form (B.25).
The first is primal-dual version of the so-called "three-point identity" for Bregman functions [14]:
Lemma B.2. Fix some p E X. y y, and let QQy). Then, for all y V, we have:
F(p.y*) = F(p.9) F(x,y") + (yt y. p).
(B.26)
Proof. By definition, have:
F(p.y*) h(p) + +h((")) (y*.p)
(B.27a)
F(p.y) h(p) + (y) - (y.p)
(B.27b)
F(x,y") h(x) + - -
(B.27c)
Thus, subtracting (B.27b) and (B.27c) from (B.27a), and rearranging, we get
F(p.y*)= F(p.y) F(x, y - h(x) - h1" (g) + (y- x) (0* -y.ppp p). Our assertion then follows by recalling that x Q(y), so hxx) + h (y) = xy.x).
(B.28)
The next result we present concerns the Fenchel coupling before and after direct update step; similar results exist in the literature, but we again provide a proof for completeness.
Lemma B.3. Fix some p X and y, w e y. Then, letting per (B.25), we have:
Q(1), 4² + w, and x Q(x²) as
F(p.y*)= = F(p.y) + (w,xx - p)) F(x*,
(B.29a)
1
$ F(p,x) + (W,x- p) + 2K
||
(B.29b)
18

---

Proof. By the three-point identity (B.26), we have
F(x. g) = F(x, y") + F(x" ly y" x - p)
(B.30)
so our first claim immediate. For our second claim, rearranging terms and employing the Munchel-Young inequality gives
g(p-y) + (w,x* - p) - F(x". ((xx")))
= F)) (w, x - p) + (wi -x) -x)- F(p.y)
F(..9) (w, p) 1
K
||wl1 || pll 2112- 1 F(p.y)
(B.31)
2K
2
claim follows from Proposition B.2.
C A short primer on stochastic analysis
In this appendix, collect some standard results from stochastic analysis in order to provide degree of ceff-completeness to the main text. For an introduction to stochastic analysis and the theory of SDEs, refer the reader to the masterful accounts of Øksendal [58] and Kuo [36].
The main focus of the theory is the study of ordinary differential equations (ODEs) perturbed by
noise, modeled informally after the Langevin equation
dZ b(Z(1)) + (1))
(LE)
di
where Z(r) is a stochastic process in R, b: R R R the drift of the process, and 17(1) is the "noise" perturbing the deterministic ODE : b(2). Unfortunately, albeit natural, the problem with (LE) is
that any reasonable continuous-timg time model of noise would lead to trajectories that are almost nowhere differentiable, the meaning of "dZ//r"" in (LF) is rather precarious."
In lieu of this, to give formal meaning to (L.E), we consider instead the stochastic differential equation
dz(1) b(Z()) dt + (Z(()) dw())
(SDE)
which is shorthand for the integral equation
z()) [ b(Z(s)) ds ('' or (r(((s)) dw(s).
(C.1)
for some state-dependent diffusion coefficient o: R R R. The key element in the above formulation is the so-called Itô integral that appears in the right-hand side of (SDE), and which is defined relative to what known as a standard Brownian motion on R. Intuitively, what this means is that the integral fo oZ((s) ds(s) is obtained in the limit ōt = TK+1 - 0 of the discrete-time approximation
L of o(((s)) dW()))))(s)))
[1/81 oZZ(Ie) (W(e.)) W(4)
Σ
(C.2)
where W(/) is some stochastic process that satisfies what one would expect from a "white noise" process (zero-mean, with independent increments). but still "regular enough" to possess reasonable behavior in the limit ōt - 0. These considerations lead to the formal definition of a Brownian motion-or, more precisely, the Wiener process- which is characterized by the following properties:
1. The increments of W are independent, that is, for all f, > 0, the future increments W(r + r) W(r) of W independent of its past values W(s). <
The increments of W are Gaussian, that is, for all f, t > O, the future increments W(r -(++))-W(1)
of W are normally distributed with mean and variance i.c., W(r + r) W(r) ~ (),
3. The sample paths of W are continuous (a.s.), i.e., W(r) is continuous function of for almost every realization of W.
'In particular, consider a noise process ()()) which is a) zero-mean: E[n(1] 0: b) uncorrelated: ([1(())((2)) = 0 12 # fı; and c) stationary, in the sense that () s) and 17()) are identically distributed for all > 0. Then, any such process does not have continuous paths [58, p. 21].
19

---

The existence of a process with the above properties is by means trivial affair, but it can constructed e.g,, as the scaling limit of random walk, or some other tiscrete-time stochastic processes with stationary independent increments.
Providing a more detailed account of the definition of W(1) and the associated stochastic integral which appears in (SDE) is well beyond the scope of our paper; for an accessible introduction, we refer the reader Øksendal [58, Chap. 2]. What is more important for our purposes that, albeit non-differentiable, the solution Z(r) still satisfies a certain version of the chain rule, known as Ito's formula [29]. Specifically, for any C² function f: R R. we have
df()) = f (Z(1))(Z(()) dt (Z()) (1) dr + f' (Z(r)) (Z(()) dw(r)
(C.3)
or, more compactly:
df(Z()) = ((()) dz()) + ( dz(1) dZ(1)
(C.4)
where the product dZ dZ is computed according the rules of stochastic calculus [58]: dr dr = O dt dW(()=
and dW(() dd(()) dr.
(C.5)
Thanks to Itô's formula, can still do calculus with stochastic processes satisfying (SDE); the resulting set of differentiation rules is known as Itô-or stochastic-callulus.
For our purposes. we will consider multi dimensional analogues of (SDE) where, mutatis mutandis, (i) Z(r) evolves in R"; (ii) the drift of the process is given by vector field b: R" R"; (iii W(r) is an m-dimensional Brownian motion evolving in R""; and (iv) o:: IR" - Ruxm is the diffusion matrix of the SDE In this case, Itô's formula for C2 function f: R becomes
0f di + 2
02 dt Tik (z(((())r)x(()) Ōz,0z, L.j1
m
(f(())) Σ bi (Z(1)) i=1
Σ
Ozi
k=
(C.6)
a
m
of
(Z(1)) dWa(1)
az.
In our analysis, will also require weaker version of Itô's formula for convex functions f: R" R that are not C² but are only L-Lipschitz smooth, ie.. C¹ c'msmooth with L-Lipschitz continuous derivatives. We borrow the precise statement from [47, Proposition C.2] which, in our notation, gives
Σ [' 0z fz(s) dz((s) L {" tlo((()) ds
f(Z()) S f(Z(0))
(C.7)
E=1
or, more explicitly,
L ( bz(Z(s)) 0z ds / l (((()
f(Z(1)) f(Z(0)) Σ
n
m
(Z(s)) 8., f (s).
(C.8)
The deterministic part of (the strong version of) Itô's formula for -mooohh functions is captured by the so-called infinitesimal generator of (SDE), defined here the differential operator L whose action on of is given by
aʃ
n Σ Σ
O. dz,0z;
Cf(x) - bi(z)
(=(())))(()))
for all R"
(C.9)
Ōzi
1,j=1
Accordingly, Itô's formula can be written more compactly as dZ()) = (z(())) di (Z(()())) (Z()1) dw(r).
(C.10)
Thus, letting P.(-) denote the law of initialized at Z(0) - z E R", and writing Ez[-] for the corresponding expectation, we readily get
Ez = f(2)+ + E. Cf(Z(s)) ds for all 2 0.
(C.11)
This shows that the infinitesimal generator of 7. captures precisely the mean part of the evolution of ((Z(t)) under (SDE). In fact, this simple expression admits a far-reaching generalization known as Dynkin's 's formula [58, Chap. 7.4]:
20

---

Proposition C.1 (Dynkin's s formula). Suppose that Z(t) is initialized at Z(0) 2E R". Then, for every bounded stopping time t and every C² -mooohhh function f: R" R. we have
= + 1 Cf(Z(s)) ds
(C.12)
Moving forward, the matrix
A(z) (2)
(C.13)
or, in components,
A1f(2)= = on 1..=,......
(C.14)
known as the principal symbol of C, and we say that is uniformly elliptic if there exists some > 0 such that u' A(z)u 2 c||u]|² for all E R" (that is, if the eigenvalues of A(z) are positíve and uniformly bounded away from 0). If this is the case, the noise in (SDE) is "uniformly exciting" in the sense that it does not vanish along any direction at any point of the state space of the process. Concretely, by standard results- see e.g., [56, Sec. 3.3.6.11 and references therein this implies that every region of R" is visited by Z(t) with positive probability, viz.
(Z()) z' for some > 0) 0 for all z, E R".
(C.15)
If (SDE) is uniformly elliptic-i.c. if the infinitesimal generator thereof is uniformly elliptic-the behavior of Z() can be further classified as transient or recurrent. Formally, these two fundamental notions are defined as follows:
Definition C.I. Suppose that (SDE) is initialized at some E R". Then:
1. Z(r) is transient from z R" if it escapes every compact subset KC of R" in finite time, i.., there exists some (possibly random) Tic < co such that
Pa (Z((() & K. for all 2 Tk) = 1.
(C.16)
Z(1) is recurrent relative to a compact subset of R" if the hitting time
TK inf (1 > 0 Z(r) E KC}
(C.17)
finite (a.s.). If, in addition, [[[x]] < co, we will say that Z(t) positive recurrent; otherwise, Z(r) will be called null recurrent.
(SDE) is uniformly elliptic, we have the following fundamental dichotomy:
Theorem C.1 (Transience/ recurrence dichotomy). Suppose that (SDE) is uniformly elliptic. Then:
1. If (SDE) is positive recurrent (resp. null recurrent) for some initial condition Z E R" and some compact subset of R", then is positive recurrent (resp. null recurrent) for every initial condition and every compact subset R".
If (SDE) transient from some initial condition z R", is fransient from every initial condition.
For more detailed version of Theorem C.I, we refer the reader to Bhattacharya [8, Proposition 3.1] who, to the best of our knowledge, was the first to state and prove this criterion. In words, Theorem C. simply states that, as long as (SDE) is uniformly elliptic, then it is either transient or recurrent; and if is recurrent, it is either positive or null recurrent; no other outcome is possible. The choice of initialization compact set in Definition C.I does not matter (so, in particular, Z cannot be transient from some region of R" and recurrent from another). This crisp separation of regimes will play a major role in our analysis, and we will refer to it as the transience recurrence dichotomy.
An important consequence of positive recurrence that, under uniform ellipticity, Z(r) admits a unique invariant measure, that is, probability measure y on R" such that Z(r) ~ y for all r 2 0 whenever Z()) v. Importantly, the proviso that is a probability measure implies that v(R") < oo; if the process is null-recurrent, the semigroup of flows of (SDE) still admits an invariant meassure in the sense of Khasminskii [32], but this measure no longer finite, i.e., r(R") = oo. Finally, if the process is transient, (SDE) does not admit such measure.
21

---

D Analysis and results in continuous time
We now proceed to prove the continuous- results for (S-FTRL) that we presented Section 3.
D.I. Proofs omitted from Section 3.1. We begin with the "gentle start" results of Section 3.1, which we restate below for convenience.
Proposition Suppose that (S-GDA) is run on the game (6a) with initial condition xo R². Then:
1. lim Ex [[ = 0o, i.e., X() escapes to infinity in mean square.
2. [xg[T,] = 00 if < ||xo||, Le., (() takes infinite time on average to get closer to equilibrium.
The limit Po. lim tx,,t) does not exist, i.e., X does admit an invariant distribution.
Proposition 2. Suppose that (S-GDA) is run on the game (6b) with initial condition xo E RR. Then:
1. lim Exi [[X()]]] = a², i.e., the dynamics fluctuate mean distance from equilibrium. The mean time required to get within distance of the game's 's equilibrium is bounded as
1 ||x0l|2 - [x
for all <r ||x0l12-
(10)
02
3. The density of X(1) is P(x,1) (1- exp( verges in distribution to a Gaussian random variable centered at O, viz.
2
(1- )or In particular, X(1) con- x
(x(x) = -im P(x,t) 1/(To²) e 11x1l//0
(11)
Proof of Proposition 1. For first claim, note that Itô's formula (C.6) applied to the function fxx = ||I|A under the dynamics (S-GDA) for the game (6a) readily yields the expression
d(I(()) = 2X(1) dx(()= + dx(() dx(()= = 20 dt + X(1) dw()).
(D.1)
Hence, by (C.11), we get
Exg [1X 20
(D.2)
which proves our claim.
For second claim, consider the hitting time inf(r 0 |[X(1)]22 r) with r ||xo]l2. and assume that EE [r] < co. Then, by Dynkin's formula (Proposition C.1) applied to f(x) = ||x|| and r, we readily get
Er S( 20 ds fxxo) + 20 Exg [T] 2 |
ExS [[X((]))
(D.3)
However, since f(X(T)) = 2 by construction, we readily get 2² || contradiction. This shows that Ex, [T] = c0, as asserted.
Finally, for our third claim, it is easy to check that (S-GDA) is uniformly elliptic under the stated assumptions. Thus, by Theorem C.1 and the fact that [r,[r]] = oo, follows that x()) cannot be positive recurrent. By the discussion following Theorem C.1, this implies that X()) does not admit an inveriant measure, so the density P(x, 1) of (() does not converge to limit either.
Proof of Proposition 2. Under the dynamics (S-GDA) for the game (6b), each coordinate of X(r) evolves as an Ornstein-Uhlenbeckk process, viz.
dX;(1) -x(()) dW;(1) for 1,2.
(D.4)
Since the processes are decoupled, we conclude by standard stochastic analysis arguments [36, Example 7.4.5] that
(1) (0)e + f. e- ((-ss) dw,(s)
(D.5)
In turn, by [36, Theorem 7.4.7], this implies that the transition probability kernel of (t)) is given by
1
(x; - (x,
Px(x..))
exp
for í 1,2,
(D.6)
- Ov
21)
22

---

that is, (1) follows Gaussian distribution with mean Ex,o [X,(1) = x1,0e and variance
([X - (1-
σ²
(D.7)
Our first and third claims then follow immediately.
For our second claim, note that the infinitesimal generator of X()) is now given by
Cx(x) = -VV((xx, + A
(D.8)
where Af = tr f denotes the Laplacian of f. Then, Dynkin's formula (Proposition C.I) applied to f(x) ||I||] at the truncated hitting time Ty A = min J), > O, readily yields
Tx
Ex [(, A ADII 1x201
18x0
210² -11((s)]13 ds
TyAt
||.xo122 Ian
2( ,2) ds
=11xol12 2( -2²) LT A
(D.9)
Since [] A 1) 2 by construction (recall that ||xoll2 r), we get
||x0||] 2 2(r2 r22) for all 0.
Ex, IT, Ar]
(D.10)
Since Ex, [T, A r is uniformly bounded, our claim follows by taking the limit - co (so A - Ty pointwise), and invoking the dominated convergence theorem.
D.2. General properties of the dynamics (S-FTRI.). We now proceed to establish the properties of the stochastic dynamics (S-FTRL) the general case, for null- and strongly monotone games respectively. Before doing we begin with result of a book-keeping nature (which is, however, necessary to ensure that the ensuing questions are meaningful).
Proposition D.1. Suppose that o is Lipschitz continuous. Then, for every initial condition X(0) - Xo @gyo) E X, the dynamics (S-FTRL) admit unique strong solution that exists for all time.
Proof. Note that the dynamics (S-FTRL) can be recast in fully autonomous form as dy(r) (Q((())) dt + (2((())) dd(().
(D.11)
Note further that a and Q are all Lipschitz, by our standing assumptions for the game, our assumptions here, and Proposition B.1 respectively. In turn, this implies that the compositions ū= Q and & or Q are likewise Lipschitz continuous, so our claim follows from the existence and uniqueness theorem for SDEs with Lipschitz data, see e.g.. (58, Theorem 5.2.1].
Our next result is an ancillary calculation responsible for much of the heavy lifting in the upcoming analysis.
Proposition D.2. Fix a base point X and consider the energy function (y.p) for y y
E(y) y) Then, for every stopping time 2 0. we have
(D.12)
E(Y(T)) - E(((0)) < [ (o(X(s)), p) ds σ o
2K
Sf'(((s) (x((s) -p) ((((s))
(D.13)
If, in particular, Q is smooth, we have
E(Y(T)) - E((()) J/ (o(X(s)), - p) ds
1 (' ir[[((ss)) Jac ((((s)) ds
2 /
f (X(s) p) o(((((s(ss dW(s).
+
(D.14)
23

---

Proof. Assume first that Q is C² -mooohh In this case, by Lemma B.1, we have VF(p. Q -P and hence,
VPE(y) = v (4) Jac (
(D.15)
Thus, by Ito's formula (C.6), we readily get dE(Y()) (X(1) - p) dY(1)) ur(o ((X)) di
=((((()) X(1) dr
2 (r(=(((1)) Jac Q(Y())) di (X(1) p) (X(()) dw(r)
(D.16)
so (D.14) follows.
Now, if Q not smooth, Proposition B.1 shows that it is still (1/K)-Lipschitz continuous, which, equivalently, means that I is (1/K)-Lipschizz smooth. Thus, (D.13) follows by the weak Itô formula for Lipschitz smooth functions (C.7) applied to h², and noting that tr(or(x)or (x)orx))) S do max
D.3. The null-monotone case. We begin analysis proper with our result for null-monotone games, which we restate below for convenience.
Theorem (Null-monotone games). Suppose that (S-FTRL) is run with a smooth mirror map Q in null-monotone game G. Suppose further that the game admits an interior equilibrium x", and
consider the hitting times _ == in > F, S Fo 5} and T inf > 0 F, Fo + E). If
o2
min > 0 and & is small enough, then
[x = and E Ix, 25/ 25/(K<r m
(15)
for some constant K = Kg > 0; in addition, x()) does not admit a limiting distribution in this case.
Proof. We start with the decreasing case, where argue by contradiction. Specifically, xet be an equilibrium of G, and assume that [T]] < co. Then, by applying Dynkin's 's formula to the energy function E(y) Tg for p - (cf. Propositions C.1 and D.2), we readily get
Exo [E((()))) = E(yo) + Exo
(I(((ss), xx) tr(E((((s)) Jac Q(Y(s))) ds
Exo = Fo+ 2
tr[E(X(s)) Jac @(r(s))) ds
by null monotonicity
2 Fo
(D.17)
where the last line follows from the fact that Σ and Jac are both positive-semidefinic. However, since Ex, (E(((T))) = Fo E by the definition of tz, we get Fo - 2 Fo. contradiction which establishes our claim.
Since Omin > O, we further conclude that Y(r) is uniformly elliptic. Thus, for any compact set K. E (y E y: F(x", .y) Fo 8), the hitting time TXc inf 0 Y(r) E K.) will be infinite average (because [Tc]] 2 Ex,, [T=] = co), so, by Theorem C.I, Y(r) cannot be positive recurrent. In turn, this implies that Y(r) does not admit invariant measure on V, which proves our claim.
Finally, for the second part of (15), applying Dynkin's formula to the energy function E(y) for x at the truncated hitting times T AI, O, we get:
E,, [E((T)) ()) = E(yo) EE
((((((s). X(s) x²) tr(E(X(s)) Jac ((Y(s)))) ds
1
Fo + 2
Exn
tr tr(E(X(s)) Jac Q(Y(s))) ds
by null monotonicity
x²
TEAs
2 Fo +
min
Exp
tr[Jac Q({(s))) ds
(D.18)
2
24

---

where the last line follows from the estimate
tr I Jac Q] = tJac 2) 2)
= (l...., (Jac Q) 1/2 [ Q) (I....,))* 1)
2 - (1, ................................ (Jac Q) (Jac 122 (I....,1)
= [a[ Q1
(D.19)
By the assumptions of the theorem (smooth Q and interior initialization), it follows that the (necessar- ily compact) set Dg (= = @(y)= F(x', y) S Fo + E) is contained in the relative interior ri of X. In turn, this implies that K K2 min Jac Q(y)) F(xx,, ,) Fo + $} > O, so (D.18) becomes
Fo + Fo
KoT min Exp [T Ar]
(D.20)
2
and hence
28
Exn 1-" A1]
for all 0.
(D.21)
KO?
min
This shows that I A x] is uniformly bounded, so the upper bound (15) follows by letting f oo (which implies T Af r pointwise), and invoking the dominated convergence theorem.
D.4. The strongly monotone case. We now turn to main result for strongly monotone games. Our proof strategy draws on methods related to the analysis of (S-FTRL) in the context of convex minimization, explored by [47], and incorporating ideas that be traced back to [28].
For convenience, we begin by restating Theorem 2.
Theorem 2 (Strongly monotone games). Suppose that (S-FTRL) is run in a-strongly monotone game G, and consider the hitting time
T T in 0: X(1) B,()")
(16)
where (x'x)) fx - $ r) is ball of radius centered on the (necessarily unique) equilibrium ofG. Then:
Ex [T, s (Fo/a)/ (12 -r)) for all > ra.
(17)
where To == maxx 22Ka. If. in addition, Omin > 0 and x" is interior, X(r) admits an invariant distribation concentrated in a ball of radius O(Tmax) around x", and we have
lim, M4 (B, (x*) r for all r To.
(18)
Proof. Our proof proceeds along the following basic steps:
Step I. Deriving estimate for the mean hitting time Ex, [.
Step 2. Descending to restricted process F(r) where any redundant degrees of freedom in Y(r) have been "modded out".
Step 3. Showing that the restricted process is positive recurrent.
Step 4. Estimating the resulting invariant distribution and pushing the result forward to X(t).
In what follows, we go through the steps outlined above, one at time.
Step 1: Estimating the hitting time. We begin with the hitting time estimate (17). To that end,
setting p < x" in Proposition D.2, we get
E(((T)) E(yo) 1-" (o(X(s)). x²) ds 2K
1 L'' [[([((())] ds
L" (x(s) (()))-")Too(( ((((s)) dW(s)
30
--0 1 [|((s) -xx(s)-x'11
-
((T)
(D.22)
2K
25

---

where we set
M(1) S. xx) dw(s)
(D.23)
Thus, by a quick rearrangement, we obtain
L xx(())xx11 ds s E(yo) E(Y(T)) +
T max
+ (()
(D.24)
2K
and hence, with E 2 O:
L II((s) -x1 ds
Fb
T maxx
((z)
(D.25)
a
2
o
Thus, applying the above to the truncated hitting time T - Tr AIE min(Tr. 0, we get
Ex0 [ IIX(s) =x'1]2
2 Exp AI] s
#bvc [X(s) x s
Fo 3 IT, A ( Ex,IM(T, AO].
(D.26)
Since T, A S / is uniformly bounded, we will have Ex [M(T A A]] = E[M(O)] = 0 by the optional sampling theorem for continuous-time martingales [31, Theorem 3.22]. Thus, simple rearrangement gives
Fo/a 2-
Ex Ty A Ar S
for all 1 0.
(D.27)
This shows that Ex, Iy Ar] is uniformly bounded, so the bound (17) follows by letting (which implies T, A - T, pointwise), and invoking the dominated convergence theorem.
Step 2: Descending to the restricted process. We now proceed to examine the recurrence properties of X()). To that end, note first that the assumption miin 0 directly implies that (S-FTRL) is uniformly elliptic in the sense discussed in Appendix C. As such, consider the set
D, = (B, = (y E y: (1(()) - s))
(D.28)
and note that
T, inf > 0: X(1) E
> 0: Y(1)= E Dz}
(D.29)
so Y(r) is positive recurrent relative to D,.. Thus, if D, is compact, Theorem C.I immediately shows that Y(r) is positive recurrent, and hence admits an invariant measure y on y. In general however, D, need not be compact, we cannot conclude that Y(r) is recurrent from the fact that it hits D, in finite time on average.
To circumvent this difficulty, we will consider a "restricted" process which is positive recurrent, while retaining all information present in Y(1). The main idea here will be to "collapse" the fibers of Q. that is, those directions in ) which map to the same point in X' under Q: since the dynamics (S-FTRL) factor through ((r) = @(((r), these directions carry no relevant information, so they can be effectively discarded.
To carry all this out, let & denote the "tangent hull" of X in V. viz.
:== af=af((** X' - X) = {z V: 1z E X for all sufficiently small / > 0 and all x E ri X). (D.30)
In words, D is the smallest subspace of V which contains X' when the latter is translated to the origin so, by construction, X' is full-dimensional when viewed as a subset of V.? In this sense, V contains all the "essential" directions of motion of the problem.
Dually to the above, we also consider the corresponding dual space I Di of D/ this is not a subspace of y, but there exists canonical surjection II: y + y defined by restricting the action of y E y to D. that is,
(II(). (y.z) for all E V. The kernel of Il is precisely the annihilator Ann(V) of D, i.e.,
(D.31)
ker II Ann(i) (w y:: (w, 0 for all v)
(D.32)
"Specifically, unless X is singleton, has nonempty topological interior when viewed as subset of 1)
26

---

so, by the first isomorphism theorem, we get canonical identification (V/D)* = ker
The main reason for descending from y to y is the following: in the original space V have Q + w) = Q(y) whenever w annihilates V2 ef. Proposition B.1. As a result, the inverse image of any compact subset of X' under will always contain copy of Ann(V), so it can never be compact itself. By contrast, by "modding out" Ann(V) and descending to the restricted space y, this is no longer the case.
To move forward, consider the restricted mirror map ¹: 5 - X given by
2 = Qτ)) whenever IT(y)= = y.
(D.33)
By the last item of Proposition B.1 we have Q = Q + w) whenever w E Ann(V); this means that the choice of representative in (D.33) does not matter, so Q is well-defined. Accordingly, letting
(() I((()))
(D.34)
and applying II (S-FTRL) yields the "restricted" dynamies
(1 = d(II Y(r)
v(X(r) dr + II- (X(1)) dW(())
(D.35)
where X(r) = Q (((()) and, in a slight abuse of notation, we are overloading the symbol II to denote both the linear map II: y - Y and its representation as matrix. These dynamics represent a time-homogeneous SDE terms of y, and they will be our main object of study in the rest of our proof.
Step 3: Positive recurrence of the restricted process. With all this in hand, positive recurrence for the restricted process F(1) boils down to the following: a) verifying that the infinitesimal generator of Y is uniformly elliptic; and b) showing that the mean time required for f(1) to reach some compact set of y is finite.
We begin by establishing uniform ellipticity. In view of (D.35), the principal symbol (C.13) of the infinitesimal generator of f(r) is
A = (II-r)
(II Пoo J = =NEN.
(D.36)
Since Σ * o /, we readily get
A >
o
min
III
min
(D.37)
with mii > 0 (by assumption) and mmin := Amin (IIITT > 0 (because II is surjective, so it has full rank). This shows that the principal symbol NΣN of the generator of y uniformly positive-definite so Y is itself uniformly elliptic.
For the second component of our proof of positive recurrence, recall that e ri ri,'' there exists some sufficiently small > 0 such that the (compact convex) set
K, = B, n X' = (x E X': ||x |||| r
(D.38)
lies in its entirety within ri X. We then claim that the inverse image
D, = i-
(ā e D
(D.39)
of Kr, under the restricted mirror map Q is compact. To see this, note first that D, = ah(K,) by Proposition 1. Thus, given that K, is a convex body in 1' that is entirely contained in the (relative) interior of the prox-domain Xr of h (because ri S dom 0h Xx), it follows that (K,)) is itself compact by the upper hemicontinuity of oh [24, Remark 6.2.3].
To conclude, note that
inf(I 0: F(1) D,) inf 0: (1(((()))))))))))))))(((())))))) x''l s)
= inf(/ > 0: ((((())))))))))))))))))))))))))) s
inn((r 0 x()) E (,(x')
Tr
(D.40)
so it follows from (17) that F(1) hits D, in finite time on average. Since f(r) is uniformly elliptic, Theorem C.I shows that it is positive recurrent, claimed.
*Strictly speaking, we are viewing here äh as taking values in 5 instead of V; this is simple matter of identifying h: V - R with its canonical restriction to V _ V.
27

---

Step 4: Estimating the long-run occupation measure. Since the restricted process F(r) is positive recurrent Itō difffusion, standard results show that it admits invariant distribution ý on D which satisfies the law large numbers
1 L f(((s)) ds S18 sav dv
lim 1-00
(D.41)
for every y-integrable test function ff on D. Thus, letting v -o²=voQ- denote the corresponding push-forward measure X, get
/'' 1(X(s) BB)
lim p (B,)
lim 1-00
liim { l(((P(s)) B,) ds
Jn
1-00
{ 1(f(s) Dr) ds
lim 1-000
/ 1( E D,) dv(
=(()))
(D.42)
In similar manner, we also get
1- --v(D,)
lim
((X(s) & BB, ds
# b/c lim My deterministic
1-00
[X(ss) x2
lim
ds
b/c [
2 outside B,
1-00
22
Fo
lim
(D.25)
7
2a
22
(D.43)
Our claim then follows by combining Eqs. (D.42) and (D.43).
E Analysis and results in discrete time
In this appendix, we proceed prove the discrete-time results presented in Section
E.1. The null-monotone case. We begin with our analysis for for null-monotone games. convenience, restate Theorem 3 below:
For
Theorem 3 (Null-monotone games). Suppose that (FTRL) is run in null-monotone game G, and let x" be an equilibrium G. Suppose further that h' is strongly convex, and let F, F(x", Y,), where F is the induced Fenchel coupling (B.22). Then lim E[F, co.
Proof. By second-order Taylor expansion with Lagrange remainder, there exists W, [Y,, Yr41] such that:
F1+1 = t xx)) +
(E.1)
2
Since is null-monotone, we have (o(X,), X, -x') by assumption, and thus
y2
Fra1 = F X, -xxx + 0, 2 (w;)
(E.2)
2
2 F -x')+ + m
y ||
(E.3)
28

---

where In denotes here the strong convexity modulus of h Moving forward, note that (i) XI [[ 1F, -x>)] and (ii) inf, E E| [2] Enf[
so there exists some V. > such that E[ [| I 2 v? for all s. We thus get
E[ 2 E[F] + プ [|
2 E| + V2
Fo my my V2
(E.4)
Our result then follows by taking the limit 1 + co.
E.2. The strongly monotone case. We now turn to our main result for strongly monotone games, which we restate below for convenience.
Theorem 4 (Strongly monotone games). Suppose that (FTRL) is run in ar-ttrongly monotone game G, and consider the hitting time
T T in 0: x(1 B,(x"))
(22)
where (x(x') fx - equilibrium x² Gf Then, for all to vylo2 (²)/(aK), we have
s r} is ball of radius centered on the (necessarily unique)
Fo
if Xo IB, (x*),
E c
(23)
Fo ary2
if Xo B,(x),
where Fo = F(x', Yo). If. in addition, x* is interior, X, admits a unique invariant distribution to which it converges in total variation, and we have
lim - E Σ
1x B,((')) (1-))))2-121111
(24)
X=0
for all r To such that B, (x)) C r.
Proof. The main theme our proof shadows the continuous- analysis, but requires distinct tools and techniques to address the specific challenges that arise in the discrete-time Markov chain setting (where, among others, the main tools of stochastic calculus cannot be applied). a nutshell, this proceeds along the following sequence of steps. First, derive upper bound on the expected hitting time the process to neighborhood of the equilibrium. Subsequently, we reduce the dynamics to a "reduced space" (formally affine quotient of the dual space), removing redundant directions and ensuring the process evolves within a minimal and non-degen degenneree domain. Within this reduced space, show that the induced Markov process satisfies several crucial probabilistic properties. Specifically, we prove:
Irreducibility: any open set in the state space can be reached with positive probability.
Minorization: after entering certain regions of the space, the process mixes sufficiently to allow for probabilistic regeneration.
Uniform control of return times: the expected time to revisit a neighborhood of equilibrium remains bounded regardless of the starting point within that neighborhood.
These properties collectively enable the construction of regeneration structure, a probabilistic framework that ensures the process repeatedly returns well-behaved region of the state space with sufficient mixing. In turn, this enables us to establish positive Harris recurrence of the learning dynamies, a key property which ensures the existence and uniqueness of a stationary invariant distribution.
To streamline our presentation, we follow step-by-step approach, outlined below.
Step 1: Deriving a hitting estimate. Due to measurability issues, we cannot apply Dynkin's lemma directly in the discrete-time setting, which makes the proof more involved. Moreover, unlike in the continuous-time regime, we need distinguish between different initializations. Specifically, we consider two cases depending whether the initial state X, lies within the ball (x") not.
29

---

. Case 1: Xo $ (x*).. Letting F; F(x', Yr) and unfolding (B.29b), we readily obtain:
y
F s Fo +
Σ
(0s, Xs - xx) +
Σ
0
(B.5)
2K 5=0
and, setting Tp AT, get:
(T,A))-1
y²
(T
Ty Fo + y
Σ
Σ
l10.
(E.6)
2K
8=0
Thus, taking expectation conditional on the initial state Yo
y, we have
(T.AT)-
y
(T,
-
E FT +o+ y
Σ
(D,, X -x²)
+
E
1
2K
5
1-1 y(8s. Xs - -x")
y
$ Fo Σ
E
110s11
1(T, 2 s
s
(E.7)
2K
For notational convenience, denote each summand above per
y2
D3 = y(0,, -xx)+ |1& 11
1(T, 2
2K
and noting that the random variable 1(T, 1) is F--meauurable, we get
D,
E
E
y0,s X,, -x') +
x
11
1(r, 2st FF
2K
y² |10s Fs
E
1(T, 2s 1) 1) E
y X, - -x') +
2K
x(1 (x.) X, -xx) y2
= E
[[ 11:
E
Fs)
2K
y²
E 1(T, 25 1) -yalIx, -x*11 2K
(E.8)
where we used that EXU(X,, w.) |F. = 0. At this point, we note that E B| 1F|
s
2 +IU(X, ,.) |1. F,
22 + o²), and since 1 = r(B²+ (ak), we get
D, ~ E
-yall - x1p ayr 1(T (5++
$ E
(-yar² + ayy 1(T, 2 s+11
(E.9)
where in the last step we used that -x,-x'11 2 on (T, 2 1). Thus, plugging the above bound into (E.7), we obtain
[-1
B s Fo
Σ
D. s Fo+ Σ E + ayrá) 11T, 2 2 s
s=0
(T)
Fo ay(12 122)
x=0
Fo ar(r2 12) [[ A ))
(E.10)
As nonnegative, we readily obtain that
ar(r2 2 (T, A r)] $ Fo
(E.11)
and, since for <r, get:
B[(T, A At) S
(ry(22 - +2) Fo
(E.
Finally, taking f - co, and invoking the monotone convergence theorem [19], we get
1
E ay(r2 - -2)) Fo
(F.13)
30

---

Caase 2: Xo E (x))). In this case, we have:
T = (Q(() E (,(()) (((0)) (,(x))
= P(Q()) e ( E (1 By [y,
= P(2(1) e (xx))) & (x B(((O))))(((())+>>)))))))))))))) e (x)))) Ey [T,]]
= =1+E =1+((1((()) E (x))
$ +1+E 1(e()) $ (,(x)) (17(( F(x
$ 11+(0r(12 r2)) [[F((",
$ s1 11+(0y62 2 E F y(0p, Xo x²) y2
2K lloll
s1t ar )
Fo y(U(o)) Xo x²) ayr
s (ay(22 - -1))) - P0 - ya - xx1 ayrr.r
$ $1 + 10y(22 - x2) / 1o eyr2d
Fo ayr ay(r2 - Po)
(F.14)
Thus, collectively, we get:
1
Fo
if Xo (x(x",, if Xo BB(x'),
B s ay(r2 Fo+ ary2
x
(E.15)
Descending to the restricted process. As in the continuous-time case, establishing positive recurrence requires analyzing "restricted" version of the process. To that end, we follow the same construction as in Step 2 of Theorem 2, and we define the canonical surjection II: y - ) by restricting the action of y y to V, that is,
Step 2:
(I(y) (y.z) for all z E i.
(E.16)
whose kernel of Il is precisely the annihilator Ann( V) of V i.e.
ker II Ann(V) y (y. z) 0 for all V/)
(B.
In addition, we consider the restricted mirror map Ô: ý X' given by ²(0) Q(y) whenever II(y) y.
(E.18)
Accordingly, letting
(E.19)
and applying II to (FTRL) yields the "restricted" process
F.+1 II Y,+ II Y, y(II v(X,) II
II- U,) = y(((X,) 0,)
(F.20)
where X, = Q(Y) = Q(,) and, in a slight abuse of notation, we are overloading the symbol II to denote both the linear map II: y and its representation as matrix. Finally, writing y as
f, = Y, ro((())) + (U(((()).
(E.21)
we conclude that is time-homogeneous Markov process, and we denote its kernel by q, where for any Y and Borel set A C Di, we have q(ū. A) P(r.1 A A ū)
31

---

Step 3: Recurrence of the restricted process. To establish the recurrence of the restricted process, we first need to understand the effect of on the distribution of U(x). As stated in the assumptions in Section 4, the probability distribution Yx of U(x) decomposes as V, v + y Noting the porw-forward measure is linear, we readily obtain that I1, = II, f II. where II,v, denotes the push-forward measure A + (vx (AA). For notational convenience, we denote D = Ann( V) and p(x,,) ()) Px (t). Then, each y E Y' can be decomposed as y ý + D, and since II has full column-rank, the measure II, has density with respect to the Lebesgue measure dy on V, given by
x(x.0) = J p plx,
(E.22)
where d3 is the Lebesgue measure on Y. Importantly, the density P satisfies the following properties which will be crucial for establishing the recurrence of the process. We formalize these in the proposition below, whose proof is deferred until after the theorem.
Proposition E.1. Let the function P defined in (E.22). Then:
(i) For any compact set K. X and every ÿ E Ô, holds infxek p(x. 9))
(ii The function P is (jointly) lower semi-continuous.
Lebesgue irreducibility. We now show that the restricted process Y, is Lebesgue irreducible; that is, starting from any point in its domain, the process has a positive probability of reaching any open set with nonzero Lebesgue measure. This property is crucial for establishing recurrence, as it ensures that the process does not avoid regions of the space indefinitely.
For this, let a Borel measurable set A c ÿ with (A) O. We will show that q(ū. A) > 0 for all ğ E D, which implies that A can be reached from any state ğ in one step with positive probability.
(0.A) = P(P.. E A
= P(ū U p(i+yo(0()) + +U(O)))))))())))))))..)
= =P(Ū((().)) E A-y
= =P(U(C().)) Ag)
2 S ((00))2)dgk A
(E.23)
where Ag = y ((())) with (p(AA) = 2 > 0. Finally, since (()())))
strictly positive, we conclude that {ū A) O, which shows that Y, induced by (E.20) is Lebesgue- irreducible.
Harris recurrence. Our next step is to show that Y, is Harris recurrent. This means that the process returns every set of positive Lebesgue measure infinitely often with probability one. Establishing Harris recurrence a key step toward proving ergodicity. as it ensures that the process does not drift away or get trapped. For this, we will show that D, (ō ÿ l(@()) x=I| S r) is recurrent set from which we can go "everywhere" with positive probability. Importantly, the set D, is compact as shown in Step 3 of Theorem 2.
The first part to prove Harris recurrence is immediate from Step of our proof; namely, since Eg[T,] oo for any initial condition ÿ D, we readily get that Pg(T, < co) = 1.
For the second part, we will prove the so-called minorization property; that is, there exists a nontrivial measure и and a constant a > 0 such that
A) 2 aH(A)
for all ğ E D, and Borel sets A c D.
(E.24)
This condition implies that, from any point in D, the process has uniformly lower-bounded probability of reaching any set A in one step according to the reference measure μ.
32

---

To establish the minorization condition (E.24), we define for notational convenience the function y'yy X,
f(g.2)
-
(E.25)
which is continuous as composition of continuous functions. With this definition in hand, we perform the change of variables in (E.23), and have:
S p pl 2))
S inf p(f(.,) 2)) BED,
2
(E.26)
To finally construct the measure μ,, we need to ensure that
0 < S inf gED,
< <0
(E.27)
To this end, we state the following proposition, whose proof is deferred until after the theorem to maintain the flow.
Proposition E.2. The density P satisfies:
0 < SS inf ((((i < 0o DeD
(E.28)
With Proposition E.1 in hand, define the measure μ as
m(AA) = La inf DED, F(f().z)dddg
for all Borel A S D.
(E.29)
IS inf geD. ((f(g2))ddg
Therefore, (E.26) becomes:
((..A)2 [ inf p(f =)) = = S inf p(f(ū. d)) u(A) DED
(E.30)
deD,
Thus, setting a = y Js inf gED, p( d) (z), we conclude the minorization condition (E.24).
Therefore, the set D, is recurrent and μ(D,) 0 (since (D,) 0), and thus by [17, Proposi- tion 11.2.1] the Markov process admits an invariant measure. In addition, based on the equivalence (D.40) the expected return time T ] to D, is uniformly bounded for all initial conditions ÿ on D,, due the continuity of the Fenchel coupling F. Therefore, invoking [55, Theorem 13.0.1] we conclude that the process Y, admits unique invariant probability measure V, and the law of Y, converges to in total variation for every initial condition ÿ y.
Step 4: Estimating the long-run occupation measure.
Finally, for the last part, letting
F, = F(x".X .Y) and unfolding (B.29b), we obtain:
y2 1-1
Σ (0s, X, xxxx)+++
11
(E.31)
2K ==0
$=0
Taking expectations in both sides, readily get
y
0 0 I[F < R
Fo + y
Σ
(0.. X, - xx)
Σ
| 113
2K ==0
< Fo ar E
Σ ||x, x"112
+ tayr2
(E.32)
Therefore, by rearranging terms and dividing both sides by f, have:
E
|X,
- x²
$ 1 Fo
(E.33)
x=0
ayr
33

---

Moreover, we have:
22 Fo +
B Σ
1(, & B,(x')) 1 r4t
E
E x²1?
1
(E.34)
ayrr
y
Now, note that (X, B, (x*)) (8, $ Dr by construction, and thus
fxx $ B, (x')) Σ ==0
!
10, & D Σ s=0
(E.35)
Taking oo, and invoking Birkhoff's individual ergodic theorem [23, Theorem 2.3.4], we readily get that the mean occupation measure A + / E invariant measure v, and therefore
1f, EEE,
A}}
converges strongly to the
lim E 1(, E (x)))) lim
E
Σ x=0
1(, $ D.)
=1-v(D,)
(E.36)
1-00 1
x=0
and, using (E.34), we have:
/ 7
v(D,) 2
(E.37)
and our proof is complete.
To keep the presentation self-contained restate and prove Proposition E.1 and Proposition E.2 below.
Proposition F.1. Let the function p as defined in (E.22). Then:
(i) For any compact set K. S X and every ÿ E D, it holds infxek p(x. g)) 0.
(ii) The function P is (jointly) lower semi-continuous.
Proof.
(i) For the first part, let ÿ D. Then
J p(x, ddl55)) z S inf p(x, ". (.))))
inf p(x,)) inf xeX:
(E.38)
xex
(ii) For the second part, let (x, 5) E X' x D, and let a sequence {(x,, ūc) ūc) JeN with ox. (x, 7) Since is jointly continuous, applying Fatou's 's lemma [19], we get
p(x,0) = S3 Ddd(()))
/
lim inf p(x,, D. (d 10000
s lim inf S plxx,,B. Dr. 9) di (i)
1000
lim inf p(x, 9.)
(E.39)
i...,
p(x 0) lim inf p(x, Dt) 1-000
(E.40)
and the result follows.
Proposition E.2. The density & satisfies:
0 < S inf (lf(ū.)))dldst <0 DeD,
(E.28)
Proof. The upper bound is trivial since P a probability density and
Js inf (((().))) 2)) & S (C(() 1 BED,
(E.41)
34

---

(a) 0.1, =.1=0.1.0 0.5
(b) 0.1,
34
( 0.5, 0.5
(d) O.S, =
Figure 2: Visualization of the long-run oun occupancy measure for the min-max game with loss-gain function ((x).x2). Each plot shows the empirical density of the final iterates of 10 runs of (FTRL) for 10 steps, starting from uniformly random initial conditions. The surface plot encodes density via both height and color. Each row corresponds different step-size y e 0.5,, while the columns vary the noise level {0.5, 1}.
For the lower bound, we will show that
inf p(f(f.2)) 0 for all z E D. De
(E.42)
Suppose not, i.e., there exists zo 5 such that inf geD, P( zn)) = 0. Since D, is compact and is lower semi-continuous, the infimum over D, is realized, meaning that there exists ÿo D, such that pC zo)) = O, or, equivalently.
p(0(6o). y 'zo 50) E(((G))) = 0
(E.43)
This contradicts Proposition E. for K. C- K-+Ki, Ky, Finally, since we integrating over set with positive measure, our result follows.
F Further numerical results and details
In this section, we present some additional numerical simulations illustrate and validate our theoretical findings. To this end, we consider two simple yet representative examples: (i) strongly monotone two-player min-max game on the unit square; and (ii) finite zero-sum game (as an example of null-monotone game).
Strongly monotone games. by f [0, 1] x [0, + R with
We consider the strongly monotone two-player min-max game defined
f(x))22) -(x 0 0.5x + 2(x2 0.5)
(F.I)
35

---

and entropic regularization. To be more precise, the payoff functions of the two players are given by un (x) = X2) X2), and (20/33, 14/33) the unique Nash equilibrium point.
Fig. 2 demonstrates the behavior of (FTRL) under varying step sizes and noise levels for the min-max game defined by the function x2). Specifically, we consider step-sizes y {0.1, 0.5), and stochastic feedback of the form 0, = o v(X,) + dww, where w N(0, I2) for o ε (0.5, 1}. For each (y.o) configuration, we perform 10 independent trials, each running for 10 steps. The initial state Yo for each trial was drawn uniformly at random from [0, 1]a. Each surface represents the empirical density of the final (FTRL) iterates, while the color overlay visualizes their distribution across the 10 independent trials. Warmer (red) regions indicate higher concentration of final iterates, whereas cooler (blue) regions correspond to lower probability of ending in those regions, as indicated by the colorbar on the side. We observe that smaller step sizes and lower noise levels lead to tighter concentration of the final iterates around the Nash equilibrium. In contrast, increasing either the step size or the noise variance results in a more dispersed distribution. This behavior aligns with both intuition and our theoretical findings: higher noise introduces greater stochastic variability, while larger step sizes amplify this effect by inducing more aggressive updates that are prone to overshooting, ultimately increasing the spread of the iterates.
To further explore the behavior of (FTRL) under different noise levels and step sizes, we conduct an additional set of experiments summarized in Figs. 3 and 4. These figures illustrate the distance from r' of the final iterate and the hitting time in a neighborhood of x with varying radii. Specifically, we consider step sizes y {0.01, 0.02, 0.05, 0.1, 0.2, 0.5) and stochastic feedback of the form i, v(X,) + dit, for noise levels o E (0.01, 0.05, 0.1, 0.5, 1}. For each (y, (T) configuration, we perform 100 independent runs, each consisting of 10,000 iterations. The initial state Yo in each run is drawn uniformly at random from [0. 1J2. The first plot reports the average final distance of the iterates from the equilibrium, averaged across the 100 runs, while the subsequent plots show the hitting time required for the iterates to enter neighborhood of the equilibrium of radius r E (0.005, 0.01, 0.05, 0.13.
10
Distance
a=0.1
a-0,55
a=0.1
0-0,5
g=1
10
10-2
10-1
Stop size
Figure 3: Average final distance from cquilibrium for different values of the step-size y and the noise level Each point represents the mean over 100 independent runs of length 10,000, with shaded regions indicating one standard deviation.
Null-monotone games. Fig. 5 shows the empirical distribution of the final iterates under the (FTRL) dynamics in the classic matching pennies game with entropic regularization, played over the probability simplex with payoff matrix
(+1,-1) (-1,+1)
(1++1)
P=
The unique Nash equilibrium of the game is the mixed strategy (0.5, for both players. As before, we consider stochastic feedback of the form 0, o(X.) +(r)) where w NO0 /2) for (0.1, 0.2) and or E (1, 2). For each (y. or) configuration, we perform 10S independent trials, each running for 102 steps. Each surface plot corresponds to different combination of step-size and noise variance,
36

---

21
121
28
X28
(a) 0.005
(b) r
387
(c) 0.05
(d) 0.1
Figure 4: Average hitting time (in iterations) to neighborhood of the equilibrium x² with radius
(0.005, 0.01, 0.05, 0.1), computed over 100 runs for each (y, or) pair.
(a) y 0.1,0=1
(b) 0.1, =2
(6) = 0.2, o =1
(d) = 0.2, O =
for the bilinear game with entropic regularization. Each plot shows empirical density the final iterates 10a runs (FTRL) for 10 steps, starting from uniformly random initial conditions. The surface plot encodes density via both height and color. Each row corresponds to different step-size E (0.1,0.2, while the columns vary the noise level or E (1,2).
Figure 5: Visualization of the long-run occupancy
37

---

with the empirical density of the final iterates represented through both height and color over the simplex domain. We see that across all configurations, the iterates tend to concentrate near the corners of the simplex, reflecting the instability of the interior equilibrium in the presence of noise. This consistent shift toward extreme points highlights the system's 's inherent tendency to escape the central equilibrium under stochastic perturbations.
38

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope?
Answer: [Yes]
Justification: It can be found in Section 3, Section 4 and the appendix.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
It can be found in Section 1.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). 'he authors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't i acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: It can be found in Section 3, Section 4 and the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
39

---

All the theorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely. any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main experi- mental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: It can be found in Appendix F, and the code is included in the supplemental material. Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (c.g., in the case of a large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
If the contribution primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., large language model), then there should either be way access this model for reproducing the results or way reproduce the model (e.g.. with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instructions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
The code included in the supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https:/ httppp.ccppblc//ggiieeeee CodeSSubmiisioonPolicyy for more details.
40

---

While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code. unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurIPS code and data submission guidelines httpp:://niis.cc/pubbba
for more details.
The authors should provide instructions data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments ones are omitted from the script and why.
reproducible, they should state which
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: It can be found in Appendix F.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or supplemental material.
Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: No statistical significance applicable.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1 1-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (c.g. negative error rates). error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed reproduce the experi- ments?
41

---

Answer:
[Yes]
Justification: It can be found in Appendix F.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code Ethics https://harrlaa.ccppbbcc////e
Answer: [Yes]
Justification: The paper conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consideration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to par- ticular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, is legitimate to point out that improvement in the quality of generative models could be used generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e-g., pretrained language models, image generators, or scraped datasets)?
42

---

Answer: [NA]
Justification:
There are such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions access the model implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode. woaddde..oo/eeeeeeeeeeeeee datasets cataaatseee has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that are re-packaged, both the original license and the license the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
43

---

The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then much detail possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applica- ble), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, non- standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development this research does not involve LLMS as any important, original, non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy should or should not be described.
for what
44


Reviews:
[{"review_id": "wiwpgNIeLC", "reviewer": "Reviewer_M4ZL", "summary": "The paper investigates the problem of convergence in multi-agent learning with noisy feedback. The authors start from analyzing the hitting times and long-run behavior of stochastic gradient descent/ascent (S-GDA) dynamics the bilinear min-max and quadratic min-max games in continuous time, which are stylized examples of null-monotone and strongly monotone games. They proceed with the analysis in the general case of follow-the-regularized-leader (FTRL) dynamics, which contains S-GDA as a special case, in null-monotone and strongly monotone games. They show that, in null-monotone games, the dynamics drift away from equilibrium and requires infinite time to return, whereas in strongly monotone games, the dynamics drift towards the unique equilibrium and return arbitrarily close to its origin infinitely often with probability 1. Next, the authors explore the FTRL dynamics under standard assumptions in discrete-time using their insights from the continuous-time analysis. Similar to the continuous-time case, they prove that the dynamics drift away to infinity in null-monotone games and drift towards the equilibrium in strongly-monotone games.", "questions": "1. It is noted that the standard tools of stochastic analysis are often inapplicable in the discrete time analysis of FTRL's long-run behavior. Could you shortly clarify the novelties and technical difficulties setting the current analysis apart from the standard techniques in the literature, particularly in the (vanishing step size) FTRL analysis in discrete time?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "**Quality and Clarity:** The paper is clearly written and appears technically sound. The organization of the paper makes it easy-to-follow. The illustrations in toy examples nicely accompanies the results and discussion. It would also interesting to see the results in play in larger-scale experiments.\n\n**Significance and Originality:** The work differs from existing works as they explore either (1) a more general class of algorithms (e.g. FTRL rather than S-GDA) or (2) a different choice of step sizes (constant rather than vanishing). The constant step size in FTRL is noted by the authors as the dominant choice in practice due to its simplicity, robustness and superior empirical performance.", "was_revised": true, "final_justification": "The authors analyze the FTRL algorithm in the theoretically understudied case of constant step-sizes. This non-trivial extension has a theoretical and empirical justification as also noted by other reviewers. The paper is clearly-written, and the authors will include further discussion that will enhance the readability. The paper is also mostly self-consistent with Appendices B and C.", "rebuttal": "Dear reviewer,\n\nThank you for your time, positive evaluation and encouraging words! We reply to your remarks and questions below:\n\n> It is noted that the standard tools of stochastic analysis are often inapplicable in the discrete time analysis of FTRL's long-run behavior. Could you shortly clarify the novelties and technical difficulties setting the current analysis apart from the standard techniques in the literature, particularly in the (vanishing step size) FTRL analysis in discrete time?\n\nYour question has two parts: stochastic analysis techniques (for the continuous-time setting), and stochastic approximation techniques (for the discrete-time analysis in the vanishing step-size regime).\n\n1. Regarding the former (comparison to the continuous-time regime), the core technical difficulty is the lack of an analogue of Itô's forumla and, a fortiori, a suitable Dynkin lemma for getting concrete hitting time estimates based on the infinitesimal generator of the process. Because of this, estimating the invariant measure of the process (and/or establishing recurrence) is a much more difficult affair which requires a series of intricate Lyapunov estimates from the theory of discrete-time Markov chains, used in turn to establish Lebesgue irreducibility and Harris recurrence (see Appendix E for the details). Specifically, in continuous time, positive recurrence and the existence of an invariant distribution are almost immediate once we establish uniform ellipticity of the diffusion process (Steps 2 and 3 of the proof of Theorem 2 in Appendix D).  By contrast, in the discrete-time regime, the analysis requires a regeneration argument to ensure that the process repeatedly returns to a well-behaved region of the state space with sufficient mixing. This regeneration structure is crucial for establishing positive Harris recurrence of the learning dynamics—a key stochastic stability property that guarantees the existence and uniqueness of a stationary invariant distribution. These subtleties are unique to the homogeneous, discrete-time setting, and they have no bona fide analogue in continuous time.\n\n2. Regarding the latter (comparison to the stochastic approximation regime), it should be noted that the use of a vanishing step-size ultimately means that the noise \"washes out\" in the long run, and the trajectories of the process can be well-approximated by the flow of an ordinary differential equation (the precise notion is that of an asympotic pseudotrajectory, cf. Benaïm, 1999, and references therein). Because of this, the long-run behavior of FTRL with a vanishing step-size is fundamentally different, and is captured by the so-called internally chain transitive (ICT) sets of a *deterministic* dynamical system. By contrast, the constant-step version of FTRL exhibits ergodicity, so one is naturally led to study questions of concentration instead of convergence—which, is significantly more demanding than studying a deterministic ODE, even in the presence of a Lyapunov function.\n\n---\nThank you again for your time and positive evaluation—we remain at your disposal if you have any further questions or remarks, and we are looking forward to further constructive exchanges during the discussion phase!\n\nKind regards,\n\nThe authors"}, {"review_id": "U9bFPZ3ZME", "reviewer": "Reviewer_kZLR", "summary": "This paper analyses the convergence of follow-the-regularized-leader (FTRL) algorithms in games with uncertainty, in both the continuous and discrete case.\nThe authors have both negative and positive results. On the negative side, they show that - differently from  full-information models of learning - games under uncertainty do not converge in general. On the positive side, they show that in strongly monotone games FTRL always return to a neighbourhood of the equilibrium in finite time (which they estimate).", "questions": "1) The authors make some assumptions about the class of games they analyse (actions selected from a closed convex subset, payoff individually concave, \\beta-Lipschitz smoothness). It would be helpful to understand the strength of those assumptions, as well as which results break down if such assumption are removed.\n\n2) Def. 1: I don't understand the difference between merely monotone and null-monotone, as in both cases \\alpha = 0.\n\n3) The authors mention different types of uncertainty in the introduction, but then in Sec. 3 all these are modelled as Brownian motion. Is this a suitable way of modelling all the different types of uncertainty mentioned in the introduction?\n\n4) Results are provided for null monotone games and strict monotone games. Any intuition about the situation for merely monotone games.", "limitations": "1) The related literature is discussed and compared, although there is no dedicated related work section.\nFor clarity, I'd suggest the authors add a section specifically devoted to comparison with the SOTA.\n\n2) The authors make some assumptions about the class of games they analyse (actions selected from a closed convex subset, payoff individually concave, \\beta-Lipschitz smoothness, \\sigma is bounded and Lipschitz\ncontinuous). Please refer to the question above.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "This paper makes two main contributions:\n\n+ The authors show that in null-monotone games with an unbounded action space, the sequence of play under FTRL drifts away to infinity on average.\n\n+ In strongly monotone games, the authors show that the mean time required to reach a given distance\nfrom the game's equilibrium is finite, and they provide an explicit estimate thereof.\n\n+ The FTRL model of learning encompasses several relevant multi-agent learning algorithms of practical interest.\n\n+ The results appear to be correct, although I did not check all the details.\n\n- The paper is extremely technical and definitely not an easy reading. However, the authors make an effort to make their paper accessible to a wider audience, e.g., consider Sec. 3.1.", "was_revised": true, "final_justification": "Happy with the paper and rebuttal.", "rebuttal": "Dear reviewer,\n\nThank you for your time, positive evaluation and encouraging words! We reply to your remarks and questions below:\n\n---\n> The authors make some assumptions about the class of games they analyse (actions selected from a closed convex subset, payoff individually concave, \\beta-Lipschitz smoothness). It would be helpful to understand the strength of those assumptions, as well as which results break down if such assumption are removed.\n\nThese assumptions are all quite standard in the study of online learning and games with continuous action spaces, and most of the positive results in the literature hinge on a variant of these assumptions.\n\nWith regard to the specific assumptions that you mention, some concern the structure of the problem at hand, and some its regularity. The role of each type of assumptions is different, so we present some details based on this grouping below, before discussing their eventual relaxation.\n\n1. First, regarding our structural assumptions—that is, convexity of the players' action sets and monotonicity of the game being played. These are both required to have an amenable \"convex structure\", which is in turn required to establish the existence of an equilibrium and/or be able to characterize it via first-order variational conditions. Without a structural characteriztion of this type, it is not even clear what type of solution concept could be relevant or meaningful, and any hope of global convergence is ruled out. In a sense, these assumptions comprise the game-theoretic equivalent of the convex / non-convex separation in minimization problems—but with the added difficulty that, in non-convex games, equilibria may not even exist, whereas minimizers (either local or global) are generically guaranteed to exist in non-convex minimization problems.\n\n2. Second, regarding our regularity assumptions (closedness of the players' action sets, Lipschitz smoothness, etc): these assumptions are mostly technical in nature and, for the most part, they can be relaxed at the cost of a (significantly) more involved presentation. They are very common in practice and, as such, they are almost universal in the literature.\n\nNow, regarding the relaxation of these assumptions: relaxing the latter (regularity assumptions) is possible, e.g., by assuming some variant of Lipschitz smoothness (such as local Lipschitz smoothness, relative smoothness, Hölder smoothness or some other relaxation), and the end results should be comparable (but at the cost of a significantly more difficult trajectory to achieve them). Relaxing the former (the problem's structural assumptions) is considerably trickier: some of our results would go through as long as the game's equilibrium admits a global variational characterization (e.g., via a Minty variational inequality or a similar structure). If, however, the game admits distinct components of equilibria, all bets are off: in that case, FTRL (and most other learning schemes that we are aware of) could transit in perpetuity between the game's different equilibrium components, and characterizing the mean sojourn and transition times of the process would only be possible in very specific settings.\n\nAll in all, the set of assumptions that we consider represents a certain \"sweet spot\" between theoretical tractability and practical relevance, and this is why they are so widely used in the literature.\n\n---\n> Def. 1: I don't understand the difference between merely monotone and null-monotone, as in both cases α = 0.\n\n\"*Null-monotone*\" means that the inequality holds with equality everywhere, i.e.,\n$$\n\\langle v(x')-v(x), x-x' \\rangle = 0\n\\quad\n\\text{for all $x,x' \\in \\mathcal{X}$}.\n$$\nBy contrast, \"*merely monotone*\" (or, more simply, \"*monotone*\") means that\n$$\n\\langle v(x')-v(x), x-x' \\rangle \\leq 0\n\\quad\n\\text{for all $x,x' \\in \\mathcal{X}$}\n$$\ni.e., that the defining inequality holds with $\\alpha=0$ (but not necessarily as an equality throughout).\n\n---\n> The authors mention different types of uncertainty in the introduction, but then in Sec. 3 all these are modelled as Brownian motion. Is this a suitable way of modelling all the different types of uncertainty mentioned in the introduction?\n\nWe should point out here that we only use Brownian motion as a model in Section 3.1, which is intended as a \"gentle start\" for our more general model. In Section 3.2, payoff shocks and disturbances are instead modeled by an *arbitrary* martingale process $M_i(t)$, which acts as a \"catch-all\" disturbance term (accounting for \"colored noise\" effects, correlations, stochastic dependencies, etc.). The representation (12) of $M(t)$ via a Brownian integrator is not an assumption per se, but a consequence of the martingale representation theorem, which allows us to express any homogeneous square-integrable martingale in this form.\n\nWe mentioned this briefly in the footnote at the bottom of p. 6, but we realize that the current presentation could potentially lead to confusion on this point. We will be happy to make this clear and include a version of the above discussion in the first revision opportunity.\n\n---\n> Results are provided for null monotone games and strict monotone games. Any intuition about the situation for merely monotone games?\n\nIn the context of our paper, merely monotone games could be viewed as a \"hybrid\" between null and strictly monotone games. Specifically, at any given action profile of a merely monotone game, there would be directions of motion where the (symmetrized) Jacobian of the players' gradient field has a zero eigenvalue, and directions of motion with positive eigenvalues; either set (but not both) could be empty, the former corresponding to the \"null-monotone\" directions, the latter corresponding to the \"strongly monotone\" ones. Our analysis suggests that, in the presence of uncertainty, FTRL would tend to \"wander around\" the null-monotone directions, and be carried along the strongly monotone directions toward the game's set of equilibria. However, making this statement precise would require a highly technical treatment that lies well beyond the scope of our paper, so we leave this undertaking as a promising direction for future research (which we will be sure to mention in the revised version of our paper).\n\n> The related literature is discussed and compared, although there is no dedicated related work section. For clarity, I'd suggest the authors add a section specifically devoted to comparison with the SOTA.\n\nThank you very much for the suggestion—absolutely, we will be happy to organize the related work under a dedicated section to make the comparison with the state of the art clearer and easier to follow. We will implement this minor restructuring in the first revision opportunity.\n\n---\nThank you again for your input and strongly positive evaluation—we remain at your disposal if you have any further questions or remarks, and we are looking forward to further constructive exchanges during the discussion phase!\n\nKind regards,\n\nThe authors"}, {"review_id": "gzzOERjAWt", "reviewer": "Reviewer_a9vV", "summary": "This paper examines how persistent uncertainty affects multi-agent \"follow-the-regularized-leader\" (FTRL) learning algorithms. The primary contribution is identifying a stark difference in behavior based on the game's structure. In null-monotone games, learning dynamics drift away from equilibrium, showing no long-term concentration. Conversely, in strongly monotone games, the dynamics are pulled toward equilibrium but continue to fluctuate within a concentrated region whose size is determined by the amount of uncertainty. The authors provide formal analysis for this dichotomy in both continuous and discrete-time models.", "questions": "* The notion of ‘uncertainty’ has many interpretations. Here, the authors interpret it as noise on the applied gradient updates, which could represent random disturbances in the game. Another interpretation of ‘uncertainty’ is epistemic uncertainty about the policy and learning dynamics of other agents, influencing the best response computation of the agents. Crucially, this epistemic uncertainty can be reduced by observing past actions from the other agents and doing Bayesian posterior updates. Are any insights from this paper relevant to the notion of uncertainty as epistemic uncertainty?\n* Line 317: the authors claim that constant step size is much more common in practice. However, in modern machine learning, learning rate schedulers are crucial to obtain competitive results. Hence, the authors should clarify and maybe make other arguments to justify their focus on a constant learning rate. It would also be great to comment on how the core results and insights would change when using learning rate schedulers. \n* It would be great to use some example games that are more relevant to real-world settings to illustrate the importance of the insights gained by this paper to a broader audience.", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 1, "originality": 2, "strengths_and_weaknesses": "Strengths:\n* Theoretical quality: the paper contains a thorough mathematical analysis of the learning dynamics in null-monotone and strongly monotone games, augmented with examples providing further intuitions, and a detailed supplementary material with proofs and required background information.\n\nWeaknesses\n* While the authors motivate their contributions by applications to machine learning and data science, it is hard to see how it can be of practical relevance in non-trivial machine learning settings. The assumptions of individually concave and monotone games are rarely satisfied in multi-agent machine learning setups, and it is unclear how the insights of the paper transfer to insights into machine learning. While the authors provide some game-theoretic examples of strongly monotone and null-monotone games, it would be beneficial to provide a discussion on how the core results of these paper can provide insights to more practical machine learning settings.", "was_revised": true, "final_justification": "The authors provided further motivation and examples on why their work is relevant for machine learning and multi-agent RL in general, thereby addressing my main concern. Therefore I raised my score to a 5.", "rebuttal": "Dear reviewer,\n\nThank you for your time, your constructive input, and positive evaluation! We reply to your remarks and questions below:\n\n> The assumptions of individually concave and monotone games are rarely satisfied in multi-agent machine learning setups, and it is unclear how the insights of the paper transfer to insights into machine learning.\n> [...]\n> It would be great to use some example games that are more relevant to real-world settings to illustrate the importance of the insights gained by this paper to a broader audience.\n\n\nWe would like to point out that our primary motivation lies in applications to online / multi-agent learning, and we provide a series of concrete applications of this type in Appendix A. In addition, the covariance matrix optimization problem described in Example A.3 is also an important application at the intersection of digital signal processing, machine learning, and information theory, and it can be modeled precisely as a monotone game.\n\nIn a similar direction, we provide below yet another example with its roots in content-based image retrieval and metric learning for image similarity search is as follows. To that end, consider a database $\\mathcal{D}$ of images represented as vectors $v_i\\in\\mathbb{R}^d$, $i\\in\\mathcal{D}$, and consider the Mahalanobis distance\n$$\nd_X(v_1,v_2)\n= (v_1-v_2)^\\top X (v_1-v_2)\n$$\nwith respect to some positive-definite precision matrix $X\\in\\mathbb{R}^{d\\times d}$. If each image $v_i$ has a set of similar and dissimilar images, $S_i$ and $U_i$ respectively, the goal is to find a precision matrix so that $d(v,v') < d(v,v'')$ whenever $v$ is similar to $v'$ but dissimilar to $v''$. By standard arguments, this boils down to minimizing the distributed optimization objective\n$$\nf(X)\n= \\sum_{i\\in\\mathcal{D}} \\sum_{j\\in S_i} \\sum_{k\\in U_i}\nL(d_X(v_i,v_j) - d_X(v_i,v_k)) + \\varepsilon\\|X - I\\|_F^2\n$$\nwhere $L$ is a convex empirical loss function (typically quadratic), $\\varepsilon$ is a regularization parameter, and $\\|\\cdot\\|_F$ denotes the Frobenius norm, cf. Bellet et al., \"*A survey on metric learning for feature vectors and structured data*\".\nTo reduce model complexity and to better exploit correlations between features that reduce over-fitting effects, it is also common to proxy low-rank precision matrices by including a trace constraint of the form $\\mathrm{tr} X \\leq c$ for some $c \\ll d$. Finally, when $\\mathcal{D}$ is large, it is common to distribute the (convex) objective above over several computing nodes, thus giving rise to a convex potential game played over the spectraplex $\\mathcal{X} = \\{X\\succeq 0 : \\mathrm{tr}(X) ≤ c \\}$. Since the game admits a (strongly) convex potential, it is strongly monotone, cf. Lim et al., \"*Robust structural metric learning*\", ICML 2013.\n\nOther ML-relevant examples include the allocation of computing resources in GPU clusters, Kelly auctions for online ad placement, etc. We will be happy to describe these applications in more detail in the first revision opportunity (though, even with the extra page available, it will be challenging to transfer them all to the main part of the text).\n\n---\n> The notion of ‘uncertainty’ has many interpretations. Here, the authors interpret it as noise on the applied gradient updates, which could represent random disturbances in the game. Another interpretation of ‘uncertainty’ is epistemic uncertainty about the policy and learning dynamics of other agents, influencing the best response computation of the agents. Crucially, this epistemic uncertainty can be reduced by observing past actions from the other agents and doing Bayesian posterior updates. Are any insights from this paper relevant to the notion of uncertainty as epistemic uncertainty?\n\nIt is true that uncertainty can be interpreted in multiple ways. In our work, we focus on aleatoric uncertainty, modeled as persistent noise in the agents’ gradient feedback and reflecting random disturbances in the environment, fluctuations in the agents' payoffs, etc. This type of uncertainty is inherent and irreducible, and it directly affects the agents' learning dynamics.\n\nBy contrast, epistemic uncertainty refers to an agent’s lack of knowledge about the game—such as the policies, strategies, or update rules of the other players. This type of uncertainty can indeed be reduced over time through observation and inference, for example via Bayesian updating. However, such inference presumes that an agent knows what they are trying to model: the number of other agents, their action spaces, and a hypothesis class for their behavior. Our framework explicitly assumes none of this information is available—in fact, the players may not even be aware that they are involved in a game. Specifically, each player is assumed to operate in an online, decentralized setting, receiving only noisy feedback about their own payoffs. They have no visibility regarding the number or behavior of the other players, let alone the structure of their opponents' strategy spaces, so epistemic issues do not come about in this context.\n\nIn this sense, drawing a direct connection between our analysis and epistemic uncertainty is difficult and lies beyond the scope of this work. While both forms of uncertainty affect the agents' learning behavior, they do so in fundamentally different ways, and they have arise from drastically different origins and modeling assumptions. Extending our framework to incorporate belief formation or adaptive modeling of other agents would be an interesting direction for future work, but it would be a completely different paper.\n\n---\n> Line 317: the authors claim that constant step size is much more common in practice. However, in modern machine learning, learning rate schedulers are crucial to obtain competitive results. Hence, the authors should clarify and maybe make other arguments to justify their focus on a constant learning rate. It would also be great to comment on how the core results and insights would change when using learning rate schedulers.\n\nWe would like to point out here that our remark in L317 that constant step-sizes are \"more common in practice\" was made in reference to *vanishing* step-size schedules, not the more sophisticated cosine / restart schedulers that are used in many state-of-the-art ML models.\n\nWith regard to this, the use of a vanishing step-size—typically satisfying a Robbins-Monro condition of the form $\\sum_n \\gamma_n = \\infty$ and $\\sum_n \\gamma_n^2 < \\infty$ or a variant thereof—is quite common in stochastic approximation, but it comes with significant caveats. Chief among these is their inherent inverse recency bias: as the step-size shrinks, newer information receives less weight in the update process, which runs contrary to the guiding principle that iterative algorithms should prioritize recent data, as emphasized by Nesterov (2009, p. 224).\n\nThese limitations manifest both in theory and in practice:\n\n- **From a theory standpoint,** vanishing step-sizes can degrade performance. Notably, FTRL under such schedules can exhibit superlinear regret even in simple settings like the exponential weights algorithm, as shown by Orabona and Pál (2018). This is one of the main reasons that FTRL has been primarily developed and analyzed in the online learning literature with constant step-size policies, cf. Shalev-Shwartz (2011), Lattimore & Szepesvári (2020), and references therein.\n- **From a practical standpoint,** algorithmic variants with a vanishing step-size are often sluggish in the beginning, requiring many iterations before reaching a neighborhood of an equilibrium. By contrast, constant step-size methods tend to reach very rapidly the vicinity of a solution (often within  0.1% accuracy), cf. Dieuleveut et al. (2020).\n\nNow, in terms of non-vanishing training schedules, many state-of-the-art transformers and LLMs utilize step-size schedules that are often constant over billions (or even trillions) of samples. As an example, we cite below an excerpt from the training schedule used for DeepSeek (DeepSeek v3 technical report, Section 4.2):\n\n```\nWe keep a constant learning rate of 2.2 × 10−4 until the model consumes 10T training tokens.\n[...]\nDuring the training of the final 500B tokens, we keep a constant learning rate of 2.2 × 10−5 in the first 333B tokens, and switch to another constant learning rate of 7.3 × 10−6 in the remaining 167B tokens.\n```\n\nOf course, there are no \"one-size-fits-all\" solutions and, ultimately, both vanishing, and non-vanishing/ constant step-size methods have their respective strengths and limitations. Choosing the appropriate approach depends critically on the specific context and goals of the problem at hand, and while our analysis does not cover the more sophisticated cosine / restarting step-size schedulers used in some DL applications, it opens the door to a rigorous analysis of their properties and long-run behavior.\n\n---\nThank you again for your time and positive evaluation—we remain at your disposal if you have any further questions or remarks, and we are looking forward to further constructive exchanges during the discussion phase!\n\nKind regards,\n\nThe authors"}, {"review_id": "ef5Ucj5TL1", "reviewer": "Reviewer_aVWf", "summary": "This paper investigates the long-run behavior of regularized multi-agent learning algorithms (notably FTRL) in continuous games under persistent uncertainty. It establishes a sharp dichotomy between null-monotone and strongly monotone games: in the former, stochastic dynamics drift away from equilibrium with no concentration, while in the latter, they recurrently return and concentrate around equilibrium within a quantifiable radius tied to noise. The analysis covers both continuous-time (via stochastic differential equations) and discrete-time (with constant step-size) settings, providing explicit estimates on hitting times and invariant distributions. The work offers the first rigorous characterization of when regularized learning dynamics stabilize versus diverge under noise.", "questions": "1. The analysis uses general mirror maps defined via strongly convex regularizers. While Euclidean and entropic regularization are covered in examples, it remains unclear whether the qualitative behavior (e.g., recurrence bounds, invariant measure support) is strongly affected by the choice of regularizer. Could the authors comment on how robust their concentration results are to this choice, and whether some regularizers might yield tighter bounds?\n2. The discrete-time recurrence argument relies heavily on a minorization condition and the construction of a regeneration structure. Could the authors comment on how realistic or restrictive these assumptions are in practical applications of FTRL (e.g., reinforcement learning or decentralized optimization)? Are there classes of noise where these conditions might fail?\n3. If an application is known to induce a null-monotone game, what should a practitioner do—should they regularize differently, or adapt step sizes?\n4. The divergence results are shown under constant learning rates. Would using a slightly decaying learning rate (e.g., $\\gamma_t = \\gamma / \\sqrt{t}$) in null-monotone games avoid divergence while preserving good empirical performance?\n5. The bounds are clean and intuitive (e.g., scaling with $\\sigma^2$ and $1/\\alpha$), but it is unclear whether they are conservative or sharp in practice. Do the empirical examples in the paper or supplementary suggest that these are close to optimal?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- Quality: The paper is technically strong, providing rigorous theoretical analysis of stochastic learning dynamics in both continuous and discrete time. The use of tools like Fenchel coupling, Dynkin’s formula, and martingale analysis is precise and appropriate. The theorems are carefully stated and proved, with all assumptions clearly laid out, and the supplementary material offers thorough proofs and additional context.\n\n- Significance: The work addresses a foundational problem in multi-agent learning—understanding the behavior of learning algorithms under uncertainty—through a lens that is both practically relevant (constant step-size FTRL dynamics) and theoretically underexplored. The results clarify which game structures lead to stability versus divergence, providing actionable insight for the design and analysis of learning algorithms in games.\n\n- Originality: The central contribution—a precise recurrence vs. concentration dichotomy for stochastic regularized learning—is novel and fills a clear gap in the literature. While some special cases have been studied (e.g., stochastic approximation with vanishing step sizes), this paper breaks new ground by characterizing the long-run distributional behavior under persistent noise and constant learning rates.\n\n- Clarity: The writing is mostly clear and well-organized, especially considering the technical depth. The structure follows a logical progression from intuition-building examples to general results, with motivating commentary throughout. Figures (e.g., Fig. 1) and appendices are well-integrated and help elucidate the theoretical claims.\n\nWeaknesses:\n- Clarity (minor): While the main exposition is clear, the technical density in some sections—especially the discrete-time analysis—may limit accessibility to readers unfamiliar with stochastic processes and advanced convex analysis. A high-level summary of the proof strategies in Section 4 (discrete-time) would help orient the reader before diving into the details.\n\n- Scope of Experiments: The numerical illustrations are minimal and largely illustrative. While this is primarily a theoretical paper, slightly more extensive empirical validation (e.g., tracking empirical hitting times and occupation measures over varied games/noise levels) would help bridge the theory–practice gap and reinforce the significance of the results.\n\n- Assumptions: Some of the regularity conditions (e.g., smoothness of mirror maps, Lipschitz noise models, interior equilibrium) are reasonable but could be discussed more explicitly in terms of how they limit applicability to real-world learning settings.", "was_revised": true, "final_justification": "Thanks to the author for the detailed response. The explanations and justifications clearly addressed my questions and concerns. I'd keep the \"accept\" score and recommend the paper to be accepted.", "rebuttal": "Dear reviewer,\n\nThank you for your time, your constructive input, and strong positive evaluation! We reply to your remarks and questions below:\n\n> While the main exposition is clear, the technical density in some sections—especially the discrete-time analysis—may limit accessibility to readers unfamiliar with stochastic processes and advanced convex analysis. A high-level summary of the proof strategies in Section 4 (discrete-time) would help orient the reader before diving into the details.\n\nOf course—we would be happy to take advantage of the extra page available at the first revision opportunity to provide a high-level overview of our proof strategy. In a nutshell, this proceeds along the following sequence of steps:\n- First, we reduce the dynamics to a \"reduced space\" (formally an affine quotient of the dual space), removing redundant directions and ensuring the process evolves within a minimal and non-degenerate domain.\n- Within this reduced space, we show that the induced Markov process satisfies several crucial probabilistic properties. Specifically, we prove:\n    1. **Irreducibility:** any open set in the state space can be reached with positive probability.\n    2. **Minorization:** after entering certain regions of the space, the process mixes sufficiently to allow for probabilistic regeneration.\n    3. **Uniform control of return times:** the expected time to revisit a neighborhood of equilibrium remains bounded regardless of the starting point within that neighborhood.\n- These properties collectively enable the construction of a regeneration structure—a probabilistic framework that ensures the process repeatedly returns to a well-behaved region of the state space with sufficient mixing. In turn, this enables us to establish positive Harris recurrence of the learning dynamics—a key property which ensures the existence and uniqueness of a stationary invariant distribution.\n\nWe will be happy to provide a step-by-step walkthrough of this proof structure—thanks for bringing it up.\n\n> The numerical illustrations are minimal and largely illustrative. While this is primarily a theoretical paper, slightly more extensive empirical validation (e.g., tracking empirical hitting times and occupation measures over varied games/noise levels) would help bridge the theory–practice gap and reinforce the significance of the results.\n\nThank you for the suggestion—we will be happy to provide statistics on hitting times and the occupancy measure of the process to provide an additional layer of empirical validation to our results. The way that OpenReview has been set up this year, it is not possible to include any simulations during the rebuttal stage (or even the result thereof through an anonymized picture or github link), but we commit to do so at the first revision opportunity.\n\n---\n> Some of the regularity conditions (e.g., smoothness of mirror maps, Lipschitz noise models, interior equilibrium) are reasonable but could be discussed more explicitly in terms of how they limit applicability to real-world learning settings.\n\nOf course—we will be happy to provide a more explicit and detailed discussion of these assumptions. We did not do so in the submitted version because most of them are quite standard and we were constrained for space, but we will take advantage of the extra page available in the revision reound to provide more details on this.\n\n---\n> The analysis uses general mirror maps defined via strongly convex regularizers. While Euclidean and entropic regularization are covered in examples, it remains unclear whether the qualitative behavior (e.g., recurrence bounds, invariant measure support) is strongly affected by the choice of regularizer. Could the authors comment on how robust their concentration results are to this choice, and whether some regularizers might yield tighter bounds?\n\nThe geometry of the regularizer is reflected in its strong convexity modulus $K$, which can in turn be seen as a measure of its curvature relative to the ambient norm of the space (and, dually to the above, the Lipschitz smoothness modulus of the players' choice map $Q$). Our bounds depend implicitly on $K$ and they indicate a trade-off between the degree of concentration of the process around the \"event horizon\" beyond which the noise dominates the drift, and the time required to hit this region. These bounds tighten when the induced Bregman divergence $D(p,x) = h(p) - h(x) - \\langle \\nabla h(x),p-x\\rangle$ of the regularizer is well-approximated by (a multiple of) the ambient norm squared, but making a precise comparison between different regularizers is otherwise very difficult. We will make sure to point this out in the final version of our paper.\n\n---\n> The discrete-time recurrence argument relies heavily on a minorization condition and the construction of a regeneration structure. Could the authors comment on how realistic or restrictive these assumptions are in practical applications of FTRL (e.g., reinforcement learning or decentralized optimization)? Are there classes of noise where these conditions might fail?\n\nThe noise covariance minorization condition is not restrictive, and it can be trivially achieved by injecting even a small amount of Gaussian noise in the process (e.g., as is done in many incarnations of SGD to ensure that the process does not get stuck in spurious local minima). We can think of somewhat degenerate stochastic first-oracles that do not satisfy this condition—e.g., when the size of a minibatch is particularly large—but, otherwise, this assumption is standard in the literature.\n\n---\n> If an application is known to induce a null-monotone game, what should a practitioner do—should they regularize differently, or adapt step sizes?\n\nThat's an excellent question. In a deterministic context, the standard remedy is to consider an extrapolation-based variant of FTRL such as optimistic or extra-gradient methods. In the presence of uncertainty however, Hsieh et al. (\"Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling\", NeurIPS 2020) showed that even extrapolation-based methods fail to converge under uncertainty.\n\nTo ensure convergence, a practitioner's best bet in this case would be to take an extrapolation-based variant of FTRL (that is, modify FTRL with an inclusion of an interim gradient-like step), with different step-size policies in the extrapolation and update phases, in the spirit of the paper of Hsieh et al. above. Of course, this would come with additional difficulties from a theoretical standpoint (Hsieh et al. only provide convergence guarantees for unconstrained problems) but this would at least mitigate *some* of the difficulties identified in this context. We will make sure to mention this in the final version of our paper.\n\n---\n> The divergence results are shown under constant learning rates. Would using a slightly decaying learning rate in null-monotone games avoid divergence while preserving good empirical performance?\n\nThank you for the insightful question—unfortunately, the short answer is \"no\".\n\nIn more detail, assuming a variable step-size $\\gamma_t$, the expectation of the Fenchel-coupling in equation (E.4) of Appendix E can be seen to scale as \n$$\n\\mathbb{E}[F_{t+1}]\n\\geq \\Theta\\left(\\sum_{k=1}^t \\gamma_t^2 \\right).\n$$\nAs a result, we would still observe non-convergence (in expectation) for any step-size sequence, and divergence (again, on expectation) for any step-size with $\\sum_t \\gamma_t^2 = \\infty$.\n\nThis type of behavior is what makes learning under uncertainty particularly difficult in the absence of a consistent drift toward equilibrium. We thank you for giving us the opportunity to discuss this phenomenon, we will be sure to include a version of the above discussion in our revision.\n\n---\n> The bounds are clean and intuitive, but it is unclear whether they are conservative or sharp in practice. Do the empirical examples in the paper or supplementary suggest that these are close to optimal?\n\nYes, the bounds are tight—showing this was one of the aims of the \"gentle start\" in Section 3.1, but we realize that this might not have been as clear as intended.\n\nTo make this precise, consider the stochastic gradient descent/ascent (SGDA) dynamics of L155 applied to the simple quadratic min-max problem (6b). These dynamics represent an Ornstein-Uhlenbeck process, so they can be solved explicitly to yield the closed-form expression (9), that is,\n$$\nX(t)\n    = X(0) e^{-t}\n    + \\sigma \\int_0^t e^{-(t-s)} \\: dW(s)\n$$\nwhere $W$ is an ordinary Brownian motion. Thanks to this *exact* expression, we are able to derive in Appendix D a likewise *exact* expression for the probability transition kernel of the process, and compute the variance of $X(t)$ in closed form as\n$$\n\\mathbb{E}[X(t)]\n    = \\frac{\\sigma^2}{2} (1 - e^{-2t})\n$$\ncf. Eq. (D.7) in Appendix D. [In fact, $X(t)$ is zero-mean Gaussian with variance given by the above expression]\n\nThis shows that $X(t)$ cannot achieve a radius of concentration sharper than $\\sigma$, an observation which, mutatis mutandis, coincides with the statement and result of Theorem 2 (importantly, all assertions therein can be put in 1-1 correspondence with the respective claims of Proposition 2).\n\nSimilar considerations apply to the bilinear / null-monotone framework; however, because the process here diverges to infinity on average, the comparison is, by necessity, more qualitative in nature.\n\nWe understand that this was not sufficiently clear in the submitted version, so we will make sure to include a version of the above discussion at the first revision opportunity—many thanks for bringing this up.\n\n---\nThank you again for your time and positive evaluation—we remain at your disposal if you have any further questions or remarks, and we are looking forward to further constructive exchanges during the discussion phase!\n\nKind regards,\n\nThe authors"}]

Author rebuttal:

Meta-review: The paper examines the convergence behavior of regularized learning algorithms in continuous games under the randomness and uncertainty in learning vs when there is no uncertainty. They study two versions of games: null-monotone and strongly monotone. In each of these games, they study both continuous-time and discrete-time variants. They find that, in null-monotone games, uncertainty drifts the dynamics from equilibrium, In strongly monotone games, the uncertainty still drifts away but not as much as in the null-monotone games. In particular, the dynamics will end up in a near-equilibrium region whose size scales with the level of uncertainty. 

**Strength**. A well-written paper, novel insights into the dynamic of regularized learning in games under uncertainty -- this is a significant problem that is relevant to both ML theory and practice. Solid and rigorous analysis with good examples and detailed supplemental material.   

**Weaknesses**. No major weaknesses from the reviews, mostly concerned about clarifications. I myself find that the consideration of two special classes of games (null-monotone and strongly monotone) is quite limited and would expect/be curious if the same phenomenon about "recurrence vs concentration" would persist in more general classes of games. However, the authors have done a good job of justifying the applications of the games they consider. 

The paper initially received positive reviews consistently from all the reviewers. After the rebuttal, one reviewer has raised their score to 5, leaving that the paper receives the score of 5 from all reviewers. I enjoy reading the author-reviewer discussion of this paper. The reviewers have provided insightful questions and the authors have explained well with additional contexts that definitely make the paper more accessible to broader audiences. For example, I particularly like the author answers about the structural and regularity assumptions in response to Reviewer kZRL and the response to Reviewer a9Vv about the justification of the assumptions in the considered games. I would encourage the authors to integrate such discussion as much as you can into the revision, even in the appendix, to make the paper more accessible.
Decision: Accept (spotlight)