The impact of uncertainty on regularized learning in games
Authors: Pierre-Louis Cauvin
Davide Legacci
Panayotis Mertikopoulos
Venue: ICML 2025 poster (2025)
Keywords: Follow the regularized leader
uncertainty
Nash equilibrium
Primary area: theory->game_theory
TL;DR: We examine how randomness and uncertainty influence learning in games

Abstract: In this paper, we investigate how randomness and uncertainty influence learning in games. Specifically, we examine a perturbed variant of the dynamics of “follow-the-regularized-leader” (FTRL), where the players’ payoff observations and strategy updates are continually impacted by random shocks. Our findings reveal that, in a fairly precise sense, “uncertainty favors extremes”: in any game, regardless of the noise level, every player’s trajectory of play reaches an arbitrarily small neighborhood of a pure strategy in finite time (which we estimate). Moreover, even if the player does not ultimately settle at this strategy, they return arbitrarily close to some
(possibly different) pure strategy infinitely often. This prompts the question of which sets of pure strategies emerge as robust predictions of learning under uncertainty. We show that (a) the only possible limits of the FTRL dynamics under uncertainty are pure Nash equilibria; and (b) a span of pure strategies is stable and attracting if and only if it is closed under better replies. Finally, we turn to games where the deterministic dynamics are recurrent—such as zero-sum games with interior equilibria—and show that randomness disrupts this behavior, causing the stochastic dynamics to drift toward the boundary on average.

The Impact of Uncertainty on Regularized Learning in Games
Pierre-Louis Cauvin'
Davide Legacci' Panayotis Mertikopoulos
Abstract
observed that, in the presence of uncertainty. "the players of the game may not have full knowledge of [the game's, s structure, the ability and inclination to go through any complex reasoning process to calculate an equilibrium. But the participants are still supposed to adapt by accumulat- ing empirical information on the relative advantages of the various pure strategies at their disposal."
In this paper, investigate how randomness and uncertainty influence learning in games. Specifically, we examine a perturbed variant of the dynamics of "follow-th-reguuaizze--eaaae (FTRL), where the players' payoff observations and strategy updates are continually impacted by random shocks. Our findings reveal that, in fairly precise sense, "uncertainty favors ex- tremes": in any game, regardless of the noise level, every player's trajectory of play reaches an arbitrarily small neighborhood of a pure strat- egy in finite time (which we estimate). Morcover, even if the player does not ultimately settle this strategy, they return arbitrarily close to some (possibly different) pure strategy infinitely often. This prompts the question of which sets of pure strategies emerge as robust predictions of learning under uncertainty. We show that (a) the only pos- sible limits of the FTRL dynamics under uncer- tainty are pure Nash equilibria; and (b) a span of pure strategies is stable and attracting if and only if is closed under better replies. Finally, we turn to games where the deterministic dynamics are sech as zero-sum games with interior cquilibria-and and show that randomness disrupts this behavior, causing the stochastic dynamics to drift toward the boundary on average.
A natural context to study this question is that of no- regret learning algorithms and dynamics- and, in partic- ular, the family of learning dynamics known as "follow-the- rggularizedleader (FTRL). The Icading example of this class the replicator dynamics of Taylor & Jonker [63], the continuous-timg time limit of the exponential/ multiplicative weights (EW) algorithm [4, 5, 40, 64), and central object of study in a rich literature the intersection of learning theory, games, and optimization, ef. the textbook treatments of Hofbauer & Sigmund [25], Weibull [66] and Sandholm [59]. The FTRL dynamics enjoy broad range of appealing properties-from (near-)optima) regret guarantees [33, 62] and convergence to equilibrium in potential games [23, 43), to a version of the folk theorem evolutionary game the- ory [26, 42]-so, together with their many variants and extensions, they have become virtually synonymous with sequential learning in games.
At the same time, many of the most powerful and widely used results of FTRL rely-often implicitly-on having ac- cess to perfect, deterministic information and exact knowl- edge of the players' payoffs. This level of precision is often difficult to justify in real-world decision-makinn making scenarios, whether due to imperfect observations, stochastic fluctua- tions in the players' environment, or intrinsic variabilities in the observed outcomes. In view of this, we ask the question:
Introduction
The surge of breakthrough applications of game theory to machine learning and data srsence-from multi-agent rein- forcement learning to online ad auctions and recommender systems-ha has brought to the forefront the fundamental ques- tion of "as if" rationality: whether selfishly-minded, myopic agents may eventually learn to behave "as if" they were fully rational. This question dates back to Nash [53, p. 21] who
What is the impact of noise, randomness, and uncertainty on the FTRL dynamics?
Our contributions in the context of related work. Our findings can be summarized by a disarmingly simple mantra:
Univ. Grenoble Alpes, CNRS. Inria, Grenoble INP, LIG, 38000 Grenoble, France. Correspondence Louire-Louis Cauvin <pierre-louis.oo www.oo...i..iieeeeee univ aaaaaiinniiii-eeroottaapppp.pss alls.b.-..p............
"Uncertainty favors extremes."
By this, we mean that, irrespective of the structure of the game or the level of noise and uncertainty, the FTRL dy- namies tend favor pure over mixed strategies.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

The Impact of Uncertainty on Regularized Learning in Games
In more detail, our model for noise and uncertainty in the dynamics hinges the introduction of catch-all, mar- tingale noise term, which is flexible enough to capture all sources of observational uncertainty, stochastic distur- bances, and/or any other elements of randomness in the players' learning dynamics. This leads to a stochastic differ- ential equation (SDE) driven by possibly correlated noise, which we refer to as the stochastic FTRL dynamics. Earlier dynamics of this type have been considered by Foster & Young [20] (in the context of the replicator dynamics as model of pairwise proportional imitation). Fudenberg & Harris [21] (in the context of population dynamics), and Mertikopoulos & Moustakas [41] (for learning in games with exponential/ / multiplicatiie weights), with follow-up works by Bravo & Mertikopoulos [13], Cabrales [14], Engel & Piliouras [17], Hofbauer& & Imhof [24), Imhof [28], and many others. We review the relevant literature in Section 3 and Appendix F.
as the "folk theorem" of evolutionary game theory, and it mirrors the deterministic version of [18), and the discrete- time analogue of [22]. Still, it is important to underline that this equivalence fails outright in other stochastic models of learning, indicating that the way that uncertainty enters the process has a critical impact on the dynamics' rationality properties.
Finally, we analyze the impact of uncertainty in cases where the deterministic FTRL dynamics are recurrent- that is, they return infinitely often arbitrarily close to where they started. This class of games includes two-player zero-sum games with a fully mixed equilibrium [48, 55] and, more broadly, the class of harmonic games [1, 15, 34]. In stark contrast to the deterministic case, uncertainty causes the dynamics to drift on average toward the boundary, escaping from any compact set of fully mixed strategies in finite time, and taking infinite time to return to it once outside.
All these results underline the central mantra that "uncer- tainty favors extremes". Specifically, in the presence of ran- domness and uncertainty, players are much more likely to alternate indefinitely- and randomly between their pure strategies instead of staying close a mixed equilibrium. This conclusion has important consequences for predict- ing the outcome of a learning process as it underscores the fragility of mixed equilibria in an unequivocal manner.
Our first main result establishes a universal property of the stochastic FTRL dynamics, marking a clear departure from the noiseless, deterministic regime. To state informally:
In any game, for any noise level, every player reaches an almost pure strategy in finite time.
Even though the dynamics may not settle at this strategy, they will return arbitrarily close to some (possibly differ- ent) pure strategy infinitely often, ultimately leading to the following important consequence:
2 Preliminaries
2.1. Basic definitions from game theory. Throughout our paper, we will work with finite games in normal form. A game of this type consists of the following primitives:
The only possible limits of the stochastic FTRL dynamics are pure Nash equilibria.
1. A finite set of players indexed by i E N = NN..
The contrapositive of this statement is also significant, be-
2. For each player i E N, a finite set of actions or pure strategies strategies-indexed indexed by a; E A = nn).
cause it shows that, unless the underlying game admits a pure Nash equilibrium, the stochastic FTRL dynamics can- not converge. In turn, this prompts the question of which pure strategies are present in sets that are stable and attract- ing under the stochastic FTRL dynamics. As it turns out, there is third universal principle at play here:
3. For each player i E N, an associated payoff function ui: A - R. where A = A, denotes the game's space of action profiles a
A finite game above will be denoted by I' T(N.A. u).
A span of pure strategies is stable and attracting iff it is closed under better replies.
When playing the game, each player i E N may randomize their choice of action by means of a mixed strategy, that is, a probability distribution x; over A,, In terms of notation, we will write Xia, for the probability with which player i e W selects o; E A,, and X; == A(AA) for the strategy space of player i A' (that is, the probability simplex over Aj). will
This echoes earlier results for the replicator dynamics in continuous [56] or discrete time [12], but it otherwise sets the stochastic FTRL dynamics apart from other models of randomness and uncertainty crnitaintt--mmmeyy the stochastic dynam- ies of Foster & Young [20) and Fudenberg & Harris [21] which do not satisfy this principle. In particular, it encom- passes as a special case the following equivalence: a state is stochastically asymptotically stable if and only if it is a strict Nash equilibrium. This principle sometimes referred to
Also, in a slight but useful abuse of notation, identify E A, with the mixed strategy that assigns all probability weight to a; thus justifying the terminology "pure strategies" for the elements of A;.
Moving forward, we will write x = (xI,....XN) for the players' mixed strategy profile and X = 1I. X, for the
2

---

The Impact of Uncertainty on Regularized Learning in Games
game's strategy space. We will also employ the standard game-theoretic shorthand (xg (x .N)) for the strategy profile where player i plays xj E X against the mixed strategy X-1 E je 2 of all other players. Ac- cordingly, the associated mixed payoff of player i e N in the mixed strategy profile x E X is given by
in continuous time, the (external) regret of player e W relative trajectory of play x(1), (0) is defined as
[
((((ppxxx(()) -u;((())) di (5)
Reg, (T) max PieA;
and we say that the player has no regret under x(1) if (7g,(7) o(T) as T co.
(x) == Ea-x [a))) = EMEA x
(1)
The most widely used method to attain no regret is the family of policies known as heglloo--he--ggdariiee--edddd (FTRL) [42, 60, 61]. The main idea behind FTRL is that, at all times r 2 0, each player i N plays a "regularized" best response to their cumulative payoff vector up to time thus leading to the dynamics
where xa denotes the joint probability of playing a A under X. To distinguish between "strategy-like" and "payoff-like" variables, we will write )/ == R and y = IT, 3/ for the game's "payoff space", in direct analogy with the game's strategy space X' = 11; X,
More concisely, game in normal form can be fully de- scribed by its payoff field v(x) (Dx()))rEN where
in (x(())
x
(1)
(FTLL)
aggregate payofl's
strategy update
(x(x) =
= (x,)((x)
(2)
where
denotes the mixed payoff vector of player E N,, that is, the vector of payoffs to pure strategies of player against the mixed strategy profile x-; of i's opponents. The game's mixed payoffs may then be recovered from (2) as
Qi(yi) = arg max
x, x, - x ,x,x))))
(6)
denotes the regularized best response map of player i E W.
In the above, yi E V = R-A: plays the role of an auxiliary "score vector" that encodes the empirical performance of each strategy of player E N over time. As for the func- tion h; that appears in the definition of Qi, it is known as the method's s regularizer, and it aims to "temper" the best- response correspondence y/ H arg maxp, (yi,x)) in a way that incentivizes exploration.
ui (x) = Em.es, (i(axx-)) Xta, = (b;
(3)
so oxx captures all relevant payoff information in the game.
2.2. Nash equilibria. The leading solution concept in game theory is that of Nash equilibrium (NE). Formally, x E X is said to be Nash equilibrium if it is unilaterally stable in the sense that
The precise assumptions for h; in the literature can be somewhat varied. For our purposes-and to streamline our presentation we will assume that h; decomposes as
" (x') 2 un (xxxx() for all xj X2 N.
(NE)
h₂(x,) =E 0: (x(r))))
Writing supp(x;) = {az E Ar Mxa, > 0} for the support of
for some smooth kernel function 0₁: (0, 1) R such that lim (x(²) = -oo and inf, ( (z) > O (so 6, is strongly convex and steep at 0). Finally, to simplify some expressions in the sequel, we will assume that (z) < 0 for all z e (0, 1); however, we stress that this assumption is only made to render some expressions more transparent, and it does not affect the gist of our results.
xy, it follows xh is a Nash equilibrium if and only
(,(axx1)) 2 u, (B;x"),,
(4)
for all a, supp(x;)) and all B, Aj. In turn, this character- ization leads to the following taxonomy for Nash equilibria:
1. x² is called strict if inequality (4) is strict for all Bi # a;-
For concreteness, we present below two prime examples of (FTRL).
2. x² is called pure if supp(x") is a singleton.
Example 1 (Entropic regularization). The go-to setup for (FTRL) is the entropic kernel 0,(z) = =zlogz. z. By standard results, (6) yields the so-called logit choice map
3. Ifx" is not pure, we say that is mixed; and if supp(x*)= =
A, we say that x" is fully mixed.
We will revisit this classification several times in the sequel.
A1 == (exp()ia))aFAA) Ea.eA. exp(yian)
(8)
2.3. Regret and regularized learning. A fundamental requirement in online learning is the minimization of the player's ' regret, i.e., the aggregate payoff difference between a player's chosen strategy over time and the best fixed strat- egy in hindsight. Formally, assuming that play evolves
and the resulting instance of (FTRL) is known as the ex- ponential or multiplicative-wette
algorithm, cf. [3- 5, 40, 64] and references therein. By another standard cal- culation, the evolution of x(1) under (FTRL) follows the
3

---

The Impact of Uncertainty on Regularized Learning in Games
replicator dynamies of Taylor & Jonker [63], viz.
RAi of player i Nr so (S-FTRL) itself represents ordi- nary (It)) stochastic differential equation. In this regard, (1 plays the role of catch-all, "colored noise" term intended to capture all sources of observational uncertainty, stochastic disturbances, and/or any other elements of ran- domness in the players' learning model.
aia; Kia, [Fta, (x) (x)]
(RD)
This is one of the most widely studied models for learning in games, and it will play major role in analysis. $
Example 2 (Log-barrier regularization). Another standard example is the log-barrier kernel (,(2) = -logz. z. In this case, direct derivation (which we omit) yields the affine scaling dynamics
More concretely, by the martingale representation theorem [54, Theorem 4.3.4], M,(1) can be written as dM (² d(((r) where W(r) = (W2(f) is m- dimensional Brownian motion and A:(() is a matrix-valued process in R" Our only assumption here will be that the diffusion matrices A, are state-dependent, that is, they only depend on time through (()) as (, = (X())) for some Lipschitz function o;: X' - R On that account, (S-FTRL) can be expressed in components as
( (AS)
aia; = xi0 Uio
x ui 1xxil1 B.S.A.
Σ
These dynamics have long and celebrated history in op- timization going back to the interior-point algorithms of Dikin [16] and Karmarkar [30, 31]; for a series of recent applications to online learning and aumet bandit prob- lems, see [65] and references therein.
dYia, (t) Via, (X(1) di
Ftank (X(t) (W&(1) (11)
$
or, more compactly, as
Going back to the general case, Kwon & Mertikopoulos [33] showed that (FTRL) enjoys the constant regret bound
dY(() =(X(t) dt + (X(I)) dw(()
(12)
Reg, (T) S max h1 - min /t
(9)
where we set (o). T Ruxm for the overarch- ing diffusion matrix of the process. This system will serve as our main model for learning in the presence of uncertainty, so some remarks are in order.
This guarantee justifies the popularity of (FTRL) as a no- regret policy and, in view of this, it will be our dynamics of choice for the sequel.
The first concerns the structure of the diffusion matrices oi which, in their simplest, diagonal form, yield the system
3 The stochastic FTRL dynamics
dYia, (1) = ota; (X(1) di Jia (X(1) dWia; (1)
(13)
The dynamics (FTRL) have been studied extensively in the literature, but their applicability to real-world decision- making is constrained by the fact that they explicitly rely on perfect, deterministic information and exact knowledge of the players' payoff's. This level of precision is often difficult to attain in practice, whether due to imperfect observations, stochastic fluctuations in the players' environment, or intrin- sic variabilities in the observed outcomes. To address this limitation, we provide below a stochastic version of (FTRL) which explicitly incorporates the effects of randomness and uncertainty, leading in this way to a more robust and realistic model for learning under noisy, uncertain conditions.
where each Wia, (t), aj E A, i E N, is Brownian motion in R, assumed independent across all a; E A, and all i e M. This uncorrelated model of uncertainty was first considered by Bravo Mertikopoulos [13] and it can be derived as special case of our general framework by taking M; (oiai ) in (S-FTRL); see also [44, 45].
From modeling standpoint, while relevant in a wide range of applications, the uncorrelated model (13) overlooks im- portant cases where the players' payoffs are influenced by a common source of randomness - for example, the out- come of the coin toss in Matching Pennies, or the choice of routing path in congestion game (where the delays along overlapping routes are inherently correlated over their com- mon edges), etc. Capturing such scenarios requires the full extent of our framework, so we will work throughout with general diffusion matrices, and we will only zoom in on the uncorrelated case when it helps make some quantitative estimates more transparent and easier to state.
3.1. Learning under uncertainty.
To put all this on solid footing, we will consider the stochastic FTRL dynam- ics
dy;(1) 0, (X(I) di + dM,(1)
(S-FTRL)
X1(1) = (,))).)
which should be seen as rigorous formulation of the infor- mal model
ii (1) = 0; (x())) + "noise".
(10)
For the requisite background to stochastic differential equa- tions and stochastic analysis, we refer the reader to Øksendal [54]. Formallyy W(t), Ar) and (t) all assumed to be adapted to some common, underlying filtration F. = (Fi)r2--
In more detail, (1), 1 2 O, denotes a continuous square- integrable martingale with values in the payoff space )) =
4

---

The Impact of Uncertainty on Regularized Learning in Games
Finally, from technical perspective, we should note that the stated assumptions guarantee that the system (S-FTRL) is well-posed, that is, for any initial condition Y(0) V, it admits unique strong solution that exists for all time. We state and prove this result formally in Appendix C using the property that the players' regularized best response maps Q: Vi- - X; are Lipschitz continuous.
We thus obtain the stochastic replicator dynamics of expo- nential weights
dXia; Xiar Ula: EpiES
XIp: uipi ds
+ Xiar
Tian dWien
E
Tipi Xip, dWisi
BrA,
3.2. Strategy dynamics and other stochastic models. Before moving forward with our analysis, we proceed to de- scribe the exact way which the players' strategies evolve over time under (S-FTRL). The relevant result is as follows: Proposition 1. The solutions of (S-FTRL) satisfy the stochastic differential equation
+
Xiai 2
iin
(1 11Xix))
Σ
i8. Xip, (1 2Xip, dr.
B.E.A,
(SRD-EW)
These dynamics were first studied by Mertikopoulos & Moustakas [41] and they should be contrasted to the bi- ological model of the stochastic replicator dynamics with aggregate shocks of Fudenberg & Harris [21], viz.
dXia. = gia: Via:
Uip dt BEEA,
Σ
(14a)
dXia: = Xian
Via
Σ
Xip, ViBe dt
BEEAA
gion
dMian
E BrE
Xip, dMip.
(14b)
+
Xia
Ola, dWia
E
o OIB
dWiB
m
BiEA,
Σ
Winn
Vi
Σ
Xip Sip.Wipp iBik dt (14c)
gim
k=1
BiCAA
- Xia of
Xia
Xia:
Σ BLE.A
(B,
iB,
dr.
where we set gio;
1/6| (Xias), Xiar giarl EpicA: giß.
(SRD-AS)
and Win.k - 200= Pia, [Fiakk Ep XiB, Tipik
Finally. third related model is the stochastic replicator
dynamics of pairwise imitation of Foster & Young [20]:
The proof of Proposition is an arduous combination of Itô's lemma with elements of convex analysis in the spirit of [13), so we defer it to Appendix C. From a conceptual viewpoint, what is worth noting is that, despite the complicated form of (14), each term admits relatively simple interpretation:
dXia
Xiao
Vian
Uipi dt PLE
1. The term (14a) represents the evolution of the players' strategies under (FTRL), i.e., the noiseless regime o O.
Xia
Dia
FiandWin
Tip Xip, dWiss
B.E.A.
(SRD-PI)
2. The martingale term (14b) captures the direct impact of the noise on the evolution of X() under (S-FTRL).
The origins of the latter two models are quite distinct from (S-FTRL), and they do not stem from learning consider- ations: (SRD-AS) was originally derived as biological model of population evolution under "aggregate shocks" to the population's 's reproductive fitness, while (SRD-PI) based on economic microfoundations involving revision protocols in population games [46). These models only co- incide in the noiseless, deterministic regime; otherwise, in the presence of noise and uncertainty, the drift is distinct (because of the Itô correction). and as we show in the next section, this leads to drastically different behaviors in the long-run.
3. Finally, the term (14c) represents the second-order Itô correction that propagated to X()) through the players' regularized best response maps 2; 3/; - X. This term also vanishes when o but, in contrast to the martin- gale term (14b), it directly affects the drift of (14) and induces a measurable bias component in the dynamics.
To facilitate the comparison of these dynamics with other models in the literature, we will specialize to the replicator dynamics induced by the entropic setup of Example with uncorrelated noise of the form (13). Here, a straightforward computation gives
4 Analysis and results
gia, Xio; Xio
(15)
We now proceed to state our main results for the stochas- tic dynamics (S-FTRL), To fix notation, we will assume throughout that (S- (S-FTRL) is initialized at some fixed x X, (16) and we will write P, and E, for the law of the process start- ing at X(0) <- x and the induced expectation thereof. Also,
and, in a slight abuse of notation
1
2 = Dia. Σ
Xip, Tipi
B.AAi
5

---

The Impact of Uncertainty on Regularized Learning in Games
Motching Peunies
Entry Deterrance
Twisted Matching Pennies
A Harmonic Game
(.--11
0L-1x
Figure 1: Trajectories of play under (FTRL) and (S-FTRL) in four different games (each game's 's payoff's are reported on the corresponding plot). Deterministic orbits are plotted in red, stochastic trajectories in shades of blue, with darker hues indicating later points in time. In all cases, the trajectories of (S-FTRL) drift toward the boundary, even when the corresponding deterministic orbits of (FTRL) do not.
to quantify the level of noise and uncertainty in (S-FTRL), we will consider the metrics
Theorem Suppose Assumptions I and 2 hold, fix a sufficiently small accuracy threshold > 0, and let
of
i.min == min min (2)(x) xEX
min = min min (I(x)
xEX
TG = =inffr 2 20: maaa Xia, (1) 1 (19)
T.max = max Amax (E)())
o max
max Amax (E(x))
XEX
xxX
denote the time player i N takes to reach an E-neigh- borhood of one of their pure strategies. Then Tie finite with probability 1, and we have
(17)
where Σ = 0F and Σ = oo are the quadratic covaria- tion matrices of the noise in (S-FTRL), and Amin (resp. Amxx) denote the minimum (resp. maximum) eigenvalues thereof.
Ex e212
(20)
To state our results, we will require the assumptions below: Assumption 1. The noise in (S-FTRL) has on > 0. Assumption 2. The kernel functions 0 enjoy the bound supo (+))((0) < 0o for all N. (18)
where A is a positive constant that scales as
1 o
i.max
A +
6
(21)
o i,min
Finally, for some- but not all-of our results, we will re- quire the following boundedness assumption:
We stress here that (i) Theorem 1 applies any game; and (ii) the behavior described in the theorem is intimately tied to the stochastic nature of (S-FTRL). Indeed, in the noise- less, deterministic regime, the assertion of Theorem is patently false: for example, in the 2 x 2 game of Matching Pennies, it is well known that the deterministic replicator dynamics- andi more generally, (FTRL) eycle periodi- cally constant distance from the game's unique Nash equilibrium [48, 55], so the conclusion of Theorem I does not hold in this case (ef. Fig. 1).
Assumption 3. The kernel functions 0, are bounded, i.e., sup) for all i A.
Of the above, Assumption I simply serves as "certificate of uncertainty" that differentiates the stochastic dynamics (S-FTRI.) from their deterministic counterpart (the case o= 0). As for Assumption 2, this is a technical requirement which is satisfied by all standard regularizers used in practice (negentropy. Tsallis, bog-berier, etc.), so it is also very mild. Finally, Assumption 3 also technical in nature, and it is used to facilitate certain bounds in the sequel; of all the examples mentioned so far, only the log-barrier kernel is excluded by this requirement.
From a technical standpoint, the proof of Theorem hinges on crafting a suitable Lyapunov function in the spirit of Imhof [28), and then bounding the action of the infinitesi- mal generator of the strategy dynamics (14) on said func- tion in order apply Dynkin's formula on T, These estimates and the resulting calculations are fairly delicate and involved, so we defer all relevant details to Appendix D.
4.1. Playing almost pure strategies infinitely often. Our first result for (S-FTRL) indicates radical departure from the deterministic setting: it shows that, in any game, regard- less of initialization, every player reaches an arbitrarily small neighborhood of one of their pure strategies in finite time.
From more high-level, conceptual viewpoint, Theorem I shows that, in a fairly precise sense, uncertainty favors pure strategies. This is further reinforced by the following conse- quences of Theorem 1:
6

---

The Impact of Uncertainty on Regularized Learning in Games
Corollary 1. Suppose that Assumptions I and hold. Then, for every player N, the limit set of X1(1) contains a pure strategy with probability 1: specifically, there exists a (possibly random) sequence of times in / oo such that Xz(In) converges to some pure strategy 0; E Ai.
With this in mind, let B = II B,, B, S A₁, be the set of pure strategies contained in some stable attractor of (S-FTRL), and let S = IT, A(B;) denote the span of B, i... the smallest face of X' that contains all strategies in B. We then ask:
When is S stochastically asymptotically stable under (S (S-FTRL)?
Intuitively, under (S-FTRL), (1) reaches a neighborhood of some pure strategy in finite time. Even if (1) does not settle there, the strong Markov property of X(1) and repeated application of Theorem 1 shows that (t) ap- proaches some other pure strategy, and so on ad infinitum, which ultimately yields the stated result. In fact, arguing in a similar way, we have the following guarantee:
As it turns out, this question admits a remarkably simple and compelling answer that hinges on criterion of strategic stability known closedness under better replies. To make this precise, following Ritzberger & Weibull [56], the set of better replies to x E 2' is defined as
Corollary 2. Suppose Assumptions and 2 hold. Then, with probability 1, there exists a (random) sequence In / such that (t,,) converges to the boundary bd(X) of X.
(x)(x) = {q E X :u 2 (;(x) for all e eV (24)
and S is closed under better replies (club) if btr(S) S S. We then have the following striking equivalence:
As in the case of Theorem 1, this assertion is demonstrably false in a deterministic context: focusing again on Matching Pennics, periodicity implies that the orbits of (FTRL) are bounded away from the boundary of X, so the conclusion of Corollary is false in this case. In fact, putting everything together, we obtain much stronger characterization of the possible limits of the players' learning process:
Theorem 2. Suppose Assumption holds. Then, with notation as above, S stochastically asymptotically stable under (S-FTRL) if and only if is closed under better replies. this is so, there exists an open initial- ization domain Uo X such that, whenever X(O) e Udo. we have with arbitrarity high probability
Corollary 3. Suppose Assumptions I and 2 hold. If
disti (X(1). s 0cc1- 00c1--22- c22t + o (Fmanx V log log
(25)
(lim, X(1) ; >
(22)
where Ci and C2 are constants (c2 > 0), and the rate function +b is given by (02) max (0,) (Z))
then & must be pure; in words, the only possible limits of (S-FTRL) are pure strategies.
Theorem 2 provides sharp characterization of which spans of pure strategies are stable attractors of regularized learning, and how fast the dynamics converge to such sets. In this re- gard, Theorem 2 echoes (i) a classical finding by Ritzberger & Weibull [56] for (RD) in a deterministic, noiseless con- text;² and (ii) more recent result by Boone & Mertikopou- los [12] for range of regularized learning algorithms in discrete time.4 4
A revealing illustration of Corollary 3 is the Entry Deter- rence game in Fig. I: in the deterministic case, around half of the initializations of (FTRL) converge to non-pure states; however, under the slightest degree of uncertainty, convergence non-pure profiles is no longer possible.
All this prompts the following important questions:
1. Are all pure strategies valid candidates for convergence?
In this regard, Theorem 2 might appear unsurprising, but this is not so. The stochastic dynamics (SRD-AS) and (SRD-PI) are also stochastic variants of (RD), but Theorem 2 is false in both cases: in the former because any pure strategy may be stochastically asymptotically stable depending on the profile of the noise [24, 28]; in the latter because, in any game, all pure strategies are stochastically asymptotically stable for high enough noise [46]. This disconnect has to do with the Itô correction term that appears in the dynamics:
2. More generally, which pure strategies are present in sets that are stable and attracting under (S-FTRL)?
We devote the rest of this section to these two questions; all relevant proofs are deferred to Appendix D.
4.2. The support of stable attractors. We begin with the second question, which is more general. To that end, we first need define the notion of "stable and attracting":
Definition 1. A subset S C X' is said to be stochastically asymptotically stable under (S-FTRL) if, for every tolerance level 8 >0 0 and every neighborhood 24 of S. there exists a neighborhood Uo of S such that X0) = x E Uo implies
IImprrtattly Theorem 2 also covers the deterministic case 0; we are not aware of another source for this result in the literature.
*We note here in passing that there is technical gap in the proof of [12] regarding stochastic asymptotic stability (and. more precisely, on establishing convergence for neighborhood of initial conditions). We detail the issue in Appendix
Px (x() e l/ for all / 2 0 and X() - s) 2 1 8 (23)
7

---

The Impact of Uncertainty on Regularized Learning in Games
in the case of (14), this term is "just right" so, even though unccrtainty draws the dynamics toward the boundary, there is sufficient information remaining to identify the rationally admissible parts thereof.
infinitely often arbitrarily close to their starting point. In this last section, our aim is to understand this disparity in greater depth, by zooming in on the behavior of (S-FTRL) in cases where the deterministic dynamics are Poincaré recurrent.
Our proof strategy involves working directly with the score variables y(r), and hinges on establishing a sort of local "domination" result for those strategies that are not sup- ported in S versus those that are. This has to be established in neighborhood of S, and doing this requires Assump- tion 3 in order to establish lower and upper bounds for the distance from S relative to the ensuing score differences. This also requires using a different set of energy functions associated to S, a step which in turn involves several fairly technical estimates. To streamline our presentation, we defer all relevant details to Appendix D.2.
To provide some context, Poincaré recurrence was first estab- lished for (RD) in two-player zero-sum games with a fully mixed Nash equilibrium [55]. This result was subsequently extended to all FTRL dynamics, always for zero-sum games with fully mixed Nash equilibrium [48], and finally, in very recent paper [34], to much more general class of games known as harmonic games [15]. This is the widest class of games known to exhibit recurrent behavior under (FTRL), and they can be characterized as follows (cf. Propo- sition E. in Appendix E): a game is harmonic whenever it admits a collection of positive weights mi > 0, E N, and a fully mixed strategy profile q E rriX- the game's ' harmonic center such that
4.3. Nash equilibria and convergence. We now turn to our first question, namely the characterization of the possi- ble limits of (S- (TRL..... Our main result here is as follows:
Σ m,(1;(().x; qi) =0 for all e X. (26) IEN
Theorem 3. Suppose Assumptions 1-3 hold. Then: 1. x' E X' is stochastically asymptotically stable under (S-FTRL) if and only if it is a strict equilibrium.
A key property of harmonic games is that (FTRL) admits a constant of motion given by the expression
2. If -2 X(t) = x²) > O, then x* is pure Nash equilibrium; in words, the only possible limits of (S-FTRL) are pure Nash equilibria.
H(x) = mi m; milqqi.xx)
(27)
where Di(qi.xi) = h;(q:)) (x1))))-((x)--V((((aa)) -x) is the so-called Bregman divergence of the regularizer of player i E N. To streamline our presentation, we defer a detailed presentation of Bregman divergences to Appendix A; for our purposes, it suffices to keep mind that D; can be seen as an asymmetric measure of distance between qi and xj, with xi(q.x) = 0 if and only if x; qi. and Di(q - oo whenever - bd(X)) As was shown in [34], the energy H(x(I) of an orbit x() of (FTRL) remains constant, so the trajectories of (FTRL) in harmonic games are contained away from the boundary (2)) of X, cf. Fig. I.
Since a pure profile is closed under better replies if and only if it is strict Nash equilibrium, the first part of Theorem 3 is an immediate corollary of Theorem 2. Importantly, as was shown in [18], a similar conclusion holds under the noiseless dynamics (FTRL)-see also [22] for discrete- time analogue. On that account, the more interesting part of Theorem 3 is the second one, which represents a drastic departure from the deterministic regime: it complements Corollary 3 in essential way, showing that the possible limits of (S-FTRL) are not just pure strategies, but pure Nash equilibria. In other words:
By contrast, the behavior of (S-FTRL) in harmonic games is drastically different, even with the least amount of noise:
If a game does not admit a pure Nash equilibrium, the dynamics (S-FTRL) do not converge.
Theorem 4. Suppose Assumption I holds. Then, in any harmonic game, we have lim, ooo [[H(((())] Moreover, the time TM- == inf 2 0: H(X(r)) > M) that X(t) takes to reach energy level M > 0 is finite with probability 1 and bounded in expectation as
co.
This assertion is unique to the stochastic setting and it offers a vivid demonstration of how "uncertainty favors extremes".
M (x(())
5 Consequences for recurrent dynamics
Ex[TM] $2
(28)
σ² s(M)
The results of the previous section show that, in the pres- ence of noise, the dynamics of regularized learning tend to drift toward the boundary. This behavior comes into stark contrast with the deterministic regime where, in several classes of games, the dynamics of (FTRL) are known to be Poincaré recurrent - that is, almost all trajectories return
where e(M) = min m; tr(Jac Q(y))
x;
@i(y.) H(x) s M) is positive constant.
In particular, if applied to the entropic regularization setup of Example 1, Theorem 4 yields the following estimate.
8

---

The Impact of Uncertainty on Regularized Learning in Games
Corollary 4. Under (SRD-EW), we have:
In words, this shows that (S-FTRL) is irreducible in har- monic games: even though orbits tend to drift toward the boundary in average, they do not collapse to any proper face thereof, so any stable attractor must span the entire strategy space of the game (cf. Fig. 1).
Ex[TM] s MMdM/ (Adrminn) for some 2 O.
(29)
Theorem 4 shows that (S-FTRL) exhibits markedly differ- ent behavior than its deterministic counterpart in harmonic games (and hence, in two-player zero-sum games with a fully mixed equilibrium): In the presence of noise, the en- ergy (x) diverges to infinity on average, indicating in this way mean drift towards the boundary (d) of X.
We should also stress here that the trajectories of (S-FTRL) do not necessarily converge to the boundary with probability I; instead, they resemble standard Brownian motion in this regard. This behavior stands in sharp contrast to (SRD-AS) and (SRD-PI) in zero-sum games, where orbits typically converge to the boundary with a nonzero drift, even under small perturbations [17, 24]. A detailed comparison of the dynamics' long-run behavior is provided in Appendix F.
From a technical standpoint, this involves using Dynkin's 's lemma on the energy function H(x). More precisely, even though (x) is a constant of motion in the deterministic case, its Itô correction under (S-FTRL) leads to a con- stant positive drift, which only vanishes at the boundary of the game's s strategy space. This implies that the limit lim, H[ (X())) exists, and the rest of the proof follows by contradiction argument in case this limit is assumed finite (this is where Dynkin's 's lemma and the infinitesimal generator of the process are evoked).
6 Concluding remarks
Our aim in this paper to quantify the impact of noise and uncertainty on the dynamics of regularized learning. Our findings can be summarized by the informal mantra that "uncertainty favors extremes", in the sense that the dynamics exhibit a tendency to drift toward the boundary of the play- ers' strategy space: (a) every player reaches an almost pure strategy in finite time; (b) every player's 's limit set contains a pure strategy; (c) the only possible limits of the dynamics are pure Nash equilibria; and (d) game dynamics that are re- current in the noiseless regime escape in expectation toward the boundary under uncertainty. We conjecture that there is an even stronger principle at play, namely that the only stochastically asymptotically stable limit sets of (S-FTRL) are entirely contained on the boundary of the game' 's strategy space; we pose this as open problem for the community.
Moving forward, we should stress that Theorem 4 does not necessarily mean that the orbits of (S-FTRL) converge to the boundary with probability 1. Nonetheless, we show below, (S-FTRL) reaches any neighborhood of the boundary in finite time on average, and takes infinite time to escape.
Theorem 5. Suppose Assumption I holds, let K. be compact subset of X. and let Tę- = inf(t 2 0: X(t) E KCY be the time it takes X(1) to escape IC starting at E K. Then, for any harmonic game, we have:
[x[x<] < co whenever K is disjoint from bd(X).
Several important directions remain open in the general context of stochastic FTRL dynamics. The first is what happens the dynamics are run with a vanishing learning rate, as in [13]. In this case, we conjecture that an ana- logue of Theorem continues hold, but Theorem 4 fails: in games where the deterministic dynamics are recurrent (e.g., harmonic games), (S-FTRL) will most likely result in the sequence of play converging to some constant (Breg- man) distance from a "central" cquilibrium of the game (the game's 's strategic center in the case of harmonic games).
2. [x[Tx] = co whenever IC contains bd(X)).
While Theorem 5 states that the average return time to K. is infinite, individual trajectories of (S-FTRL) may still reach it in finite time on positive probability event. This distinction, based on return times to compact subsets, is known as the transience/recurrence dichotomy and, in this context, Theorem implies that (S-FTRL) not positive recurrent for detailed discussion, cf. Appendix B.
The proof of Theorem 5, like that of Theorem 4, hinges an application of Dynkin's 's lemma to the energy function Hut)-but this time, we require its bona fide, stopping time version. This involves lower- and upper-bounding the action of the generator of X(1) on (xx,, and then integrating the result; we defer the relevant details to Appendix E.
Another major extension of our work involves examining the impact of uncertainty in games with continuous ac- tion spaces-which, arguably, are more relevant for many applications of game theory to data science and machine learning-aae also, undertaking a discrete-time analysis that goes beyond the vanishing step-size considerations that are common in the stochastic approximation literature ap- plied to learning in games [6, 8-10, 27, 37, 38, 47, 50). Both of these directions would require significantly different tools and techniques (especially in the discrete-time setting), so we defer all this to the future.
In view of all this, it is natural to ask if at least some pure strategies are attracting. This is not the case:
Theorem 6. Suppose Assumption 3 holds. If the game is harmonic, there is no proper face S of X that is stochasti- cally asymptotically stable under (S-F.....
9

---

December The Impact of Uncertainty on Regularized Learning in Games
Acknowledgments
of invariant measures for multidimensional diffusions. The Annals of Probability, 6:541-553, 1978.
This research was supported in part by the French Na- tional Research Agency (ANR) in the framework of the
[12] Boone, V. and Mertikopoulos, P. The equivalence of dynamic and strategic stability under regularized learning in games. In NeurlPS '23: Proceedings of the 37th International Con- ference on Neural Information Processing Systems, 2023.
PEPR IA FOUNDRY project LANR-23-PEIA-ONE "Investissements d' avvniir" program (ANR- 15-IDEX-02), and the LabEx PERSYVAL (ANR-11-LABX-0025-00 under grant IRGA-SPICE. PM is also a member of the Archimedes Research Unit/Athens RC, and was partially supported by project MIS 5154714 of the National Recov- ery and Resilience Plan Greece 2.0 funded by the European Union under the NexIGenerationEU Program. Program..
the
[13] Bravo, M. and Mertikopoulls, P. On the robustness of learn- ing in games with stochastically perturbed payoff observa- tions. Games and Economic Behavior, 103(nohn Nash Memo- rial issue):41 -6, May 2017.
[14] Cabrales, A. Stochastic replicator dynamics. International Economic Review, 41(2):511 1-1444155511 81, May 2000.
[15] Candogan, O., Menache, I., Ozdaglar, A., and Parrilo, P. A.
Flows and decompositions of games: Harmonic and potential games. Mathematics of Operations Research, 36(3):774-03,, 2011.
Impact Statement
This paper presents work whose goal is to advance the field of Machine learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
[16] Dikin, 1. 1. Iterative solution of problems of linear and quadratic programming. Proceedings of the USSR Academy of Sciences, 174(4)7747-748, 1967.
[17] Engel. M. and Piliouras, G. A stochastic variant of replica- tor dynamics in zero-sum games and its invariant measures. Physica D: Nonlinear Phenomena, 456:133940) 2023.
References
[18] Flokas, L., Vlatakis- Sataaki--Gaarakkunnis, E. V., Lianeas, T., Mer- tikopoulos, P., and Piliouras, G. No-regret learning and mixed Nash equilibria: They do not mix. In NeurlPS '20: Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020.
[1] Abdou, J., Pnevmatikos, N., Scarsini, M., and Venel, X. De- composition of games: Some strategic considerations. Math- ematics of Operations Research, 47()):176-208, February 2022.
[2] Alvarez, F., Bolte, J., and Brahic, O. Hessian Riemannian
[19] Földes, J. and Herzog, D. P. The method of stochastic charac- teristics for linear second-order hypoelliptic equations. Prob- ability Surveys, 20(none); 1 13-169, January 2023.
gradient flows in convex programming. SIAM Journal on Control and Optimization, 43(2):477-501, 2004.
[3] Arora, S., Hazan, E., and Kale, S. The multiplicative weights update method: A meta- algor-ttg and applications. Theory of Computing, 8(1):121-1644 2012.
[20] Foster, D. and Young, H. P. Stochastic evolutionary game dy- namics. Theoretical Population Biology, 38:219-232, 1990.
[21] Fudenherg, D. and Harris, C. Evolutionary dynamics with aggregate shocks. Journal of Economic Theory, 57(2):420- 441, August 1992.
[4] Auer, P.. Cesa-Biance N., Freund, Y., and Schapire, R. E. Gambling in rigged casino: The adversarial multi-armed bandit problem. In Proceedings of the 36th Annual Sympo- sium on Foundations of Computer Science, 1995.
[22] Giannou, A., Vlatakis-Gkarakkoun Gkaragkounis, E. V., and Mertikopou- los, P. Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information. In COLT
[5] Auer, P.. Disa-Bianchi, N., Freund, Y., and Schapire, R. E. The nonstochastic multiarmed bandit problem. SIAM Journal Computing, 32(1):48-77, 2002.
21: Proceedings of the 34th Annual Conference on Learning Theory, 2021.
[23] Héliou, A., Cohen, J., and Mertikopoulos, P. Learning with bandit feedhack in potential games. In NIPS '17: Proceed- ings of the 31st International Conference on Neural Informa- tion Processing Systems, 2017.
[6] Benalm, M. Dynamics of stochastic approximation algo- rithms. In Azéma, J., Émery, M., Ledoux, M., and Yor, M. (eds.), Séminaire de Probabilités XXXIII, volume 1709 of Lecture Notes in Mathematics, pp. 1-68. Springer Berlin Heidelberg, 1999.
[24] Hofbauer, J. and Imhof, L. A. Time averages, recurrence and transience in the stochastic replicator dynamics. The Annals of Applied Probability, 19(4):1377 147--16678 2009.
[7] Benaïm, M. and Hurth, T. Markov Chains on Metric Spaces: A Short Course. Universitext. Springer International Publish- ing, Cham, 2022.
[25] Hofbauer, J. and Sigmund, K. Evolutionary Games and Pop- ulation Dynamics. Cambridge University Press, Cambridge, UK, 1998.
[8] Benaim, M.. Hofbauer. J., and Sorin. S. Stochastic approxi- mations and differential inclusions. SIAM Journal on Control
[26] Hofbauer, J. and Sigmund, K. Evolutionary game dynamics. Bulletin the American Mathematical Society, 40(4):479- 519, July 2003.
and Optimization, 44(1):334)))) (1)22288-3 2005.
[9] Benaîm, M., Hofbauer, J., and Sorin, S. Stochastic approx- imations and differential inclusions, part II: Applications. Mathematics of Operations Research, (14):67736695 2006.
[27] Hsieh, Y.P.P. Mertikopoulos, P., and Cevher, The limits of min- optimization algorithms:: Convergence to spurious non-critical sets. In ICML '21: Proceedings of the 38th International Conference on Machine Learning, 2021.
[10] Benaim, M.. Hofbauer, J.. and Sandholm, W. H. Robust per- manence and impermanence for stochastic replicator dynam- ics. Journal of Biological Dynamics, 2(2): 180-195, April 2008.
[28] Imhof, L. A. The long-run behavior of the stochastic repli- cator dynamics. The Annals of Applied Probability, 15(1B): 1019-1045, 2005.
[11] Bhattacharya, R. N. Criteria for recurrence and existence
10

---

The Impact of Uncertainty on Regularized Learning in Games
[29] Karatzas, I. and Shreve, S. E. Brownian Motion and Stochas- ric Calculus. Springer-Vertee Berlin, 1998.
[47] Mertikopoulos, and Zhou, Z. Learning in games with continuous action sets and unknown payoff functions. Math- ematical Programmingg 173(1-2):465- -577,, January 2019.
[30] Karmarkar, N. A new polynomial-time algorithm for linear programming. Combinatorica, 4(4):373-39) 1984.
[48] Mertikopoulos, P., Papadimitriou, C. H., and Piliouras, G. Cycles in adversarial regularized learning. In SODA 'I8: Proceedings of the 29th annual ACM-SIAM Symposium on Discrete Algorithms. 2018.
[31] Karmarkar, N. Riemannian geometry underlying interior point methods for linear programming. In Mathematical Developments Arising from Linear Programming, number 114 in Contemporary Mathematics, American Mathematical Society, 1990.
[49] Mertikopoulos, P., Lecouat, B., Zenati, H., Foo, C.-S,, Chan- drasekhar, 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.
[32] Khasminskii, R. Z. Stochastic Stability of Differential Equa- tions. Number 66 in Stochastic Modelling and Applied Prob- ability. Springer- Verlag, Berlin, 2 edition, 2012.
[50] Mcrtikopoulos, P., Hsich, Y-P.,, and Cevher, V. A unified stochastic approximation framework for learning in games. Mathematical Programming, 203:559 609, January 2024, [51] Michel, D. and Pardoux, F. An introduction to Malliavin Calculus and some of its applications. Recent advances in stochastic calculus (College Park, MD, 1987), pp. 65-104, 1990.
[33] Kwon, J. and Mertikopoulos, P. A continuous-timg timee approach to online optimization. Journal of Dynamics and Games, 4 (2):125-148, April 2017.
[34] Legacci. D., Mertikopoulos, P., Papadimitriou,, C. H.. Pil- iouras, G., and Pradelski, B. S. R. No-regret learning in harmonic games: Extrapolation in the presence of conflicting interests. In NeurlPS 24: Proceedings of the 38th Interna- tional Conference on Neural Information Processing Systems, 2024.
[52] Monderer, D. and Shapley, L. Potential games. Games and Economic Behavior, 14(1):124 143, 1996.
[35] Legacci, D., Mertikopoulos, P., and Pradelski, B. S. R. A geometric decomposition of finite games: Convergence vs. recurrence under exponential weights. In ICML. '2:: Pro- ceedings of the 41st International Conference on Machine Learning, 2024.
[53] Nash, J. F. Non-cooperative gumes. PhD thesis, Princeton University, 1950.
[54] Øksendal. B. Stochastic Differential Equations. Springer-
Verlag, Berlin, edition, 2013.
[55] Piliouras, G. and Shamma, J. S. Optimization despite chaos: Convex relaxations to complex limit sets via Poincaré re- currence. In SODA '14: Proceedings of the 25th annual ACM-SIAM Symposium on Discrete Algorithmss 2014.
[36] Lépingle, D. Sur le comportement asymptotique des martin- gales locales. Séminaire de probabilités de Strasbourg, 12:
148-161, 1978.
[37] Leslie, D. S. Reinforcement Learning in Games. PhD thesis, University of Bristol, 2004.
[56] Ritzberger. K. and Weibull, J. W. Evolutionary selection in normal-form games, Econometrica, 63(6): Novem- ber 1995.
[38] Leslie, D. S. and Collins, E. J. Individual Q-learning in nor- mal form games. SIAM Journud on Control and Optimization, 44(2):495-5)) 514, 2005.
[57] Rockafellar, R. T. Convex Analysis. Princeton University Press, Princeton, NI, 1970.
[39] Liptser, R. strong law of large numbers for local martin- gales. Stochastics, 6(1-4):217-22) January 1980.
[58] Rockafellar, R. T. and Wets, R. J. B. Variational Analy- sis, volume 317 of A Series of Comprehensive Studies in Mathematics. Springer-Verlag, Berlin, 1998.
[40] Littlestone, N. and Warmuth, M. K. The weighted majority algorithm. Information and Computation, 108(2):112-61,
[59] Sandholm, W. H. Population Games and Evolutionary Dy- namics. MIT Press, Cambridge, MA, 2010.
1994.
[41] Mertikopoulos. P. and Moustakas, A. L. The emergence of rational hehavior in the presence of stochastic perturhations.
[60] Shalev-Shwarz,, S. Online learning and online convex opti- mization. Foundations and Trends in Machine Learning, 4 (2):177-194, 2011.
The Annals of Applied Probobiliry, 20(4): 1669-):3591133 July
2010.
[61]
S. and Singer, Y. A primal-dual perspective of online Ieamning algorithms. Journal of Machine Learning Research, (9(2))115-11 2007.
[42] Mertikopoulos, P. and Sandholm, W. H. Learning in games via reinforcement and regularization. Mathematics of Opera- tions Research, 41(4): 1324, November 2016.
[62] Sorin, S. Exponential weight algorithm in continuous time. Mathematical Programming. 116(1):513- -288, 2009.
[43] Mertikopoulos, P. and Sandholm, H. Riemannian game dynamics. Journal of Economic Theory, 177:315-364,
[63] Taylor, P. D. and Jonker, B. Evolutionary stable strategics and game dynamics. Mathematical Biosciences, 40(1-2): 145-156, 1978.
September 2018
[44] Mertikopoulos, P. and Staudigl, M. On the convergence of gradient-like flows with noisy gradient input. SIAM Journal on Optimization, 28(1):163-119) 19 January 2018.
[64] Vovk, V. G. Aggregating strategies. In COLT '90: Proceed- ings of the 3rd Workshop on Computational Learning Theory,
pp. 371-383, 1990.
[45] Mertikopoulos, P. and Staudigl, M. Stochastic mirror descent dynamics and their convergence in monotone variational in- equalities. Journal of Optimization Theory and Applications, 179(3):838-86, December 2018.
[65] Wei, C.-Y. and Luo, More adaptive algorithms for adver- sarial bandits. In COLT '18: Proceedings of the 31st Annual Conference on Learning Theory, 2018.
[46] Mertikopoulos, P. and Viossat, Y. Imitation dynamics with payoff shocks. International Journal of Game Theory, 45 (1-2):2913320, March 2016.
[66] Weibull, J. W. Evolutionary Game Theory. MIT Press, Cambridge, MA, 1995.

---

The Impact of Uncertainty on Regularized Learning in Games
A Basic properties of regularizers, mirror maps, and Bregman/Fenchel divergences
In this appendix, we collect number of standard properties concerning regularizers, their associated mirror maps, and Bregman/Fenchel distances; we closely follow [42, 47] for notation and conventions.
A.1. Preliminary definitions.
Remark. All the constructions described in the following apply to each player of a finite game I I(V. A()); to simplify notation, suppress throughout the player index i E N.
Given a finite game, each player has effectively n - degrees of freedom in the choice of a mixed strategy x E X. due to the constraint a=1 Xa In light of this, we denote the following by V the unite-dimensional vector space RR-1 equipped with the Euclidean norm ||- and denote with slight abuse of notation each player's effective strategy set as X' = {x IR"-1, >0=1 X I); with this convention, X' is closed convex subset of V with non-empty interior. We will furthermore write ) = V" for the dual space of V. (y.x) for the canonical linear pairing between e V and y V", and Ilyll max (y.x) ||x||| = } for the dual norm induced on V
Following standard conventions in convex analysis, functions will take values in the extended real line R U (0o), and a convex function f: - R will be identified with the extended-reallvalueed function f: RU {oo} that agrees with f on X' and identically equal to on V X: we will denote the effective domain of a convex function f: V R U {co} on as dom f (x V: f(x) oo).
For the scope of this work, regularizer on X is convex function of Legendre type on int(x), namely a closed proper convex function h: X' - R u {oo} with the following properties:
(i) int( = ido h);
iii) Steepness h is smooth on int(2),, and (omm)->o//VV(xxa)) - co for any sequence (xn) in int( converging to a boundary point of (2);
(iii) is K-strongly convex on int(A)):
h(p) 2 h(x) + (Vh(x),p-1))
llp x|I
for all E X, int(x).
(A.1)
Following Alvarez al. [2, Proposition 4.10], regularizer of Legendre type can be obtained as
n-1 for all x X
h(x) En=l 0(xx) + 0
1
Σ Xa
(A.2)
where 0: [0, - R u (oo) is convex function of Legendre type, called kernel of the regularizer, fulfilling
(i) ((z) for all z O;
(ii) Steepness 0 is smooth on (0, co), and lim--o- (2) = -00;
(iii) is strongly convex on (0, oo). namely infz>o (2)
A.2. Regularized best response map and Fenchel coupling. In what follows, we will need the following fundamental objects:
1. The convex conjugate h": y - of h:
h' (y) max (v. h(x)} xEă
for all y V.
(A.3)
The regularized best response map or mirror map 1::p-2:30 y X induced by h:
Q = arg (
for all y e y
(A.4)
XEX
3. The associated Bregman distance D: X x int( - R of h:
D(p.x) = h(p) h(x) (Vh(x).p-x)
for all p E X, x int(2).
(A.5)
12

---

The Impact of Uncertainty on Regularized Learning in Games
The Fenchel coupling F: Xxy - of
g(p.y) = h(p) + + - (y.
for all p E X, y E V
(A.6)
Remark. The terminology "Fenchel coupling" is due to [42].
The proposition below provides some basic properties concerning the first two objects above:
Proposition A.1. Let h be regularizer on X. Then:
(a) The convex conjugate h" of is differentiable, and
Q(y) (y) for all E y
(A.7)
(b) V is one-to-one from int(X) to y, and Q = (Vh) namely
= Q(y) y= Vh(x).
(A.8)
for all x E int(X) and y E y.
(c) Q is (1/K)-ipschhttz continuous, that is,
11((y)) - Q (1/K)lly' - yll. for all y.u' V
(A.9)
Proof. Since these fact are relatively well-known, only provide specific pointer the literature.
(a) The equality Q = Vh follows from Danskin's theorem, see e.g., Shalev-Shwartz [60, Section 2.7.2].
(b) See Rockafellar (57, Theorem 26.5).
(c) See Rockafellar Wets [58, Theorem 12.60(b)]
Lemma A.1. The trace of the Jacobian matrix of the mirror map (A.))fulfill
tr Jac Q(y) O for all y y
(A.10)
Proof.
Jac 2y tr Jac [4
by (A.8)
[Jac Vhl @(w)
(A.11)
ir [Hess h1 kl
(A.12)
(A.13)
eig., [Hess h((())))
where eig, HHess h((())) is the a-th eigenvalue the Hessian matrix of h at Q(y). By strong (in particular, strict) convexity of h, Hess h(x) is symmetric an positive-defintt for all x E int(X) im Q, which concludes our proof.
Next, we collect some basic properties of the Fenchel coupling.
Proposition A.2. Let h be regularizer on X. Then, for all X and all y. e V, we have:
(a) F(p.y) 0 with equality if and only if Q(y).
(A.14a)
(b) F(p.y) (p, (()))
(A.14b)
(c) F(p-y) K 1y) p 211
(A.14c)
Proof. (a) By the Senchel-Young inequality, we have h(() + hr(y)) 2 (y.p) for all p E X, y E V, with equality if and only if y = Vh(p), so our claim is immediate by Item (b) in Proposition A.1.
13

---

The Impact of Uncertainty on Regularized Learning in Games
(b) Fix p X' and y e V. and x Q(y): then, by the definition of F, we have
F(p.y) h(p) + h' h'(y) (y.p)
(A.15)
= =h(p) + (y.x) h(x) - ky. p)
% since ((0)
= =h(p) - h(x) (Vh(x),--)
% since y Vh(x)
(c) By the previous point and Eq. (A.1), Eq. (A.14c) follows immediately.
Remark. In view of Proposition A.2, (p,xx can be seen an anti-symmetric measure of divergence between X and X E int X, and F(p.y y) as a "primal-dual" measure of divergence between X and y E ) with F(p,y) - if and only if Q(y) = p. and Fpp.y) - oo whenever (uy) - bd(
B Elements of stochastic analysis
In this appendix, review standard results from stochastic analysis and apply them (S-FTRI) classify the long-term behavior of its trajectories into two mutually exclusive categories: transience and recurrence.
B.1. Infinitesimal generator and the transience/recurrrence dichotomy. time-homogeneous diffusion on R" given by
Throughout this section, let us consider the
dZ(1) b(((t)) di I(Z())dW())
(SDE)
where W(1) an m-dimensional standard Brownian motion, and b: R² R", Σ: R" bounded functions. The infinitesimal generator associated to (SDE) is defined as the differential operator L acting smooth functions f: R² - R through
Rux= Lipschitz continuous
H (2 az:
of (2)
n +
f d2,0z,
Cf(z) = (<)))=b,b))
Σ
aij (z)(z)
(z) for every z e IR".
(B.1)
2 1,/=1
where a(z) Σ(z)E(2) denotes the principal symbol of (SDE). Equivalently, L can also be characterized the only operator such that the stochastic process M() given by
= Mf = f(Z() f(Z(0)) J." Cf(Z(s)) ds
(B.2)
a local martingale for every smooth function f: - R (this follows from an application of Itô's formula). In practise, the representation from Eq. (B.2) is commonly used estimate hitting times through what is often referred as Dynkin's lemma:
Lemma B.1 (Dynkin's lemma [54, Theorem 7.4.1)). For every bounded stopping time and every smooth function f: R
==L] + E. [ C.(Z(s)) ds
(B.3)
Following classical notations, the infinitesimal generator said to be uniformly elliptic if there exists a constant such that u" a(z) c|lu||2 for every u, E R". Intuitively, it means that the noise coefficient matrix is uniformly bounded away from zero or, in other words, that the noise does not vanish across the state space. More precisely, it also implies that every point of the space is explored with positive probability by trajectories of (SDR) (cf. Subsection 3.3.6.1 of [51], albeit in much more general setting), in the sense that
P. (Z(1) = for some 1 2 0) > 0 for every 2, z' Rd
(B.4)
Uniform ellipticity enables a full classification of the long-term behavior of (SDE) into two fundamental classes of processes: recurrent and transient processes. These behaviors are generally defined as follows:
Definition 2. Let (1) be a solution orbit of (SDE).
14

---

The Impact of Uncertainty on Regularized Learning in Games
Z(1) is said to be recurrent a compact subset IC _ R" if the hitting time FK inf 2 0: Z()) e K} is almost-surely finite for some initial condition e R" K. Moreover, if [y[TT]] < co, then the process is further called positive recurrent, while it is called null recurrent if the expectation is infinite.
Z(1) is said to be transient from E R" if it definitely exits every compact subsets in finite time when starting from i.e.
if
P- (there exists to < oo such that Z(1) & K. for every 1 2 fo) =
(B.5)
for every compact subset K. _ R"
Under uniform ellipticity, it can then be shown that recurrence and transience are the only behaviors that may happen in the long-run, and that they are perfect complementaries to one another:
Lemma B.2 (Transience/recurreece dichotomy in R" [11,32]) 32]). Ler (SDE) be a diffusion on R with uniformly elliptic generator. Then,
1. If trajectories of (SDE) are positive recurrent (resp. null recurrent) for some compact subset K S R" and initial condition E R", then they are positive recurrent (resp. null recurrent) for every compact subsets and every initial conditions.
2. If trajectories of (SDE) are transient for some initial condition z E RR,, then they are transient for every initial conditions.
3. Trajectories of (SDE) are either all recurrent or all transient.
Remark The uniform ellipticity condition can be relaxed while preserving the transiencerrecurrence dichotomy and its significant implications. This is typically achieved through the use of Hörmander conditions, which require that a specific family of vector fields spans the entire space. However, these considerations go beyond the scope of this paper, and we instead refer interested readers to [7, 19, 51] for more concrete results on this topic.
B.2. The transience/recurrene dichotomy in X. Instead of the Euclidean diffusion considered in Appendix B.I, we now turn our attention to the more intricate constrained diffusion (S-FTRL), which we recall is given by
dY, (r) (x(()) di + (X) dW(r). X; Q:(Y)).
(FTRL-S)
A natural question that arises is whether a similar dichotomy result Lemma B.2 also holds for the player's choices within the (constrained) polyhedron X. The goal of this subsection is to motivate and establish such result.
One might be tempted to first consider the stochastic differential equation
dY; 02 (()(()))) di or)()(r)) dw(().
(B.6)
which is of the form given in Appendix B.1 with uniformly elliptic generator, and so should verify the transience / recurrence dichotomy. However, even if (r) were itself recurrent (or transient). this would not necessarily imply that ( = (() is also recurrent (or transient). Indeed, the inverse of the choice map Q-1 is generally neither single-valued nor continuous, meaning that a compact subset of X' does not necessarily remain compact in y when mapped through --!
To bypass this issue, we will instead study the dynamics of (S-FTRL) in a third space Z, sometimes referred to as the space of payoff differences.
Following the notations of Legacci al. [34], let r' = r(N.A, u) be a given finite game, and let â; Ai be fixed benchmark strategy for each player i E N. We then consider the hyperplane Z, [zi R ziá; 0}, which is evidently isomorphic to R Elements of each player's strategy space Y/ can then be mapped onto Z, through the linear operator
I1 )4 Z, (1; (ytu, ytu, a; à;-)
(B.7)
The product space Z Ieav Z, is called the game's payoff differences space, and we denote by II the product projection map II liie II;
Importantly, if we define the payoff-adjusted choice map Q = ITeN Q: 2 - X by
(,(z,)= = Q;( for any yi (
(B.8)
then we obtain the following regularity result:
15

---

The Impact of Uncertainty on Regularized Learning in Games
Lemma B.3. For every player N, stralegy x X and action oi # âG
Liog = ( =x((x)))) (xiá,)
(B.9)
In particular, δ- riX Z is a single-valued continuous map.
Proof. The proof is immediate by the Baansh-Kuhn-Tuunn conditions applied the convex problem posed in Q, stating that yia, = (Xia,) + for some multiplier μ E IR, and the definition of Q through payoff differences.
Consequently, any compact subset living in X' mapped through --1 a compact subset 2. Therefore, to establish a dichotomy result for stochastic dynamics within ri X. suffices demonstrate that the diffusion on Z, obtained by mapping (S-FTRL) through II, is uniformly elliptic.
Interpreting II as full-rank matrix (which is possible because it is linear function), it is easy to show that Z(1) = ITY(1)
verifies the stochastic differential equation
dZ(1) = Il(()(()))d + lo -d))))))dd(() (I
(FTRL-Z)
(x)] where (x) |o (x))) denotes the overarching diffusion matrix over all players.
Accordingly, the principal symbol of (FTRL-Z) is given by
a(2) (é()) (M=((())) (((((())) o2 "IIT
omin x 7iin 1
(B.10)
where mii denotes the smallest singular of or, which assumed to positive (cf. Assumption 1), and mii denotes the smallest singular value of II (positive because II is full-rank). Consequently, the infinitesimal generator of (FTRL-Z) is uniformly elliptic, and thus Lemma B.2 holds true for its trajectories.
The arguments developed above naturally lead to the following definition of recurrence and transience for trajectories of (S-FTRL) evolving within the space ri X::
Definition 3. Let (r) be solution orbit of (S-FTRL).
(t) is said to be recurrent in ri X' if, for every relatively compact subsets S ri X' and every initial condition x E ri X, the hitting time tx = in 2 0: (1) E IC} is almost-surely finite. Moreover, Ex [TX] < oo, then the process is further called positive recurrent X. while is called null recurrent is the expectation infinite.
X()) is said to be transient ri if, for every initial condition x xi X(1) converges to bd X' almost-surely.
Furthermore, Lemma B.2 can be applied to derive a transience/recurrence dichotomy for such trajectories:
Theorem (Transience/rrcurrenee dichotomy in ri. Trajectories of (S-FTRL) are either all positive recurrent or all null recurrent or all transient X.
Proof. virtue of Lemma B.3, any compact included ri is mapped through Q-1 to a compact in 2. Accordingly, (r) recurrent (resp. transient) in ri X' whenever Z(t) is recurrent (resp. transient) in Z. But the stochastic differential equation (FTRL-Z) defining Z(t) is uniformly elliptic, either all trajectories of (FTRL-Z) are recurrent or all trajectories transient (cf. Lemma B.2). Consequently, trajectories of (S-FTRL) are also either all recurrent all transient in ri X. The same logic can also be adapted to show that either all trajectories are positive recurrent or all are null recurrent.
B.3. Additional standard results. We conclude this appendix by reviewing several results from stochastic analysis. which are typically stated in classical textbooks for the specific case of Brownian motion, but that are more difficult to find in their full generality:
Lemma B.4 (Law of iterated logarithm for martingales [36]). Let M(1) be a continuous square-integrable local martingale. Then, the trajectories of (1) verify
M(r)
lim sup 7-a00
(B.11)
([M M(()
on the event (lim (M](1) oo).
16

---

The Impact of Uncertainty on Regularized Learning in Games
Lemma B.5 (Strong law of large numbers [39]). Lel M1) be a continuous square-inteerabble local martingale and let us define
PM L-"
dsM](s
(B.12)
(1+s)²
If poo (1) < oo (a.s.), then M(1)/1 0 (a.s.).
C Omitted proofs from Section 3
In this appendix, provide the proofs from Section 3 that were omitted in the main text. Specifically, demonstrate that the stochastic differential equation defining (S-FTRI admits unique strong solution, and we present an explicit computation of the stochastic differential equation governing the evolution of the player's 's strategies in X.
We recall that the stochastic dynamics under study is given by the stochastic differential equation
dy, 02 (X()) dr + dM,(1)
(FTRL-S)
X,(1) (())()))
where M, (X(())(W))) for some underlying on-dimensional Brownian motion.
Proposition C.1. The stochastic differential equation (S-FTRI.) admits unique strong solution Y(1) for every initial condition Y(0) V.
Proof. The existence and uniqueness of a strong solution can be proved using a classical Picard's iteration argument (see e.g., Øksendal [54, Theorem 5.2.1J). To do so, we only need to show that the drift and diffusion coefficients verify a mild growth condition and that they are Lipschitz continuous on V. First, notice that Q is (1/K)-Lipscitzz on y where K denotes the smallest strong convexity constant among the regularizer functions h; E N (ef. Proposition A.1). As such, the composition of (resp. o with Q remains Lipschitz-comtinuuut Furthermore, Q takes values into the compact set X, it is immediate that the growth condition is verified (the coefficients are in fact all uniformly bounded on the state space). The stochastic dynamics (S-FTRL) therefore admits unique strong solution as required.
The uniqueness mentioned in Proposition C.1 should be understood in the sense of equivalence up to evanes- cence, meaning that any two solutions of (S-FTRL) must be equal any time with probability 1; i.e., they should be indistinguishable from one another stochastic processes.
Remark 2.
Proposition The solutions of (S-FTRL) satisfy the stochastic differential equation
dXia;
gia:
Uta;
Σ
UiB
dt
(14a)
BiEAL
+ gia
dMia
-
E
Xip, dMip
(14b)
BiEA:
m
+ gia:
Σ
Vinnk
V
Σ
Xip.
ip,k
dt
(14c)
k=l
Bie.A,
where we set gia, (Xta,) Xia, = g EBEAA gipp, and V. = - [Fink EBEE Xip, Xip, x
Proof of Proposition 1. For simplicity (and without loss of generality), let us suppress the player's index i E N in the remaining of the proof. Due to h being assumed steep and decomposable as h(x) = Σ. 6(xa) (see Appendix A for the collection of assumptions verified by 0), the Karush-Kuhn Tucker conditions applied to the convex optimization problem of Eq. (6) posed to define Q leads ye 0' (xx) A for some Lagrange multiplier IR whenever x Q(y). In particular, applying this identity to the solution orbits Y(r) and X()) of (S-FTRL) yields the existence of continuous stochastic process 1(r) such that
(1)() = 0' (1) + A(1) for every 1 2
(C.1)
17

---

The Impact of Uncertainty on Regularized Learning in Games
Applying the classical Itö's formula (see e.g.. Section 3.3 of Karatzas Shreve [29]) on both sides of the equality therefore gives
dA = = 00" (xx (Xa)d(aa)
(C.2)
where (1) denotes the quadratic variation process of X().. Before proceeding with the proof, let us introduce some notation that will be useful for simplifying the subsequent computations:
8 = (Xa))
8" =""
(C.3)
Ya = 1/6"
G= G=EB 4B. Xa = ga/G.
(C.4)
If we rearrange the terms of Eq. (C.2) and take the sum over all A, we get
0 = Σ. dXæ En gadYa En d[xa] Gdd,
(C.5)
where the first equality comes from the simplex constraint Σa Xa 1. Consequently, a(1) is given explicitly by
da XadY 1 Xaodd
(C.6)
By inserting this expression into Eq. (C.2), we therefore get
dXa =a( Eg XodYs) 29 6"' d["x Es d[xx]
1
(C.7)
= =galva- -Ep x dt ga E Ex (oak
dWx 3 0- d[x] Ep X0l d(xpl). (C.8)
1
The quadratic variation of (x can thus be computed as
d[Xa] g Ex Tax XB0T8) XB d(W, Wi] - Ex (Takk -E XBOBK)
1 dr, (C.9)
which ultimately proves the stochastic differential equation stated in Proposition upon substituting d[x,] with its expression in Eq. (C.8).
D Omitted proofs from Section 4
In this appendix, we collect the proof' of the results presented in Section 4.
D.1. Proof of Theorem 1. Our aim in this appendix is to prove Theorem 1, which we restate below for convenience.
Theorem 1. Suppose Assumptions I and 2 hold, fix sufficiently small accuracy threshold & O, and let
T it 2 0: maxa,eAAA Xio, (t) 2 1-
(19)
denote the time player E N takes to reach an e-neighborhood of one of their pure strategies. Then Ti,s is finite with probability 1, and we have
Ex[T/,s] S 1212
(20)
where A 0 is positive constant that scales as
2
O
i.max
0"
8
(21)
i.min
n1
To facilitate more modular proof of Theorem 1, reformulate its results two distinct propositions detailed below: Proposition D.1. The hitting time Ti. is finite with probability 1.
18

---

The Impact of Uncertainty on Regularized Learning in Games
Proposition D.2. The expectation of Tr. upper-bounded by
Ex s 12
(D.I)
where A is a positive constant that scales as
+ o²?
2) σ² 1.min
8
maxx 87'
(D.2)
-
Before proving any of these results, let us restate the stochastic differential equation defining the evolution of ( (cf. Proposition 1) as
dXian EB, gior 18m.p GT gip, (oip, + + EB, gior 15mp -G gip, JdMap.
(D.3)
where:
a) gia, 1/0 (Xia))
b) G; = EB gipi:
1 8i" (Nias)
Sta, 2 107 (Xian) )
Flack EE. 9.
Borrowing the idea from Imhof [28] - who has studied the same type of property for the replicator dynamics with aggregate shocks (SRD-AS) in symmetric games we aim construct well-behaved Lyapunov function éi for the collection A, of pure strategies of player E .. More precisely, such a function should verify the following properties:
1. (x) 0 for every x X, with equality reached only when is pure strategy:
Away from pure strategies of X, & decreases average along trajectories of (S-FTRL).
Intuitively, the existence of such function would suggest that the solution orbits of (S-FTRL) converge average toward neighborhood of pure strategies in N, which in turn would imply that the time required to reach such a neighborhood is finite.
For the sake of readability, let us drop completely the reference to the player's index in the remainder of this appendix.
This can be done without any loss of generality, as we are focusing solely on the hitting time of single player.
Accordingly, us propose o of the parametric form
((x) = -- - E. 2x
(D.4)
with positive parameter that will be chosen afterwards (depending on the parameters interest of the problem). Claim 1. ((x) 2 with equality reached only when x is pure strategy.
Proof. This claim follows from the inequality ex ea+ e e 1 holding for every b 2 0 (this is easily shown by fixing b and taking derivative with respect to a). Indeed, iterating this inequality on every elements Ax, O, we get
En Ne s dE fo + n e² I.
(D.5)
where the right-hand side is reached exclusively for pure strategies. Consequently, we readily obtain
((x) 2 n 1+ el ed (n
(D.6)
as required.
Claim 2. Away from pure strategies, & decreases in average along trajectories of (S-FTRI)..
19

---

The Impact of Uncertainty on Regularized Learning in Games
Proof. More precisely, will show that outside the neighborhood Ug {xx X za I for some a E A), there exists parameter A big enough such that
d E. E.(0(((0)] Lx(x) <0 for every x X Ur.
(D.7)
dt
To do so, let first notice that a (x) and that its partial derivatives are given by
dΦ -e and dxa0xB
02 - daß.
(D.8)
ax
As such, Itô's lemma and the stochastic differential equation from Eq. (D.3) can be used to obtain
22 ga Epyloar G
[Ø(x) = -A Ia loap G GG'g3((up + Sp)
'9'g3 [öy - G Gr'rr\ZBr (D.9)
(1)
(II)
where we recall that Σ = o denotes the quadratic covariation matrix of noise (for player i).
Lower bound for (/): From the definition of Ja and G, and the fact is strongly convex and steep, it is evident that 0 G-1ya yo for every A. Furthermore, by Assumption 2, we have 10 (xx) M for some constant M co. As such, already bound the absolute value of Sr by
M |S s 2
Fak + EEp G BB(TKK]
M Σ s
max + o = m moo?
(D.10)
2
max
k=1
where recall that i denotes the maximal eigenvalue of Σ uniformly on E X. Using this bound in tandem with [xa(x)] s M, oo for every a E A. X (holding from continuity of va the compact X), then leads to
B (1) 2 -o n M mMomax gae g = E. g
(D.11)
where B = =nnMM, + mo max).
Lower bound for (If): Notice that E > 2 with Jnin 0 by Assumption 1, which allows us to bound (IT) as
(II) Ea e ozi Egldap G G-1gp g=)gp
onin (1- G (0)gg)))2" 2e Easg
golG | exa
(D.12)
2
2 min
En 2u (1- G-1 G-1gn)² 2
(D.13)
Combining the bounds for both (I) and (II) therefore leads
CΦ(x)= s Em.
Iue g 1xa [B do² min G-1 (1-
(D.14)
Now, let us consider the region of interest R. = X' \ Ule. Any E Re thus verifies Xa S - for every E A. Furthermore, notice that there always exists at least one action a A such that X, 2 1/n.
Accordingly, let us the decompose the set of actions as A4(x) (a E A : xx, 2 1/n) and A-(x) = \ AA)(x) We also define the following quantities, which will be useful in establishing the bound:
Hmax max (x) and Hmin min 1/n 1/0" O:
b) C, (g. G- (x)
x R²) 0.
where the positiveness of both Hmin and c, comes from the fact that ga (x) 0 only when 0 (consequence of the regularizer being steep).
Using these notations we can then write, for any x E R
d s
LΦ(x)
B
Σ
to (B 2o2 d Ce)
Σ txa aea
(D.15)
2 aea
20

---

The Impact of Uncertainty on Regularized Learning in Games
1
$ 2 Hmax B(n 1)e min
1
Σ
goedso
(D.16)
2 min
Ce
acA.
Consequently, if we choose big enough that
Hmax (n 1)B 1
A
B +
(D.17)
min Co
Mmin
then readily get
Hmax (n
$ Ld(x)
B(a 1)
1)B 1)B+
Σ acA,
gaedxa
(D.18)
2
Hmin
A
Hmax (n Bll BlHiie Iminn
$
mma (n 1)e
(D.19)
2
Hmin
Hmine e i < 0
(D.20)
2
for every Rg which verifies the claim.
Building on the two previous claims, we are now ready prove Proposition D.I and Proposition D.2.
Proof of Proposition D.I. Let Tr in 0: (1) & for some a E A). For every fixed 2 O, Dynkin's formula yields
E.Io(X(T& A 0)] = (xx E, [ TaAr Lo(X(s)) ds
(D.21)
Claims and 2 can then be used to argue that there exists (deterministic) parameter big enough so that
d 0 Os n 3 Mmine A/n Ex(Te 1]
(D.22)
for every 2 0. Rearranging the terms and taking the monotone limit as / / oo therefore give
2 ed +
Ex[Te]
(D.23)
Hmii
for every initial condition x X, which finishes the proof.
Proof of Proposition D.2. Based on Eq. (D.23), it is evident that the hitting time Te has an average bounded as
Ex[Te] $ ed
(D.24)
1
for d big enough. Furthermore, due to the condition from Eq. (D.17), 2 can also be chosen proportional to hidden multiplicative constants depend neither on noise nor 8).
Gem +1
(where the
c Cx min
To prove Proposition D.2, we therefore only need to show that ce is of order [0" (s/(n-1))]2 for & small enough. Recall that ce is defined through the minimization problem
cx min G (x)) A+(x),x Rz).
(D.25)
where Rs fx E X Na s 1 for every a E A} and A,(x) E A: 2 1/n). For the sake of clarity, let us also define
= -
and c(x) min c(x,ar, asA,(x)
(D.26)
so that c. = min c(x) for any & 0.
21

---

The Impact of Uncertainty on Regularized Learning in Games
The main idea of the proof is the following observation: c(x) 2 0 for every X, with equality occurring if and only if is pure strategy (this is consequence of (x) 0 if and only if xa 0). Accordingly, for small enough, we should expect c. to be reached for an x Rs that is the closest possible to pure strategy.
To make this argument rigorous, note that by definition 0" is locally decreasing around O, and so there exists an 17 < 1/n small enough verifying (x) 2 (y) for every x - S The proof is then separated into two parts: for & < small enough, we decompose the minimization space Rs as R, and Rs \ R,. and find a lower-bound for both spaces independently.
Before jumping into those steps, notice that c(x, a)) can be rewritten as
(x)
G(x)2 Euco 9p(x))
(D.27)
where the term go (x) is lower-bounded uniformly on a E A, (x) and E Re-
Step I: Minimization on Ry- As c(x) O when x converges to a pure strategy, there exists an s' < small enough such
that, for any < E', c(x) c(x*) whenever.x R, and.x" e Ur. In partieular, for x" (1-8)ea- nf Esta ep, it implies that
min c(x) > c(x') 2 10" (0((0(()))))) xER,
(1))1-1) x (0"( E
-2
(D.28)
A
by definition x".
Step 2: Minimization on R Ry, Let E R₂ \ Ry i.e., Na 1 & for every a A and there exists a B E such that xB -). In particular, we know that xB E, so there exists y' B verifying
S xy s.
(D.29)
n
Furthermore, 7 was initially taken so that 1 < 1/n, thus A. = (B), which leads to
c(x) = c(x, R E (xyy) 1-)) 2 [0" (xx:)) 2 10"
(D.30)
A -
where the last inequality comes from the local monotony of 6" for -ー S Sxy= S n7.
Combining those two steps, we conclude that
Ce min c(x) min min c(x), min R
c(x) 2 0"' 6
(D.31)
Xx
xERx
12 1
On the other hand, taking x = (1 - E)Ea +
n-T Eppa eB E Rs leads to
E
Cs S c(x,0) = 0n(1 8) (1(( -
+
n
(n 1)2
1)2(0m( 0 E 1
(D.32)
0" ("(E((n ()-
1-
E -2
$ (A- - 20 (1- -) 8"r n1
(D.33)
$ |0' n1
8 )]
-2
(D.34)
which finally shows that c. = =o(lrr
)
-2)
as needed.
D.2. Proof of Theorem 2. Our goal in this appendix is to prove the following theorem:
Theorem 2. Suppose Assumption 3 holds. Then, with notation as above, S is stochastically asymptotically stable under (S-FTRL) if and only if it is closed under better replies. If this is so, there exists an open initialization domain Uo S X such that, whenever X(0) Ug we have with arbitrarily high probability
disty (X(1),) s cfc
-2t c2t 00mmax Vo logr)
(25)
where e₁ and C2 are constants (c2 > 0), and the rate function & is given by (0z) = (8))
22

---

The Impact of Uncertainty on Regularized Learning in Games
Let B ITN B, be a product of pure strategies, and let S be the face spanned by B. Recall from Appendix A that, for every player e N, the Bregman divergence defined as
D2 D:(pi, h:(p:) (x;)) Pi for all Pi E X; Ei
(D.35)
For each player E N, let C; = A, \ B, denote the collection of pure actions not included in B,. The main idea behind proving the stability closed under better replies faces is to show that the family of energy functions
Eiar (x) Xi(etan for X2 Ni ar E C,
(D.36)
can be combined to yield well- "Lyyppnov-like" function for S.
The definition of these energy functions is motivated by the following property, which will also play crucial role in deriving convergence rates:
Lemma D.I. If the kernels verify 8,(0) < oo for every player i E N, then there exist constants < co and C2 > -00 such that
Σ Σ iEN ajEC;
Di(c2 Eiar (x)) S dist (x, S) 2 Σ Σ JEN orEc,
Dílci Eia,
(D.37)
with i defined as 01(2) (01) (2).
Proof. From the definitions of the Bregman divergence and of the regularizers, we can write
Eigg (x) htg(e.,)) h,(x;) (Vi, xi) Cia. En (Xip,) (x((i)))) Ep, Xip (xiB))
(D.38)
where Cia, is finite constant. As result, the convexity of 0; yields
Eig, (x) Cio - 1 min 0,(2) (x(x)))) + (1(1) S C1 (xion)) zE(0.1]
(D.39)
for some constant 01 < oo obtained by taking the maximum over all actions a; C2 and all players E N. On the other hand, note that for players i N and every z E (0. 1), we have
20,(2) = [[" (()))) L' o7())dt = 01(z) - (1()),
(D.40)
where the inequality comes from the (strong) convexity of 0; As such, also get
Eiay (x) 2 Cia, Ep, (x((ap)) (x(m))))) + Ep, [0, (0)) Cia, n;0;(0) (x(ar))) 2 (x((x))) (D.41)
where 02 -00 thanks to the assumption that (0) co, Putting both sides together, we therefore obtain
$ Eia, (x)] Xia, 0,[c, Eiar, (x)]
(D.42)
for every a; E C,, E W, e X. Now, note that by definition of the face S,
disti (x, S) = min -
min x'eS TE.V
Σ
Xiar + Σ
Σ 0,E8,
|xin X/anl
Σ Σ Xiar IEN acEC,
(D.43)
='ES
(.,EC
Furthermore, if we pick some arbitrary pure action a² B and define
if C₁
x/a; = Xias
if E Bi \ {ay*)
(D.44)
Xior;
Ep,C, Xip,
if a; a
for each E X' then x' e S by construction and we get
||x x'111 -
Σ
Nia, +
Σ
Xipi
= Σ Σ
Xiar
(D.45)
iEN
BcC:
IeN aFEC,
23

---

The Impact of Uncertainty on Regularized Learning in Games
Consequently, Eqs. (D.43) and (D.45) yield
Σ iEN ayEc,
Σ
Xia s dist)(x, 2 Σ Σ iEN a:EC;
Xaar
(D.46)
which concludes the proof when combined with Eq. (D.42).
According to Lemma D.I, we can derive two consistency results for the family Ero, (x):
1. x + S if and only Eio, (x) - co for every action at E C and every player E NV;
2. For every neighborhood Us of S, there exist constants M' 2 M > 0 such that Uyr S Us S UM. where
UM = (x E X:: Fia, (x) M for every og C, M
(D.47)
Our proof scheme for showing stability of closed under better replies faces is similar to the one proposed by Boone & Mertikopoulos [12] in a discrete setting, but uses a different family of energy functions in order to fix a flaw in their initialization domain's 's construction. To better understand this flaw, recall that they define the set of outward deviations from 8 as 2 (eip. Eía, 0r E B Br C, E N), and they argue that the associated family of energy functions Ey(y) (y. z) forms good Lyapunov function for S. In particular, they show that Q(y) converges to S whenever 2 (y) - -00, which is similar property that we have obtained in Lemma D.I. However, in their framework, the reverse implication is not true in general, i..., there could be sequence (x") converging to S but such that max (y") remains hounde. For instance, if there exists a player i N for which |8: 2 2 (this is equivalent to ask that $ is not restricted to a vertex of X) and if we fix some pure strategies a" E B, a E B, \ (a7), Bi E C₁, then any sequence (x") converging to ea- E S with <o. = 1Bg satisfies
Remark 3.
inf Ex) inf Yip. n21
-ia inf (1(1)))) 0,(2%,,) 0 -00 n2l
(D.48)
n2l
for the deviation 2 = eig, Cia, E Z. Due to this subtlety, the initialization domain 240 fx E X' max,ez Eg(y) < -2M, x = ) (for M > big enough) proposed by Boone & Mertikopoulos [12] does not describe a bona fide neighborhood of S: in fact, from the previous example, the vertex exr S is not even included in 2g. Since the initializatton domain is required to be neighborhood of the whole face in order to verify the stochastic stability criterion (ef. Definition 1), it means that the energy functions used in [12] are not precise enough to prove such result.
To gain insight into how these energy functions arise in local stability proofs, let us assume S to be closed under better replies. By definition, we then know that u; u,(ar;;; xx-) - u;(x) < for every az C, i e N and all e S. Since the payoff functions ij are continuous on the compact space X, implies that there exists neighborhood Ut of S and a finite constant 0 such that
u, (a;;;-i)) (x(x) S -m for every or C, E AX uu.
(D.49)
Now, let X(r) be solution orbit of (S-FTRL). Using Itô's lemma in tandem with the dual representation of the Bregman divergence (ef. Appendix A and the proof of Lemma F.1). we then get
dFin,((())) = [x:(X) - u;(a;; X-)] + 2 tr(Jac (x0))),(X)dd + (X; Eiar (M)
(D.50)
Specifically, if we temporarily ignore the martingale term (X) eia, (f) (i.c.. if we consider the noiseless setting), then all energy functions are expected to locally increase along trajectories of (S-FTRL) evolving in li as d'i,, (X()) 2 mdt. As result, player's strategies will remain in for any time and converge to S thanks to Lemma D.
However, once the noise term is reintroduced, this local increase of the energy no longer holds: the noise, being modelled as continuous martingale with zero mean, can counterbalance the positive drift and, with positive probability, cause the energy to decrease locally. For instance, under Assumption 1, we know that trajectories of (S-FTRL) cannot even stay in l with probability 1; they always visit any strategy in ri &' with positive probability (cf. Eq. (B.4) and the related discussion about uniform ellipticity in Appendix B).
With that being said, although trajectories could exit 24 with positive probability, we can still show that the total energy converges to so along those trajectories that do stay into U:
24

---

The Impact of Uncertainty on Regularized Learning in Games
Claim 3. IfE (X(1) U for every 0} has positive probability, then Eta; (X(1) almost surely on E for every
0i C₁, i N.
Proof of Claim On the event E, integrating Eq. (D.50) yields
Eta, (x(1) = Eia, (X()) [[" dEia, (X(s))ds 2 Eia, (x) + mt + Eia, (1)
(D.51)
where Eig, (1) is the square-integrable martingale given by dgiar (1) = (X:(1) Cia,. dM,())). By definition of M; (1), the quadratic variation of Eia, (1) can be upper-bounded as
d[Eia, 1()) (Xi-eaa)) "d(M))d((XX.... - -iia)) eia) Exx()xx & ||X; - cia, 1 di s 20 20 dt, (D.52)
where Ommax by continuity of noise coefficients and compactness of X. The strong law of large numbers for martingales (cf. Lemma B.5) can then be used to obtain Eia, (X()) - oo almost surely on the event E, which finishes the proof.
With this claim established, we begin to see the connection to stochastically asymptotic stability: if we can demonstrate that trajectories remain within 4/ with arbitrarily high probability, depending on how close their initial conditions are to S, then would directly obtain convergence toward S with the same (arbitrarily high) probability.
To show that, we use Lemma D.I to describe the neighborhood U through the energy functions Dia. Indeed, we know from the aforementioned lemma that there exists a constant M > 0 (which can be taken as large as needed) such that E 44 whenever x E My, where we recall that UM denotes the non-empty subset of X' given by
UM = {x E X' Eia, (x) > M for every E C,, N).
(D.53)
The main idea is show that if the initial condition is sufficiently close to S, say with x E U2M (which describes neighborhood of S thanks to Lemma D. then we can choose M big enough that every energy functions remains above M at all times, with arbitrarily high probability. In other words, we want to ensure that the noise perturbations are not strong enough to counterbalance the linearly increasing drift. More precisely, we aim to prove the following intermediate result: Claim 4. For every O, there exists M := (M) O big enough such that
P2 (X(() UM for every 2 0) 1
(D.54)
whenever E U2M-
Proof of Claim For every M big enough, let TM denotes the first time at which the minimal energy is lower than M, viz.
= in 2 0: min Eia, (X(1) s M).
(D.55)
Proving the claim is therefore equivalent to showing that P(TM oo) 2 1 1--6 & for a well-chosen constant M. To prove this, we will reduce the problem estimating TM to examining specific hitting times of Eia, (1). Since Eia, (1) is continuous square-integrable martingale, these hitting times will be significantly easier estimate using standard results in stochastic analysis.
First, let us define the auxiliary hitting time
inf 0: Sia, (1) - mt for some a; E C,, N).
(D.56)
We claim that z TM almost surely. Indeed, let us assume on the other hand that there exists a non non-negligible event on which TM- Then TM is necessarily finite this event, and X(1) U for every TM, so Eq. (D.50) leads to
Eia, (X(TM)) 2M + MTM + Eia, (TM) 2M MTM M MTM M
(D.57)
for every a E C, and e N, where the second inequality is consequence of TM < r. This contradicts the definition of TM- which prove that S TM with probability as required.
25

---

The Impact of Uncertainty on Regularized Learning in Games
follows from the previous argument that (r = 00) S (TM =00, which readily implies the bound
P(TM < <00) P(T oo) 1 Σ Σ
P(Tia < c0).
(D.58)
ieN aFEc,
where Tea is the hitting time given by
Fia: inf 0: Eio, (1) -M mf).
(D.59)
To estimate the probability that Tia is finite, remember that the quadratic variation Sia, (t) is upper-bounded by 20 max (a.s.). Moreover, the time-change theorem for continuous martingales [29, p. 174] states that there exists standard Brownian motion (()) (defined on a possibly enlarged probability space) such that Eie, (t) = W(LEia,(1))
Accordingly, if we let i denotes the stopping time
mi
f = inf 2: W() = -M-
(D.60)
20 Bamax
then we readily get P(Tia <00) S P(# < involves standard Brownian motion, for which classical results of the literature (see for instance [29, Subsection 3.5.CJ) yield P(f < oo) eAM with A m/o max.
oo) for every at E C, e N. This last hitting time is easily computed as it only
Putting all these estimations back into Eq. (D.58) then allows us to obtain
P(TM < <00) s |C|e -aM
(D.61)
where |C| Eee In particular, if we take M big enough so that M P(TM = 0o) 2 1 - E, which finishes the proof.
Umax log((CI/s), then finally get
With Claims 3 and 4 established, we are now ready to prove Theorem 2.
Proof of Theorem 2 (club = stable). Let us fix a threshold & > 0 and neighborhood Uo of S. By previously discussed arguments, if S is closed under better replies, we can find a neighborhood 2 and constant m > 0 small enough such that
(,(a;;;=;) - mx(x) s -m for every a; E C,,i N.x
(D.62)
Furthermore, can choose U Uo without loss of generality. Claim 4 therefore yields constant M big enough so that P. (X E Uo for every: 1 2 0) 2 (x E U for every 2 0) 2 (x(((1) E Uy for every : 2 0) 2 1 -
(D.63)
whenever x E U2M (which describes a neighborhood of S). Moreover, X(1) - S almost surely on the event (X(1) for every 2 0} by Claim and Lemma D.I, so S is stochastically asymptotically stable as required.
Proof of Theorem 2 (convergence rate). Coming back to Eq. (D.51), we obtain that, on the event (X(1) U for every 2 0} which has probability greater than 1-8,
Eia, (X(1) 2 mt Eia (1)
(D.64)
for every pure actions a; E C and all players i E N, where Eia, (1) is square-integrable martingale with [Eia, 1(1) S 20 In particular, if [t) / co, then the law of iterated logarithm (Lemma B.4) yields
Eii, (1) = lim sup
Eio (f)
2 (()) log logléin,
lim sup
< 2V2 (a.s.) (D.65)
Tmax / log log 1-000
V2l J (t) log ia, (1))
Pmast log logs
On the other hand, if [ 1(1) / [E:n) < co, then Eia, (r) converges to finite random variable and so Isia (1) o' v log l). Consequently, as C, and N are finite, it implies that ma (0) = O (FTmax v log (a.s.) in any cases.
26

---

The Impact of Uncertainty on Regularized Learning in Games
Now, in virtue of Lemma D.I and by the fact that Ø is increasing (0, is convex), we therefore get
di(x(), 2 Σ
Σ
C1
mt +
max a,EC,
KEion (1)l $ o 0(c1- - mmt + O (mxx log logr
(D.66)
iEN 0; EC;
on the event E, which readily finish the proof.
Proof of Theorem 2 (stable = club). Assume that the face S is stochastically asymptotically stable but not closed under better replies. Then, there exists player i E N and pure strategies a E B, a' E C such that a 2 4q (a).
Now, let us consider the restriction of (S-FTRL) to the face spanned by a and (af; a-)), by taking as initial condition (0) = aii) where supp.;; = {a;, {a,,, As is steep, trajectories of (S-FTRL) are invariant in this subface, meaning that (t) (x) with supp (r) {az. [ for every time 2 O.
Consequently, the score difference between strategies a; and of is given at any time by
dYia - dVio; = (a) - u;(af; dt + dE(1)= & dg(1),
(D.67)
where E(1) is the square-integrable martingale given by É(T) (eian - Ciaf, (1)). The quadratic variation of g() is lower-bounded as (t) 2 20 (a.s.), which implies that [t] / 0o when - co. We can therefore invoke the law of iterated logarithm for martingales (cf. Lemma B.4) to obtain lim i = -oo (a.s.). Coming back to Eq. (D.67), we then get
lim inf Yia, (1) Via;(1 (1) s Via, (0) - (ia;(0) + lim g(1) = 00 (a.s.).
(D.68)
[ 10000
1-200
This implies that, with probability one and for any initial condition, there exists subsequence (fn) / oo such that Yia, (f,) - YYaa (tn) (In) - cc. Moreover, the Karush-Kuhn- Tucker conditions applied to the convex problem posed in the definition of Qi yield your = (x(xia,) + μr for some Lagrange multiplier μ4; E whenever x; = Qi(y)). Consequently, we
also get
8x(iia, (In) = (Xao;; Yio (1n) - Yio; (1n) s (()) Yia, (1,) Vio; - oo (a.s.).
(D.69)
meaning that Xia, (4n) - 0 with probability one thanks to the convexity of o, This contradicts the fact that S is stochastically asymptotically stable (as ca E S, we should have X()) ca with positive probability for trajectories starting close enough to ea), thus S is necessarily closed under better replies.
D.3. Proof of Theorem 3. In this section, we provide the proof of Theorem 3, whose statement is recalled below for convenience:
Theorem 3. Suppose Assumptions 1-3 hold. Then:
1. x* E X is stochastically asymptotically stable under (S-FTRL) if and only if it is strict equilibrium.
2. P noo X(t)= =x") 0, then x" is a pure Nash equilibrium; in words, the only possible limits of (S-FTRL) are pure Nash equilibria.
First, note that any stochastically asymptotically stable strategy must be pure, shown by Corollary 3 (and similarly, any strategy toward which trajectories of (S-FTRL) converge with positive probability is pure). Therefore, it is sufficient to prove the following claims in order to establish Theorem 3:
Claim 5. A pure strategy is stochastically asymptotically stable if and only if a strict Nash equilibrium.
Claim 6. Trajectories of (S-FTRL) converge only to Nush equilibria.
Proof of Claim 5. By Theorem 2 and the fact that strict Nash equilibria are the only pure strategies whose support is closed under better replies, Claim 5 is automatically proven true.
Claim 6, on the other hand, does not follow from any of our previous results. However, this property of (S-FTRL) has already been established by Bravo & Mertikopoulos [13] under the same kind of assumptions as ours. For the sake of completeness, we also provide the proof of this result here.
27

---

The Impact of Uncertainty on Regularized Learning in Games
Proof of Claim 6. For the sole purpose of proving contradiction, assume that there exists an event E with positive probability and strategy x" that is not a Nash equilibrium such that (() - x" E. xsx" in not Nash, there must exists player i E N and actions a; E supp(x;), Bi A; verifying Via; (x') < tig; (x"). By continuity of u, can therefore find a small enough neighborhood U1 of x' and a positive constant m > 0 such that Dip, (x) Pta, (x) 2 m for every x E U. As X (1) converges to xx on E, it follows that there exists a finite (random) time to such that ((1 E l/ for every 1 2 to when conditioned on the event E. In particular, for big enough, we get
to (Via, - vip,) ds + S" (Vii -Uip) vig,) ds + E() S C mI + E(T), !,"'
Yia, (1) Yip, (1) yyi,, yip, +
(D.70)
fo
where C = yiur - yip, + +00 (Via, vip, ) ds mto is a random constant finite on E, and g(t) is the square-integrable martingale given by
(oio)( (xxxx(()))))) [ (s).
m
5(1) = Σ k=1
(D.71)
As the quadratic variation of É is upper-bounded by C'r for some positive deterministic constant C', the strong law of large numbers (ef. Lemma B.5) implies that Yra; (t) - Yıp, (r) -
E, which directly leads to Xia, (1) - 0 by the same
argument used in the proof of Theorem 2. This contradicts the fact that we should have Xia, (1) - xia, > 0 on E, hence proving that x" must be a Nash equilibrium.
E Harmonic games and closedness under better replies
In this appendix, we present some general facts about harmonic games, following the framework of Legacci et al. [34], and establish the following original result: no subface of a harmonic game can be closed under better replies.
Originally introduced by Candogan et al. [15] and later generalized by Abdou et al. [1], harmonic games games model strategic scenarios where players have confticting, anti-aligned interests. These games encompass two-player zero-sum games with a fully mixed equilibrium, a widely studied framework for modeling conflicting interactions [48]. By contrast, harmonic games are, in a precise sense, complementary to the class of potential games of Monderer & Shapley [52], which model strategic situations where players' interests align to maximize outcomes by collectively optimizing a shared potential function.
A defining feature of harmonic games is the existence of special strategy, known as strategic center. Intuitively, the center has the property that the game's 's payoff vector is always parallel to an ellipsoid centered at this point, imparting a circular character to the game's 's strategic structure. This should be compared with the payoff vector of potential games [59], which is always perpendicular the level sets of the underlying potential function. In the deterministic setting, these strategic structures reflect in the dynamics as follows: harmonic games exhibit a constant of motion with bounded level sets, closely related to the Fenchel coupling introduced in Appendix A; conversely, potential games are characterized by a Lyapunov functtttuunntioon the form of their potential.
An important additional property of harmonic games is the following: excluding trivial situations where all unilateral payoff' deviations are identically zero, harmonic games cannot have strict Nash equilibria. In Theorem E. we shall prove that this is an instance of more general result: given a harmonic game r = I(N, A, u), no proper subset B c A of pure action profiles can be closed under better replies (club).
Since their introduction, harmonic games have generated a substantial body of literature; for a brief survey, we refer the reader Legacci et al. [35].
E.1. Harmonic games. Roughly speaking. a finite game r I(N, A, u) is harmonic if, whenever a player considers deviating towards a specific action profile E A, there are other players inclined to deviate away from that profile. More formally, game is harmonic if there exist strictly positive weights Hioz > 0 that each player i A assigns each of their pure actions a; A,, such that for any action profile E A, the j-weighted sum of unilateral utility deviations to is zero:
Σ Σ Mip [ui(a;;; ui (Br: a a)] 0 0 for all E A.
(E.1)
TEN B.A.A
An immediate consequence of this definition is that, excluding trivial games where all unilateral payoff deviations vanish identically, harmonic games cannot have strict Nash equilibria: If a were a strict NE, all terms within the square brackets in Eq. (F.1) would by definition be strictly positive, leading to contradiction.
28

---

The Impact of Uncertainty on Regularized Learning in Games
This stands in stark contrast to the behavior of potential games, which always admit least one pure (and generically striet) Nash equilibrium. This important difference stems from rather deep geometrical fact: the orthogonal nature of potential and harmonic games, discussed in detail by Abdou et al. [1], Candogan et al. [15], which we briefly describe here. For fixed sets of players N and actions A with cardinalities N and n respectively, the payoff function of game I = I[V. u) can be represented as an element of a n -i-diimesioonll vector space. Potential games and harmonic games comprise linear subspaces of this vector space; moreover, endowed with a suitable inner product, this vector space admits an orthogonal direct sum decomposition into the subspaces of potential and harmonic games (modulo strategic equivalence, an equivalence relation that identifies games with the same strategic structure). In other words, up strategic equivalence, the payoff functions of any finite game r = T(V, u) can be uniquely decomposed as Up 4h. where (N, Up) is potential game and (W, A. un) is harmonic one.
Moving on, the defining property (E.1) for finite game I to be harmonic can be reformulated in terms its mixed extension's payoff vector D:
Proposition E.1 ((34)), A finite game I = I(N. A(,) is harmonic if and only if its mixed extension A(T) (N, "y and (ii) fully mixed strategy q E ri X, such that
fulfills the following: there exist (i) a tuple m E RR
Σ
m;(us()), qi) = for all x X.
(E.2)
TEN
Whenever the above holds true, m and q are called respectively mass and strategic center of the underlying harmonic game.
Proof. By standard arguments, Eq. (E.1) holds true if and only if its multilinear extension holds true, that is if and only if
EieN Ep,sA, A, pip, [ui(xxix=i)) -u; (B;xxxx))] = O for all X. By Eqs. (2) and (3), this is equivalent to
Σ ieN
(1x(x).xx)
Σ HiB. - (ui (x Bi
Σ Hip (os(s)) IEN Br
Σ
Hi
>|
= for all E X,
(E.3)
Ep, Mip,
where we denote μ == (Hia;) A and all sums involving players' pure actions are taken over Bi E Ar. Now, assume that Eq. (E.3) holds true; then Eq. (E.2) holds true by setting m; Σe Mig and qia, Miaz/ Ep, Hig, for all e N and a; E Ai Conversely, if Eq. (F.2) holds true, then Eq, (E.3) holds also true by setting Pia, m;qia for all i e N and or E Ai.
An immediate corollary is that harmonic games encompass two-player zero-sum games with a fully mixed equilibrium:
Corollary E.1. Every two-player zero-sum game with a fully mixed Nash equilibrium x² is harmonic, with weights x".
Proof. An interior equilibrium of two-player zero-sum games null variationally stable [47-49], that is Ei x;) for all x E X, which implies that Eq. (E.2) is fulfilledd with m, = and qi x
Proposition E. implies that the payoff vector a of harmonic game is parallel to the parametric family of hyperellipsoids given by the level sets of the function x + ΣVEN m;(x; qi)² e IR. Each hyperellipsoid in this family is centered at q, with the ratios among the semi-axes determined by the game's 's mass m, and their absolute lengths varying based on the level value. As shown by Legacci et al. [34, Th. 2], a consequence of this "circular" strategic structure that the (deterministic) dynamics (FTRL) are "almost-perioe "eriosstperiodic" in harmonic games more precisely, they exhibit Poincaré recurrence. The authors establish this result by demonstrating that the FTRL dynamics in harmonic games admit constant of motion; for completeness, we include the proof of this fact here.
Proposition E.2. Assume (FTRL) is run in a harmonic game with mass m and strategic center q. Then the function
F F(m.q) (y) = => mi [l((g)) + h;(()) (qi. mi)]
(E.4)
ieN
remains constant along score trajectories y(1).
Remark. Eq. (E.4) expresses the sum of Fenchel couplings F(qi.y) y:), as defined in Eq. (A.6), for each player i e N. Each term is computed relative to the strategic center qi, and weighted by the corresponding mass m,.
29

---

The Impact of Uncertainty on Regularized Learning in Games
Proof. By chain rule,
d F (m..)) (y(1)) = - m; (VV) (qi. (1) dt
-- mx(x;(1) qí. (x(())) 0 iEN
(E.5)
iEN
where we used Eq. (A.7), the definition of (FTRL), and the characterization (E.2) of harmonic games.
In the following sections, we will show that the absence of strict Nash equilibria in harmonic games is a special case of a broader principle, namely the absence of sets that are closed under better replies. To this end, we first review some basic properties of the better-reply correspondence over pure strategies, later extending our results to the case of mixed strategies.
E.2. Pure better reply correspondence and club sets. Given a finite game I' T(N,A,, u), Ritzberger & Weibull [56]
introduced the better reply correspondence btr;: A 3 A as the set-valued map returning all (weakly) profitable deviations for player i E N from a given action profile a E A::
(ar;(a))= [B: A (B(;ar))))) 2 (;(a):-))))
(F.6)
Extending this to all players, we will write btr == NIEN btz; A = A for the product correspondence; we then say that a subset B S AA of action profiles is closed under better replies (club) if btr(a)) B for all B. Clearly, the whole A is always closed under better replies; the question of whether set of action profiles is club or not is thus non-trivial only in the case of proper subsets B c A.
Next, we provide a simple characterization of club sets in terms of unilateral utility deviations: heuristically, a subset B of action profiles is club if and only if each unilateral deviation towards B is strictly profitable. To make this precise, we set some notation.
Definition E.I. Let T(V A. u) be finite game. Two action profiles a. e A form unilateral deviation if they differ in the action of precisely one player; whenever this is the case, write + B. and simply say that / is a deviation from The deviations from any E A constitute the set Z, == (B A B + a). Whenever + B, we write Du(a, B) == (;(a) - u; (B;; for the payoff difference of the (necessarily existing and unique) player i E N deviating from B to a: furthermore, if the game is harmonic with weights jr, we write p(a. B) == Hiß, where again i is the (existing and unique) deviating player.' Note that Du(-,-) is anti-symmetric in its two arguments, while p(:.-) does not generically possess any symmetry. Consider now a subset B s A: For any fixed a E A, we denote by Za,8 == Z, n B the set of deviations from a that belong to B, and by ~ == Za Za. the set of deviations from a that do not belong to B.
Remark. These notations allow to recast the defining property (E.1) of harmonic games as
Σ B
((a.B)Du(a,,)) = 0 for all a E A.
(E.7)
Lemma E. (Characterization of club sets). Given a finite game r= .VW.A.u) u), a proper subset B C A of action profiles is closed under better replies if and only if the following condition holds true:
Du(a, B) > 0 for all a e B and all B E ZB
(E.8)
Proof. We proceed by contradiction. Let B be a club set, and assume the existence of a pair E B. 2" 2g,8 such that Du(a, B) s O. Then by Eq. (E.6), Bi E (ar; for some unique i E N. Since B = a-i and aj E btr for all E N, this implies that / E btt(a). This is a contradiction, since by assumption a E B. B E B, and B is closed under better replies.
Conversely, let Eq. (E.8) hold true, and assume not closed under better replies. Then there must exist a (non-strictly) profitable deviation leaving B, that is pair a E B, B Zz, such that / btr(a). This in turn implies Du(a, B) s 0, contradiction.
Remark. Note that in the above we consider any subset B A; in particular, B is not necessarily spanning subface of X, that is, it is not necessarily factoring as B = NleN B, for family (B, c Adlie. The case in which B does span subface of X' is described in Corollary E.2.
'It important to observe that ((a, B) Mig, as defined in the text is indeed a function of both of its arguments: While the first argument does not explicitly appear on the rinht-hand side, player i in the definition depends implicitly on both a and B. A more explicit, albeit verbose, definition would be p(a. B) = Mplayaa (1aanii. where play(a, (a. BB) E A is the player deviating hetween a and B. for any pair a e B.
30

---

The Impact of Uncertainty on Regularized Learning in Games
-b+ d
c
a
d d
+b
Figure 2: Left Response graph of a 2 x 2 x 2 uniform harmonic game. Red labels on edges: freely chosen payoff' deviations b. d, E R. Black labels on edges: payoff deviations constrained as to make the game harmonic according to Eq. (E.1). Violer vertices: generic subset B of pure action profiles. As detailed in Example I, there is no way to choose the parameters b. c,d,& 6 e R make the B closed under better replies. Right- Response graph of generic of pure action profiles. Red labels on edges: unilateral payoff deviations hetween elements of Black labels on vertices E B: sum of unilateral payoff deviations towards a within B, that is Epc 2,, Du(a, B). As detailed in Lemma E.2, summing these values for all yields zero by the anti-symmetry of the Du(;,)) operator. Note that 2 @ for TLP, which hence does not contribute the sum.
2 x game. Violet vertices: generic subset
E.3. No pure club sets in harmonic games. With the notions of the previous sections at hand, move to show that harmonic games do not admit proper subsets of action profiles that are closed under better replies. Rather than directly stating and proving the general result, we take a more pedagogical approach to develop intuition by proceeding as follows: (i) We begin with Example 1, which considers the special case of uniform harmonic game, where Hía, = for all A and all a E A,, involving three players each having two available actions; (ii) Next, we provide the proof for the case of uniform harmonic games with arbitrary number of player and actions, as presented in Proposition E.3; (iti) Finally, we extend the result to general harmonic games, as detailed in Theorem E. Readers familiar with the topic may choose to proceed directly to this final proof.
Example E.1 (2 x 2 x 2 uniform harmonic game). A harmonic game is called uniform if all players assign a weight of to each of their actions. As shown by Candogan et al. [15, Prop. 4.11, the number of degrees of freedom available in choosing unilateral payoff deviations in a uniform harmonic game is given by the formula (N 1) Ilie n1 ΣiEN' [i nj 1, where is the number of players and n; the number of actions available to player i. For a x x game, this yields degrees of freedom; we denote them by a, b. c. d, 6 R, and represent them Fig. 2 (left) as payoff deviations on the game's 's response graph [15], oriented graph with node for each of the 8 action profiles and edge for each of the 12 unilateral deviations of the game."
The values of the remaining payoff deviations required for the game to be harmonic are readily computed by Eq. (E.1), and are also represented in Fig. (left). For example, label the action profiles of the game by the positions they occupy in the response graph.? Deviating towards the TLA profile entails a payoff difference of c c d for the first player, -8 for the second player, and of -c + for the third player: Summing these differences yields zero, as required for the game be harmonic.
Having the general form of 2 x 2 x 2 uniform harmonic game in place, claim that cannot find values for the free parameters a, b, c, d, 8 E RR such that some proper subset of action profiles be closed under better replies. Consider, for example, the set B = (TLA, BLA, BRA, BRP) c A, whose elements are highlighted in violet in Fig. 2 (left). By Lemma 1, if B were closed under better replies, then each unilateral payoff deviation from a profile not in B to any profile in B would be strictly positive. This would yield the following system of incqualities for the parameters a, b, c, d, 5 E R:
[c -
bbaa>0 BRP:
TLA
BLA fc>0
BRA fa- d
(F.9)
(-b>0 0
'The label each oriented edge represents the payoff difference for the player performing the deviation indicated by the arrow. TT and for top and bottom; L. and R. for left and right; and P for anterior and posterior.
31

---

The Impact of Uncertainty on Regularized Learning in Games
This system is easily verified to have no solution, summing all of the left-hand sides yields zero Consequently, it is impossible select values for the parameters a, b, d IR such that the set B closed under better replies. It is straightforward to verify that this does not depend on the particular choice of B, and holds true for any subset of action profiles of the game.
The reasoning employed in the previous example can be generalized to the case of uniform harmonic games with arbitrary number of players and actions, as follows.
Proposition E.3. In uniform harmonic game, no proper subset of action profiles can be closed under better replies.
Proof. Let l = T(N.A,u u) be a uniform harmonic game, and assume by contradiction the existence of some B C A that is club. For any a E B, specialize Eq. (E.7) characterizing harmonic games to the uniform case (Hia, for all i E N, ag E Ai), and split the domain of summation as the disjoint union 2, = Za.8 B Ll 2 to obtain
Σ Be 2..
Du(a. B) +
Σ Du(a, B) =0 for all a e BB BEZ,,
(E.10)
By Lemma 1. each term of the second summation is strictly positíve, and so is the whole second summation; hence, the first summation must be strictly negative. In other words, if a uniform harmonic game admitted a club set B, it should be true that
Σ
Du(a, B) < 0 for all a B.
(E.11)
2
However, this contradicts Lemma E.2 below, concluding our proof.
Lemma E.2 (Antisymmetric contraction). In any finite game I I(N.A.u) u) and for any A.
Σ Du(a, =0. BEB,EZ2,8
(E.12)
Proof. The idea is that for each term appearing in the sum, it's opposite also appears, by anti-symmetry of Du(:.-.. Take B. If Zo.8 = Ø there is nothing to show. Assume then that 2a,5 # Ø. Each ß 2,,5 contributes with term Du(a, to the sum. However, B Za,B implies that E Zp.B. since a + B is symmetric and both a and B belong to B. Hence each B E 2, contributes to the sum also with a term Du(B. a) -Du(a, B), canceling out the previous contribution.
Example E.2 (Antisymmetric contraction). Let Fig. 2 (right) be the response graph of generic 2 x 2 x 2 game. Consider the set of profiles a e B = [BLA, BRA, BRP, TRA, TLP), with payoff deviations among them given by a, b.b.c. C. E R; it is not necessary to consider any of the deviations to TLP, since none of them belongs to B. We have that EueB EBe Du(a, B) = -a + (a + - b)
- c = 0, in agreement with Lemma E.2.
Finally, we generalize this result to the case of harmonic games with non-unitary weights. Theorem E.1. Assume r = I(N,A,u) u) is a harmonic game. Then no proper subset B c A can be closed under better replies.
Proof. The proof is formally almost identical to that of Proposition E.3, but hinges on a more general version of the key Lemma E.2, taking into account the "symmetry breaking" due to the presence of weights. Let r I'A' A, u) be a harmonic game with weights μi and assume by contradiction the existence of some c A that is club. For any a B, invoke Eq. (E.7) characterizing harmonic games, and split the domain of summation as the disjoint union Z, 2a, Z², to obtain
Σ ((a.)) BE
+ Σ ((a.B)Du(a, BEZ
for all a e B.
1F.13)
By Lemma 1, each term of the second summation is strictly positive, and so is the whole second summation; hence, the first summation must be strictly negative. In other words, if a harmonic game with weights admitted club set B, it should be true that
Σ B
ula, Du(a, B) < 0 for all E B.
(E.14)
32

---

The Impact of Uncertainty on Regularized Learning in Games
However, this leads contradiction: indeed, for any B A, claim that
Σ e LEEN
Pjaj
Σ BE
pla, ((uaa, B) = 0.
(E.15)
If we show that Eq. (E.15) holds true, our proof is complete; note that this equation is a generalization of Lemma E.2 in the presence of non-uniform weights. As such, is proved analogously: recall that for any profile a E B and any deviation 8 E Zu.B, the map (a, ~ D)(a, is anti-symmetric, and observe that (on the same domain) the map B) ~ [TT Hjay] p(a, B) is symmetric. To verify the latter statement, denote by . the (existing and unique) player deviating between and B. that is, (Bi, ai). Then,
Pja p(a,B) JEN
n
I Mia (()
Pia,HiB
n JEN
HiB; H(B,a).
(E.16)
For conciseness we denote this symmetric map by B(arB) [ JEN Mja,] I p(a,, B) for all a B. Za, Eq. (E.15) then reduces to LeeB Z.. S(a, Du a. B) O, and follows as the contraction of a symmetric map with an anti-symmetric one: for each term appearing in the sum, it's opposite also appears. Take a B. If Zu.B Ø, there is nothing to show. Assume then that 2.. # Ø. Each B ε za contributes with a term S(a. Du(r, B) to the sum. However, B a implies that 2g,8, since a < B is symmetric and both and ß belong B. Hence each B E 2,.8 contributes the sum also with a term S(B, a) Du(BB. a) -(a. Du(a,, e, B), canceling out the previous contribution.
Example E.3 (Antisymmetric contraction revisited). Consider again the deviations of Fig. (right), this time assigning positive weight Pio, to each player's action. Let B (BLA, BRA, BRP, TRA, TLP). The condition given by Eq. (E.14) for B to be club assuming that the game is harmonic yields the following system of incqualities (one for each a E B such that 2 # Ø):
BLA (-(aa) <0
BRA : NI. pre (-((b) <0
(E.17)
BRP Hab < 0
TRA : (B(-c) <0
This system of inequalities admits no solution the domain Pia, > 0, a, b, Indeed,
Evre [I lle Miar] EpeZu u(a. B) H
+ MaHnMll<aab
(E.18)
+ |TtuRHal--BS
+ MEMAHAlMLL + MIC- Upb] 0,
in agreement with Eq. (E.15), making it impossible for the system (E.17) to admit solution.
E.4. No club subfaces in harmonic games. We conclude this appendix by extending Theorem E.1 to the case of mixed strategies. To set the notation we recall the definition of the following standard objects:
Definition E.2. Given the mixed extension A(T) of finite game I A...Au), the support of any xi E X is supp(x;) = {a; Aj Nia, 0}. Given family (B; S AdieN, face spanned by B = lix B; is
Sg
I (x E X supp(x;) s B,) IeN
I SB, I&N
(E.19)
A subface of X' (sometimes also referred to proper face) is proper subset of X' that can be written in the form (E. for some (B; C A.)ieN. Moving on, the better reply correspondence (E.6) extends to mixed strategies as the correspondence
btr: X 3 X' define by
(xr
I (x E Xi u(x,,x=)) u(x))
(E.20)
ieN
and we say that a subface S of X is closed under better replies (club) if btr S S for all E S.
Corollary E.2. Assume A(T) the mixed extension of a finite harmonic game I = I(N. A. u). Then no subface of X can be closed under better replies.
33

---

The Impact of Uncertainty on Regularized Learning in Games
Proof. Let Sg c X' be a subface of X' with spanning set B = IIIEN B, A, with B A, for all e N. Our claim follows as consequence of Theorem E.I, and the fact that
Sg club = B is club.
(E.21)
Indeed, assume that Sy is club. Then for any x E Sy and any x' E X, if e btr(x), that is, if (T((x,,,xi)) 2 (x(x) for all i N, then x' Sg. For any a E B, this holds true in particular the mixed profile a E SB such that supp(a;) = {a,), i... at the mixed representation of the pure profile a E B, in which each player plays the strategy a; with probability 1. Hence, for any E B and any x' X, if un (x, a-1) 2 (a)a)) for all i E N, then x' E Sg. With the same reasoning, this holds true in particular at the mixed representation B E X' of any B E A: for any a E B and any ß X, if (;;B;, ar-) u;(ar) for all i E N, then f E Sg, meaning that supp(B;) 3 B, i.c., Bi E B,
As consequence, we can now prove Theorem 6, which restate here for ease of reference: Theorem 6. Suppose Assumption 3 holds. If the game is harmonic, there is no proper face S of X that stochastically asymptotically stable under (S-FTRL).
Proof. By Theorem 2, stochastically asymptotically stable subfaces of X' are necessarily closed under better replies. Corollary E.2 shows that harmonic game do not admit any such faces, which completes our proof.
F Omitted proofs from Section 5
In this appendix, we prove the various results stated in Section 5 regarding the fragility of deterministic recurrence in noisy environment. As mentioned in the main text, the primary object of interest of this section will be the energy function
H(x) Em, iEN
(F.1)
where m and q denote respectively the mass and the strategy center of a fixed harmonic game r, and D, denotes the standard Bregman divergence generated by the regularizer function h;-
In fact, will not directly work with the energy function H through its "primal" definition Eq. (F.1), but instead use its "dual" representation
Fly) Σ FiFiggi.900 y1) iEN
(F.2)
where F; denotes the Fenchel coupling defined in Appendix A. In particular, Proposition A.2 implies that H(x) = Fly) whenever x (yy) which allows this change of function. This choice of representation greatly simplifies the computations, as it avoids the need to an explicit expression of trajectories in X. In the deterministic setting for instance, it provides quick proof that the energy H (resp. F) is constant of motion for (FTRL) in harmonic games (cf. Appendix E).
F.1. Proof of Theorems 4 and 5. The main idea underlying the proofs of Section 5 is to show that the infinitesimal generator L of (S-FTRI) applied to is positive on y. To be more precise, recall from Appendix B that
+En [ (F( ds
E,[F(Y())= = Fly) + By
(F.3)
for every 1 2 0, so - (r))( is increasing whenever CF is anywhere positive. The interesting aspect is that this result also holds when is replaced by any (almost surely bounded) hitting time r (see Lemma B. enabling us to obtain even finer results beyond just the average increase of the energy function
For this reason, we begin with a preliminary lemma allowing us to accurately estimate this quantity in harmonic games: Lemma F.I. For every harmonic game I and every y E y.
2-2
min
m; (Jac Qi(y:)) s LF
max 2
m; tr(Jac (v)))
(F.)
2
N
N
34

---

The Impact of Uncertainty on Regularized Learning in Games
Proof. Let fix the player's index i N. By It''s formula, we have
O (q1. (Y) Yıpl dFi(qi, Y,) = (grad Ki, Eup dy.
(F.5)
dQie (Y)) agd) + dēi
=Q, - qr, 9: (X))
Σap op
(F.6)
dyp
(X; - q: 0; (X)) tr(Jac (x)d dE;
(F.7)
where Σ = 0,0% and & denotes a square-integrable martingale starting from 0. Consequently, we get
CF(y) = Σ iEN
m L.F((qi
Σ ieN
m, tr(Jcc (x))
(F.8)
for every E y and x = Q(y).
Now, notice that the eigenvalues of each Σ; are all included the interval [o m by Assumption on the diffusion matrix. Furthermore, Jac (y) Hess hy (y) symmetric and positive semi definitee for any y e y (this is consequence of h" being convex and of Proposition A. By classical results of linear algebra, we therefore obtain
i tr(Jac (v)) s tr(Jac ( s max tr(Jac 2i(y)))
(F.9)
for every player i e N, which finishes the proof when combined with Eq. (F.8).
With this lemma in hand, we are now ready to prove every results stated in Section 5.
Proof of Theorem 4 (H- - oo in average). From Lemma F.1 and the convexity of h, it is evident that LF(y) 2 0 for every y E y. According to Eq. (F.3), it then implies that + B[F(Y is a non-decreasing function. In particular, it admits (possible infinite) limit. Assume for a moment that this limit is finite. Then, Eq. (F.3) and Fubini's theorem would imply that J (s) should be finite almost-surely. But as CF is positive for every E A, this is possible only (F) - 0 almost-surely. Due to the lower bound of Lemma F.I, would mean that tr ())); - 0 for every player E N, but this can only occurs if X()) (r) converges to the boundary bd X' (indeed, this quantity strictly positive the relative interior of X due to Lemma A.I). However, this leads contradiction because F(Y()) H() explodes to infinity whenever (t) converges the boundary. Consequently, the limit of E[F(Y(r))) is necessarily infinite as required.
Proof of Theorem 5. 1. Let K. be compact subset of X' disjoint from bd(X). Due to Dynkin's 's lemma (Lemma B.1) and Lemma F.1 we have, for every fixed / 2 O,
2=2
TKA
M(K) 2 E.[F(Y(TX A ()) F(y)+ +
min
E
tr(Jac (.({(s)) ds
(F.10)
2
30
ieN
2 F(y) + min
(AC) Ex(Te A1
(F.11)
2
where
M(K) == H : <0,
(F.12)
mIC) == min Σ ieN
m; tr(Jac Qi(y:)) x Q()).x( 1W).xeK
(F.13)
The finiteness of (IC) follows from properties of the Bregman divergence, while the positiveness of m (IC) comes from Lemma A.1. Rearranging the inequality and taking the monotone limit as co, we therefore obtain
E, [x] s M(K) H(x) oo;
(F.14)
o min
hence the mean escape time finite as required.
35

---

The Impact of Uncertainty on Regularized Learning in Games
2. From Lemma F.1 and the fact that by is both convex and L-smooth (ef. Appendix A), we obtain
Lo
0 S (F()) S
min
Σ IEN
m;
m.
(F.15)
2
In particular, it implies that F(Y(1)) (resp. H()())) is a submartingale (this is a consequence of the martingale characterization of infinitesimal generators, cf. Eq. (B.2)). Let us consider the compact subset K = {x E X H(x) 2 M) and assume that Ex [Tc] < for some initial condition x E ri. such that (x) 2 + 1. Then, Dynkin's lemma and Eq. (F.15) yield
(XT A AD)] & H(x) [Tx Ar] & H(x) K [ < <o.
(F.16)
Consequently, the stopped process (HT 120 is a uniformly integrable submartingale. Doob's martingale convergence theorem [29, Theorem 3.15 p.17] therefore implies that
[(x) S [H(((((TK A O)] E.(H((((T)) s M,
(F.17)
which contradicts the fact that Hxx) 2 M + 1. We therefore deduce that [T<] = co for some x E K, so trajectories of (S-FTRL) cannot be positive recurrent in the sense of Definition 3. particular, the mean escape time is also infinite for any compact subset containing (2)) due to the transienceerecurrence dichotomy of Theorem 7.
Proof of Theorem 4 (Hitting time estimate). The proof follows directly from Eq. (F.14) with the particular choice K. = {x X Hx)) s M), which leads to (KC) = M and m(C) = a e(M).
Proof of Corollary 4. Let us consider the entropic kernel (z) = z log and let us drop the player's index i for moment. A standard computation shows that, in this case, the Bregman divergence D(q.x) is equal to the Kullback-Leidh divergence between 9 and xx given by
(L, Σ. qa log
qa
h(q))
E., aa logxa.
(F.18)
Xa
On the other hand, computing the Jacobian matrix of the logit map Q leads to
tr(Jac Q(y))
Σ. a xa xx).
(F.19)
Applying the inverse exponential function on Eq. (F.18) then yields
e D(q.x) = =e- -h(q) II. xa = h(a))
[1l Nu 9¹
Na
Na qa
s se- (1 Ne q'
(F:20)
where q¹ min, aa > O. Furthermore, we can upper bound 11
xy 1,,,,
n(n-1) Ensg 1, n(n - 1) Σ arg XaxB
n(n 1) Σ. xa - xxa).
(F:21)
where the the penultimate inequality follows by taking xy S 1 for every y & {ar, B), and the last equality uses the simplex constraint Σ. Xa I. Putting this bound back into Eq. (F.20) therefore leads to
D(q.9) h [n(n 1)] Σ. xa xa(1 - xxa) c(q) tr(Jac Q(y)).
(F.22)
with c > 0 constant depending only on q and n.
Adding back the players' indices, we define q² min of and c(q) max, Ci (i)) which allows us write
mi tra Oi(y))) c(q) IeN
Σ
Σ me D(((,)) > m c(g)
e my Ei (q
=cje -2H
(F.23)
ieN
where m = Ei m;, C1 and C2 are positive constants, and the penultimate inequality holds thanks to the convexity of e-x Accordingly, if ((q.x) z M, then
Σ F
mi tra Qi()))) cie -cM
(F:24)
36

---

The Impact of Uncertainty on Regularized Learning in Games
and, therefore, the same lower bound also holds true for sMM). Substituting this bound inside the hitting time estimate of Theorem then yields the desired result, accordingly that
M
Ex
[MM]
ecM
(F.25)
σ
min
for some positive constant O.
E22 Comparison with related works: the pure noise setup. To conclude this appendix, we discuss the main differences between the behavior of (S-FTRL) and those of (SRD-PI) and (SRD-AS) in harmonic games. In particular, we aim to clarify why the Itō correction term in (S-FTRL) is the one that preserves most of the rationally admissible properties of the deterministic case.
For this purpose, we focus on the pure noise regime, i.e., the case where v across all X (which, by definition, is also a trivial harmonic game). In this setting, the system's 's behavior is entirely determined by the noise and the corresponding Itô correction term, making it suitable approximation for analyzing the impact of noise (S-FTRL).
To simplify the analysis, we consider uncorrelated noise where each dia, is independent of the players' strategies. Under these assumptions, the dynamics of (S-FTRL) reduce to the following form:
Yia, (1) Fia, Wia. (1), (1(1) = (1()(()).
(FTRL-N)
Since Q-1 is generally neither continuous nor single-valued, the behavior of X(1) cannot be inferred directly from that of (()). Instead, we must map (1) to the space of payoff differences Z(cf. Appendix B), where (FTRL-N) then takes the form:
Zi (1) Dio, Wia, (1) Gíd, Wia (f); (1() = (z)
(F.26)
for every a; à where à A₁ is a fixed benchmark action and Q denotes the is continuous and single-valued by Lemma B.3). In particular, the long-run behaviors of (r), i.e., the classification of those as either transient or recurrent, are completely the same as that of a (correlated) Brownian motion.
mirror map (whose inverse
This identification explains why the deterministic stability properties of (FTRL) largely persist under any level of noise: in terms of players' strategies, the induced noise essentially behaves like a standard Brownian motion and therefore negligible compared to most drifts, as justified by the strong law of large numbers (Lemma B.5).
Additionally, this also explains why positive recurrence is impossible in harmonic games: results in trajectories of (S-FTRL) resembling ones of (correlated) Brownian motion. Since the effective dimension of such a process is at least (and finite games require at least 2 players), it generally cannot exhibit positive recurrence.
the absence of significant drift
To illustrate these points, consider two specific examples of pure-noise settings:
Example F.4 (2 x 2 zero game). Let be a 2 x zero game, i.e., a game with two players each having two strategies, and take all noise coefficients equal to for simplicity. In this case, we get
(1) Win (1) - Wi Bi(())
1
(1)
(F.27)
V2
1
Zz(1) W2an (1) (2)a(t) B2(1)
(F.28)
v2
where B()- = (1) B2))) is a standard 2-dimensional Brownian motion. Accordingly, Z(1) is proportional to 2- dimensional Brownian motion, which is known to be null recurrent from classical results (see e.g., Examples 3.11 and 3.12
of [32]). Accordingly, x() must also be null-recurrent by Lemma B.3.
Example F.5 (2 x 2 zero game). Let I be a x x zero game, with then three players each having two strategies, and all noise coefficient equal 1. Similarly the previous example, we therefore obtain that Z(1) 1 B()) for B() 3-dimensional Brownian motion. Such a process is transient, so X(r) must also be transient.
v3
The previous examples highlight an important observation about (S-FTRL) in harmonic games: although trajectories converge on average toward the boundary by Theorem 4, this is not enough to distinguish between convergence with probability one (transience) and infinite oscillations in the strategy space (null recurrence).
37

---

The Impact of Uncertainty on Regularized Learning in Games
With that in mind, let now examine the different stochastic differential equations proposed study random perturbations the replicator dynamics (RD) (and more generally in (FTRL)), namely the stochastic replicator dynamics with aggregate
shocks (SRD-AS) [14, 21, 24, 28] and the stochastic replicator dynamics of pairwise imitation (SRD-PI) [10, 17, 20, 46].
Still in the pure-noise setting and with slight abuse of notation, both of these dynamics can be recast within the framework of (S-FTRL) (at least for the entropic regularizer from Example 1) as:
1i (1) = Jim 2
+ Tia Wi, (1) (1)
(FTRL-AS-N)
and
ay a = - 1 2x (1) joia dr Dia dWia (t); (1) = Q,(y,"
(FTRL-PI-N)
respectively, Mapping both (FTRL-AS-N) and (FTRL-PI-N) into the payoff differences space 2 then yield
Zia, (1) =- -ia (ta)r+ r+ Gia, Win Jid, Wia,
(AS-Z)
and
(1) -22 (1) XPe (1) di Tia, dWia, (1) Giá, dWia, (1).
(PI-Z)
To highlight their differences, we discuss each of these dynamics in separate examples.
Example F6 (Stochastic replicator dynamics with aggregate shocks). Notice that the drift in (AS-Z) is deterministic and only depend on the relative difference of noise magnitude. By the strong law of large numbers (Lemma B.5), we therefore get the following classification of its behaviors:
1. If of ia, F.. for some ai # âi then Z (r) 00 (a.s.). and so x (t) (a.s.): trajectories are transient.
2. If o <o. for some a; à; then 2,A5 (t) co (a.s.), and so X (1) (a.s.): trajectories transient.
3. If Dia o; for every a E A. then Z,AS(1) o, (Wia, (1) Wia, (f)): same behavior (FTRL-N).
This classification can also be recovered from results proved in [24, 28] concerning the extinction of dominated strategies and stability of equilibria under (SRD-AS).
Example F.7 (Stochastic replicator dynamics of pairwise imitation). Note that if xP!(1) remains close enough to a pure strategy, say å; then the drift of (PI-Z) is strictly decreasing with order for every 0; # å; In other words, trajectories have a strong tendency to drift toward pure strategies. Moreover, similar argument to the one developed in the proof of Theorem then shows that each pure strategy is stochastically asymptotically stable under (FTRL-PI-N). As a result, trajectories are always transient and attracted strongly toward pure strategies. This aligns with the findings of Engel & Piliouras [17] in two-player zero-sum games, where pure strategies are attractive in terms of their invariant measures, and trajectories converge to the boundary regardless of the noise level.
From the previous examples, we conclude that both (SRD-AS) and (SRD-PI) exhibit strong bias towards the strategy boundary, even when the payoffs do not favor any particular outcome. In contrast, (S-FTRL) does not show such tendencies and behaves as we would expect in a pure noise setting, namely, similarly to white noise (Brownian motion).
38


Reviews:
[{"review_id": "CXyjzXR7BO", "reviewer": "Reviewer_BYeZ", "summary": "The authors consider the continuous time limit of the FTRL dynamics under noisy observations of game payoff matrixes and prove that, unlike in the noiseless case, the dynamics converge to pure Nash, along with several other results.\n\n## Update After Rebuttal\nThe authors answered my questions quite well -- I might suggest adding in parts of said answer to the discussion section of the paper, as space permits.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer,\n\nThank you for your time, positive evaluation and encouraging words! We reply to your remarks and questions below:\n\n> I'm mostly familiar with the discretized, discrete-time version of FTRL. Could you comment on how your results would transfer to this setting? Like, with noisy payoffs, should I expect discrete-time FTRL to avoid circling equilibria and only converging on average?\n\nThis is a very interesting question, thanks for raising it!\n\nIn a nutshell, it depends.\n\nTo begin, there are several factors that come into play - whether FTRL is run with a constant or vanishing step-size / learning rate, the origin of the noise in the algorithm (e.g., pure payoff vector information versus bandit, payoff-based feedback) and, of course, the specific result under study.\n\n- For games with \"circling FTRL dynamics\" (e.g., zero-sum games with a fully mixed equilibrium, or harmonic games) our intuition is as follows:\nIf the algorithm is run with a vanishing step-size, it will most likely converge to some random (Bregman) distance from the equilibrium / center of the game, but it won't necessarily return close to where it started.\n- If the algorithm is run with a constant step-size, the picture is less clear: some first results in [1] for the exponential weights algorithm with pure payoff vector information suggest that the algorithm converges to the boundary in two-player zero-sum games. We conjecture that an analogue of Theorems 1 and 5 also holds in this setting, but this is likely a paper in itself.\n\n[1] Bailey et al. \"Stochastic Multiplicative Weights Updates in Zero-Sum Games\"\n\n\n> I was wondering if there is anything interesting one could say about that flavor of approach [optimism and high-resolution limit] in comparison to the ideas explored here.\n\nAgreed: in discrete time with full information (that is, perfect observations of the players' mixed payoff vectors), optimism can mitigate non-convergence in certain games where the continuous-time dynamics are Poincaré recurrent (such as two-player zero-sum games or harmonic games). However, this gain only manifests itself in the deterministic case; in the stochastic case, optimistic methods (and other extrapolation-based methods, like extra-gradient and its variants) fail to converge altogether and, as you say, only time-averages remain convergent. Because of this, it does not seem that the properties of FTRL would be particularly different from optimistic FTRL in the presence of noise, because the noise in the process would overshadow the finer, smooth structure of optimistic FTRL. For similar reasons, a higher-resolution approximation would not help either, because the noise would cancel any gain obtaine from using a finer discretization scheme.\n\n---\n\nThank you again for your time and encouraging words - please do not hesitate to reach out if you have any further questions!\n\nKind regards,\n\nThe authors", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "Nope.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "Nope.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "(+) I thought this paper was exceptionally well written -- even as someone without a strong background in the area, I could understand the high-level theoretical take-aways and implications thereof. Kudos to the authors on this -- I often struggle to do this myself on papers this theoretical :).", "other_comments_or_suggestions": "N/A", "questions_for_authors": "These questions are not particularly important but I'd be curious for responses if the authors have time:\n\n1) I'm mostly familiar with the discretized, discrete-time version of FTRL. Could you comment on how your results would transfer to this setting? Like, with noisy payoffs, should I expect discrete-time FTRL to avoid circling equilibria and only converging on average?\n\n2) When I think of the discrete-time FTRL dynamics, people will often use ideas like optimism to avoid the player strategies circling the Nash equilibrium (i.e., only converging on average rather than for the last iterate). My understanding is that the continuous-time analog of these results requires taking some \"high-resolution\" limits (e.g. https://arxiv.org/abs/2112.13826). I was wondering if there is anything interesting one could say about that flavor of approach in comparison to the ideas explored here.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MoW8BgcTuK", "reviewer": "Reviewer_57JY", "summary": "This paper investigates the impact of uncertainty on the dynamics of the Follow-The-Regularized-Leader (FTRL) algorithm. The author first shows that under uncertainty, the FTRL algorithm approaches a pure strategy. Then, the author demonstrates that pure strategies are the only possible limit points of the stochastic FTRL. Additionally, the paper proves that the recurrent behavior observed in FTRL dynamics under deterministic settings disappears when uncertainty is introduced.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer,\n\nThank you for your time, input, and positive evaluation! We reply to your remarks and questions below:\n\n>I am curious about the difference between Corollary 3, Theorem 3, and the results presented by [19]. Do Corollary 3 and Theorem 3 generalize their results to broader settings?\n\nRegarding Theorem 3, the general setting of [19] and our own are qualitatively similar - regularized learning with stochastic feedback - but quantitatively quite different - discrete vs. continuous-time, a decreasing step-size in [19], different assumptions on the noise, etc. Thus, even though Part I of Theorem 3 of our paper and the corresponding result of [19] involve similar notions - stochastic asymptotic stability - they are otherwise completely distinct as results.\n\nIn addition, the extension of the discrete-time analysis of [19] to the continuous-time setting of our paper is far from trivial. One major difficulty that arises has to do with the way noise is injected into the system, and which plays a crucial role in the long-run behavior of the dynamics . For instance, the stated result breaks down completely when considering the stochastic replicator dynamics with aggregate shock (SRD-AS); the stochastic replicator dynamics of pairwise imitation (SRD-PI), for which stable points of trajectories usually need to be strict Nash equilibria in a noise-adjusted payoff field, cf. [21, 37].\n\nIn a similar vein, Corollary 3 and the second part of Theorem 2 are totally new results compared to [19]: Instead of characterizing only (stochastically asymptotically) stable strategies as in [19], those results also identify which states can appear as (possibly non-stable) limits of the stochastic dynamics. In words, **pure Nash equilibria are the only strategies appearing as pointwise limits of (S-FTRL)**, and among these equilibria only those that are strict can be (and are) stochastically stable.\n\n> (...) as far as I understand, it is well known that FTRL satisfies the no-regret property even in the stochastic setting. I am wondering if this fact contradicts the derived theorems and corollaries in the paper.\n\nAgain, this is a matter of the general setting of each paper: the no-regret property of FTRL is, indeed, classical in discrete time; in continuous time however, the situation is much more complicated, and the only no-regret result that we're aware of is [10], which involves a vanishing learning rate or noise that becomes vanishingly small over time. Both of these postulates are orthogonal to our paper, where we assume positive noise covariance (Assumption 1), which, in turn, rules out the \"vanishing noise\" framework..\n\n> (...) it’s unclear to me how the harmonic center is determined in a two-player zero-sum game setting.\n\nA generic two-player zero-sum game is not harmonic; however, if it admits a fully mixed Nash equilibrium, then it is harmonic (cf. Corollary E.1). In that case, the harmonic center coincides with the Nash equilibrium and can be calculated in the same way. \n\n> In the discrete-time setting, it might be possible to control the noise level by adjusting a learning rate sequence. By doing so, is there any possibility of preventing the FTRL dynamics from approaching a pure strategy?\n\n\nGreat question, thanks for raising it! We conjecture that adding a slowly decreasing learning rate as per [10] (decreasing to zero slowly enough over time) would mitigate the escape to the boundary, so we would expect the result that \"any player's choices approach pure strategies\" to be false in this setting. However, because of the extra terms introduced in the analysis by Itô's formula, the calculations are far from trivial and require a drastically different approach.\n\nConsidering a learning rate also opens a vast array of other interesting non-trivial questions, such as what happens to the \"non-recurrence\" results of Section 5 or what can we deduce on the discrete-time FTRL algorithm. As those questions typically require different and more precise tools than the ones we have used here (the stochastic dynamics becoming time-inhomogeneous due to the presence of a time-dependent learning rate), we have chosen to not explore those directions in this paper, and to defer such considerations to future work.\n\n---\nWe thank you again for your time and positive evaluation! Please let us know if any of the above points is not sufficiently clear.\n\nKind regards,\n\nThe authors", "claims_and_evidence": "The claims are generally supported by mathematical proofs.", "methods_and_evaluation_criteria": "Since FTRL is a well-studied algorithm for learning in games, it is meaningful to investigate its behavior under uncertainty.", "theoretical_claims": "The proofs employ standard techniques for stochastic differential equations. While I did not verify all of the proofs in the paper, the presented theorems and corollaries appear rigorous and align with my intuition.", "experimental_designs_or_analyses": "The empirical results on (twisted) matching pennies, entry deterrence, and harmonic games are provided.", "relation_to_broader_scientific_literature": "The theoretical results seem novel compared to the existing literature. However, I am curious about the difference between Corollary 3, Theorem 3, and the results presented by [19]. Do Corollary 3 and Theorem 3 generalize their results to broader settings?\n\nFurthermore, as far as I understand, it is well known that FTRL satisfies the no-regret property even in the stochastic setting. I am wondering if this fact contradicts the derived theorems and corollaries in the paper.", "essential_references_not_discussed": "The paper appropriately cites relevant prior works on learning in games under the noisy feedback setting.", "other_strengths_and_weaknesses": "Please see “Other Comments Or Suggestions”.", "other_comments_or_suggestions": "Since I’m not familiar with harmonic games, it’s unclear to me how the harmonic center $q$ is determined in a two-player zero-sum game setting.\n\nFurthermore, in the discrete-time setting, it might be possible to control the noise level by adjusting a learning rate sequence. By doing so, is there any possibility of preventing the FTRL dynamics from approaching a pure strategy?", "questions_for_authors": "Please see “Other Comments Or Suggestions”.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GZz74atSyZ", "reviewer": "Reviewer_yDto", "summary": "This work investigates the impacts of the noises on the observed payoffs when applying continuous-time FTRL for game solving. The main conclusions are that every player will reach an almost pure strategy in finite time and the limit of the dynamics of the continuous-time FTRL will converge to the pure Nash equilibria.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer,\n\nThank you for your time, input, and positive evaluation! We reply to your remarks and questions below:\n\n> I would be curious about proof idea and basic techniques that lead to the main results (…) I'm a bit surprised that these results weren't discovered in previous work. Therefore, I think it will benefit the readers a lot if the proof sketches and techniques of the main results are given.\n\nWe also very much aligned with the reviewer's opinion that more extensive proof sketches would be of benefit ot the reader, but we were unfortunately limited due to space constraints. That said, we will be happy to use the first revision opportunity (and the extra page provided) to add an overview of the technical apparatus and trajectory required to prove our results; note that all the details are already provided in the appendix.\n\n> If I understand correctly, the results in this work hold in the self-play setting, where each player adopts the same FTRL algorithm. Can the noise $M_i(t)$ on the LHS of Line 187 account for the case where some players are potential adversaries?\n\nThe \"adversarial\" setting that you describe would be more aptly captured by making the evolution $X_i(t)$ of certain players arbitrary. The noise $M(t)$ has a lot of statistical features, so it cannot simply be replaced by an arbitrary stream of payoff-like observations.\n\n> Does the conclusion (c) on the RHS of Line 431 imply the conclusion (a) and (b) on the RHS of Line 429-431? That is, can we say “the strategy of every player reaches an almost pure Nash equilibrium in finite time” and “every player’s limit set contains a pure Nash equilibrium strategy”?\n\nTo clarify, the formal version of conclusions (a), (b), (c) is as follows:\n- (a) For every neighborhood $U_{i}$ of pure strategies for player $i$, there exists a finite (random) time $t$ such that $X_{i}(t) \\in U_{i}$ (**Theorem 1**).\n- (b) The (random) limit set $\\lbrace x_{i} \\in \\mathcal{X_{i}} : X_i(t_{n}) \\to x_{i} \\text{ for some sequence } t_{n} \\nearrow \\infty  \\rbrace$ contains (at least) a pure strategy (**Corollary 1**).\n- (c) If there exists a strategy $x^{\\*}$ such that $X(t) \\to x^{\\*}$ with positive probability, then it is necessarily a pure Nash equilibrium (**second part of Theorem 3**).\n\nAccordingly, (c) only make sense for trajectories that _do converge_ (in a pointwise sense), whereas conclusions (a) and (b) hold for every trajectories even those that do not converge to a point (for instance, those that wander indefinitely in the state space or those that converge only toward some subface of the boundary). As such, (c) does not imply any of the other two conclusions, and it is thus not possible to conclude that \"the strategy of every player reaches an almost pure Nash equilibrium in finite time\" nor that \"every player’s limit set contains a pure Nash equilibrium strategy\" (in fact, there may not even be any pure Nash equilibrium in some game, so those conclusions cannot hold in full generality).\n\n---\nWe thank you again for your time and positive evaluation! Please let us know if there are any lingering questions in the above.\n\nKind regards,\n\nThe authors", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I did not check the correctness of the proof details.", "experimental_designs_or_analyses": "Not applicable.", "relation_to_broader_scientific_literature": "To my knowledge, the findings are new and technically valuable.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "**Strengths**\n1. **Theoretical Results**: The theoretical results in this work seem to be new and might be of great interest to the community.\n2. **Writing**: This paper is generally well-written.\n\n**Weaknesses**: If any, I would be curious about the proof idea and basic techniques that lead to the main results in this paper, which do seem to be discussed in the main body of the paper. I think the results in this work are fundamental to the literature so I'm a bit surprised that these results weren't discovered in previous work. Therefore, I think it will benefit the readers a lot if the proof sketches and techniques of the main results are given.\n \nOverall, I think the results in this paper are valuable, but I am not fully familiar with the techniques of continuous FTRL, so I would recommend a weak acceptance of this work while maintaining a low confidence level.", "other_comments_or_suggestions": "NA.", "questions_for_authors": "1. If I understand correctly, the results in this work hold in the self-play setting, where each player adopts the same FTRL algorithm. Can the noise $M_i(t)$ on the LHS of Line 187 account for the case where some players are potential adversaries?\n2. I am a bit confused about some statements about the main results. Does the conclusion (c) on the RHS of Line 431 imply the conclusion (a) and (b) on the RHS of Line 429-431? That is, can we say “the strategy of every player reaches an almost pure Nash equilibrium in finite time” and “every player’s limit set contains a pure Nash equilibrium strategy”?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9lpRdyL94c", "reviewer": "Reviewer_fPnc", "summary": "The paper examines the behavior of the stochastic FTRL dynamics in games, in which the usual FTRL algorithm is randomly perturbed. It provides a general characterization: every player reaches an almost pure strategy in finite time. This stands in contrast to the deterministic setting. A consequence of the previous result is that the only possible limits of stochastic FTRL are pure Nash equilibria. The final main result shows that a span of pure strategies is attracting if and only if it is closed under better replies, which mirrors some earlier results in the deterministic setting.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer,\n\nThank you for your time, input, and overall appreciation, both in terms of results and presentation! We reply to your remarks and questions below:\n\n> Theorems 2 and 3 mirror some existing results from the deterministic setting, but are still interesting and new.\n\nIndeed, Theorems 2 and 3 extend the result by [15] on the asymptotic convergence of FTRL to strict Nash equilibria. However, as you rightly point out, generalizing this result to the stochastic setting is far from straightforward. The analysis requires substantially different techniques and introduces non-trivial challenges that do not arise in the deterministic case. In particular, while carrying on those results to our stochastic FTRL setting works as intended, this is not the case at all when considering different (yet rational) stochastic models. For instance, they are not true for the stochastic replicator dynamics with aggregate shocks (SRD-AS) nor for the stochastic replicator dynamics of pairwise imitation (SRD-PI); both of which that can be seen as stochastic versions of the (continuous-time) multiplicative weights algorithm.\n\n> (..) after (8) there should be a comma\n\nWill fix, thanks for spotting it!\n\n> In section 5, it is claimed that harmonic games is a much broader class than zero-sum games; but, if I am not missing something, this is not really true.\n\nTo be clear, in the context of Poincaré recurrence (Section 5), any reference to zero-sum games should be understood as shorthand for “two-player zero-sum games with a fully mixed equilibrium”, or $\\text{2PZS}\\*$ for brevity. The claim that harmonic games form a significantly broader class than $\\text{2PZS}\\*$ simply referred to the fact that, while every $\\text{2PZS}\\*$ game is harmonic (cf. Corollary E.1), harmonic games allow for any number of players, and the players' payoffs need not sum to zero. We will make this point more explicit, thanks for flagging it.\n\n---\nWe thank you again for your time and positive evaluation! Please let us know if there are any lingering questions in the above.\n\nKind regards,\n\nThe authors", "claims_and_evidence": "All claims made in the paper are sound and supported by clear evidence.", "methods_and_evaluation_criteria": "Not applicable; the paper makes a theoretical contribution.", "theoretical_claims": "All claims appear to be sound; I did not find any notable issues.", "experimental_designs_or_analyses": "Not applicable; the paper makes a theoretical contribution.", "relation_to_broader_scientific_literature": "The paper is part of a broader effort to characterize the behavior of natural learning algorithms in multi-player games. While most prior work has focused on the deterministic setting, this paper makes progress on the stochastic setting.", "essential_references_not_discussed": "All relevant references have been discussed; I did not identify any notable omission. Overall, the paper adequately places its contributions in the context of the related work.", "other_strengths_and_weaknesses": "Overall, the paper makes concrete contributions to a fundamental problem in multi-agent systems. It provides a comprehensive characterization of the behavior of stochastic FTRL in the continuous-time setting. Perhaps the most surprising result is Theorem 1, as it represents a departure from the deterministic setting. The main message here is very clear and interesting: stochasticity favors pure strategies. Theorems 2 and 3 mirror some existing results from the deterministic setting, but are still interesting and new. From a technical standpoint, the paper is highly non-trivial. The writing and organization of the paper are also exemplar, and it was a joy to read the paper.", "other_comments_or_suggestions": "- A minor typo: after (8) there should be a comma. \n\n- In section 5, it is claimed that harmonic games is a much broader class than zero-sum games; but, if I am not missing something, this is not really true.", "questions_for_authors": "No further questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: All reviewers appreciate the contributions of the paper.
Decision: Accept (poster)