No-regret Learning in Harmonic Games: Extrapolation in the Face of Conflicting Interests
Authors: Davide Legacci
Panayotis Mertikopoulos
Christos Papadimitriou
Georgios Piliouras
Bary Pradelski
Venue: NeurIPS 2024 spotlight (2024)
Keywords: learning in games
no-regret algorithms
FTRL
harmonic games
Poincaré recurrence
Primary area: algorithmic_game_theory
TL;DR: We consider a flexible algorithmic template (FTRL+) that guarantees convergence to Nash equilibria at constant individual regret in a class of N-player adversarial games.

Abstract: The long-run behavior of multi-agent online learning -- and, in particular, no-regret learning -- is relatively well-understood in potential games, where players have common interests. By contrast, in general harmonic games -- the strategic complement of potential games, where players have competing interests -- very little is known outside the narrow subclass of $2$-player zero-sum games with a fully-mixed equilibrium. Our paper seeks to partially fill this gap by focusing on the full class of (generalized) harmonic games and examining the convergence properties of "follow-the-regularized-leader" (FTRL), the most widely studied class of no-regret learning schemes. As a first result, we show that the continuous-time dynamics of FTRL are Poincaré recurrent, i.e., they return arbitrarily close to their starting point infinitely often, and hence fail to converge. In discrete time, the standard, "vanilla" implementation of FTRL may lead to even worse outcomes, eventually trapping the players in a perpetual cycle of best-responses. However, if FTRL is augmented with a suitable extrapolation step -- which includes as special cases the optimistic and mirror-prox variants of FTRL -- we show that learning converges to a Nash equilibrium from any initial condition, and all players are guaranteed at most $\mathcal{O}(1)$ regret. These results provide an in-depth understanding of no-regret learning in harmonic games, nesting prior work on $2$-player zero-sum games, and showing at a high level that potential and harmonic games are complementary not only from the strategic but also from the dynamic viewpoint.

No-Regret Learning in Harmonic Games: Extrapolation in the Face of Conflicting Interests
Davide Legacci'
Panayotis Mertikopoulos
Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG 38000 Grenoble, France
alavidelloaaccl.paayyttt mertikopoulos) Sunioo-sssnnnvvunneeueeee Duniv-grenoobl-llpes...
Christos Papadimitriou
Georgios Piliouras Google DeepMind London, UK gpil@google.com
Columbia University, NYC, &
Archimedes/Athenna RC, Greece
christos@columbla.dde
Bary Pradelski
CNRS, Maison Française d'Oxford
2-10 Norham Road, Oxford, OX2 6SE, United Kingdom bary Baryppradelskiocnrs.ft
Abstract
The long-run behavior of multi-agent learning and, in particular, no-regret learn- ing is relatively well-understood in potential games, where players have aligned interests. By contrast, in harmonic games the strategic counterpart of potential games, where players have conflicting interests very little is known outside the narrow subclass of 2-player zero-sum games with fully-mixed equilibrium. Our paper seeks partially fill this gap by focusing on the full class of (generalized) har- monic games and examining the convergence properties of follow-the-reguaaiii leader (FTRL), the most widely studied class no-regret learning schemes. As a first result, we show that the continuous-tin dynamics of FTRL are Poincaré recurrent, that is, they return arbitrarily close their starting point infinitely often, and hence fail to converge. In discrete time, the standard, "vanilla" implementation of FTRL may lead even worse outcomes, eventually trapping the players in a perpetual cycle of best-responses, However, if FTRL. is augmented with suitable extrapolation step which includes as special cases the optimistic and mirror-prox variants of FTRI- we show that learning converges to Nash equilibrium from any initial condition, and all players are guaranteed at most O(1) regret. These results provide an in-depth understanding of no-regret learning in harmonic games, nesting prior work on 2-player zero-sum games, and showing at a high level that harmonic games are the canonical complement of potential games, not only from strategic, but also from a dynamic viewpoint.
Introduction
The question of "as if" rationality that is, whether selfishlyminnded, myopic agents may learn to behave "as if" they were fully rational has been one of cornerstones of non-cooperative game theory, and for good reason. Especially in modern applications of game theory to machine learning and data science from online ad auctions to recommender systems and multi-agent reinforcement
Cooreesoondig author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

learning - the standard postulates of rationality (knowledge of the game, capacity to compute an equilibrium, flawless execution of equilibrium strategies, common knowledge of rationality, etc.) are almost never met in practice; as a result, game-theoretic predictions that rely on these assumptions are likewise put into question. By contrast, given the ease of implementing and deploying cheap, computationally efficient learning algorithms and policies at large scale, it is often more logical to turn to the policy being deployed as the object of interest. The aim is then to understand its long-run behavior and, in particular, whether it ultimately leads to equilibrium.
major obstacle in this approach is the complexity of computing a Nash equilibrium, a problem which is known to be complete for PPAD and hence intractable by the seminal work of Daskalakis al. [12]. This result implies that is not plausible to expect any algorithm to converge Nash equilibrium in all games (at least, not in reasonable amount of time), so it dovetails naturally with the impossibility results of Hart& & Mas-Colell [22, 23] who showed that there are no uncoupled learning dynamics that converge to Nash equilibrium in all games. On that account, it is natural to ask in which classes of games we can expect a learning algorithm to converge, in which classes we cannot, and under what conditions.
Perhaps the most well-behaved class of games in terms of learning is the class of potential games [44, 55], where players have common interests - not necessarily driving them to play the same strategy, but in the sense that externalities are symmetric and aligned along a common objective (the potential of the game). In this class of games, the behavior of learning dynamics and, in particular, no-regret learning [8. 13, 19, 27, 28, 36, 40, 43, 59] are relatively well understood, and there is a wide range of equilibrium convergence results, from continuous to discrete time, and even with bandit, payoff-basee based feedback [24, 25, 55].
By contrast, in the presence of conflicting interests, the situation can be quite different. In two-player zero-sum games with a fully-mixed equilibrium such as Matching Pennies the continuous-time dynamics of no-regret, regularized learning are recurrent in the sense of Poincaré that is, the induced trajectory of play returns arbitrarily close where it started infinitely many times 48], In discrete time, the situation becomes more complicated: the vanilla version of follow-the-regee rehuraeuu--- leader (FTRL) - the most widely studied family of no-regret algorithms it diverges away from equilibrium in the same class of games [18, 42]. On the other hand, if players employ an optimistic/ extra-gradee grrai-gt variant of FTRL, the induced trajectory of play converges to equilibrium [15, 42] and, under certain conditions, it is even possible to show that it converges at geometric rate [62].
no longer recurrent, but
At the same time, zero-sum games may also admit a potential function, so it is not possible to predict the outcome of a learning process based on where it stands along the potential / zero-sum axis. The non-trivial intersection of these classes means that potential and zero-sum games are not complementary, and this, not only from a strategic. but also from dynamic viewpoint, Instead, the true strategic complement of potential games is the class of harmonic games. This class was first considered by Candogan et al. [6]. who established remarkable decomposition result: Every game in normal form can be decomposed as the sum of potential game and harmonic game, and this decomposition unique up to affine transformations that do not alter the equilibrium outcomes of the game. In particular, the class of potential and harmonic games intersect trivially (up to strategic equivalence), and all two-player zero-sum games with an interior equilibrium are harmonic, thus lending credence to the fact that it is harmonic games, not zero-sum games, that correctly capture the notion of conflicting interests in this context.
This raises the question:
What the behavior of no-regret algorithms and dynamics in harmonic games?
Except for a very recent paper by Legacci et al. [35] (which we discuss below), almost nothing is known this question. With this backdrop, contributions can be summarized as follows:
1. Starting with a continuous- are Poincaré recurrent in all harmonic games. This generalizes and extends the recent result of Legacci et al. [35] for the replicator dynamics in uniform harmonic games (a subclass of harmonic games in which the uniform distribution is always Nash equilibrium).
model of no-regret learning, we show that all FTRL dynamics
IIn more detail, the way that Legacci et al. [35] obtained their result hinges on the so so-called Shahshahani metric, choice which is essentially "mandated" by the structure of the replicator dynamics. Specifically, the key

---

R, each 2. In discrete-time models of learning, the standard implementation of FTRL cannot be expected to converge (since it fails to do in Matching Pennies). To correct this behavior, we consider flexible algorithmic template, inspired by Azizian et al. [3] and dubbed extrupolated FTRL (FTRL+), which augments FTRL with a forward-looking extrapolation step (including as special cases the optimistic and extra-step variants of FTRL. cf. Section 4). We then establish the following results:
(a) Under extrapolated FTRL,, players are guaranteed constant individual regret (so, consequence, the players' empirical frequency of play converges to coarse correlated equilibrium at a rate of ((ITT)), This should be contrasted with the results of [13, 14] who showed that players can achieve polylogarithmic regret in any game (finite or convex).
(b) The induced trajectory of play converges to Nash equilibrium from any initial condition.
Our results aim to provide in-depth understanding of no-regret learning in harmonic games, nesting prior work on 2-player zero-sum games from Poincaré recurrence [41, 48] to constant regret [27] and convergence under optimistic/ / extra-gradient schemes [11, 15, 18, 42, 62]. In partiucular, at high level, our results show that harmonic games are the canonical complement of potential games, not only from strategic, but also from dynamic, learning viewpoint.
2 Preliminaries
2.1. Preliminaries finite games. Throughout the sequel, we will work with finite games in normal
form. Formally, such games consist of (i) finite set of players i E = ".....,N); ; (ii a finite set of actions A per player i E N; and (iii) ensemble of payoff functions u;: [í determining the reward u; (a(a) of player i e N in given action profile a = (a)..... .NN). Putting everything together, we will write A == I1 for the game's action space and r I(N A..) for the game with primitives as above.
During play, each player selects an action according some mixed strategy, that is, probability distribution X, over A, which assigns probability Xia, to aj E A₁. In a slight abuse of notation, if x assigns all probability mass some action 0; E AA (that is, Xia, 1), will identify x; with a; and we will call it pure. We will also write X; A(A,)) S R- for the mixed strategy space of player i, x = .i,.....NN for the strategy profile collecting the strategies of all players, and X' = II X, for the game's strategy space.
The mixed payoff of player under a mixed strategy profile x E X' may then be written as
(x(x) = [F:x([;(o)]] = Σ
uu(ar) Xa = Σ ui u;(a;;-i) .EA
m
where x.r = 11 Xia, denotes the joint probability of a (a11..., (N) A under x e X, and, in standard game- theoretic notation, we write (xixx_1)
for the profile where
player i plays xi Xj against the strategy x-i E X_, == [s X2 of all other players. We also respectively define the individual payoff player i and the game's 's payoff field as
(2) so (x) = EaseA, vian (x))aia = (Ii(xx, where (:.-) is the standard duality pairing on RRA, By multilinearity, each player's individual payoff field is Lipschitz continuous on X, and we will write G, for its Lipschitz modulus, that is
0,(x) (ui(axi-=))aa and o(x) =
uw(())
a|l (x') (x11l S G/ll'' xxl for all x E X.
(3)
Remark. In the above and throughout, ||-I| denotes an ambient norm on R (usually the L' norm), and I1-II, is the corresponding dual norm (usually the L norm). To simplify notation, we will not earry the player index i in I|- and will instead rely on the context to resolve any ambiguities.
property of the Shahshahani metric is that incompressibilityy of the replicator field is equivalent to the underlying game being uniformly harmonic; however, finding variant of the Shahshahani metric attuned to FTRL seems be formidable task, and likewise for non-uniform harmonic games. Because of this, the "incompressibility" approach of [35] does not seem applicable to our setting least, not a straightforward way.
'ee clarify here that "constant" refers to the horizon T of play: the dependence on the number of actions may be logarithmic or worse (depending the specific regularized learning scheme employed by the players).
3

---

In terms of solution concepts, we will focus almost exclusively on the notion of a Nash equilibrium (NE), i.e., a strategy profile E X that is unilaterally stable in the sense that
";(x") 2 (x(xxx2,)) for all x; E d4 i E N. Equivalently, (NE) can be expressed in terms of the game's payoff field variational inequality of the form
(NE)
(u(x"),x x²) 00 for all E X.
(VI)
Thus, writing supp(x;) = {a, A Xio; 0} for the support of x₁. it follows that x² is a Nash equilibrium if and only if uz (axxx"))) 2 u: (;(xx"",, for all or E supp(x;) and all Br E Ai, E N. We will use all this freely in the rest of our paper.
2.2. Harmonic games. Our main focus in what follows will be the class of harmonic games, first introduced by Candogan et al. [6] as game-theoretic model for strategic situations with conflicting. anti-aligned interests. Specifically, as was shown by Candogan et al. [6] and, in more general setting, by Abdou et al. [1] - every game in normal form can be decomposed as the sum of a potential game and harmonic game, and this decomposition is unique up to affine transformations that do not alter the equilibrium outcomes of the game.* 4 In this decomposition, the potential component of game captures multi-agent strategic interactions with common interests, whereas the harmonic component covers interactions with conflicting interests."
Formally, adapting the more general setup by Abdou et al. [1], we have the following definition: Definition 1. A finite game r = I(N. u) is said to be harmonic when it admits a harmonic measure, i.c., a collection of weights floa E (0, oo), 0j E A,, i E N, such that
Σ Σ Mip, [u:(ar; ax:)) - u: a-)) O for all a A.
(HG)
LEN BEEAA
In particular, if I is harmonic relative to the uniform measure Mia: = 1, E A,iEN, we will say that I' is a uniform harmonic game (UHG).
Remark. With regard to terninology, Candogan et al. [6] call "harmonic games" what we call "uniform harmonic games", and Abdou al. [1] call "p-harmonic games" what we call "harmonic games". We use this convention because it simultaneously simplifies notation and terminology while capturing all relevant strategic features of the game; for detailed discussion, see Appendix A. To avoid needless repetition, and unless there is danger of confusion, when we say that I is harmonic, we will write μr for the corresponding measure, and we will write m; = |p ER.AA, HiB, for the total mass of μı:
Broadly speaking, in harmonic games, for any player considering a deviation toward a specific pure strategy profile, there exist other players with incentive deviate away from said profile. In this regard, harmonic games can be seen as the strategic complement of potential games, where player interests are aligned and sequences of unilateral best responses generate finite improvement path that terminates at a pure Nash equilibrium [44]. By contrast, except for trivial cases (like the zero game) harmonic games do not admit pure Nash equilibria, and they possess non-terminating best-response paths. For all these reasons, harmonic games can be considered as "orthogonal" to potential games, in sense made precise by the decomposition results of Candogan et al. [6] and Abdou et al. [1].
It is of course natural to ask what is the relation between harmonic games and zero-sum games. Games belonging to the latter class such as Matching Pennies and Rock- Rock-Paper-Scissee Paper-Scissors have long been used prototypical examples of strategic conflict; at the same time, there are zero-sum games that are also potential (and even possess strict equilibria), so the potential zero-sum distinction does not capture the whole picture. As matter of fact, it is not coincidence that the textbook examples of zero-sum games admit fully-mixed Nash equilibria: as we discuss in Appendix A, two-player zero-sum games with fully mixed Nash equilibrium are harmonic, the existing results for such games are, in a sense, more closely attuned to their harmonic character.
"We briefly recall here that I = T(V,A, is potential game if it admits potential function $: X R such that u, (B;; a) - u, ax)) :)= = a(B)a),,, - +aa; a-1) for a, e A and all i e A [44].
"The terminology "harmonic" is due to Candogan et al. [6] and alludes to the harmonic component of the graphical Hodge decomposition [30].
'To be even more precise. the definition of Abdou et al. [1] involves an additional set of weights, called a comeasure; however, as we explain in Appendix A, these weights do not change the preference structure of the game, disregard this extra degree of generality.

---

3 Continuous-time analysis: Poincaré recurrence
The most basic rationality postulate the context of online learning is the minimization of a player's (external) regret, i.e., the difference between player's cumulative payoff and that of the player's best possible strategy in hindsight. In more detail, assuming for the moment that play evolves in continuous time, the regret of player N relative a sequence of play x(1) e X' is defined as
(" [I.(ppxxx(0)) (x(((())]
Reg, (T)
max PiE.
and we say that the player has regret under x(1) if Reg o(T) as ~ 00.
The most widely used scheme for attaining no regret is the family of policies known as follow-the- regularized-leader (FTRL) [57, 58]. At high level, the idea behind FTRL is that, at all times / 2 O, each player i E N plays a mixed strategy (1) X; that maximizes the player's 's cumulative payoff up to time / minus a certain regularization penalty. In our continuous-time setting, this gives rise to the FTRL dynamics
((iloiisss(t))) dr hi(pi) -hi((pi)
[ (o((((T)) pi) dr he(pi)) P.E
(1) = arg max P.EX,
arg max
(5)
or, more compactly,
(t (x(()) x1(1) (r(
(FTRL-D)
where h;: X; - R is convex penalty function known as the regularizer of the method, Q, denotes the regularized choice map of player i, and Q = (QI..... QN) denotes the profile thereof. Formally, writing }/- = RA for the payoff space of player E N that is, the space of all possible payoff vectors of player - the regularized choice map Q:: V; + A is defined as
@x(y:) arg max X (yr, xi) (x,))) for all y: E V;
In essence, O, is "soft" version of the arg max correspondence y/ arg manmax,,, (1),,)), suitably regularized by a penalty term intended to incentivize exploration. For technical reasons, we will also assume that each h, is strongly convex, i.c.,
h (Ix; (1 rxx (x,)
(1 (1-1)4;xx)) (1 r)|x; -x/11 xx111
(7)
for some K2 > 0 (commonly referred to as the strong convexity modulus of h4), and for all x,, x E X, r e [o. 1]. plain words, this simply means that h; has "enough curvature" in the sense that it can be bounded from below by (positive) quadratic function which agrees with h; to first order.
The go-to example of this setup is the entropic regularizer
hx(x,)
Σ are.i
Xia, log Xia;
(8)
which yields the so-called logit choice map
@rly)) A,(y) (cxp(Uia)))asAA
for all yi e V/.
(9)
Ea,EA, exp( exp(Yia.)
By Pinsker's inequality, the entropic regularizer is I-strongly convex relative to the L Lnoro on 2; [57], and by standard calculation [37, 54], the induced sytem (FTRL-D) boils down to the replicator dynamics of Taylor& & Jonker [60]. Some other standard examples of (FTRL-D) include the Euclidean projection dynamics of Friedman [17] when (x,) = (1/2) the q q-replicator dynamics [21, 38). etc. To streamline our presentation, we defer a detailed discussion of these examples to Appendix C, and we proceed below to state the main regret guarantee of (FTRL-D), originally due to [33]:
Theorem 1. Under (FTRL-D), each player's 's regret is bounded as Reg, (T) H, max h, min hi-
Theorem 1 showcases the strong no-regret properties of (FTRL-D): it is not possible to guarantee less than constant, ((1) regret, (FTRL-D) is optimal in this regard. In turn, by standard results [47], Theorem implies further that the players' (correlated) empirical frequencies Zay.....r (1) := (1/r) 6' Ia (T) dr converge the game's 's set of coarse correlated equilibria (CCE) at rate of (1/rr)
5

---

Importantly, this result makes no assumptions about the underlying game, but it does not carry the same predictive power in all games: for one thing, a game's 's set of CCE may include highly non-rationalizable outcomes (such as dominated strategies and the like) [61]; for another, the time- averaging that is inherent in the definition of empirical distributions may conceal a wide range of non-convergence phenomena, from cycles to chaos [48, 56]. On that account, the day-to-day behavior of (FTRL-D) in harmonic games cannot be understood from Theorem alone, and requires a closer, more in in-depth look.
Our first result below provides such a lense and shows that (FTRL-D) is almost-periodic in harmonic games, a property known as Poincaré recurrence.
Theorem 2. Suppose I is harmonic. Then almost every orbit x(1) of (FTRL-D) returns arbitrarily close to its starting point infinitely often: specifically, for (Lebesgue) almost every initial condition x(0) = (()) & X, there exists an increusing sequence of times In 1 co such that x(In) - x(0).
An immediate consequence of Theorem 2 is that no-regret learning under (FTRL-D) fails to converge in any harmonic game; in particular, since the orbits of (FTRL-D) eventually return (almost) where they started, it is debatable if the players have learned anything at all, despite the fact that they incur at most constant regret. This cyclic, non-convergent landscape is the polar opposite of the long-rum behavior of (FTRL--D) in potential games, where the dynamics are known to converge globally [24]. Thus, in addition to the strategic viewpoint of the previous section, Theorem shows that harmonic games are orthogonal to potential games also from a dynamic viewpoint.
Theorem also provides a far-reaching generalization of existing results on Poincaré recurrence in (possibly networked) two-player zero-sum games with an interior equilibrium [41] to general-sum, N-player games. Combined with our previous remark, and given that the zero-sum property is not as meaningful for N players as it is for two,? the class of harmonic games can be seen as the more natural N --payye generalization of two-player zero-sum games from learning viewpoint.
To the best of our knowledge, the only comparable result to Theorem in the literature is the very recent paper of Legacci al. [35] who showed that the replicator dynamics- a special case of (FTRI-D) - are Poincaré recurrent in uniform harmonic games, that is, in harmonic games where the uniform distribution is Nash equilibrium, cf. (A.1) and the discussion surrounding Definition 1. In this regard, Theorem 2 extends the recent results of Legacci et al. [35] along two axes: (i) it applies to the entire class of FTRL dynamics (not only the replicator dynamics); and (ii) it applies to the entire class of harmonic games (and not only uniformly harmonic games).
In terms of techniques, Legacci et al. [35] obtained their result through a surprising connection between a certain Riemannian metric underlying the replicator dynamics and the defining relation of uniformly harmonic games. This relation no longer holds for different instances of (FTRL-D) or for non-uniform harmonic games, so the techniques of [35] cannot be extended - and, in fact, Legacci al. [35] stated this generalization as open problem. Our techniques instead rely on the fact that the orbits y(r) of (FTRL-D) comprise a volume- presee-in flow in the game's payoff space y = TI V/ (though not necessarily on X), and then deriving suitable constant of motion. In the case of the logit map (9), this constant of motion can be written as
G(x) = I I
Biar
for all x E X,
(10)
iEV a..AA
where μ = (H)a)) )a NEN is the harmonic measure on X' defining I". In the more general case, the construction of a constant of motion for (FTRL-D) involves a characterization of harmonic games in terms of a "strategic center", which we carry out in detail in Appendix C.
4 Discrete-time analysis: Convergence and constant regret via extrapolation
We now proceed to examine the regret and convergence propertics of regularized learning algorithms in harmonic games. Starting with the standard, vanilla implementation of FTRL, we reproduce a well-known observation that FTRL spirals out to a non-terminating cycle of best-responses in Matching Pennies (which is harmonie game). Subsequently, to correct this non-convergent behavior, we examine a flexible algorithmic template, which we call extrapolated FTRL (FTRL+), and which includes as special cases the optimistic and extra-gradient versions of FTRL.
Recall that any N- l-playe game can be turned into equivalent zero-sum game by adding fictitious player.

---

4.1. Vanilla implementation of FTRL. Building on the discussion of the previous section, the standard implementation of FTRL in discrete time for I.2.... .. is
Xi,++1 = arg max P:
E k-1 "i(pr: -
-, (phi(
arg max f Ex (oi(())) pi) 1phi(pe)) (11) P:eR;
or, in more compact, iterative notation
yl.++1 = =I,, + ()((((n)) Xi,n = Qi(ym)
(FTRL)
where, as per (6), the map Q:: D; - X; denotes the regularized choice map of player E E,, A; is player-specific regularization weight parameter, and 1/: = 1/4; represents the learning rule of player i. Apart from their obvious differences discrete vs. continuous time salient point that sets (FTRL) apart from (FTRL-D) is the inclusion of the parameter q/; this parameter is necessary to control the algorithm's behavior, and we will discuss it in detail in the sequel.
As mentioned in the introduction, a major shortfall of (FTRL) and one of the main reasons for the increased popularity of optimistic/ / extra-gradient methods - is that it may spiral away from Nash equilibrium, even in simple 2 x games with a unique equilibrium. The standard example of this behavior is Matching Pennies, two-player zero-sum game with fully-mixed equilibrium which is also uniformly harmonic, so the trajectories of (FTRL-D) are Poincaré recurrent (and, in fact, periodic). In more detail, this game can be compactly represented by the payoff field x2x1,x2) (4x² - 2, - 4x1) for X1, E [0, 1], and its unique Nash equilibrium is x" = (1/2. 1/2). Thus, if we run (FTRL) with a Euclidean reqularizer that is, hx,x)) x2/2 for i = 1, and the same learning rate 17 for both players, a straightforward calculation shows that the distance Dn = (x1,n xx) 22 (x2,n - x/)2/2 between Xn and x" evolves as
Dn+1= = (x1, _ + (x,) - x))² + [x2,,n + nu2(xn) - xx²² = (1 + 16n))
(12)
as long as X, + 7po(x,,) E X. In other words, the distance of the iterates of (FTRL) from the game's equilibrium grows at a geometric rate until X,, reaches the boundary of X and is ultimately trapped in conminimmnn cycle of best responses, cf. Fig. 1. In this regard, the rationality properties of (FTRL) are even worse than those of (FTRL-D) because the game's 's equilibrium is now repelling.
4.2. Extrapolated FTRL. To mitigate this undesirable, divergent behavior of (FTRL), a standard approach in the literature is the inclusion of a forward-looking. "extrapolation step". Instead of updating the algorithm's 's "base state" x, directly, players first move to an interim "leading state" kn+1/2 using payoff information from xx, (this is the extrapolation step); subsequently, players update Nn, using payoff information from the leading state 1n+1/2 and the process repeats. this way, players attempt to anticipate their payoff landscape and, in so doing, to take a more informed update step at each iteration.
The seed of this idea goes back to Korpelevich [32] and Popov [49] in the context of solving monotone variational inequality problems, and it has since percolated to a wide array of " "extra-gre extraa-raddent" or "optimistic" methods, such as the mirror-proe algorithm of Nemirovski [45], the dual extrapolation variant of Nesterov [46], the optimistic mirror descent algorithm of Chiang et al. [9] and Rakhlin & Sridharan [50], and many others. Given the different operational envelope of each of these methods, we consider below an integrated algorithmic template, which we call extrapolated FTRL (FTRL+), and which is sufficiently flexible to account for broad range of these schemes.
Formally, the proposed algorithmic blueprint unfolds in two phases as follows:
a) Extrapolation phase: b) Update phase:
ft, Vi.n + di
Xi,n+1/2 = 2: (1..+11))))
(FTRL+)
Vi,++1 = Vi.. + 1/0i,n+1/2
Xi,++1 = 11(1in)11)
In the above, > O is the learning rate of player i, Xn and Xn41/2 denote respectively the method's base and leading states at stage 1.2...., and 0g,n and 0,,n+1/2 are sequences of "black-box" payoff models at xn and kn+1/2 respectively.
Specifically, following Azizian al. [3], we will assume throughout that
0 = 0; (xx+11122 for all i e N and all n = 1,2....
(13a)
i.c., players always update the base state x,, using payoff information from the leading state Xn+1/2- By contrast, the leading state Xn+1/2 can be generated in many different ways, depending on the targeted update structure. In this regard, we will consider the linear model
,n a; (x))) + b, (1221112)) for all i e A and all n = 1,2....
(13b)
7

---

where the coefficients a, by 2 O satisfy + b, S 1 and represent mix of past and present payoff information. In this way, depending on the values a; and b;. we obtain the following prototypical regularized learning methods as special cases of (FTRI++):
FTRL: if a; b; = for all E N,, players essentially forego any look- efforts, so we get for all n = 1,2.... In turn, this gives kn+1/2 Xn, i... (FTRL+) regresses to (FTRL).
in = 0
(14a)
b) Extra-Step FTRL: if a; = and b; for all i E N, we have
i₂ ((x,))
for all 1,2....
(14b)
ie., players use payoff information from their current state to generate the leading state 1n+1 This update structure requires two payoff queries per iteration and its origins can be traced back to the work of Korpelevich [32]. Specifically, depending on the choice of h; it is essentially
equivalent the mirror-prox [45] and dual extrapolation [46] algorithms, it contains a special
case the forward-looking algorithm of [15, 42], etc.
Optimistic FTRL: if a; = 0 and b; = 1 for all i E .,, we have
0 (xn-11/) for all n 1.2....
(14c)
i.e., players reuse the latest available payoff information instead of making a fresh query at Xn (so the algorithm only requires one payoff query per iteration). In this way, (FTRL+) recovers the optimistic algorithms of [9, 26, 50, 59], the OMW update scheme of [11, 59] when Q A, etc.
Clearly, the list above is not exhaustive: many other configurations possible, e.g., with different players using different parameter settings for a; and b;, depending on the information they have at hand and any other individual considerations. To avoid needlessly complicating the analysis, our only standing assumption will be that a; + b; > O for all i E N (since, otherwise, the benefits of the extrapolation step would vanish). In particular, by rescaling the players' learning rates if needed, we will normalize a, and by to a; + b, = 1, leading to the convex model
f A (x,,) + (1) (X
(15)
for some arbitrarily chosen ensemble of player-specific extrapolation coefficients A; e [0, 1J, e W. Remark. To simplify the presentation of our results, we will assume throughout the rest of our paper that (FTRL+) is initialized with y1 /1/2
4.3. Analysis & results. With all this in hand, we are finally in a position state our main results for (FTRL+) in harmonic games. We begin by showing that (FTRL+) achieves order-optimal regret: Theorem 3. Suppose that each player in a harmonic game I' is following (FTRL+) with learning rate Ti S miKi[2[N maxj j m,G;]=+ and payoff models as per (13a) and (15). Then the individual regret of each player i E N is bounded as
Hi
2G
Hj JeN G,G
Reg, (T)
max P n=1
Elu(prx-Lan (x))
S T
Σ
(16)
N+2
where H; max h; - min hú, and G2 is the Lipschitz modulus of
Even though Theorem 3 invites natural comparison with the constant regret bound of Theorem 1, the continuous- and discrete-time settings are fundamentally different, so any conclusions drawn from such a comparison would be specious. Indeed, constant regret guarantees in the spirit of (16) are particularly rare in the context of discrete-time algorithms, and as far as we are aware, similar bounds have only been established for optimistic methods in variationally stable and two-player zero-sum games [27]; other than that and always to the best of our knowledge the tightest regret bounds available for general games (finite or convex) seem to be (poly)logarithmic [13, 14]. In this regard, just like the recurrence result of Theorem 2, the O(1) regret bound of Theorem represents a significant extension of existing results on zero-sum games (and polylogarithmic regret in general games), and suggests that, from a learning viewpoint, harmonic games are the most natural generalization of two-player zero-sum games to general N-player context. We defer the proof of Theorem 3 to Appendix D.
8

---

1-20
8.
Straingy Secre Sla
0.2
8
3.0
Stretagy
The evolution of vanilla vs. extrapolated FTRL schemes in harmonic games. In the left figure, we consider the game of Matching Pennies (blue: FTRL+; green: FTRL; red: continuous time FTRL); in the center and the right, different orbits in 2 x 22 harmonic game from two different viewpoints (blue: FTRL+; green/orange:FTRL. payoff profiles on vertices). all cases, we ran optimistic variant FTRL+ (d, for all players), and we see that the trajectories of (FTRL) diverge away from equilibrium and the trajectories of (FTRL-D) are recurrent (actually, periodic), whereas (FTRL+) converges. We also see the highly non-convex structure of harmonic games evidence by their equilibrium set (thick red line in center and right subfigures).
Figure 1:
As an immediate corollary of the above, we conclude that, under (FTRL+), the empirical frequencies of play Za.n == (1/n) Σ== Xa.ks E A. converge the game's set of CCE at a rate of O(1/n). This rate is, again, optimal, but as we discussed in Section 3, it offers little information in games where the marginalization of CCE does not lead to Nash equilibrium and, in general N N-player harmonic games, there is little hope that it would. In addition, even when the marginalization of CCE Nash, the actual trajectory of play may - and, in fact, often does behave very differently from the time-averaged frequency of play.
Despite these hurdles, we show below that (FTRL+) does converge Nash equilibrium. To state this result formally, we will focus on the case where each player's regularizer is smooth in the sense that
h (x; (x/ - x;)) is continuously differentiable at =0
(17)
for all x; E im Q, and all x E &. Our prototypical examples the entropic and Euclidean regulariz- ers - both satisfy this mild requirement, as do all regularizers of the form (x;)) = Lo 0, (X for some smooth convex function 0; [0, 1] R. We then have the following convergence result: Theorem 4. Suppose that each player in a harmonic game I follows (FTRL+) with learning rate $ K, [2(N + 2) maxj m n, and payoff models as per (13a) and (15). Then xn converges to the set of Nash equilibria of I.
To the best of our knowledge, Theorem 4 is the first result of its kind for harmonic games - and, in that regard, it is somewhat unexpected. To be sure, two-player zero-sum games with fully-mixed cquilibrium exhibit comparable pattern: FTRL is Poincaré recurrent in continuous time, its vanilla discretization is unstable, and its optimistic/ forward-looking implementation convergent. However, the conccve structure of min-max games which enables this analysis is completely absent in harmonic games, so it is less clear what to expect in this case (where even the of Nash equilibria is non-convex, cf. Fig. 1). By this token, the convergence of (FTRL+) in harmonic games is a property that one could optimistically hope for, but not one that can be taken for granted.
From a technical standpoint, the proof of Theorems and 4 involves two concurrent challenges:
1. Deriving Lyapunov function with "sufficient descent" property for all harmonic games.
2. Providing an integrated analysis for all possible update structures in (FTRL+).
With regard to the first point, our analysis hinges on the "energy function"
E(p.y) = Σ mi
F((p..)))
p PEX.YE
(18)
TEN
In the above, X is benchmark strategy profile acting as "reference point" for the analysis while
Fr vi) max (y), h,(x:)) (y p.) h:(p:)
(19)
X,
'The restriction to im Qi is technical in nature and is related the subdiiferreniabiiiiy of ht, cf. Appendix B.

---

denotes the Fenchel coupling associated to the regularizer hú of player e N, and represents "primal-dual" measure of divergence between pi É X; and yi E );; (for an in-depth discussion, see Appendices B and D). Then, letting En E(p.yn) the heavy lifting for our analysis is provided by the "template inequality"
Ex+1 En +
Σ
mi
pi)
iEN
(xn+1/2))1)))))))))))))))))))))) (1:)))-(((AA (z(xx)) xi,x+1/2)
+
Σ
m;(1 (1 (x)(v(()))) 0z (xn-1/2), Xint! - x1,
iEA
m;Ki
Σ iNN
[|lxi,ne1 - ||xi, - x1.
(20)
A first important consequence of (20) is that the sequences A, = ||xx+1 - 1/21/2 and B, ||xn=1//2 Xn 2 are both summable: this requires repeated use of the Fenchel- inequality, and an instantiation of p the strategic center 9 of I; we detail the relevant arguments in Appendices A and D. Then, by establishing similar template inequality for each player i E N. we are able to bound the players' individual regret by the same upper bound that we derived for Σ,, An and Σn, Bn, and which is (up to certain secondary factors) the bound (16).
For the convergence to Nash equilibrium, the summability argument above also plays crucial role. First, by a standard result on numerical sequences, the summability of A, and B, coupled with the template inequality (20) implies that the energy E, of the algorithm relative to the game's s strategic center converges to some limit value Ego- In turn, this implies that the score sequence yn is bounded up to multiple of the vector (1, (I...., 1), which corresponds to constant payoff shift in the underlying game. Then, by focusing on convergent subsequences of yn and the optimality condition resulting from the definition of Q, are able to show that any limit point of o(x,)) satisfies the variational characterization (VI) of Nash equilibria, from which our claim follows.
5 Concluding remarks
Our results suggest that the long-run behavior of no-regret algorithms and dynamics in harmonic games is very rich topic, and one which opens the door to an entirely new class of games where positive convergence results can be obtained. We find this particularly appealing, not only because harmonic games comprise the strategic complement of potential games, but also because they go beyond standard problems with a convex structure - for instance, even their equilibrium set is non-convex. As such, the fact that it is possible to obtain optimal regret guarantees and positive equilibrium convergence results this setting very promising for future work on the topic.
In terms of open questions, it would be important to examine the rate of convergence of (FTRL+) to cquilibrium. Even though (FTRL+) has order-optimal regret bounds, this only helps in establishing a convergence rate to the game's 's set of coarse correlated equilibria; for Nash equilibria, earlier work by Golowich et al. [19] and some more recent results by Cai et al. [5] and Gorbunov al. [20] have shed some light on the convergence of constrained Euclidean optimistic methods, but the technology therein does not extend to monnoone,,, non- non-Euclidean problems. Inspired by Wei et al. [62], we conjecture that the convergence rate of (FTRL+) in harmonic games is linear: this is based on the observation that any harmonic game admits a fully-mixed Nash equilibrium, and the weighted sum in the definition of harmonic game looks formally similar to the condition needed to establish metric subregularity in [62]; however, a proof would likely require different techniques.
Another important research direction has to do with the information available to the players. A first open question here concerns the case where players do not have access to full information on their mixed payoff vectors, but can only observe their pure payoffs- either in a "what if", counterfactual manner, in the form of bandit, payoff- based feedback. In a similar manner, the algorithms presented here are not adaptive, in the sense that the players' step-size policy has to satisfy a certain bound that depends on correctly estimating some of the game's 's parameters. Obtaining an adaptive version of (FTRL+) which, in the spirit of Rakhlin & Sridharan [50] and Hsieh et al. [27, 28, 29], remains convergent and attains order-optimal regret both adversarial and game-theoretic settings without any pre-play tuning is also an ambitious question for future research.
10

---

Acknowledgments and Disclosure of Funding
This research was supported in part by the French National Research Agency (ANR) in the framework of the PEPR IA FOUNDRY project ANN-23-PEIA--ONE the "Investissements d' a'aveii program" (ANR-15-1H) 15-IDEX-02) the LabEx PERSYVAL AANR-1I-LBB 11-LABX-0025-011 0025-01), MIAI Grenoble Alpes LINR-19-P98 119--31--0003) the project IRGA2024- G7H-IRG24E90, and NSF grant CCF2212233 PM is also with the Archimedes Research Unit/Athena RC & NKUA and acknowledges financial support by project MIS 5154714 of the National Recovery and Resilience Plan Greece 2.0 funded by the European Union under the NextGeneration Program.
References
[1] Abdou, J., Pnevmatikos, N.. Scarsini, M., and Venel, Decomposition games: Some strategic considerations. Mathematics of Operations Research, 47(1):176 February 2022.
[2] Amold, I. Mathematical Methods of Classical Mechanics. Springer-Veraag 1989.
[3] Azizian, W., lutzeler, F., Malick, J., and Mertikopoulos, P. The rate of convergence of Bregman proximal methods: Local geometry vs. regularity vs. sharpness. SIAM Journal on Optimization, 34(3):2440 2471, September 2024.
[4] Bertsekas, D. P. Convex optimization algorithmss Athena Scientific, 2015.
[5] Cai, Y., Oikonomou, A., and Zheng, W. Tight last-iterate convergence of the extragradient and the optimistic gradient descent-ascent algorithm for constrained monotone variational inequalities. 2022.
[6] 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):474-503, 2011.
[7] Chen, G. and Teboulle, M. Convergence analysis of proximal- like minimization algorithm using Bregman functions. SIAM Journal on Optimization, 3(3):338- 543, August 1993.
[8] Chen, X. and Peng, B. Hedging in games: Faster convergence of external and swap regrets. In Larochelle, H., Ranzato, M., Hadsell, R., Balean, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 18990-18999 Curran Associates, Inc., 2020.
[9] Chiang, C.-K.. Yang. T., Lee. C.-J.. Mahdavi, M., Lu, C.-J. Jin, R., and Zhu. S. Online optimization with gradual variations. In COLT 11: Proceedings the 25th Annual Conference on Learning Theory, 2012. [10] Combettes, L. Quasi-Fejérian analysis of some optimization algorithms. In Butnariu, D., Censor, Y., and Reich, S. (eds.), Inherently Parallel Algorithms Feasibility and Optimization and Their Applications, pp- 115-152. Elsevier, New York, NY, USA, 2001.
[11] Daskalakis, C. and Panagcas, I. Last-iterate convergence: Zero-sum games and constraincd min-max optimization. In ITCS '19: Proceedings of the 10th Conference on Innovations in Theoretical Computer Science, 2019.
[12] Daskalakis, C., Goldherg, P. W., and Papadimitrion, C. H. The complexity of computing Nash equilibrium. Communications of the ACM, 52(2))89-97, 2009.
[13] Daskalakis, C. C., Fishelson, M., and Golowich, N. Near-optimal no-regret learning in general games. In Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, 2021.
[14] Farina, G., Anagnostides, I., Luo, H., Lee, C.-W., Kroer, C., and Sandholm, T. Near-optimal no-regret learning dynamics for general convex games. In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, (eds.), Advances in Neural Information Processing Systems, 2022.
[15] Fasoulakis, M.. Markakis, E., Pantazis, Y., and Varsos, C. Forward looking best-response multiplicative weights update methods for bilinear zero-sum games. In Camps-Valls, G., Ruiz. F. J. R., and Valera, I. (eds.). Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Rexearch, pp. 11096-11117. PMLR, 28-30 Mar 2022.
[16] Flokas, L.,, Vlatakis-Gkaan Gkaragkounis, E. V., Lianeas, T., Mertikopoulos, 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.
[17] Friedman, D. Evolutionary games in economics. Econometrica, 59())6377666, 1991.
[18] Gidel, G., Berard, H., Vignoud, G., Vincent, P., and Lacoste-Julien, S. A variational inequality perspective on generative adversarial networks. In ICLR '19; Proceedings of the 2019 International Conference on Learning Representations, 2019.
[19] Golowich, N., Pattathil, S., and Daskalakis, C. Tight last-iterate convergence rates for no no-regret learning in multi-play player games. In NewrIPS '20: Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020.
11

---

[20] Gorbunov, E., Taylor, A., and Gidel, G. Last-iterate convergence of optimistic gradient method for monotone variational inequalities. In Oh, H., Agarwal, A.. Belgrave, D., and Cho, K. (eds.), Advances in Neural Information Processing Systems, 2022.
[21] Harper, M. Escort evolutionary game theory. Physica D: Nonlinear Phenomena. 240(18):1111-415.
September 2011.
[22] Hart, S. and Mas-Colell. A. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68(5):1127 1150, September 2000.
[23] Hart, S. and MaleCl,,,,,, A. Stochastic uncoupled dynamics and Nash cquilibrium. Games and Economic
Behavior, 57:286-3000 303,,,33330000 2006.
[24] Héliou, A., Cohen, J., and Mertikopoulls, P. Learning with handit feedhack in potential games. In NIPS *17 Proceedings of the 3 International Conference on Neural Information Processing Systems, 2017. [25] Hofbauer, and Sigmund, K. Evolutionary Games and Population Dynamics. Cambridge University Press, Cambridge, UK, 1998.
[26] Hsieh, Y-G., Iutzeler, F., Malick, J., and Mertikopoulos, P. On the convergence of single-call stochastic extra-gradient methods. In NeurlPS '19: Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp. 6936-6946, 6946, 2019.
[27] Hsieh, Y.-G.. Antonakopoulos, K., and Mertikopoulos, P. Adaptive learning in continuous games: Optimal regret bounds and convergence to Nash equilibrium. In COLT '21: Proceedings of the 34th Annual Conference on Learning Theory, 2021.
[28] Hsich, Y.G.., Antonakopoulos, K., Cevher, V., and Mertikopoulos, P. No-regret learning in games with noisy feedhack: Faster rates and adaptivity via learning rate separation. NeurlPS '22: Proceedings of the 36th International Conference on Neural Information Processing Systems, 2022.
[29] Hsieh, Y.G.,, lutzeler, F., Malick, J., and Mertikopoulos, P. Multi-agent online optimization with delays: Asynchronicity, adaptivity, and optimism. Journal of Machine Learning Research, 23(78):1-49, May 2022.
[30] Jiang, X., Lim, L.-H., Yao, Y., and Ye, Y. Statistical ranking and combinatorial Hodge theory. Mathematical Programming, 127(1):203-244, 2011.
[31] Juditsky, A.. Nemirovski, A. S., and Tauvel. C. Solving variational inequalities with stochastic mirror-prox
algorithm. Stochastic Systems, 1(1):17-58, 2011.
[32] Korpelevich, G. M. The extragradient method for finding saddle points and other problems. Ékonom. i Mat. Metody, 12:747-756, 1976.
[33] Kwon, J. and Mertikopoulos, P. A continuous-ting approach to online optimization. Journal of Dynamics and Games, 4(2)) 148, April 2017.
[34] Lee, J. M. Introduction to Smooth Monifolds. Number 218 in Graduate Texts in Mathematics. Springer- Verlag, New York, NY, 2 edition, 2003.
[35] Legacci, D., Mertikopoulos, P., and Pradelski, B. S. R. A geometric decomposition of finite games: Convergence vs. recurrence under exponential weights. attps://arxits wowg/ba////////e////eo 2ala/2205.0775 007244, 2024. [36] Lin, T., Zhou, Z., Mertikopoulos, P., and Jordan, M. I. Finite-time last-iterate convergence for multi-agent learning in games. In JCML '20: Proceedings of the 37th International Conference on Machine Learning, 2020.
[37] Mertikopoulos, P. and Moustakas, A. L. The emergence of rational behavior in the presence of stochastic perturbations. The Annals of Applied Probability, (0(()):35991)))) 1388, July 2010.
[38] Mertikopoulos. P. and Sandholm. W. H. Learning in games via reinforcement and regularization. Mathe- matics of Operations Research, 41(4):127-11244 November 2016.
[39] Mertikopoulos, and Sandholm, W. H. Riemannian game dynamics. Journal of Economic Theory, 177:
315-364, September 2018
[40] Mertikopoulos, P. and Zhou, Z. Learning in games with continuous action sets and unknown payoff (6611-)):65-077 January 2019.
functions. Mathematical Programming,
[41] Mertikopoulos, P., Papadimitriou, C. H., and Piliouras, G. Cycles in adversarial regularized learning. In SODA '18 Proceedings of the 29th annual ACM-SIAM Symposium on Discrete Algorithmss, 2018.
[42] Mertikopoulos, P., Lecouat, B., Zenati, H., Foo, C.-S., Chandrasekhar, V., and Piliouras, G. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In ICLR '19: Proceedings of the 2019 International Conference on Learning Representations, 2019.
[43] Mertikopoulos, P., Hsieh, Y.P.., and Cevher, V. A unified stochastic approximation framework for learning in games. Mathematical Progranming, 203:559 609, January 2024.
[44] Monderer, D. and Shapley, L. S. Potential games. Games and Economic Behavior, 14(1): 124 - 143, 1996.
[45] Nemirovski, A. S. Prox-method with rate of convergence (1/rt) for variational inequalities with Lipschitz continuous monotone operators and smooth convex saddle point problems. SIAM Journal on Optimization, 15(1):229 2,1, 2004.
12

---

[46] Nesterov, Y. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematical Programming, 109(2):319-344, 2007.
[47] Nisan, N., Roughgarden, T., Tardos, É., and Vazirani, (eds.). Algorithmic Game Theory. Cambridge University Press, 2007.
[48] Piliouras, G. and Shamma, J. S. Optimization despite chaos: Convex relaxations to complex limit sets via Poincaré recurrence. In SODA '1: Proceedings of the 25th annual ACM-SIAM Symposium Discrete Algorithms, 2014.
[49] Popov, L. A modification of Kirow-Hurwics method search saddle points. Mathematical Notes of the Academy of Sciences of the USSR, (8(5):845844, 1980.
[50] Rakhlin, A. and Sridharan, K. Optimization, learning, and games with predictable sequences. In NIPS' '13: Proceedings of the 27th International Conference Neural Information Processing Systems, 2013.
[51] Robinson, Dynamical Systems: Stability, Symbolic Dynamics, and Chaos. CRC Press, November 1998.
[52] Rockafellar, R. Convex Analysis. Princeton University Press, Princeton, NJ, 1970.
[53] Rockafellar, T. and Wets, R. J. B. Variational Analyxis, volume 317 of A Series of Comprehensive Studies in Mathematics. Springer-Verlee Berlin, 1998.
[54] Rustichini, A. Optimal properties of stimulus-response learning models. Games and Economic Behavior, 29(1 (9())):24 273, 1999.
[55]
Sandholm, W. Potential games with continuous player sets. Journal of Economic Theory, 97:81-108, 2001.
[56] Sato, Y., Akiyama, E., and Farmer, J. D. Chaos in learning simple two-person game. Proceedings of the National Academy of Sciences of the USA, 9977):4748-4751, April 2002.
[57] Shalev-Shwartz. S. Online learning and online Learning, 4(2):107- 194, 2011.
optimization. Foundations and Trends Machine
[58] Shalev-Shwart,, of the 19th Annual Conference on Neural Information Processing Systems, pp. 1265-1272. MIT Press, 2006.
Singer, Y. Convex repeated games Fenchel duality. NIPS' 06: Proceedings
[59] Syrgkanis, V., Agarwal, A., Luo, H., and Schapire, R. E. Fast convergence of regularized learning in games. In NIPS '15: Proceedings of the 29th International Conference on Neural Information Processing Systems, pp. 2989-2997, 2015.
[60] Taylor, P. D. and Jonker, L. B. Evolutionary stable strategies and game dynamics. Mathematical Biosciences, 40(1 40(1-2):145-156 1978.
[61] Viossat, Y. and Zapechelnyuk, A. No-regret dynamies and fictitious play. Journal of Economic Theory, 148(2):825-88) 842, March 2013.
[62] Wei, C.-Y., Lec, C.-W. Zhang, M., and Luo, Linear last-iterate convergence in constrained saddle-point optimization. In ICLR '1: Proceedings of the 2021 International Conference on Learning Representations, 2021.
13

---

Appendices
Harmonic Games
14
A.1 Harmonic games, measures and comeasures
14
A.2 Preference equivalence between harmonic games
15
A.3 Mixed characterization of harmonic games
16
A.4 Harmonic and zero-sum games
Basic properties of regularizers and the induced choice maps
19
B.1 Preliminary definitions
19
B.2 Basic lemmas
21
Continuous-time analysis
23
C.I Dynamical systems notions
23
C.2 Basic properties of FTRL
23
C.3 Constant of motion for ................................
24
C,4 FTRL the space of payoff differences
24
C.5 Recurrence of FTRL in harmonic games
27
Discrete-time analysis
27
D.1 Lyapunov functions and template inequalities for (FTRL+)
27
D.2 Proof of Theorem 3
30
D.3 Proof of Theorem
A Harmonic Games
The class of uniform harmonic games (UHGs) introduced by Candogan et al. [6] provides a game- theoretic framework for modeling strategic situations with conflicting, anti-aligned interests. Broadly speaking, the characterizing property uniform harmonic games the following: for any player considering deviation towards specific pure strategy profile, there exist other players who motivated to deviate away from that profile.
Given finite game r = MWN. A,u,, this is formalized by the condition that, for all E A.
Σ Σ
(u:(a;;a,) (B(Baaa)))) =0.
(A.1)
TEA B.S.A.
From a strategic viewpoint, uniform harmonic games complement potential games: Candogan et al. [6] showed that any finite game be uniquely decomposed into the of potential game and uniform harmonic game, up to linear transformations of the payoff functions that do not change the strategic structure of the game.
Since their introduction, harmonic games have generated a substantial body of literature; for a brief survey, we refer the reader to [35].
A.I. Harmonic games, measures and comeasures. The class of uniform harmonic games exhibits intriguing, yet restrictive, properties. Notably, a UHG always admits the uniformly mixed strategy as
We include here the word "uniform" to distinguish the class of harmonic games introduced by Candogan al. [6] from the general class of harmonic games considered in this work, cf. Definition 1.
14

---

a NE, and it generally possesses continuam of Nash equilibria [6]. Additionally, the framework of UHGs and the decomposition proposed by Candogan al. [6] are incompatible with common caee-theoretical transformations, such as the duplication of strategies or rescaling of payoffs [1]. To address the above limitations, Abdou et al. [1] extended the definition of harmonic games by the introduction of two parameters: measure, that is a positive weight each player assigns to each of their own strategy; and a comeasure, that is a positive weight each player assigns to each of the other players' action profiles.
Definition A.1. Let I(V.A. be a finite game. A player measure μii is a function μi: Ar - R++; a player co-measure Yi function y: A-; R... Correspondingly, a collection μ {Mi Jie (resp. y = (yi)ienr) of player measures (resp. comeasures) is called game measure (resp. game comeasure). If μ4; is player measure, we will write |M; == La, Mia, Finally, probability measure is game measure l such that lla = 1 for all i E N uniform measure is game measure such that Hia, for all E a, E AA and a uniform comeasure is a game comeasure y such that Yia., = for all E NN a- A_..
With these notions in place, Abdou et al. [1] define a finite game I' be (n. hharrmoii if there exist a game measure j and game comeasure such that, for all a E A.
ΣΣ I
Hip,Yiar (u((rr ar-)) - u;(Baaa))) =.
(A.2)
In this work, we focus solely harmonic games with uniform comeasure. As discussed after Definition in the main body of the article, this choice comes without loss of generality; the game comeasure in Eq. (A.2) can be absorbed by payoff rescaling to give game that is still harmonic, and preference equivalent to the original game- in a sense that we make precise in the next section.
A.2. Preference equivalence between harmonic games. The strategic structure of a game is preserved under monotonic transformations of the utility functions, since the set of pure Nash equilibria game is an ordinal object- - depends only on the signs unilateral payoff differences, and not on their absolute values. For this reason, two games I(N A. u) and ("NN,A u') are called (PE) if for all a, E and all E N, we have
sgn (1 a/(a a a sgn [n| (Bi (aj(a;
(A.3)
Two games are strategically equivalent (SE) - and we write r I' if they have the same unilateral payoff differences, that is if
u((Bi;rri) - u4(a;;; -1:-)))-(((( = =u; (B(Baa)))) a((a;;a-))
(A.4)
for all a $ E A and all i E A; strategically equivalent games are clearly preference-equuivllnt.
Lemma A.2. Let Pu, = T (N. be a harmonic game in the sense of Eq. (A.2). Then the game (N. A,"')) with a(());=1)) Yia,,, ua(ajja) is preference-equivate it is harmonic in the sense of Eq. (A.2) with measure μ and uniform comeasure.
the game I Fu.yy and
Proof. Let (a Mia,Via Via, uiaaaa a-). Then replacing above, for all a E A.
(a
(B;aa)
0= Σ Σ Miß
iEN BEEA,
Pia,
Pig
Let aelafaaaa))) (apar))
Via Via_, (a((aa)))))) The game u' is preference--qqiivalent to u, and
Mia
0 Σ Σ Hig (1) ((;;;:
(A.5)
iEN A,
for all a E A, so u' is harmonic in the sense of A.2 with measure μ and uniform comeasure.
In the proof above we perform the intermediate step u - 1²" rather than defining directly - u' to stress the difference between rescaling the payoffs of game by game measure μ and by a game comeasure y. The game with payoffs u' = yu (the meaning of this notation made precise in the proof above) preference-equivalent to the game with payoffs u, i.e., rescaling the payoff's by a comeasure does not change the strategic structure of the game. On the other hand, the game with
15

---

payoffs n" = pmu again, the meaning made precise in the proof - is not PE to the game with payoffs u': rescaling the payoffs by a measure can change the preferences of the players, and leads a game with intrinsically different strategic structure.
Lemma A.2 motivates choice focus in this work harmonic games with arbitrary measures and uniform comeasures, and to adopt (HG) from Definition to characterize harmonic games: harmonic game (HG) F = n (N, A. u) is finite game (W, A. u) with game measure j such that (HG) holds, i.e., ΣieN Es.eA,, Mip,
- in (Br: a a-i) = 0 for all a E A.
A.3. Mixed characterization of harmonic games. The defining property (HG) allows for an equivalent characterization of harmonic games terms of their mixed payoffs:
Lemma A.3. A finite game r ([N.A, u) is harmonic with measure y if and only if
uui (x)())) ieN
Σ
Hi [pol ) =0 for all X.
(HG-mixed)
Proof. Given finite game I' TW,, u) u) and a game measure μ. let Fj: A - be defined by F((a) = Ep HiB, [u;(0;: 0=;) (;;B a.:)]. By definition, I is a j-harmonic game if and only F(a) LieN Fi(a)= = 0 for all a E A. Denote (with slight abuse of notation) by F: X - the multilinear extension of F: A - R. i.e., F(x) = Ea F(a), with X, = IT Nia Now, F(a) = for a E A if and only if F(x) = for x E X. which is the case if and only if
0= F(x) = E. Jo Σ, Fi(() = Σ, Σ a Ea, a., XiaiN-ia-: Ee pig [ur(a;;--) ui (B;ja-))) ail Σ, Es, ss Hip, (x,(xx)) -u, (Bixx-i)) = E, [1x])(1;(x)xxx)) - (v,(x), mi)] for all x X.
from which we conclude by factoring out the Ipe terms.
Remark.
The first equality in the second line holds true for harmonic games with uniform comeasure Yia_, = 1. since Yia., # terms would couple with the corresponding x-ta-; terms in the sum.
The above result can be reformulated as follows:
Proposition A4. finite game r I(N, A, u) is harmonic if and only if it admits a strategic center (m, (m.4), viz. if there exist (i) a vector m E RR,, and (ii) a fully mixed strategy E X such that
Σ mi (u;(x), qi) =0 for all x E X. TEN
(HG-center)
This expression is intriguing: it suggest that a game is harmonic precisely if there exists a fully mixed strategy q such that, for all x E X, the payoff vector o(x) is perpendicular (with respect to a m-ieittted inner product) to x - qi cf. Example A.1 and Fig. 2. The striking dynamical consequences of this "circular" strategic structure hinted in Fig. 2, showing periodic orbit of FTRL in continuous time- are captured precisely by Theorem in the main text.
Proof of Proposition A.4. Let r, = (N'. u) be harmonic; then by Lemma A.3 that there exist strategic center (m, q) given by m, == | and qi == 41/lul with E A. Conversely let r T(N. A, u) admit strategic center (m, q); then by the same argument I' is harmonic with μi == migi for all N.
An immediate corollary is the following:
Corollary A.5. If a finite game I admits a strategic center (m, q), then q is a Nash equilibrium.
Proof. By Proposition A.4 I admits a strategic center (m, q) then is p-harmonic with μ4; = m;qi for all E N; and (ul/e) is always NE for μ- u-harmonic games [1. Theorem 1].
Remark. The converse does not hold: a fully mixed Nash equilibrium is not necessarily a strategic center. it were, a game would be harmonic precisely if it admitted fully mixed NE, which is not the case think for example of coordination or anti-coordination games, that admit fully mixed Nash equilibrium and are not harmonic.
16

---

(AN): : (2, -4)
(N,N) (0, 0)
(A.D): : u (-3, 1)
(N,D) : (0, -1)
Figure 2: Representation of the harmonic payoff structure for the game in Example A.I. Each payoff vector uxx) (black arrows) is perpendicular (with respect to a weighted inner product) to the vector x - (dotted segment) hetween the evaluation point x of the payoff field and the fully mixed Nash equilibrium consequence every orbit of FTRL in continuous time (such as the one represented by the black curve) is Poincaré recurrent (in this low-dimensional example, even periodic), as detailed in Theorem in the main text. Color shading and dotted lines represents player I's utility level sets, with brighter regions indicating higher payoffs.
(red point). As
Example A.1 (A harmonic game: Siege). Consider the following x 2 game: an army (the row player) must choose between Attacking fortress (pure strategy ) and Not attacking (pure strategy N ). Simultaneously, the fortress (the column player) decides whether to activate its Defenses (pure strategy D) or Not (pure strategy
Engaging in either action (the attack or the defense) incurs preparation cost of c O. The army gains a, c if it attacks undefended fortress, but suffers a loss of a > if it attacks and encounters defenses (the subscripts y and f standing respectively for "successful" and "failed")). Conversely, the fortress benefits by d, O if it is defended against an attack, while it incurs a loss of d > 0 attacked without defenses; defeating the attacking army is worth the preparation cost for the fortress, namely d, following payoff matrix, specialized on the right to the case c 1, a, = 3, = 2, dg 2, dy = 4:
-dy. This scenario is captured by the
D
N
D
N
(-ap- c. dg -c) c) (as c, -d. (0. 0)
A
-3,1
2.
(A.6)
N (0. -c)
N
0,-1
0,0
To determine if the game harmonic, look for a solution of the linear system
Σ
Σ
Mip, Mup, [u,(a; a-)) aB = for all e A,
(HG)
TEN B.A.A
subject to the constraints Mia > for all N.a; A, For a fixed payoff function this is system of JeE A, linear equations (one for each a E A) in the ΣjeN Aj variables s, where A, is the number of pure actions of player i E N. With u given by (A.6) - left.
c
-c cc+d +d, )
a- a=-c
aa +c' ac+c "aayat"
(A.7)
a feasible solution of (HG) for any d > O, so the game is harmonic with a 1-dimensional set of measures. The corresponding strategic center (m, q) with m; Ea, Mia. qi p:/m;, (1, is
d dy + de af as) ac+c" as+ )
-c dr + de) ) as u--c as as+c
)]-
9=
(A.8)
d
aa aj+ as
As a sanity check, compute the payoff field and verify that (HG-center) holds true in the spe- cialized case (A.6) - right. Denoting the mixed strategies of players and 2 respectively by x E A[(A,N)) and y A)),,N)) the payoff fields are ta (x.y) (-3yp + 0). v2(x,y)
17

---

(xA-XN, -4x)). Choosing 1 = 3 the strategic center gives weights m (6, and Nash equilibrium q = [=166. 5/6), (2/5.3/5) Condition (HG-center) boils down to 6 ( -1) + (U2. y q2) which one readily verifies to hold true by replacing the expressions above and recalling that XA + XN = yD yN. Fig. 2 illustrates the situation: each payoff vector v(x) (black arrows) is perpendicular (with respect to weighted inner product) to the vector x q (dotted segment) between the evaluation point x of the payoff field and the fully mixed Nash equilibrium q (red point).
A.4. Harmonic and zero-sum games. Candogan et al. [6]'s uniform harmonic games, defined by Eq. (A.1), are precisely the harmonic games with uniform measure, which makes uniform harmonic games a strict subset of the set of HGs. Importantly, HGs include another archetypal class of perfect- competition games: as we show in this section, two-player zero-sum games (2ZSGs) with an interior NE x² are harmonic with (probability) measure μ = x"
To show this, we will need the following definition and lemma:
Definition A.6 (Non-strategic game). A finite normal form game = I(N.A, k) is called non- strategic if the payoff of each player does not depend on their own choice, viz. if ki(ar, a-i) k,(B,, -1) for all E N. a E A.B. A,
Lemma A.7. Two finite games I(N, u.,, are strategically equivalent in the sense of Eq. (A.4) if and only if their difference is non-strategic game.
Proof. L
be non-strategic; then == u' u fulfillss the condition of Definition A.6, which shows that u and u' fulfill Eq. (A.4). Conversely let I' and I" be strategically equivalent; set k == u uu and rearrange the terms in Eq. (A.4) to immediately conclude that k is a non-strategic game.
Proposition A.8. Let (N, be harmonic game. If the measure μ fulfills lpil | for all j E N then F is strategically equivalent to a zero-sum game.
Proof. Recall that |p;| = En, Mig. Under the assumption |us| |uنا for i, Nr let c == lua for any i E N. By (HG), the payoff u of F in this case fulfills Erev( k; k;)) = 0 for all E A, with ky a1) == c-1 Σp, Higs uy (B a-)). Set Set == u ky. By definition u' is a zemo-sum game; furthermore, the difference between it and u² is non-strategic, since (ay; a does not depend on ay Thus Hy and nf, are strategically equivalent by Lemma A.7.
In particular we have the following:
Corollary A.9. Let F L,NN,A,u be a harmonic game. If the measure μ is a probability measure, then I is strategically equivalent to a zero-sum game.
The converse holds true only in the case of two-player games:
Proposition A.10. Every two-player zero-sum game with an interior Nash equilibrium x" is harmonic, with (probability) measure μ =
Proof. Let I' = TWW u) be a two-player zero-sum game with interior Nash equilibrium x". If we show that
Σ Eki (01())))))) tEN
xi | =0 for all E X lx7
(A.9)
then we can conclude by Lemma A.3 that I is harmonic with measure x". Eq. (A.9) holds indeed true: [xj] = 1 for all / e A, and is well known [41, 42] that two-player zero-sum games with an interior equilibrium x" fulfill (x) x7) = 0 for all x X, so we are done.
Harmonic games thus encompass and substantially generalize two prototypical classes of games with anti-aligned incentives, serving an ideal complement to the class of potential games. This is made precise in [1]: building on the work of Candogan et al. [6], Abdou et al. [1] showed that, for any choice of game measure μl, every finite game can be uniquely decomposed into the sum of potential and a μ harmonic game, up to strategic equivalence.
This establishes harmonic games as the natural complement of potential games from strategic perspective; Theorem in the main text shows that this holds true from a dynamic perspective as well.
18

---

B Basic properties of regularizers and the induced choice maps
In this appendix, we collect a number of properties concerning regularizers and the associated choice maps. To avoid carrying around the player index i .V, we state all our results for generic convex subset of some real vector space V. The desired properties for FTRL will then be obtained by specializing X₁ or X' and V R-. or II R- depending the context.
B.I. Preliminary definitions. To begin, let V be a d-dimensional normed space with norm ||-Il- In what follows, we will write y = V" for the dual space of V. (y.xx for the canonical pairing between x E V and y E V and llyll max (y.x( ||*||| < 1) for the induced dual norm on y. Following standard conventions in convex analysis, functions will be allowed to take values in the extended real
line RU foo), and if f: R (co) is convex function V. we will denote its effective domain as
dom = (: f()) < co).
(B.1)
In addition, assuming dom f * Ø, the subdifferential of f at is defined
0f(x) ty e y: f(x) 2 f(x) + (y.x' x) for x' V)
(B.2)
and we denote the domain of subdifferenticabiliyy of f as
dom f = {xx E V 0f(x) * 0
(B.3)
Finally, to ease notation, a convex function f: C - R will be identified with the extended-reall-vluued function f: V - R u {oo} that agrees with f on C and is identically equal on V \ C.
With all this in hand, let be a closed convex subset of V, and let h: - R be a K-strongly convex regularizer on C, that is,
httx + (1 - r)x') S th(x) + +11 (1-1)h(x)) 2 1011 r)|l'' - xx|2.
(B.4)
By standard arguments in convex analysis, this readily implies that
K
h(x') 2 h(xx) 0h(x;x' x) +
2 I|xx x112 for all x, X.
(B.5)
where
Oh(x;'' xx) lim [4(x 0(x' - h(x)]/0 e--0
(B.6)
denotes the oie-sided directional derivative of x along the direction of x' x. To proceed, we will need the following basic objects:
1. The convex conjugate h" y - R h:
h" (y) max h(x))
for all y e y
(B.7)
xex
2. The regularized choice map- or mirror map Q: y - X induced by h:
Q(y) = arg max (yy,)) (y.xx) -h(x)) for all y e y
(B.8)
xEX
3. The associated Fenchel coupling F: x of h:
F(p.y) h(p) h (y) (y.P)
for all p X, y y.
(B.9)
Remark. The terminology "Fenchel coupling" is due to [38, 40], which we follow closely in terms of notation and conventions.
The proposition below provides some basic properties concerning the first two objects above:
Proposition B.1. Let h be K K-strongly convex regularizer on C. Then:
(a) Q is sangle-valued on y; in particular, for all x dom ôh and all y D, we have:
x = Q(y) and only if y oh(x).
(B.10)
19

---

(b) The image im Q of Q satisfies ri _ im Q dom åh S C. The convex conjugate h" y R of is differentiable and @ Vh' (y) for all y
(B.11)
(d) Q is (1/K)-Lipschitz continuous, that is, 11@(y)) - -(y)) & (1/K)lly' - yll for all y e y.
(B.12)
(e) Fix some y and set Q()). Then, for all x' X we have: ah(x;x' - Z xx)x'xx).
(B.13)
In particular, 0h admits continuous selection Vh: dom 0h - Y, we have
(Vh(x),x's -x) xy,x'= - for all x e dom òh and all x E C,
(B.14)
or, equivalently,
öh(x) Vh(x) PC(x) for all dom Oh,
(B.15)
where
PC(x) = (w E y: (w,x' - x) s O for all x' X)
(B.16)
denotes the polar cone to C af x.
Proof. These properties are fairly well known (except possibly the last one), so we only provide a quick proof precise pointer to the literature.
(a) The maximum in (B.8) attained for all y V and is unique because h is strongly convex. Furthermore, solves (B.8) if and only if y ah(x) O. i.e., if and only if E ah(x).
(b) By (B,,0), we readily get im Q dom oh. Consequently, the rest of our claim follows from standard results in convex analysis, see e.g., Rockafellar [52, Chap. 26).
(c) The equality Q Vh follows immediately from Danskin's theorem, see e.g., Bertsekas [4, Proposition 5.4.8, Appendix BJ.
(d) See Rockafellar & Wets [53, Theorem 12.60(b)].
(e) Since y (d((x) by (B.10), we readily get that h(x + 0(x' x)) h(x) 0(y x) xx)
for all [O. 1] Hence, by rearranging and taking the limit 0 0+ 10 conclude that
(B.17)
h(x + 0(x' x)) h(x) 2 (y,x'
Oh(x;x' x) lim e-0
(B.18)
as claimed. Finally, for our last assertion, let x' x and set
((0) h(x + 0z) [h(x) 0z)] for all 0 [0.
(B.19)
(0)) |001|=112/2 2 0 for all 0 E [0, 1]. By construction, it is straightforward verify that the function (0) = (Vh(x + 0z) y, z) is selection of subgradients of Φ, i.c.
((6') 2 ((0) (0) #) for o, 0' [0, 1].
(B.20)
Since is in addition continuous (because vh is), follows that ('(9) (0) for all 0 E [0, 1J by a well-known characterization of the one-sided derivatives of convex functions, Rockafellar [52, Theorem 24.2]. Hence, with & convex and &(0) 2 ((0) for all e [0. 1].
we conclude that (Vh(x) 2) = (0) = ø' (0) 2 0, and our proof is complete.
The next proposition collects some basic properties of the Fenchel coupling.
The existence of the limit is guaranteed by standard results, e.g., Bertsekas [4, Appendix BJ.
20

---

Proposition B.2. Let h be K K-strongly convex regularizer on C. Then, for all X and all y.y E V. we have:
(a) F(p.y) 2 with equality if and only i Q(y).
(B.21a)
(b) F(p.y) 2 ( - pll.
(B.2lb)
Proof. These properties are also fairly standard, but we provide quick proof for completeness.
(a) By the Fenchel-Young inequality, we have h(p) + h h"(y)) 2 (y, p) for all E X. y E V, with equality if and only if y E dh(p). Our claim then follows from (B.10).
(b) Let Qy) so y E ah(x) by (B.10). Then, by the definition of F, we have
F(p.y) 9) h(p) (1)))) (y.p)
h(p) (y.x) h(x) ky. p)
% since y ah(x)
h(p) h((x Oh(x:p-
by Proposition B.1 % by (B.4)
2 K||l - pll
and our proof is complete.
In view of Proposition B.2. F(p.y) can be seen "primal-dual" measure of divergence between E X and y E V, and the alternate expression (19) straightforward. This observation will play a major role in the sequel.
B.2. Basic lemmas. Moving forward, we note that the various update steps in (FTRL+) can be written as
y" y and x² = (u)")
(B.22)
for some y. E V. With this in mind, we proceed below to state series of basic lemmas for the Fenchel coupling before and after an update of the form (B.22). These results are not new, cf. [31, 40, 42] and references therein; however, the assumptions used to derive them vary significantly in the literature, so we provide detailed proof' for completeness.
All of the results that follow below are stated for K K-strongly convex regularizer on C. The first result a dual version of the so-called "three-poin identity" for mirror descent [7]:
Lemma B.1. Fix some p E X, y y, and let x Q(y). Then, for all y Y, we have:
F(p.y*) F(p.y) +(x.y" + (y* y.x p).
(B.23)
Proof. By definition, we have:
F(p.y*) h(p) + h²()") - -wy" (yy,p)
(B.24a)
F(p.y) h(p) (y) (y.p)
(B.24b)
F(x.y*) h(x) + +h*(y*) (y*,x)
(B.24c)
Thus, subtracting (B.24b) and (B.24c) from (B.24a), and rearranging, get
F(p.y*)= F(p.y) F(x, y h(x) h (g) (y* x) (ut - y. p)p)
(B.25)
Our assertion then follows by recalling that x Q(y). so h(x) + h hy) xy.x).
The next result we present concerns the Fenchel coupling before and after direct update step; similar results exist in the literature, but again provide proof for completeness.
Lemma B.2. Fix some p X and y. E y. Then, letting Q(1), y² + w, and x Q(y²) as per (B.22), we have:
F(p.y*) = (p..y) + (w,xx - p) F(x*,1)
(B.26a)
S F(pxx) (w.x- p) + K
(B.26b)
21

---

Proof. By the three-point identity (B.23), we have
F(x, y) = F(x,y")) + .x) (y- yx p)
(B.27)
so our first claim follows by rearranging. For our second claim, simply note that
F(p, y) + (w,x* - p) - F(x", .y) = F(p.y) + (w,x p> + (w, x² - xx - F(p.y)
K
Fp. (w,x p) 1w +
||x pll F(p.9)
2K
(B.28)
so our claim follows from Proposition B.2.
The last result present here is sometimes referred to "four-point lemma", and concerns the Fenchel coupling before and after an extrapolation step:
Lemma B.3. Fix some E X and y, wr. uz E y. Then, letting x = Q(y), yf = + wi. and x 2())), 1,2, as per (B.22), we have:
F(p.y)) F(p.y) + (w2,x p) [u2,, x7) F Fxxx .y]
(B.29a)
=((p.y) + (w),x} p) + (w> W1 x - xxx) - F(x; v/²) F(x
(B.29b)
K
s F(p.y) + (w2,x p) + 2K I wn 11.
2 1|, - xx12
(B.29c)
Proof. By Lemma B.2, we have
F(p.u)) = F(p.)) + (w2,x² p) - F(xt.
(B.30)
(B.29a) follows by writing (w2,x; p) (w2, x p) (w2, x and (B.29b) follows from the three-point identity (B.23) for the Fenchel coupling. Finally, for (B.29c), the Tenchel-Young inequality in Peter-Paul form yields
(w/ W1, w1. x - -x)> s 2K ||w wi will.+
2 ||x - x112
(B.31)
and our claim follows again by invoking Proposition B.2 write
2 || x F(x551))) F(xx -F( s - || - xx|
(B.32)
and then substituting the result in (B.31)
Lemmas B.2 and B.3 will be responsible for most of the heavy lifting to derive a Lyapunov function for (FTRL+). We discuss the relevant details in Appendix D.
We conclude this section with a variational characterization of the abstract update (B.22) in the case where Oh of h admits continuous selection or, alternatively, h is smooth in the sense of (17).
Lemma B.4. Fix some y.y" Y, and xetx* QQy*). Then, for all p X, have
(u+ - y. - x S (Vh(x*)= - y. x-x)).
(B.33)
Proof. Invoking (B.14) in Proposition B.1 with y y,, x t x², and - we get
(--ppx*) (vh(x*) x-
(B.34)
Our claim then follows by subtracting (y. p x*) from both sides of the above.
22

---

Continuous-time analysis
C.1. Dynamical systems notions. To fix notation, we recall here some basics from the theory of dynamical systems, roughly following [2, 51]. In this section, .M an open subset of a Euclidean space of dimension d.
We consider system of ordinary differential equations (ODEs) of the form
x()) (xx()))
(DS)
where x() a curve in M defined on an open interval I S R (that without loss of generality we assume to contain 0), and X M - Rd is smooth function. The function X is called vector field because it assigns a vector (x) to each point x in M, and (DS) is called dynamical system generated by X.
Given XO E M, an orbit with initial condition xo a solution x(1) of (DS) with x(0) xo. The flow generated by X is the smooth function @: I x M - . such that (xx) = An for all xo E .M and di (x) ((e, (x)) for all E I. In words, (xo) is the orbit x(() with initial condition xo; the existence and uniqueness of this function is guaranteed by the existence and uniqueness theorem of solutions of ordinary differential equations.
A flow + is called volume- prreeniiiree if vo)( = vol((f) for any (Lebesgue) measurable subset U . and all f e I. Liouville's theorem gives sufficient condition for a flow to be oolume-preservvee based on the divergence of its generating field:"
Theorem (Liouville). If div X then the flow generated by X is volume-preserving.
Volume-preserving flows are closely related to recurrent dynamical patterns. A point.x e M is said to be recurrent under (DS) if, for every neighborhood U of x M, there exists increasing sequence of time in 1 oo such that Gr, (x) is defined and falls in 24 for all n. Moreover, (DS) is said to be Poincaré recurrent if almost every point x E .M is recurrent. The celebrated Poincaré recurrence theorem gives a sufficient condition for dynamical system to be Poincaré recurrent:
Theorem (Poincaré). Let X be smooth vector field on M. If the flow induced by X is volume- preserving and all the orbits of (DS) are bounded, then (DS) is Poincaré recurrent.
C.2. Basic properties of FTRL. In this section we survey some of the properties of the follow- the-regularized-leader learning scheme in a continuous-time, multi-agent setting, in line with the presentations of [16, 38, 41J. For ease of reference we recall here some of the notions introduced in Appendix B and in Sections 2 and 3 from the main body of the paper.
Let I(N, A. be a finite normal form game, and let v denote its payoff field. The game's strategy space is X' = I1jeN A(A)) VV= = II, RA,, and the game's ' payoff space is y = V*. The payoff field is a map D: V - y' that evaluated at strategy E X acts linearly on any x' e X by
(o(x).x²) = Emev(o(s)) = EieN E Viar (x) (x)xx
(C.1)
= EieN (x,,xx))) R.
Assume now that I' is played continuously over time. As discussed in Section 3, the main idea behind the fellow-th-reguulrrize---e- tracks their cumulative payoff up to time / and plays a "regularized" best response strategy in light of this information. Concretely, given a cumulative payoff vector ()( E }/ each player i E A selects this optimal strategy xy E X, by means of a regularized best response map Q:: 3/- - X, a single- valued analogue of the best-response correspondence yi + arg max m (y), x1). A standard way [57] of obtaining such map is to introduce regularizer function h X; - IR that is (i) continuous on X, (ii) smooth on X, the relative interior of X,, and (iii) strongly convex on X, (as per Eq. (B.4)); and to consider the induced choice map Q:: )/ - X; defined by
learning scheme is that, any given time 2 O, each player i W
()(y)) arg x (yr, xi) hx(x;) for all y E V
(6)
By Proposition B. Q; is well-defined and Lipschitz continuous, and it coincides with the differential
Vh; of h; V/ - R, the convex conjugate of h,
Recall here that the divergence is differential operator mapping vector field X on M to the real-valued function div x(x) == nd 0, (x), where å, is shorthand for the partial derivative 0/0xa
23

---

In continuous time setting, this regularized learning scheme translates into the following implicit equations of motion, which govemn the evolution of the cumulative payoff y(t) e y and of the mixed strategy profile x(1) X' as the players attempt to maximize their payoff over time:
yio; (1) = yi (0) (0)+))++)))))) + ''' Uio, (x(T)) dr with x1(1) = (((((()),
(C.2)
for all i E N. E Al- A straightforward computation shows that this is equivalent to Eq. (5) from Section in the main text, that governs the evolution of the mixed strategy x(t) N::
( dr dr -h(pi)))) = arg max Pre
(,," (e:x(((())))))) dr hilp)) (5)
(1) arg max
P.E
Importantly, Eq. (C.2) can be cast in the form (DS) of a dynamical system in the game's 's payoff space. For each i E N, differentiation with respect r yields
(1) 0; (x(())
x1()= = ()),
(FTRL-D)
and by aggregating the player indices we obtain the system of ODEs
y = Ygy)
(C.3)
where Y == o Q: y - 3/ is continuous vector field on )) cf. Fig. 3.
Existence and uniqueness of global solution y(r) y of Eq. (C.3) for any initial condition ((0) y are guaranteed by standard arguments [38, Prop. 3.1]: in line with the terminology of the previous section will refer to such solution dual orbit.
C.3. Constant of motion for harmonic games. The following result shows that FTRL in harmonic games admits constant of motion.
Proposition C.1. Let I(N. A. u) be a finite game and consider a vector m E R and a fully mixed strategy q X. Then the weighted Fenchel coupling Fm.q: Y - R defined by
Fm.((1) = mi.FF. = E, my (h((g)) + kÇ(w)) (91-9))
(C.4)
a constant of motion under (FTRL-D) if and only i is harmonic with strategic center (m, q).
Proof. Let y(t) be dual orbit. Then by chain rule
d
dt Fm..(u(t))
(g:. [i) -,, mi (xi(1) qı, (;(())
(C.5)
where the second equality holds by (FTRL-D) and Eq. (B.11). Then, by the characterization of harmonic games in terms of strategic center (HG-center), the time derivative of the weighted Fenchel coupling vanishes identically along a dual orbit of (FTRL-D) precisely if the underlying game is harmonic.
The existence of this constant of motion is fundamental for proving Theorem 2, i.e., the Poincaré recurrence of continuous-tim FTRL in harmonic games. With this key element established, the remainder of this appendix closely follows the proof technique described by [41] for the analogous result in the context of two-player zero-sum games.
C.4. FTRL in the space of payoff differences. For any initial condition y(0) E ), a dual orbit of (FTRL-D) induces a curve x(1) = Q(y(r) in the game's strategy space X' which solves Eq. (5) for all r 2 O: in the following we will refer to such curve as trajectory of play. Crucially, trajectory of play in general not the global solution of a dynamical system x X(x) for some vector field X X' in the game's 'ss strategy space. The reason for this is that the map Q: y X' is not necessarily invertible, so there is in general no way to identify unique a vector field X on that related to the vector field Y on via Q.
24

---

V= B1
R-
V
>>
F y
R
Q
X
Z
Q
Figure 3: FTRL diagram. Commutative diagram of the maps discussed Appendices C.2 C.4; note in particular that a o Q is a vector field on y. The notation X' < V'ss equivalent c V.
Related vector fields and induced dynamical systems. The concept of vector fields related by a smooth map is standard in differential geometry (e.g- [34, p. 181J). Let M, be open subsets of Euclidean space: given a vector field Y on M and a smooth map F: MM- - MM, a vector field X on M' is called F-related to Y if, for all y M, (Jac F) Y(y) = (x)), with the Jacobian matrix of F, and represents matrix- vector multiplication. If F is invertible then such vector field exists always and is unique; else, it might exist and not be unique, or not exist at all.
F(y). Here Jac F is
Vector fields that are related via a smooth map are useful inasmuch as they generate "compatible" dynamical systems:
Lemma C.2. Let F: M- be smooth map between open subsets of Euclidean spaces, and let y = Y(y be dynamical system on M. Let y(t) be an orbit with initial condition yo E M, and consider the curve on M' defined by x(t) == Fly()). If there exists a vector field X on M' that is F-related to Y, then the curve x(1) is an orbit of the dynamical system x X(xx with initial condition
Xo = F(y)).
Proof. By chain rule,
d di _x -(y(t) = (Jac F)y()) j()) = (Jac Fly() Y(y(t)) = X(x()),
(C.6)
di
where the last equality follows by the assumption that X is F-related to Y.
In the following, if F: M MM' is a smooth function between open subsets of Euclidean spaces, and Y, are vector fields fulfilling the assumptions of Lemma C.2, we say that the dynamical system ý Yyy) .M induces the dynamical system x = (xx) on M' via F.
FTRL induced in the space of payoff differences. The choice map Q: 3 - X' is in general not smooth, and neither injective nor surjective [16, Sec.3), so it generally does not allow to induce the dynamical system (C.3) from the game's 's payoff space y to the game's 's strategy space X. In other words, the learning process (FTRL-D) in a finite game gives rise to a dynamical system in the game's ' payoff space V, which the theorems presented in Appendix C.I can in principle be applied: however, it can be shown that the orbits of Eq. (C.3) in y' are not bounded, preventing the application of Poincaré's theorem. Furthermore, the dual orbits do not convey direct information on the day-to-day behavior of the players, due to the lack of invertibility of the choice map.
Conversely, the objects of interest from dynamical, learning viewpoint- that is, the trajectories of play in the game's 's strategy space X - present technical difficulties and do not easily fit the dynamical systems framework depicted in Appendix C. In the following we show how these difficulties can be circumvented by analyzing the dynamics induced by (FTRL-D) in yet a third space Z, that arises by taking the differences between payoffs rather than their absolute values as the objects of study.
To make this precise, given the game r A, u) fix a benchmark strategy â; E A, for every player i e N, and consider the hyperplane 2, == [2 E RA: žιd; = 0) c RA, Clearly, 2, = RA:- Each player's strategy space );- RA: can be mapped onto Z, by the linear operator
I1 D/ - Zi with Zia. = Yia Viá
(C.7)
for all a; E A..
A detailed treatment of the conditions under which a trajectory of play x(i) actually is a solution of dynamical system in the game's 's strategy space X' is beyond the scope of this work; we refer the interested reader [38, 39] for an in-depth treatment.
25

---

I1 is clearly smooth, and standard check shows that II, is surjective and not injective: ker II; {y: Yiu yip, for all a; B, A is the 1-dimensional linear subspace spanned by the vector 1, = (I.....1) Vi; and II (z,) = 2; + ker II, for any 2 E Z, In partieular, for all Di e 3i we have that (1)))) = I1 (1/) if and only if yi y/ is proportional to 1,
Since every zi E Zi is the image of some payoff yi via II, the space = IT Zj is called the game's payoff-difference space, we will denote by II the product map II = [I, [l,, i.e., (cf. Fig. 3)
II: y 2, [1y)= = (IINN
(C.8)
Lemma C.3. The choice map Q: y - X is invariant on the level sets of II.
Proof. Let y. V. By the discussion above, Iy(y) II(y') iff y/ yi 21, for some E R. Then for each i N,
Qi(y/) = arg max (1/, hxxx))) arg max (y: xi) + x(1,, h;(x;)) Qu(y)) x,EAi
x,
Proposition C.4. The dynamical system (C.3) in the game's 'ss payoff space y induces a dynamical system
غ = Z(z)
(C.9)
the game's 's payoff-different space via the map (C.8).
Proof. By the discussion in the previous section (and in particular Lemma C.2), if we exhibit a vector field Z on Z that I-related to Y, then our proof is complete. Thus we look for a vector field Z such that, for all y E y
(Jac IT) Y(y) 7(22)
(C.
with [y)) By Eq. (C.7), (Jac O1 =,aff, Sā, Since Y o Q, the sought-after vector field Z must fulfill, for all y E y and all 0; E Ai,
(Uja, v(ū,) Qi(y;) Zian (zz),
(C.11)
with (1)). For each i E N define now (cf. Fig. 3)
e: 2, + Xr ii(zi) = Q(yi)
(C.12)
for any y (z)), and denote by @: 2 - X' the induced product map. Such map exists since IT; surjective, and is well-defined by Lemma C.3. It follows that the vector field on 2 defined by
Zio (zi) = (Uio, Uta,) (z(z))
(C.13)
for a e N. a, E A, fulfills Eq. (C.11), and is hence I-related to Y.
This result shows that, for every dual orbit y() of Eq. (C.3) with initial condition yo E V, the curve z(r) [[((()) is orbit of the dynamical system (C.9) in Z with initial condition Iyy)). To conclude this section we give a result implying that if the weighted Fenchel coupling (C.4) is a constant of motion constant then the solution orbits of (C.9) in Z are bounded.
Lemma C.S. For any i N, let yi be a sequence in Vi, and let pi be a point in the relative interior of X. suu,,, (yi,n) - (yi pi)l < so, then also the score differences remain bounded, i.e., 1ya,, yip,,al < so for all u.. B; E Ai and all n.
Proof. See [41, Appendix DJ.
Lemma C.6. the weighted Fenchel coupling (C.4) is constant of motion under (FTRL-D) for some fully mixed p e X then the orbits of 2 = Z(z) as in Eq. (C.9) are bounded in Z.
Proof. Assume that (y) E, M; yi) Σ, m; (ha(p:) (;(()) (pix (P:)y)) is constant of motion for (FTRL-D) for some fully mixed p X' and some m E RRN Let y(1) be an orbit of (FTRL-D) in V, and let yi, = g;(1n) for any sequence of time 4,- Let furthermore Fi,, = (y,,)) yr.)) Then sup, Find co. By Lemma C.5, this implies that Rza < co for all di E A, all E N. and all n.
26

---

C.5. Recurrence of FTRL in harmonic games. We now have all the ingredients to prove that almost every trajectory of play x(t) of (FTRL-D) in harmonic games returns arbitrarily close its starting point infinitely often.
Theorem 2. Suppose I' is harmonic. Then almost every orbit x(1) of (FTRL-D) returns arbilrarily close to its starting point infinitely often: specifically, for (Lebesgue) almost every initial condition x(0) = (O)( E X, there exists an increasing sequence of times In 1 oo such that x(tn) - x(O).
Proof of Theorem 2. The proof relies on the following steps:
1. the vector field defined in Eq. (C.13) has vanishing divergence, so its induced flow volume- preserving in Z by Liouville's theorem;
2. the orbits of the dynamical system Z(z) of Eq. (C.9) are bounded in since the weighted Fenchel coupling (C.4) is a constant of motion for FTRL in harmonic games;
3. the dynamical system غ Z(z) is recurrent in 2 by Poincaré theorem;
4. by continuity of Eq. (C.12), almost every trajectory of play x(t) of (FTRL-D) with initial condition in the image of Q returns arbitrarily close to its starting point infinitely often.
Indeed, div Z(z)= Ei Eai dza;
a ((Via, vid,) Qi(z))). For the first term, by chain rule,
Tvaa, (Ō(z)) aQ (z) diaa (()(z))) = Σ. o2 Σ EB,
div 7(2)
Σ oi d Ozia
0x
dzam
ausa (())) 0lip (2) 0
Σ E. 01 Σ Bi dxis.
Ozia
since 0xie,
0 by multilinearity of the payoff functions. The second term yields identical result with à; - aa, so we conclude that div Z O. By Lemma C.6, the invariance of the weighted Fenchel coupling under (FTRL-D) implies that the payoff differences Zio; (1) yio, (1) Zi (t) remain bounded for all / E [0, oo). So, by Poincaré theorem, the dynamical system غ = Z(z) is Poincaré
recurrent, i.e there exists a sequence of time f, such that lim, z(t,) = 20 for almost every
zo Z. By continuity of (C.12), almost every trajectory of play x(1) Q Q(z(t)) with
xo E im @ fulfills lim x(x,)) Xo, which concludes our proof by noting that the image of Q is the same as the image of Q.
D Discrete-time analysis
In this appendix, our aim is to provide the full proofs for the discrete-ting guarantees of (FTRL+), as presented in Section 4. Our analysis hinges series of energy functions and associated template inequalities, which we introduce in the next section.
D.1. Lyapunov functions and template incqualities for (FTRL+)) The main building block of analysis is suitable Lyapunov function for the discrete-ting time algorithmic template (FTRL+). Motivated by the continuous-ta analysis of Appendix C, we begin by considering the player-specific Fenchel couplings
Fi(P..t)) = h;(p:) + (1)) (yi p.) for P: E X₁ y: E );
(D.1)
induced by the regularizer h; of player i E N.
Suppose now that the game is harmonic relative to some measure = (HI...., MNN, ), let m; E Mio, denote the mass of μ. and assume further that each player running (FTRL+) with learning rate ni > O. Our analysis will hinge on the energy function
E(p.y) = Σ mi
F. yi)
Peppe PEX.yE))
(18)
IEN
which, as we show below, satisfies the following template inequality:
27

---

Proposition D.1. Suppose that each player is running (FTRL+) with learning rate ni > 0 in harmonic game as above. Then, for all pi E N2 E N. and all 1,2. .... the algorithm's energy En == [p yn) enjoys the iterative bound:
Eat1 S En +
Σ
m (11
pi)
iEN
Σ
mi(u; (xm+1122) oz(NN) xi,x+1/2)
Σ
--) 02 (12) Xi,tt x1,n+1/22)
Σ
mi
EN
M
Σ
mi
(D.2)
EN
M
Proof. We begin by applying the bound (B.29b) of Lemma B.3 with the array of substitutions
1. p p-p Pi
2. W1 - nidi, = 17d24 (xn) + 17:(1 11) (x(x-11/2)
3. un - 11/2 = 11101 (An+1())
4. y yi
x Qilyi.n) Xi,n
5. , - 11,n+1/2
so x Xin+1/22
6. y/ - Vi.++l
80 x2 - Xi,ntl
We then get
(w2 W/, x1 x22 - x 77 (Xn=+12)))2 - (;(n) - ( 112 - -xn++122
17 (Xm+112)) (xn),, X1,
+ 71 10)1-1))00 (1(((n) (x x1,n+1/2)
(D.3)
and hence, by (B.29b):
Fr (t.1)) S Fi(pi. (i.)) + ni 11(t((HH++1122.:0001111 -P))
n (1 (x x1,n+1/2)
+ n/ (x) - (1(( xt,+1122
F((
F/(8).+1/2-
(D.4)
Accordingly, with E, yp), the bound (D.2) follows by multiplying both sides by mi/n and summing over i N.
Thanks to Proposition D.I, now in position to state and prove the following summability guarantee for (FTRL+).
Proposition D.2. Suppose that each player in a harmonic game I with harmonic measure μ is following (FTRL+) with learning rate S m, mm + 2) max, m MjG,Y G,1 Then, for all T, we have:
2E
El - x, Σ ||, Xn xn21/2112 (N + 2) max; m;G;
(D.5)
n=l
n=2
In particular, the sequences A, == [|xx+1/22 x2 and B,, ||x x are both sunmable.
Proof. By reshuffling the terms of the template inequality (D.2), we get
(1(1)(Xm=1/2)- Pi x1,n+112) E,,- Eyt1 IEN
Σ
+ Σ
(=((2((n++12) Uz (z(xn), Ni,ut1 -ii,++1/2)
(D.6a)
28

---

+
Σ m;(1 - (x) - (2 N1,++1/2)
(D.6b)
Mi Σ Fj (1
Σ
F Yi,)) (D.6c)
ieN
M
iEN m
We now proceed to bound each term of (D.6) individually, paying no heed to make the resulting bounds as tight as possible.
Bounding (D.6a).
By the Fenchel- Fennhel-Young inequality, we have:
(D.6a)
Σ
mi
(x=+11))
0z(xx)11
Σ
m
||xi,
11/
2G;
2
leA
icN
m,G
Σ
1/+11/2
xnl1²=
Σ
||x XLx+1/211
% vx() Gi-Lipschitz
2
IEN
IEN
N max; m,G, ||xx+1/2 - xnl
+ max; m,G; ||x++1 X211/211
(D.7)
Bounding (D.6b).
Again, by the Fenchel- Fenchel-Young inequality, we obtain:
mi -2)
my (1)
(D.6b) $ Σ
[[0;(X,) By (x(xn-1/2)13
Σ
||xi,tt] - 1/241/221
2G;
2
E&N
IEN
m2(1 - G;
m; (1 - -2:)
< Σ
||xm - 1121/2112
Σ
||x|,tt] Xi,n+1/211
2
2
ieN
ieN
% (x) is Gi-Lipcchizz
N max; m;G; ||xn 11-1/2 max; m;G; ||xm+1 1211/21
(D.8)
Bounding (D.6c).
Finally, by the lower bound on the Fenchel coupling of Proposition B.2, get:
Σ
mi
(x (i,
Σ
mi 1/(xx,n+1/2--H..))
iEN
iEN
K;Ki
m;Ki ||xi,
s
Σ
||xintt - X 1/2
Σ
xinll? xi 2m
% by (B.21b)
2m
icN
m;Kr Ki
S min;
[[[x,+] x
||x x, [1]
(D.9)
2mi
Thus, by folding Eqs. (D.7)-D.99 back into (D.6), we obtain the bound
Σ
mi (1(((Xn+1))) Pi xinn+1/2) s En Ens1
max; m.G min, M,K;
||xm+1/2 - =x,l1
m m;K;
2 max; m,G, min;
|| - xnt1/211
T
max; m;G; ||x, xn21/2112
(D.10)
Now, if we instantiate (D.10) to p + q where q is the strategic center of r, its left-hand side (LHS) will vanish by (HG-center). Hence, summing over all 1,2..... (D.10) ultimately yields
m;K;
0 S E1 max; m,G; - min;
|,41122 - x,,1
m
n=1
m;Ki
(N+ 2) max; m;G; - min;
|x - 1/21/211 Σ
1
m,Ki
2 max; m, m,G, - min
||xTН| - x
mi
29

---

max; m; ||x| x1/2112.
(D.11)
Now, by our step-size assumption, we readily obtain
m;Ki
(N + 2) max, m, Gr $ min; 171
(D.12)
(D.11) becomes
m.K,
m,K; T El1a,
0 s Ei
min
Σ
1 -xx11²
min,
-1
1221
(D.13)
77
#=1
T n=2
where we used our initialization convention x1 negative. We thus get
X1/2 and the fact that the third line of (D.11) is
T x,,1 Elxn X 11xxa-1/--
7
4E
(D.14)
min, m Ki
m=
n=2
from which assertion follows immediately.
D.2. Proof of Theorem 3. We are in position to prove the regret guarantees of (FTRL+), which we restate below for convenience.
Theorem 3. Suppose that each player in harmonic game I' is following (FTRL+) with learning rate S mm K;Ki + 2) max m,G G and payoff models as per (13a) and (15). Then the individual regret of each player NN bounded as
H.
2G
H njG
Reg,(T) max Elu(prx--in) (x,)) S PLEA R=1
Σ JEN
(16)
N
+
where II max h; min h;, and G; is the Lipschitz modulus of uj.
Proof. By a minor reshuffling of terms in (D.4), we readily get
1
(v: (Di(Kn+1/2) Pi Ki,n+1/2) s - -[Fi(p..y..) Pi(Pi.yi.ntl)
m
+ (v,(xn+1/2) (xxx) Xi,t1 xt,+11/2)
+ (1 AxME)((n)) (1n- xi,n+112)
Fi(xintt 9i,41122
Fr(2i, yi.n)
(D.15)
π]
and hence, by repeated application of the Tenchel-Young inequality in its Peter-Paul form:
(vz(xx+1/2)- Pi x1,n+1/2)
[ii(ps Fi mi.1
7
G
+
||l (x)+112)) - (x,xx)
[|x,,+]] x1,4+1/212
2G;
A
[]1;(X,)) 02 (xn (1 (1-1,
||xi,tt]
1/2m1
2G,
[|lx,,n1- x1.m41/211 || - x1,,n
(D.16)
2m,
Hence, by using the Lipschitz continuity of u; we finally get
(x)(1111/)) Pi x1,n+112)
Fi(p..y..)) ((pi))
771
G;
G; 2
+
||x xx112++
||x - x1,411/212
2
G;
G;
||x,, - -xn-1/211++
| X2,0112112
2
30

---

Ki
[|x x/,0+1/211*+ 1|/,,
-x,nll Xi,nll]]
(D.17)
2m
Thus, summing over n = and keeping in mind that our assumptions for dii also give G₁ < (2/(2n)), we finally get
H;
Gi
T Σ ==1
T Σ |x Xn 1/211 n=
x1,m+1/2) Pt $
+
x,112
(D.18)
M
2
where used the fact that Fi(p,, 0) h(p) min h max h, min h = He. Our result then follows by invoking (D.5) and using the fact that m,G, S max, my myG for all E N.
D.3. Proof of Theorem 4. With all this hand, we are finally in a position to prove our main equilibrium convergence result for (FTRL+). For convenience, restate the relevant theorem below. Theorem 4. Suppose that each player in a harmonic game I follows (FTRL+) with learning rate Hi $ m; K; [2 + 2) max, m,G G]] and payoff models as per (13a) and (15). Then Xn converges to the set of Nash equilibria of I.
Proof. Our proof proceeds in a series of steps, as detailed below.
Step 1: Convergence of energy levels. We begin by showing that the energy En = E(q, yie) of (FTRL+) relative to the game's 's harmonic center converges to some finite value Eos- That this so follows from well-known property of quasi-Fejér sequences [10, Lemma 3.1], whose proof reproduce below for completeness.
Indeed, by Eq. (D.10) and Proposition D.2, we have
Entl S En + En
(D.19)
with Ep, 1,2. summable. Letting Eú = En Dk-n Ek. we further get
E/ Ent1 +
Σ EK E, + =x
(D.20)
k=n+1
k=
by (D.19), so E, converges. Since En is summable, it follows that E, also converges, as claimed.
Step 2: Boundedness of score differences. We now proceed to show that the normalized score differences 2n = II(y,) where the normalization operator (C.8) are bounded. Indeed, by the definition of En = E(q, yn) (m; (i It.,), it follows that sup, Fi 9t.n) < co for all i W. Thus, by Lemma C.5, we conclude that each component of zn is bounded, so is itself bounded.
Step 3: Convergent subsequences of (FTRL+). We now observe that (FTRL+) enjoys the following series of properties:
1. The sequence zn IT())) admits subsequence Zng that converges to some limit point E Z (a consequence the fact that žn is bounded, see above).
2. In turn, this implies that the subsequence Xnx Q(yme)) Q(zz.) converges some x X'
3. Since the sequences A, ||x - xx and B, ||x 1/21 are both summable (by Proposition D.2), we further have limg-co Xny +1/2 X and, more generally, by straightfor- ward induction:
lim Anger = Xoc for any (fixed) = 1/2, k00
(D.21)
4. Likewise, for the sequence of payoff signals On. we have
dr.ng d, 1, + (1 - Ar) 0y (x k000 Awxi(Xaw) + -1))u((xx)) = 1x(Xa)) (D.22)
so limg- v(xmg) v(xso).
31

---

Step 4: Variational characterization of limit points. We now proceed to show that tae == u(Xw)) belongs the polar cone PC(x {w y (w,x (w, & 0 for all 2 X' at Noo To do so, suppose that (FTRL+) performs r steps from
yugtr ynu +
mg2
(D.23)
where, to ease notation, we have made the simplifying assumption that dii = 1 for all W.13 Then, by invoking Lemma B.4 with y < you and y² yngtr, we obtain
1/2- P Inetr s (Vh(xme+r) Yn P Xngtr)
1=1
= <Vh(xnnet)) Zny. P Kngtr)
(D.24)
where, in the second line, we have used the fact that (y,x' -) = (I(y)) - x) for all x, e X' and all y E V Thus, letting k co, we get from Step 3 and the continuity of Vh that
mR (x(x x s (Vh(xw) Zoo xaa)
(D.25)
for all r = 1,2.... and all x X. 14 Since can be chosen arbitrarily, we must have x s 0 for all x E X. Hence, by the variational characterization (VI) of Nash equilibria, conclude that Xse must be itself a Nash equilibrium of r, and our proof is complete.
19his assumption does not affect the core of our arguments, but it greatly streamlines the presentation.
14ehe fact that E dom dh is consequence of Lemma C.5 and the convergence of En Eco
32

---

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

---

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

---

Answer: [No]
Justification: We do not release the code at this point as we don't to have time to anonymize it. We describe in detail how simulations are performed and will make the code available later stage.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cccpubiii
Suldda//CoddSummmssiiooolllgg for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https://nips cc/public/ ccc/pulic/guides/CCCan http://eeeeuammiiooooooiiiiiiiie
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparame- ters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provide all details for the simulations.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question:
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors variability that the error bars are capturing should clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar the standard deviation or the standard error of the mean.
35

---

It is OK to report I-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: All simulations performed on standard laptops and as such do not carry any particular computational burden.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experi- mental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:////eeiiieecpppppp////eeeee
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
Justification:
We discuss in the introduction the of learning in games.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
the authors answer NA or No, they should explain why their work has no socictal impact or why the paper does not address societal impact.
Examples negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
36

---

The conference expects that many papers will be foundational research and not tied to particular applications. let alone deployments. However. if there is a direct path any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could he used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (c.g,, gated release of models, providing defenses addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system Iearns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors take this into account and make a best faith effort.
12. Licenses for existing assets
Question: Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.comm www.:wtwwwe..oooooooo com/dataseta datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged reach out the asset's s creators.
13. New Assets
37

---

Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL include anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribution of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
38


Reviews:
[{"review_id": "IraxaT5sXu", "reviewer": "Reviewer_1Wrk", "summary": "The contributions of this paper are two-fold:\n\ni) They prove that continuous FTRL dynamics for general harmonic games are Poincaré recurrent and hence do not converge. Their result generalizes the original result of \n\nMertikopoulos, P., Papadimitriou, C. H., and Piliouras, G., 'Cycles in adversarial regularized learning,' In SODA ’18: Proceedings of the 29th annual ACM-SIAM Symposium on Discrete Algorithms, 2018, \n\nfor zero-sum games with an interior equilibrium (as a trivial example of harmonic games), and the result of \n\nLegacci, Davide, Panayotis Mertikopoulos, and Bary Pradelski, 'A geometric decomposition of finite games: Convergence vs. recurrence under no-regret learning,' arXiv preprint arXiv:2405.07224 (2024), \n\nfor uniform harmonic games to general harmonic games by volume-preserving flow arguments.\n\nii) Moreover, they show that the regret of general harmonic games for the class of Extrapolated FTRL algorithms (discrete-time dynamics) is constant in time ($T$).", "questions": "I do not have any particular question (as the results shown in this paper are not unexpected) except that could authors provide some intuition on the conjecture that convergence to Nash Eq. of no-regret learnings for general harmonic games would be linear beyond the work of \n\nWei, C.-Y., et al. Linear last-iterate convergence in constrained saddle-point optimization. In ICLR ’21: Proceedings of the 2021 International Conference on Learning Representations, 2021.\n\n? (Non-asymptotic version of Theorem 4)", "limitations": "Not applied.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The contributions of this paper are solid and interesting. This paper addresses fundamental problems in harmonic games.\n\n- I enjoyed reading the paper. It is well-written, especially the introduction to harmonic games in the appendix and the new viewpoint of Mixed characterization of harmonic games and its role on upper bounding the path length of the no-regret dynamics.", "weaknesses": "- Just some missing citations on no-regret learning for games, e.g.,\n\n-- Daskalakis, Constantinos, Alan Deckelbaum, and Anthony Kim. \"Near-optimal no-regret algorithms for zero-sum games.\" Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms. \\\n-- Chen, Xi, and Binghui Peng. \"Hedging in games: Faster convergence of external and swap regrets.\" Advances in Neural Information Processing Systems 33 (2020). \\\n-- Piliouras, Georgios, Ryann Sim, and Stratis Skoulakis. \"Beyond time-average convergence: Near-optimal uncoupled online learning via clairvoyant multiplicative weights update.\" Advances in Neural Information Processing Systems 35 (2022). \\\n...\n\n\n__Minor Suggestions__\n- Please emphasize in the claims that the regret bounds entailed are constant in $T$ and not potentially in the dimension of the action sets $\\mathcal{A}$, since $H_i$ is not constant in $|\\mathcal{A}_i|$.\n- Regarding the notation for $\\nu_i(x)$, maybe consider changing it to $\\nu_i(x_{-i})$ to improve readability.\n- In line 268, $x_{n + 1}$ instead of $x_{n}$?\n- In line 277, \"and\" before \"which\" seems to be a typo.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer 1Wrk,\n\nThank you for your strong positive evaluation and encouraging remarks! We reply to your questions and comments below:\n\n> Just some missing citations on no-regret learning for games [suggestions follow]\n\nThanks for the pointers, we were aware of some but not all of the references you provided -- we will discuss them accordingly.\n\n\n> Please emphasize in the claims that the regret bounds entailed are constant in $T$ and not potentially in the dimension of the action sets $A$, since $H$ is not constant in $A$.\n\nDuly noted - we will note this dependence explicitly to avoid any misunderstandings. Thanks for bringing this up!\n\n\n> Regarding the notation for $v_i(x)$, maybe consider changing it to $v_i(x_{-i})$ to improve readability.\n\nYou mean in order to make explicit the non-dependence on $x_i$, correct? This is an excellent suggestion - we will run through the paper with a fine-toothed comb to make sure it does not create any clashes of notation and adjust things accordingly. Thanks!\n\n> [Typos]\n\nWill fix those, many thanks for the careful read!\n\n\n> Could the authors provide some intuition on the conjecture that convergence to Nash Eq. of no-regret learnings for general harmonic games would be linear beyond the work of [Wei et al.]? (Non-asymptotic version of Theorem 4)\n\nOur intuition comes from the fact that the harmonic measure always gives rise to a fully mixed equilibrium. Since this *specific* equilibrium of the game lies in the interior of the simplex, the weighted sum in the definition of a harmonic game formally looks quite similar to the condition needed to establish metric subregularity in the work of [Wei et al.]. Our conjecture reflects our (optimistic :-) ) belief that this formal similarity could be leveraged to yield a linear convergence rate result in the spirit of [Wei et al.]. However, at this stage, there are too many unknown variables - and metric subregularity can be tricky in problems without a convex structure to rely on - so, for the moment, this is purely conjectural.\n\n---\n\nPlease let us know if you have any follow-up questions, and thank you again for your time and positive evaluation!\n\nRegards,\n\nThe authors", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "Lk2k3FCRgB", "reviewer": "Reviewer_gj66", "summary": "This paper studies multi-agent no-regret learning dynamics in general harmonic games, which is the strategic complement of potential games. The paper's main contributions are the convergence properties of the family of \"Follow-the-regularized-leader\" (FTRL) algorithms and its variants in general harmonic games, significantly extending previous results in two-player zero-sum games with fully mixed equilibrium and uniformly harmonic games. Specifically, the main results are (1) the continuous-time dynamics of FTRL are Poincaré recurrent, (2) the discrete-time dynamics of FTRL diverges, but FTRL with an extrapolation step (called FTRL+) guarantees $O(1)$ individual regret and global asymptotic last-iterate convergence/point convergence to a Nash equilibrium. These results show that potential and harmonic games are complementary not only from the strategic but also from the dynamic viewpoint.", "questions": "1. $m_i$ is used to choose the step size for convergence of FTRL+. Is there an efficient way to estimate an upper bound of $m_i$?\n2. This paper left the rate of convergence for FTRL+ as an open question. I would like to know if similar results hold for optimistic online mirror descent (OOMD)-type algorithms in harmonic games. I think proving convergence rates for OOMD algorithms, especially OGDA, might be more promising than FTRL+.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. This paper is very well-written and easy to follow. I appreciate that the main body clearly explains the main ideas, and the appendix provides rigorous and detailed proof. \n2. The problem of no-regret learning dynamics in games is relevant. This paper contributes to the area by establishing the previously unknown convergence properties of the FTRL dynamics in general harmonic games, including Poincaré recurrence of continuous-time FTRL, last-iterate convergence, and constant regret of FTRL+. The results and techniques in this paper shed light on the further development of learning in harmonic games.", "weaknesses": "I do not see any major weakness in the paper. \n\nMinor comments:\n\nTheorem 3/4: $m_i$ is used to choose the step size but has not been defined? The definition is in the appendix but a pointer should be given in the main body.\n\nLine 314: \"Similar bounds have only been established for optimistic methods in two-player zero-sum games [25]\". [25] established constant regret bounds for all variationally stable games, a class of multi-player games that includes two-player zero-sum games. This should be acknowledged. \n\n[25] Hsieh, Yu-Guan, Kimon Antonakopoulos, and Panayotis Mertikopoulos. \"Adaptive learning in continuous games: Optimal regret bounds and convergence to nash equilibrium.\" In Conference on Learning Theory. 2021", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer gj66,\n\nThank you for your strong positive evaluation and encouraging remarks! We reply to your questions and comments below:\n\n> Theorem 3/4: $m_i$ is used to choose the step size but has not been defined? The definition is in the appendix but a pointer should be given in the main body.\n\n$m_i$ is actually defined in L140, just after the definition of a harmonic game, but we understand that it is easy to miss. We will nest it inside Definition 1 to make it easier to find – thanks for pointing this out!\n\n\n> \"Similar bounds have only been established for optimistic methods in two-player zero-sum games [25]\". [25] established constant regret bounds for all variationally stable games, a class of multi-player games that includes two-player zero-sum games. This should be acknowledged.\n\nFair point. This was an omission on our end, we will rectify it accordingly, thanks for pointing it out!\n\n\n> $m_i$ is used to choose the step size for convergence of FTRL+. Is there an efficient way to estimate an upper bound of $m_i$?\n\nGood point! In general, we do not see an easy way of obtaining an upper bound for $m_i$ based on *local* knowledge alone. However, as far as the step-size tuning is concerned, we believe that an AdaGrad-type step-size would obviate the need to estimate $m_i$, as it obviates the need to know the Lipschitz modulus of the players' payoff functions in zero-sum games. As we state in the paper's concluding remarks, this is a very fruitful direction for future research, and one which we intend to undertake in future work.\n\n\n> This paper left the rate of convergence for FTRL+ as an open question. I would like to know if similar results hold for optimistic online mirror descent (OOMD)-type algorithms in harmonic games. I think proving convergence rates for OOMD algorithms, especially OGDA, might be more promising than FTRL+.\n\nWe are not aware of *any* convergence rates for harmonic games (or even asymptotic convergence results for that matter); to the best of our knowledge, our paper provides the first convergence result in the literature for general harmonic games.\n\nNow, we agree that optimistic GD might be easier to analyze than FTRL+ in terms of rates, and it would be a natural first step. However, when the players' regularizer function is steep (in the sense that the induced choice map takes values in the interior of the strategy simplex), optimistic FTRL and optimistic mirror descent are equivalent, so all the difficulty would already be present in the OptMD case. Still, beyond the \"steep\" regime, it may well be that the \"primal-dual\" formulation of mirror descent (versus that of dual averaging) could be more amenable to a rate analysis. At the current state of our knowledge for learning in harmonic games, it is very difficult to tell without doing the full analysis.\n\n---\n\nThank you again for your time and positive evaluation – and please let us know if you have any follow-up questions!\n\nKind regards,\n\nThe authors", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "jx9Yir4qb3", "reviewer": "Reviewer_sMJW", "summary": "The paper studies the behavior of no-regret dynamics, and in particular follow the regularized leader (FTRL), in harmonic games--the strategic counterpart of potential games. They establish the following main results: i) the continuous-time version of FTRL is Poincare recurrent; ii) an extrapolated version of FTRL (FTRL+), which includes the optimistic and mirror-prox variant, converges to a Nash equilibrium; iii) under FTRL+ each player attains $O(1)$ regret.", "questions": "No further questions.", "limitations": "The authors have adequately addressed the limitations.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper provides a clear and compelling motivation for investigating no-regret dynamics in harmonic games. In particular, the decomposition of Candogan et al. shows that, together with potential games, harmonic games constitute the basic building blocks of any game. Further, harmonic games generalized zero-sum games with a fully-mixed equilibrium, the latter class having received extensive attention in the literature. The results obtained in the paper make a concrete step towards better understanding no-regret dynamics in harmonic games, which I believe is an important contribution and will be welcomed by the learning in games community at NeurIPS. I also believe that the paper may lead to interesting follow-up work on harmonic games. Overall, the main message of the paper is compelling.\n\nThe writing of the paper is also exemplary and of really high quality. The main body does a great job at providing high-level sketches of the main technical ideas, and the appendix is also very well organized and polished. I did not detect any notable issues with the soundness of the claims.", "weaknesses": "Regarding the significance of the results, it can be argued that some of the results are somewhat incremental based on existing results. The fact that FTRL is Poincare recurrent is perhaps not that surprising conceptually given the recent paper of Legacci et al. which shows that for the special case of replicator dynamics; I do understand though that the extension requires some new ideas, as the authors discuss. Moreover, the fact that FTRL+ attains constant regret is also not particularly surprising. To put that result into better context, I would recommend citing the paper of Daskalakis, Fishelson and Golowich (NeurIPS 2021) that shows $O(\\log^4 T)$ regret for any game; as far as I understand, the only improvement pertains to logarithmic factors in $T$, which is perhaps not very significant. But I do not believe that the points above constitute basis for rejection.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer sMJW,\n\nThank you for your positive evaluation and your input! We reply to your questions and remarks below:\n\n> The fact that FTRL is Poincare recurrent is perhaps not that surprising conceptually given the recent paper of Legacci et al. which shows that for the special case of replicator dynamics; I do understand though that the extension requires some new ideas, as the authors discuss.\n\nFrom a conceptual standpoint, we agree that it is plausible to expect that FTRL is recurrent in harmonic games, given that the replicator dynamics (a special case of FTRL dynamics) are recurrent in uniform harmonic games – the result of Legacci et al. [32]. At the same time, we were genuinely surprised that the proof technique of [32] could **not** be extended along either direction – that is, to prove that FTRL is recurrent in *uniform* harmonic games, or that the replicator dynamics are recurrent in *general* harmonic games.\n\nThe reason for this is that the result of [32] revolves around a special mathematical construct – the so-called *Shahshahani metric* – which is essentially \"mandated\" by the choice of [32] to work with the replicator dynamics. The key property of this metric is that incompressibility / preservation of volume under the replicator dynamics is equivalent to the underlying game being uniformly harmonic. As such, a first step to extend the results of [32] would be to see if a suitably \"adjusted\" variant of the Shahshahani metric could provide an equivalence between incompressibility and harmonicity under a different measure – however, all our efforts to establish such an equivalence failed. Likewise, if we work with only *uniform* harmonic games, it is still not easy to find an analogue of the Shahshahani metric that makes a given, non-replicator FTRL scheme incompressible (at least, all our efforts to do so failed). Because of this, the \"incompressibility\" approach of [32] does not seem generalizable – at least, not in a straightforward way.\n\n**TLDR:** Even though, conceptually speaking, the recurrence of FTRL may not seem surprising, the failure of the incompressibility approach of [32] in more general settings and the apparent need to take a radically different approach does seem surprising (at least to us), and we believe that it carries important insights as to which techniques are more suitable for the analysis of general harmonic games.\n\n\n> Moreover, the fact that FTRL+ attains constant regret is also not particularly surprising. To put that result into better context, I would recommend citing the paper of Daskalakis et al, that shows $\\log^4 T$ regret for any game.\n\nFirst off, thanks for bringing up the paper of Daskalakis et al! We should have cited and discussed this paper, this was an omission on our end.\n\nNow, as to the significance of the polylog factor: if $T$ ranges between $10^3$ and $10^6$ (a reasonable range for online learning applications), the factor $\\log^4 T$ ranges roughly between $2000$ and $35000$. Thus, ceteris paribus, shaving off the $\\log^4 T$ factor could result in a gain between $3$ and $4$ orders of magnitude, depending on the context. We believe that this gain can be significant in several applications – though we freely acknowledge that there is a certain degree of subjectivity as to which gains are considered significant in which setting.\n\nGoing beyond this point, we should clarify that, in our view, the true importance of the constant regret guarantee of FTRL+ is the associated path length bound (D.6) which, in turn, plays a crucial part in establishing the convergence of FTRL+ to equilibrium. This would not be possible with a non-constant bound (at least, not without a fairly different technical approach), a fact which, from our standpoint, further adds to the significance of an $\\mathcal{O}(1)$ versus an $\\mathcal{O}(\\mathrm{polylog} T)$ bound.\n\n---\n\nPlease let us know if you have any follow-up questions, and thank you again for your time and positive evaluation!\n\nKind regards,\n\nThe authors", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "2NKBlxg5y0", "reviewer": "Reviewer_aEEw", "summary": "The paper looks at how no-regret learning algorithms behave in harmonic games, which model situations where players have conflicting interests. This is different from the often-studied potential games where interests are shared. The authors show that in continuous time, FTRL dynamics are Poincaré recurrent and do not converge. In discrete time, FTRL can cause never-ending cycles of best responses. But, by adding an extrapolation step (FTRL+), they show that learning can reach a Nash equilibrium from any starting point, ensuring constant regret and giving important insights into harmonic games.", "questions": "How do the choices of parameters $\\lambda_i$ and $\\eta_i$ affect the performance of the FTRL+ algorithm? How might one select these parameters for different types of harmonic games? Could you expand on the types of harmonic games tested in your experiments? Are there benchmarks the algorithm could be compared against?", "limitations": "Limitations are sufficiently covered given the theoretical nature of the paper.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper stands out for its novel exploration of no-regret learning in harmonic games, which are less studied compared to potential games. The use of FTRL+ to ensure convergence in these games is a creative extension of existing algorithms. Furthermore, the the result on Poincare recurrence in Theorem 2 is insightful and interesting. The statements and proofs of the results are clear and rigorous, and the figured and presentation aid clarity.", "weaknesses": "Empirical results beyond the matching pennies example could strengthen the work. The proofs are somewhat dense and challenging to follow. A stronger differentiation from the work by Legacci et al. would be beneficial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer aEEW,\n\nThank you for your strong positive evaluation and encouraging remarks! We reply to your questions and comments below:\n\n> Empirical results beyond the matching pennies example could strengthen the work.\n\nDuly noted. We have included a pdf in our global rebuttal with additional figures in a series of $2\\times 2 \\times 2$ harmonic games that better illustrate the differences between FTRL and FTRL+.\n\n\n> The proofs are somewhat dense and challenging to follow.\n\nPoint well taken. Being fully aware of the NeurIPS reviewing load and the time that it takes to review a paper, we tried to make our proofs as concise and straight-to-the-point as possible, but we understand that we may have overshot our original target. We will be happy to expand our proof sketch in the main part of the paper and provide more explanations and intuition along the way in the first revision opportunity.\n\n\n> A stronger differentiation from the work by Legacci et al. would be beneficial.\n\nTo provide the necessary context, Legacci et al. [32] showed that the replicator dynamics – a special case of the FTRL dynamics with entropic regularization – are Poincaré recurrent in uniform harmonic games (a subclass of harmonic games for which the uniform distribution is always a Nash equilibrium). In the continuous-time setting, our paper's contribution is that *all* FTRL dynamics are recurrent in *all* harmonic games.\n\nThe way that [32] obtained their result hinges on a special mathematical construct – the so-called *Shahshahani metric* – which is essentially \"mandated\" by the structure of the replicator dynamics. The key property of this metric is that incompressibility of the replicator field is equivalent to the underlying game being uniformly harmonic. As such, a plausible first step to extend the results and analysis of [32] would be to see if a suitably \"adjusted\" variant of the Shahshahani metric could provide an equivalence between incompressibility and harmonicity under a different measure; however, all our efforts to establish such an equivalence failed. Likewise, if we work with only *uniform* harmonic games, it is still not easy to find an analogue of the Shahshahani metric that provides a link between incompressibility of the associated FTRL dynamics and (uniform) harmonicity (at least, all our efforts to do so failed). Because of this, the \"incompressibility\" approach of [32] does not seem generalizable -- at least, not in a straightforward way.\n\n**TLDR:** We see no way of extending the incompressibility approach of [32] to more general FTRL dynamics and/or non-uniform harmonic games. We will be happy to include a version of this discussion when it is again possible to revise the paper to better highlight the differences between our dualization approach and the Riemannian incompressibility approach of [32].\n\n\n> How do the choices of parameters $\\lambda_i$ and $\\eta_i$ affect the performance of the FTRL+ algorithm? How might one select these parameters for different types of harmonic games?\n\nGreat question! The main things to keep mind are as follows:\n- For $\\eta_i$: in principle, $\\eta_i$ should be chosen as large as possible, as larger values of $\\eta$ lead to lower regret in (16), and to faster convergence to Nash equilibrium. The bound of L307 provides an upper limit to $\\eta_i$ so, from an operational standpoint, $\\eta$ should be taken as high as allowed by this limit.\n- For $\\lambda_i$: the precise dependence is determined by Eq. (D.9) in Appendix D. We provided a rough upper bound at that point to simplify the end expression. In principle, taking $\\lambda = 1$ leads to better bounds, but this comes at a cost of two queries per iteration, so there is still a trade-off involved (but one which is harder to quantify exactly).\n\n> Could you expand on the types of harmonic games tested in your experiments?\n\nThe payoffs of each game appear in the vertices of the phase portrait (in the paper as well as the rebuttal pdf). The games themselves were generated by randomly selecting a game with integer payoffs from the subspace of games satisfying the harmonicity condition of Definition 1.\n\n> Are there benchmarks the algorithm could be compared against?\n\nThe most widely used benchmarks that we are aware of are the three algorithms presented in Eqs. (14a,b,c) in our paper. Of these, (14a) is FTRL, which diverges (we plotted this throughout for comparison); (14b,c) are both special cases of FTRL+, and their trajectories are almost indistinguishable, so we only used the optimistic variant of the algorithm to minimize visual clutter.\n\n---\n\nPlease let us know if you have any follow-up questions, and thank you again for your time and positive evaluation!\n\nKind regards,\n\nThe authors", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:
Dear reviewers, dear AC,  

We are grateful for your time, comments, and positive evaluation!  

To streamline the discussion phase, we replied to each of your questions and comments in a separate rebuttal below, and we will integrate all applicable points in the next revision opportunity. To better illustrate the differences between FTRL and FTRL+, we have included in this global reply a pdf with further experiments for $2\times 2\times 2$ games, with different initializations in different harmonic games.

Thank you again for your input and encouraging remarks, and we are looking forward to continuing this constructive exchange during the discussion phase.  

Kind regards,  

The authors

Meta-review: This paper considers the problem of no-regret learning in games, for a general class of *harmonic* games which can be viewed as generalizing zero-sum games. The main results are to (1) show that in continuous time, FTRL dynamics in harmonic games are Poincare recurrent and do not converge, and (2) a variant of FTRL with extrapolation can achieve O(1) regret for general harmonic games (improving recent log(T) regret results for general-sum games).

Reviewers unanimously agreed on acceptance, and felt that the paper makes a solid and clear contribution that meaningfully expands our understanding of no-regret learning dynamics, highlighting the role of harmonic games as a counterpart to potential games.

For the final version of the paper, please incorporate the reviewers' suggestion to include a comparison to recent works that achieve log(T) regret in general-sum games.
Decision: Accept (spotlight)