On the Convergence of No-Regret Learning Dynamics in Time-Varying Games
Authors: Ioannis Anagnostides
Ioannis Panageas
Gabriele Farina
Tuomas Sandholm
Venue: NeurIPS 2023 poster (2023)
Keywords: no-regret learning
optimistic gradient descent
time-varying games
dynamic regret
TL;DR: We provide new results on the convergence of no-regret learning algorithms in time-varying games.

Abstract: Most of the literature on learning in games has focused on the restrictive setting where the underlying repeated game does not change over time. Much less is known about the convergence of no-regret learning algorithms in dynamic multiagent settings. In this paper, we characterize the convergence of optimistic gradient descent (OGD) in time-varying games. Our framework yields sharp convergence bounds for the equilibrium gap of OGD in zero-sum games parameterized on natural variation measures of the sequence of games, subsuming known results for static games. Furthermore, we establish improved second-order variation bounds under strong convexity-concavity, as long as each game is repeated multiple times. Our results also apply to time-varying general-sum multi-player games via a bilinear formulation of correlated equilibria, which has novel implications for meta-learning and for obtaining refined variation-dependent regret bounds, addressing questions left open in prior papers. Finally, we leverage our framework to also provide new insights on dynamic regret guarantees in static games.

On the Convergence of No-Regret Learning Dynamies in Time- Varying Games
Ioannis Anagnostides Carnegie Mellon University ianagnosccs. cmu. edu
Ioannis Panageas University of California Irvine ipanagealics. edi.edu
Gabriele Farina MIT gfarina@mit.
Tuomas Sandholm
Carnegie Mellon University Strategic Machine, Inc. Strategy Robot, Inc. Optimized Markets, Inc. sandholm@cs. cmu. edu
Abstract
Most of the literature on learning in games has focused on the restrictive setting where the underlying repeated game does not change over time. Much less is known about the convergence of no-regret learning algorithms in dynamic multia- gent settings. In this paper, characterize the convergence of optimistic gradient descent (OGD) in time-varying games. Our framework yields sharp convergence bounds for the equilibrium gap of OGD in zero-sum games parameterized natural variation measures of the sequence of games, subsuming known results for static games. Furthermore, establish improved second-order variation bounds under strong convexity-concavin times. Our results also extend to time-varying general-sum multi-player games via bilinear formulation of correlated equilibria, which has novel implications for meta-learning and for obtaining refined variation-dependent regret bounds, addressing questions left open in prior papers. Finally, we leverage our framework also provide new insights on dynamic regret guarantees in static games.
as long as each game is repeated multiple
Introduction
Most of the classical results in the literature on learning in games exemplified by, among others, the work of Hart and Mas-Colell [49], Foster and Vohra [42], Freund and Schapire [43] [43]-rest rest on the as- sumption that the underlying repeated game remains invariant. Yet, in many paradigmatic learning en- vironments that is unrealistic [35, 93, 19]. One such class is settings where the underlying game is actually changing, such as routing problems the internet [58], online advertising auctions [55], and dynamic mechanism design [67, 31j. Another such class consists of settings in which many similar games need to be solved [48]. For example, one may want solve variations of game for the purpose of sensitivity analysis with respect to the modeling assumptions used to construct the game model.
Despite the considerable interest in such dynamic multiagent environments, much less is known about the convergence of no-regret learning algorithms time-varying games. No-regret dynamics natural learning algorithms that have desirable convergence properties in static settings. Also, the state-of-the-an algorithms for finding minimax equilibria in two-player zero-sum games are based on advanced forms of no-regret dynamics [37, 11]. Indeed, all the superhuman milestones in poker have used them in the qquiibrium-fiiding module of their architectures [8, 10, 12].
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

In this paper, we seek to fill this knowledge gap by understanding properties of no-regret dynamics in time-varying games. In particular, we primarily investigate the convergence of optimistic gradient descent (OGD) [20, 72] in time-varying games. Unlike traditional no-regret learning algorithms, such as (online) gradient descent, DGD has been recently shown to exhibit last-iterate convergence in static (two-player zero-sum games [27, 46, 16, 47]. For the more challenging scenario where the underlying game can vary in every round, fundamental question arises: Under what conditions on the sequence of games does OGD approximate (with high probability) the sequence of Nash equilibria?
1.1
Our results
In this paper, we develop a framework that enables us to characterize the convergence of OGD, and generalizations thereof, in number of fundamental varying multiagent settings.
Bilinear saddle-point problems First, building on the work of Zhang al. [93], identify natural variation measures on the sequence of games whose sublinear growth guarantees that almost all iterates of OGD under a constant learning rate are approximate Nash equilibria in time-varying (two-player) zero-sum games (Corollary 3.4). More precisely, in Theorem 3.3 we derive sharp con-asymptotic characterization of the equilibrium gap of OGD as a function of the minimal first-order variation of approximate Nash equilibria and the second-order variation of the payoff matrices. We stress that our variation measure that depends on the deviation of approximate Nash equilibria of the games can be arbitrarily smaller than the one based on (even the least varying) sequence of exact Nash equilibria (Proposition 3.2), thereby significantly sharpening the measure considered by Zhang et al. [93]. It is also a compelling property, in light of the multiplicity of Nash equilibria, that the variation of the Nash equilibria is measured in terms of the most favorable iee., one that minimizes the variation-such sequence.
From a technical standpoint, our analysis revolves around a connection between the convergence of OGD in time-varying games and dynamic regret. In particular, the first key observation is that dynamic regret cannot be too negative under any sequence of approximate Nash equilibria (Property 3.1); this was first observed by Zhang et al. [93] under sequence of exact Nash equilibria. We also generalize this property by connecting it to the admission of a minimax theorem (Property A.4), as well as the so-called MVI property in the more general context of time-varying variational inequalities (VIs); this will enable us to extend our scope to certain multi-player games such as polymatrix zero- sum [15] (Theorem A.1 By combining Property 3.1 with a dynamic RVU bound [93], we obtain a variation-depente deeeedeen bound for the second-order path length of OGD under a constant learning rate in time-varying zero-sum games. In turn, this leads to our first main result, Theorem 3.3, discussed above. In the special case of static games, our theorem reduces to a tight 1/2 our results to the special setting of meta-leurning, where each game repeated multiple times.
1/2 rate. We also instantiate
Strongly convex-concave games Moreover, for strongly convex-concave time-varying games, we obtain a refined second-order variation bound on the sequence of Nash equilibria, as long as each game is repeated multiple times (Theorem 3.5); this is inspired by an improved second-order bound for dynamic regret under analogous conditions due to Zhang et al. [92]. As a byproduct of our techniques, we point out that any no-regret learners are approaching a Nash equilibrium under strong convexity-concavin convex-concane settings by suitably trading off the magnitude of a regularizer that makes the game strongly convex-concave. This offers significant gains in the meta-learning setting as well.
(Proposition 3.6; cf. [85]). Those results apply even in non-strongly
General-sum multi-player games Next, we extend our results to time-varying general-sum multi-player games by expressing correlated equilibria via a bilinear saddle-point problem (BSPP); while this formulation goes back to the early work of Hart and Schmeidler [50], it is rarely employed in the literature on learning in games. By leveraging a structural property of the underlying BSPP, we manage to obtain convergence bounds parameterized on the variation of the correlated equilibria (Theorem 3.9). To illustrate the power of our framework, we immediately recover natural and Algorithm-indeeenae
similarity measures for the meta-learning setting (Proposition A.14) even in general games (Corollary A.25), thereby addressing an open question of Harris et al. [48]. Our techniques also imply new per-player regret bounds in zero-sum and general-sum games (Corollaries A. and A.26), the latter addressing a question left open by Zhang et al. [93], albeit under different learning paradigm (Section 3.3 contains a discussion on this point). We further

---

parameterize the convergence of (vanilla) gradient descent in time-varying potential games in terms of the deviation of the potential functions (Theorem 3.7).
Finally, building on our techniques in time-varying games, we investigate the best dynamic-regret guarantees possible in static games (see also the work of Cai and Zheng [14)). We first note that instances of optimistic mirror descent guarantee O(VT) dynamic per-player regret (Proposition 3.10), matching the known rate of (online) gradient descent but for the significantly weaker notion of external regret. We further point out that Ollo 7') dynamic regret is attainable, but in a stronger two-point feedback model. In stark contrast, even obtaining sublinear dynamic regret for each player precluded in general-sum games (Proposition 3.12). This motivates studying a relaxation of dynamic regret that constrains the number of switches in the comparator, for which we derive accelerates rates in general games (Theorem 3. 3.)3) by leveraging the techniques of Syrgkanis et al. [78] in conjunction with the dynamic RVU bound. Interesting, this relaxation of dynamic regret gives rise to a natural refinement of coarse correlated equilibria, recently investigated by Crippa et al. [22].
1.2 Further related work
Even in static (two-player) zero-sum games, the pointwise convergence of no-regret learning algorithms is tenuous affair. Indeed, traditional learning dynamics within the no-regret framework, such as (online) mirror descent, may even diverge away from the equilibrium; e.g., see [74, 60, 83, 45]. Notwithstanding the lack of pointwise convergence, the empirical frequency of no-regret learners is well-known to approach the set of Nash equilibria in zero-sum games [43], and the set of coarse corre- lated equilibria in general-sum games [49, 42] standard relaxation of the Nash equilibrium [63, 3]. Unfortunately, those classical results are of little use beyond static games, thereby offering a crucial in games with time-varying component- ubiquitous
impetus for investigating theme in many practical scenarios of interest [31, 67, 82, 44, 81, 71, 69, 89, 70, 6]. One concrete and quite broad example worth mentioning here revolves around the steering problem [91]. where a mediator dynamically modifies the utilities of the game via nonnegative and vanishing payments so as to guide no-regret learners to desirable equilibria. In particular, when the payment function varies over time, the steering problem can be naturally phrased as a time-varying zero-sum game [91].
In this context, there has been considerable effort endeavoring to extend the scope of traditional game-theoretic results to the time-varying setting, approached from a variety of different standpoints in prior work [55, 93, 17, 58, 59, 35, 41, 79, 40, 86). In particular, our techniques in Section 3.1 are strongly related to the ones developed by Zhang et al. [93], but our primary focus is different: Zhang et al. [93] were mainly interested in obtaining variation-dependent regret bounds, while our results revolve around iterate-convergence of OGD (under a constant learning rate) to Nash equilibria. Minimizing regret and approaching Nash equilibria two inherently distinct problems, although connections have emerged [2. 93], and are further cultivated in this paper. Moreover, in an independent work Feng et al. [40] established surprising separation between the behavior of optimistic GDA and the axtra-gradient method in time-varying unconstrained bilinear games; it is open whether such discrepancy persists in the constrained setting well. We also point the concurrent work of Yan et al. [86] that focuses on improved guarantees for strongly monotone games; the results obtain in Section 3.2 complementary to theirs.
Another closely related direction is on meta-learning in games [48, 77, 34], where each game can be repeated for multiple iterations. Such considerations are motivated in part by number of use-cases in which many "similar" games- or multiple game variations- ought to be solved [9], such as Poker with different stack-sizes. While the meta-learning problem is special case of our general setting, our results are strong enough to have new implications for meta-learning in games, even though the algorithms considered herein are not tailored to operate in that setting.
2 Preliminaries
Notation We let N (1, be the set of natural numbers. For a number p E N, we let [p] = (l....,p. For vector E Rd we use ||w]|2 to represent its Euclidean norm; we also overload that notation so that || || denotes the spectral norm when the argument is matrix.
For two-player zero-sum game, we denote by X' C TR and y C TRdy the strategy sets of the two Soayers-namely Player z and Player y, respectively-wwe where de dy IN represent the corresponding
3

---

dimensions. It is assumed that A' and y' are nonempty convex and compact sets. For example, in the special case where X' := Ad and y dd,eeach each set corresponds to a probability simplex- the game is said to be in normal form. Further, we denote by Dx the lz-diameter of X, and by ||x1||2 the maximum fo-norm attained by a point in X. We will always assume that the strategy sets remain invariant, while the payoff matrix can change in each round. For notational convenience, we will denote by = (x, yy the concatenation of æ and y. and by Z = X x ) the Cartesian product X and V. In general n-plaaerr games, we instead use subscripts indexed by E [n|] to specify quantities related to a player. Superscripts are typically reserved to identify the time index. Finally, to simplify the exposition, often use the (-) notation to suppress time-independen parameters of the problem.
Dynamic regret We operate in the usual online learning setting under full feedback. Namely, at every time t E N the learner decides on a strategy x( E X, and then subsequently observes utility function + (a,, u="), for uz (t) _Rd= A strong performance benchmark in this online setting is dynamic regret, defined for a time horizon I' E N as follows:
DReg (5
(T)
(T))
Σ (1 (1) (u!")
(1)
where 8 = (x (= E X" above is the sequence of comparators; by setting (1..+) (2.++) =... x (T:+) in (1) we recover the standard notion of (external) regret (denoted
(T)))
simply by Reg(")) which is commonly used to establish convergence of the time-average strategies in static two-player zero-sum games [43]. On the other hand, the more general notion of dynamic regret, introduced in (I), has been extensively used in more dynamic environments;
e.g., [94, 92, 53, 18, 51, 54, 62]. We also define DReg (T) max max,(a) EX) (Ree!""(s""" While ensuring (T) dynamic regret is clearly hopeless in a truly adversarial environment, Section 3.4 reveals that non-trivial guarantees are possible when learning in zero-sum games (see also [14]).
Optimistic gradient descent Optimistic gradient descent (OGD) [20, 72] is no-regret algorithm defined with the following update rule:
(1() = 11x (z(() + +nm!
(OGD)
((+11) = Ix (1)) + +mp
Here, > 0 is the learning rate; a(1) = arg min || 122 represents the initialization of OGD; m (t) E Rd, is the prediction vector at time I, and it set as m = (t-1) when / 2 2, and m = Oz,; ; and finally, Ixx(+) represents the Euclidean projection to the set X, which is well- and can be further computed efficiently for structured sets, such as the probability simplex. For our purposes, we will posit access to projection oracle for the set X, in which case the update rule (OGD) indeed efficiently implementable.
In a multi-player n-player game, each player i E [M]] is associated with a utility function w; X",, X > TR. We recall the following central definition [64].
Definition 2.1 (Approximate Nash equilibrium). A joint strategy profile (æi......z) E X" X, is an e-approximate Nash equilibrium (NE), for an 2 0, if for any player E [m] and any possible deviation x X, it holds that u, (z oi.... ...., xt) u, ........ x',, ....... .......,. x;))
3 Convergence in time-varying games
In this section, we formalize our results regarding convergence in varying games. We organize this section as follows: First, in Section 3.1, we study the convergence of OGD in time-varying bilinear saddle-point problems (BSPPs) and beyond, culminating the non-asymptotic characterization of Theorem 3.3; Section 3.2 formalizes our improvements under strong cunvexity-concavity we then extend our scope to time-varying multi-player general-sum and potential games in Section 3.3; and finally, Section 3.4 is concerned with dynamic regret guarantees in static games.

---

3.1 Bilinear saddle-poine point problems
We first study an online learning setting wherein two players interact in a sequence of time-varying BSPPs [93]. We assume that in every repetition t E [T]] the players select a pair of strategies (a y (*) X' x V. Then, Player x receives the utility u = ( E R where A IR xd, represents the payoff matrix the t-th repetition: similarly, Player y receives the utility Uy = (A) T( E Rdv, We also extend our scope to a more general class of time-varying problems, as formalize in Section 3.1.1. The proofs of this subsection are in Appendix A.I.
We commence by pointing out a crucial property: by selecting a sequence of approximate Nash equilibria as the comparators, the sum of the players' dynamic regrets cannot be too negative:
Property 3.1. Suppose that 2 2(1,a) (arllit,, , ((in))) is an e -0-approximate Nash equilibrium of the I-th game. Then, for 8g
(T) = (zll).)) and 8y
(T)
DReg (s! + +DDgg (s -2
Σ E())
A special case of this property was previously noted by Zhang et al. [93] by considering a sequence of exact Nash equilibria; the approximate version stated above leads significant improvement in the convergence bounds, as we shall see in the sequel. In fact, as we note in Property A.4, Property 3.1 applies even in certain (ame-varying) it is a consequence of the minimax theorem. Property 3.1 also holds for time-varying variational inequalities (VIs) that satisfy the so-called MVI property, as we elaborate further in Section 3.1.1.
serconvex-nonconeeee
min- mix-max optimization problems, and
Now, building on the work of Zhang et al. [93], let us introduce some natural measures of the games' variation. The first-order variation of the Nash equilibria was defined by Zhang et al. [93] for T 2 2 as V == iiffgtt.)) (E(T) Etn [|x((++1,++ 2*1.*)] |2, where (1,+)) is the (nonempty) set of Nash equilibria of the t-th game. We recall that there can be multiplicity of Nash equilibria [80]; as
such, a compelling feature of the above variation measure is that it depends on the most favorable
sequence of Nash equilibria-on one that minimizes the first-order variation.
is important, however, to come to terms with the well-known fact that Nash equilibria can change abruptly even under a "small" perturbation in the payoff matrix (see Example A.5), which is an important caveat of the variation VLTT To address this, and in accordance with our more general Prop- erty 3.1, we consider a more favorable variation measure, defined as
DIT) C-NE = inf Σ [[=(+++++) - 2(10>))22 +
for a sufficiently large parameter > (see (28)); the infimum above is subject to e() E Rzo
and 2tt.*) E 2((x²) for all t E [T]], where 2(1,t) is the set of c(1) -pp-appox NE. It is evident that (T()
C-NE - NE since one can take e1)) =.. = (T) 0; in fact, vST) can be arbitrarily smaller:
Proposition 3.2. For any T there is a sequence of T games such that (2) T while
C-NE S for any 8 > 0.
This shows that (T) c-NB is a more compelling variation measure compared to V It is worth noting
here that Zhang et al. [93] also considered the variation measure Wx(T) == E A| (4) Al/,, where
A is the average payoff matrix and | denotes the spectral norm.' It is in fact not hard to construct instances such that ( NE < min(y (() w(T)) (Proposition A.6).
Moreover, we also recall another quantity that captures the variation of the payoff matrices: VITT ET ||A (t+1)_ A (1) l|. Unlike V(T). the variation measure ()TT depends on the second-order variation (of the payoff matrices), which could translate to lower-order impact compared to NE
Any equivalent norm in the definition of (T) suffices for the purpose of Proposition A.6.
5

---

(see, e.g., Corollary A.9). We stress that while our convergence bounds will be parameterized based on EEN
(T) the underlying algorithm-namely OGD-will remain oblivious those
NE and A variation measures. We only make the mild assumption that players know in advance the value of L == gax || (f/1222 so that they can tune the learning rate appropriately.
We are now ready to state the main result of this subsection. Below, we use the notation (QGAP()(<(()) to represent the Nash equilibrium gap of (xx(1) (1)) = 2(() E Z at the t-th game. More precisely, EQGAP(*) (z(") = max (BR, (ax(1), B (y( where (R(((((()) (ax(t) = m { (zz, (222) (ar(1),
(t)) is the best response gap of Player (and analogously for Player y)- Theorem 3.3 (Detailed version in Theorem A.11). Suppose that both players employ OGD with 1
learning rate 17 = 4I in a sequence of time-varying BSPPs, where L = maxişi5T A 12. Then,
EL (=!)) 2
O (1 +1+)2 y! NE + + ) where (22 ISiST is the sequence of joint strategy profiles produced by OGD.
The proof of this theorem is based on upper bounding the second-order path length of OGD, Ex (Iz(0) 1 + ||=(0) e(++1)
[[2). as a function of the variation measures y:(T) NN and (
This is shown via dynamic RVU bound [93] (Lemmas A. and A.2) in conjunction with Property 3.1.
It is worth noting that when the deviation of the payoff matrices is controlled by the deviation of the players' strategies, in the sense that > ||A - A A S W > || 20)) ||
for some parameter W& E RR the variation measure V in Theorem 3.3 can be entirely elimi- nated; Corollary A.9. The same in fact applies under improved prediction mechanism (see Remark A.13); while that prediction is not implementable in the online learning setting, it can be used, for example, when the sequence of games is known in advance (as is the case in certain applications).
We next state some immediate consequences of Theorem 3.3. (Item 2 below follows from Theorem 3.3 by Jensen's 's inequality.)
Corollary 3.4. In the setting of Theorem 3.3,
1. If at least a ò-fraction of the iterates have >> 0 NE gap, 28 2 1 (1+ C-NE + +)
2. The average NE gap is bounded as O (V (1
(1+ C-NE +1
y
In particular, in terms of asymptotic implications, if limy +00 for any c > 0 the fraction of iterates of OGD with at least an Nash equilibrium gap converges to O; and (ii) the average Nash equilibrium gap of the iterates of OCD converges to 0.
NB
limy -- = 0. then (i)
T
In the special case where D!T) NE: D O(1), Theorem 3.3 recovers the T-1/2 iterate-convergence rate of OCD in static bilinear saddle-point problems.
Meta-learning Our results also have immediate applications in the meta-learning setting. More precisely, meta-learning in games is a special case of time-varying games which consists of a sequence of H E N separate games, each of which is repeated for m E N consecutive rounds, that T: x H. The central goal in meta-learning is to obtain convergence bounds parameterized by the similarity of the games; identifying suitable similarity metrics is central question that line of work.
In this context, we highlight that Theorem 3.3 shown above readily provides a meta-learning guarantee parameterized by the following notion of similarity between the Nash equilibria:
infggch.))ezt.>)),.. [ Σm' (1++++++++ (hh,,))22 I|2. where (h,,²) is the set of Nash equilibria of
the h-th game in the meta-learning sequence, as well as the similarity of the payoff matrices corresponding to the term y²(T), In fact, under suitable prediction-the one used by Harris et al.
[48] dependence on (T) can be entirely removed; see Proposition 14 for our formal result. A compelling aspect of our meta-learning guarantee is that the considered algorithm is oblivious the
boundaries of the meta-learning. It is also worth noting that our similarity metric can be arbitrarily
In accordance with Theorem 3.3, this similarity metric can be refined using sequence of approximate NE.

---

smaller than the one considered by Harris et al. [48] (Proposition A.15). We further provide some novel results on meta-learning in general-sum games Section 3.3.
3.1.1 Beyond bilinear saddle-point problems
As we alluded to earlier, our approach can be generalized beyond time-varying bilinear saddle- point problems to a more general class of time-varying variational inequality (VIs) as follows. Let F(O 2 + 2 be the (single-valued) operator of the VI problem at time / E N. P(t) is said to
satisfy the MVI property [61, 36] if there exists a point (t..)) E Z such that (z - -z (t.)), =((+=) (z)) 2 0 for any E 2. For example, in the special case of a bilinear saddle-pone point problem
have that 2 = (z. y) + (Ay, A xt), and the MVI property is satisfied by virtue of Von Neumann's 's minimax theorem. It is direct to see that Property 3.1 applies to any time-varying sequence of VIs with respect to (2((:*))
long as every operator in the sequence (F(1,, ..... FFT)) satisfies the MVI property. (Even more broadly. it would suffice if almost all operators in the sequence in that their fraction converges to as T +-o--oootits satisfy the MVI property.) This observation enables extend- ing Theorem 3.3 to a more general class of problems. As a concrete example, we provide generaliza- tion of Theorem 3.3 (Theorem A, polymatrix zero-sum games [15] in Appendix A.1.7. By con- trast, in problems where the MVI property fails it appears that a much different approach is called for.
We finally point out that our framework could have certain implications for solving (static) general VIs, as we discuss in Appendix A.I.8.
3.2 Strongly convex-concave games
In this subsection, we show that under additional structure we can significantly improve the variation measures established in Theorem 3.3. More precisely, we first assume that each objective function fxx 3) is p-strongly convex with respect to and p-strongly concave with respect to y. Our second assumption is that each game is played for multiple rounds m E N, instead of only a single round; this is akin to the meta-learning setting. The key insight that as long as m large enough, m = (2(1/)), those two assumptions suffice to obtain a second-order variation bound in terms
of the sequence of Nash equilibria, S(E) == Σmー [1=( 20h+*) 12. where (hh,*) is a Nash equilibrium of the h-th game. This significantly refines the result of Theorem 3.3, and is inspired
by the improved dynamic regret bounds obtained by Zhang et al. [92]. Below we sketch the key
ideas of the improvement; full proofs are deferred to Appendix A.2.
In this setting. it is assumed that Player obtains the utility u = -v (x((1, .y ()) at every time E [7]. while its regret will be denoted by Reg2.;: similar notation applies for Player y. The first observation is that, focusing on single (static) game, under strong convexity-concant the sum of the players' regrets are strongly nonnegative (Lemma A.18):
m
(m) Regg, (x=) + Regg. (y")
(m)
for any Nash equilibrium z" E 2 of the game. In turn, this can be cast in terms of dynamic regret over the sequence of the h games (Lemma 1.19). Next, combining those dynamic-regret lower bounds with a suitable RVU-type property leads to a refined second-order path length bound as long
2(1/H), which in turn leads to our main result below. Before present its statement, let us introduce the following measure of variation of the gradients: v(H) = IKI1 maxxez (2)
where let F z == (x, y) + (V=f(æ, y), (v,(x, y)). This variation measure is analogous (T) introduced earlier for time-varying BSPPs.
Theorem 3.5 (Detailed version in Theorem A.21). Let f(h) X y be a s--strnngly convex-concave and L-smooth function, for all h. E [A] Suppose further that both players employ OGD with
learning rate = min 1 1. foor T E N repetitions, where T = m x H and m 2 2. ap. Then, BL. 24
E' (EOGAD)(<!00) 0(1 + (()) + v(H))
7

---

Our techniques also imply the improved regret bounds (2) (T) 2. Regg.g =0
(V S + v
under suitable tuning of the learning rate (see Corollary A.22).
There is another immediate but important implication of (3): any no-regret algorithm in (static) strongly convex-concave setting ought to be approaching the Nash equilibrium;" in contrast, this property is spectacularly false in (general) monotone settings [60].
Proposition 3.6. Let X x - IR be a p-strongly convex-concave functiionn If players incur regrets such that Regg, + +Reg2.
(T)
(T) CT for some parameters C and E (0, 1}. then for
(2C 1/W
any c > 0 and T
there a pair of strategies (!)) E such that ||z(0) (t) z² 1l2 S c,
.uc2
where: x² Z is Nash equilibrium.
The insights of this subsection are also of interest in general monotone settings by incorporating a strongly convex regularizer; tuning its magnitude allows us to trade off between a better approximation and the benefits strong convexity-concave revealed in this subsection.
3.3 General-sum multi-player games
Next, we turn our attention to general-sum multi-player games. For simplicity, in this subsection we posit that the game is represented in normal form, so that each player i E [n] has a finite set of available actions A,, and X₂ == (A.). The proofs of this subsection are included in Appendix A.3.
Potential games First, we study the convergence of (online) gradient descent (GD) in time-varying potential games (see Definition A.23 for the formal description); we recall that unlike two-player zero-sum games, gradient descent is known to approach Nash equilibria in potential games, In our time-varying setup, is assumed that each round E [T] corresponds to a different potential game described with a potential function (((), We further let d (Φ, +b) + maxzex; X, (Φ(z) +z)),
so that V ΣT= d($((), ((+++)); we call attention to the fact that d(-.-) is not symmetric. Analogously to Theorem 3.3, we use EQGAP(*)<<(() E Rgo to represent the NE gap of the joint strategy profile 21)) = (21 (t) x!12) at the t-th game.
Theorem 3.7. Suppose that each player employs (online) GD with a sufficiently small learning rate in sequence of time-varying potential games. Then, Et= (=(GAP(((((0)) + mas VTT))
where mar is such that (x)1 S 4mar-
We refer to Appendix B for some illustrative experiments related to Theorem 3.7.
General games Unfortunately, unlike the settings considered thus far, computing Nash equilibria in general games computationally hard even under crude approximation c (11 [25, 19, 30]. Instead, learning algorithms are known to converge-in time-average sense-to relaxations of the Nash equilibrium, known as (coarse) correlated equilibria. For our purposes, we will employ bilinear formulation of correlated equilibria, which dates back to the seminal work of Hart and Schmeidler [50] (see also [84, Chapter 12] for an excellent exposition). This will allow us to translate the results of Section 3.1 to general multi-player games.
Specifically, correlated equilibria* can be phrased via game between the n players and a mediator, an additional agent. At a high level, the mediator is endeavoring to identify correlated strategy E = A (X""A,) Ar) for which no player has an incentive to deviate from the recommendation. In contrast, the players are trying optimally deviate as maximize their own utility. More precisely, there exist matrices A A,, with each matrix A, depending solely on the utility of Player for which the bilinear saddle-point problem can be expressed as
Σ CuAAn A,D; X 1=1
min FE
JEXP
Succ observations were independently documented by Wang et al. [85]. 'There is also a bilinear formulation tailored to coarse correlated equilibria, but we will focus solely on the stronger variant (CE) for concreteness.
8

---

where R; above is a suitable set of strategies; we elaborate more on this formulation in Ap- pendix A.3. This zero-sum game has the property that there exists strategy μ E E such that E (1*) A, I 0, for any player E [n| which is precisely correlated equilibrium.
Before we proceed, it is important note that the learning paradigm considered here deviates from the traditional one in that orchestrating the protocol requires an additional learning agent, resulting in less decentralized protocol. Yet, the dynamics induced by solving (4) via online algorithms remain uncoupled [49], in the sense that each player obtains coreepci-oorsssoodiing to the deviation benefit that depends solely on its own utility.
Now in the Lime-varying setting, the matrices A An that capture the players' utilities can change in each repetition. Crucially, we show that the structure of the induced bilinear problem (4) such that there is a sequence of correlated equilibria that guarantee nonnegative dynamic regret; this refines Property 3.1 in that only one player's strategies suffice to guarantee nonnegativity, even if the strategy of the other player remains invariant. Below, denote by DReg the dynamic regret of Player min in (4), and by Regi (T) the regret of each player E [in] up to time T N, so that the regret of Player max in (4) can be expressed as 1 (T)
Reg!")
Property 3.8. Suppose that (((+.t) is correlated equilibrium of the game at any time & [T]. Then, (Reg(T)((llle (T.,,)) + Σ i=1 Reg. (T) 20.
As a result, this enables us to apply Theorem 3.3 parameterized on (i) the variation of the CE
v(T) inf pat. the 1-th game, and (ii) the variation in the players' utilities DIT) = E' |A (A(*))) A 1
Et (| (=(,,)>12 ||2, where ((t.)) denotes the set of CE of
below, we denote by CEGAP( (1) the CE gap of μ E at the 1-th game.
Theorem 3.9. Suppose that each player employs OGD in a sequence of time-varying BSPPs (4) with sufficiently small learning rale. Then, Σi= (CEGA)()((()))
0(1 CE + +
There are further interesting implications of our framework that are worth highlighting, First, we obtain veta-leaming guarantees for general games that depend on the sogorithm-iddpendeem. similarity of the correlated equilibria (Corollary A.25); that was left as open question by Harris al. [48], where instead algorithm-depenndnt similarity metries were derived. Further, by applying Corollary A2, we derive natural variation-dependent per-player regret bounds in general games (Corollary A.26); this addresses a question left by Zhang et al. [93], albeit under a different learning paradigm. We suspect that obtaining such results parameterized on the variation of the CE-are are not possible without the presence the additional agent, as in (4).
3.4 Dynamic regret bounds in static games
Finally, in this subsection we switch gears by investigating dynamic regret guarantees when learning in static games. The proofs of this subsection included in Appendix A.4.
First, we point out that while traditional no-regret learning algorithms guarantee O(vT) external regret, instances of OMD-a generalization of OGD; see (5) in Appendix A-in fact guarantee O(vT) dynamic regret in two-player zero-sum games, which is a much stronger performance measure:
Proposition 3.10. Suppose that both players in a (static) two-player zero-sum game employ OMD with smooth regularizer. Then, DReg!!) DDReg (T) = O(VT).
In proof, the dynamic regret of each player under OMD with a smooth regularizer can be bounded by the first-order path length of that player's strategies, which in tur be bounded by O(VT) given that the second-order path length is O(1) (Theorem A.7). In fact, Theorem A.7 readily extends Proposition 3.10 to time mareiiayyngg zero-sum games as well, implying that (Teg( (RReg(",,DRggg))) =0 - (V E-NE )
question that arises from Proposition 3.10 is whether the O(VT) guarantee for dynamic regret of OMD can be improved in the online learning setting. Below, point out a significant improvement to

---

(llo T', but under stronger two-point feedback model;" namely, we posit that in every round each player can select an additional auxiliary strategy, and each player then gets to additionally observe the utility corresponding to the auxiliary strategies. Notably, this is akin to how the extra-gradte extra-gradient method works [52] (also cf [72, Section 4.2] for multi-point feedback models in the bandit setting).
Observation 3.11. Under two-point feedback, there exist learning algorithms that guarantee DReg!" (7), [ "Degg (T) (logT) in two-player zero- games.
In particular, it suffices for each player to employ OMD, but with the twist that the first strategy in each round is the time-average of OMD; the auxiliary strategy is the standard output of OMD. Then, the dy- namic regret of each player will grow as O
(Ei=it) = O T") since the duality gap of the average strategics is decreasing with a rate of T [72]. is an interesting question whether the bound of Ob- servation 3.11 can be improved to O(1) [14]; we conjecture that there is lower bound of 22(lo T)..
General-sum games In stark contrast, no (computationally efficient) sublinear dynamic regret guarantees are possible in general-sum games:
Proposition 3.12. Any polynomial time algorithm incurs Ei= DReg." (T) CT for any polynomial T E N, even if = 2 and C >> O is an absolute constant, unless ETH for PPAD is false [73].
Indeed, this follows immediately since computing a Nash equilibrium to 0(1) precision in two-player games requires superpoylnomial time [73]. As such, Proposition 3.12 applies beyond the online learning setting. This motivates considering a relaxation of dynamic regret, wherein the sequence of
comparators is subject the constraint ΣT_ [(x ((+1,,) * * =x("") S K 1, for some parameter K' E N [22]; this will be referred to as K K-DReg, (X) Naturally, external regret coincides with
K-DReg, (T) under K 1. In this context, we employ Lemma A.l to bound K- K-DReg(") under OGD:
Theorem 3.13 (Precise version in Theorem A.28). Suppose that all players employ DGD with suitable learning rate in an L-smooth game. Then, for any K E N,
1. Σi= K-DReg! (T) = OOK /nLD²);
2. K-DReg (T) = 0(K3//T1/4 1/4 "3/ 232
for any player i E [n]]
One question that arises here is whether the per-player bound of 0(K3/1T1/4) (Item 2) can be improved to Ö(K). where Ö(-) hides logarithmic factors. The main challenge is that, even for K = 1, all known methods that obtain Ô(1) [29, 68, 1, 38] rely on non-smooth regularizers that violate the preconditions of Lemma A dynamic RVU bound beyond (squared) Euclidean regularization; yet, we point out that it is possible under a slightly stronger feedback model (Remark A.29). We finally highlight that the game-ther theoretic significance of the solution concept that arises as the limit point of no-regret learners when K- K-DReg o(T)) was recently investigated by Crippa et al. [22].
Conclusions and future work
In this paper, we developed a framework for characterizing iterate-convergence of no-regret learning poorithms-primrii optimistic gradient descent (OGD)-in time-varying games. There are many promising avenues for future research. Besides closing the obvious gaps highlighted in Section 3.4, it is important to characterize the behavior of no-regret learning algorithms in other fundamental time-varying multiagent settings, such as Stackelberg (security) games [5]. Moreover, our results operate in the full-feedback model where each player receives feedback on all possible actions. Extending the scope of our framework capture partial-feedback models well is another interesting direction for future work.
'The same asymptotic bound was independently established by Cai and Zheng [14] but in the standard feedback model.
10

---

Acknowledgments and Disclosure of Funding
We are grateful anonymous referees for providing valuable and constructive feedback. We also thank Vince Conitzer and Caspar Oesterheld for many helpful comments. This material is based on work supported by the National Science Foundation under grants IIS-190140) and CCF-1733556 and by the ARO under award W91
References
[1] I. Anagnostides, G. Farina, C. Kroer, C. Lee. H. Luo, and T. Sandholm. Uncoupled learning dynamics with (log T) swap regret in multiplayer games. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2022.
[2] I. Anagnostides, I. Panageas, G. Farina, and T. Sandholm. On last-iterate convergence beyond zero-sum games. In International Conference on Machine Learning (ICML), volume 162 of Proceedings of Machine Learning Research, pages 536 581. PMLR, 2022.
[3] R. Aumann. Subjectivity and correlation in randomized strategies. Journal of Mathematical Economics, 1:67-96, 1974.
[4] W. Azizian, I. Mitliagkas, S. Lacoste-Julien, and G. Gidel. A tight and unified analysis of gradient- based methods for whole spectrum of differentiable games. The 23rd International Conference on Artificial Intelligence and Statisties, AISTATS, volume 108 of Proceedings of Machine Learning Research, pages 2863-2873. PMLR, 2020.
[5] M. Balcan, A. Blum, N. Haghtalab, and A. D. Procaccia. Commitment without regrets: Online learning in stackelberg security games. In Proceedings of the ACM Conference on Economics and Computation (EC), pages 61-78. ACM, 2015.
[6] L. Baudin, M. Scarsini, and X. Venel. Strategic behavior and no-regret learning in queueing systems. CoRR, abs/2302.03614, 2023.
[7] H. H. Bauschke, M. Moursi, and X. Wang. Generalized monotone operators and their averaged resolvents. Math. Progrum., 189(1):55-744 2021.
[8] M. Bowling, N. Burch, M. Johanson, and O. Tammelin. Heads-up limit hold' am poker is solved. Science, 347(6)88), January 2015.
[9] N. Brown and T. Sandholm. Strategy-based warm starting for regret minimization in games, In AAAI Conference on Artificial Intelligence (AAAI), 2016.
[10] N. Brown and T. Sandholm. Superhuman for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374):418 424, 2018.
[11] N. Brown and T. Sandholm. Solving imperfect minimization. In AAAI Conference on Artificial Intelligence (AAAI), 2019.
imperfect-informatior information games via discounted regret
[12] N. Brown and T. Sandholm. Superhuman Al for multiplayer poker. Science, 365(6456):883-899, 2019.
[13] Y. Cai and W. Zheng. Accelerated single-call methods for constrained min-max optimization. CoRR, abs/2210.03096, 2022.
[14] Y. Cai and W. Zheng. Doubly optimal no-regret learning in monotone games. In International Conference on Machine Learning (ICML), volume 202 of Proceedings of Machine Learning Research, pages 3507-3524. PMLR, 2023.
[15] Y. Cai, O. Candogan, C. Daskalakis, and C. Papadimitriou. Zero-sum polymatrix games: generalization of minmax. Math. Oper. Res., 41(2):648-66 655, 2016.
[16) Y. Cai, A. Oikonomou, and W. Zheng. Finite-time last-iterate convergence for learning in multi- player games. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2022.
11

---

[17] A. R. Cardoso, J. D. Abernethy, H. Wang, and H. Xu. Competing against nash equilibria in adversarially changing zero-sum games. In International Conference on Machine Learning (ICML), volume 97 of Proceedings of Machine Learning Research, pages 921-930. PMLR, 2019.
[18) N. Cesa-Bianchi P. Gaillard, G. Lugosi, and G. Stoltz. Mirror descent meets fixed share (and feels no regret). Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), pages 989-997, 2012.
[19] X. Chen, X. Deng, and S.-H. Teng. Settling the complexity of computing two-player Nash equilibria. Journal of the ACM, 2009.
[20] C.-K. Chiang. T. Yang, C.-J. Lee, M. Mahdavi, C.-J. R. Jin, and S. Zhu. Online optimization with gradual variations. In Conference Learning Theory, pages 6-1, 2012.
[21] L. Combettes and Pennanen. Proximal methods for cohypomonotone operators. SIAM J. Control. Optim., pages 731-742, 2004.
[22] L. Crippa, Y. Gur, and B. Light. Equilibria in repeated games under no-regret with dynamic benchmarks. CoRR, abs/2212.031522 2023.
[23] C. D. Dang and G. Lan. On the convergence properties of non-euclidean extragradient methods for variational inequalities with generalized monotone operators. Comput. Optim. Appl., pages 277-310, 2015.
[24] C. Daskalakis. Non-concave games: A challenge for game theory's 's next 100 years, 2022.
[25] C. Daskalakis, P. Goldberg, and C. Papadimitriou. The complexity of computing a Nash equilibrium. SIAM Journal on Computing, 2008
[26] C. Daskalakis. A. Deckelbaum, and A. Kim. Near-optimal no-regret algorithms for zero-sum games. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011.
[27] C. Daskalakis, A. Ilyas, V. Syrgkanis, and H. Zeng. Training gans with optimism. In 6th International Conference on Learning Representations, ICLR. OpenReview.net, 2018.
[28] C. Daskalakis, D. J. Foster, and N. Golowich. Independent policy gradient methods for competitive reinforcement learning- In Proceedings of the Annual Conference Neural Information Processing Systems (NeurIPS), 2020.
[29] C. Daskalakis, M. Fishelson, and N. Golowich. Near-optimal no-regret learning in general games. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), pages 27604-27616, 2021.
[30] A. Deligkas, J. Fearnley, A. Hollender, and T. Melissourgos. Pure-circuit: Strong inapproxima- bility for PPAD. In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS), pages 159-170. IEEE, 2022.
[31] Y. Deng, V. Mirrokni, and S. Zuo. Non-clairvoyant dynamic mechanism design with budget constraints and beyond. In Proceedings of the 22nd ACM Conference on Economics and Computation, Proceedings of the ACM Conference on Economics and Computation (EC). Association for Computing Machinery, 2021.
[32] Diakonikolas. Halper iteration for optimall and parameter- free monotone inclusion and strong solutions to variational inequalities. In J. D. Abernethy and S. Agarwal, editors, Conference on Learning Theory (COLT), volume 125 of Proceedings of Machine Learning Research, pages 1428-1451. PMLR, 2020.
[33] Diakonikolas, C. Daskalakis, and M. Jordan. Efficient methods for structured nonconvex- nonconcave min-max optimization. In The 24th International Conference on Artificial Intel- ligence and Statistics, AISTATS, volume 130 of Proceedings of Machine Learning Research, pages 2746-2754 PMLR, 2021.
12

---

[34] Z. Duan, W. Huang, D. Zhang, Y. Du, J. Wang, Y. Yang, and X. Deng. Is nash equilibrium approximator learnable? In Autonomous Agents and Multi-Agent Systems, pages 233-241. ACM, 2023.
[35] B. Duvocelle, P. Mertikopoulos, M. Staudigl, and D. Vermeulen. Multiagent online learning in vire-iarying games. Mathematics of Operations Research, 2022.
[36] Facchinei and J.-S. Pang. Finite-dimensioal variational inequalities and complementarity problems. Springer, 2003.
[37] G. Farina, C. Kroer, and T. Sandholm. Faster game solving via predictive Blackwell approacha- bility: Connecting regret matching and mirror descent. In Proceedings of the AAAI Conference on Artificial Intelligence 2021.
[38] G. Farina, I. Anagnostides, H. Luo, C. Lee, C. Kroer, and T. Sandholm. Near-optimal no- regret learning for general convex games. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2022.
[39] G. Farina, C. Kroer, C. Lee, and H. Luo. Clairvoyant regret minimization: Equivalence with nemirovski's conceptual prox method and extension to general convex games. CoRR, abs/2208. 14891, 2022.
[40] Y. Feng, H. Fu, Q. Hu, P. Li, I. Panageas, B. Peng, and X. Wang. On the last-iterate conver- gence in varying zero-sum games: Extra gradient succeeds where optimism fails. CoRR, abs/2310.02604, 2023.
[41] Fiez, R. Sim, S. Skoulakis, G. Piliouras, and L. Ratliff. Online learning in periodic zero-sum games. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), pages 10313-10325, 2021.
[42] D. Foster and R. Vohra. Calibrated learning and correlated equilibrium. Games and Economic Behavior, 21:40-55, 1997.
[43] Y. Freund and R. Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 103, 1999.
[44] D. Garrett. Dynamic mechanism design: Dynamic arrivals and changing values. Games and Economic Behavior, 104:595-612, 2017.
[45] A. Giannou, E. MattaissGGaragkkoune and P. Mertikopoulos. Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information. In Conference on Learning Theory (COLT), volume 134 of Proceedings of Machine Learning Research, pages 2147-2148. PMLR, 2021.
[46] N. Golowich, S. Pattathil, and C. Daskalakis. Tight last-iterate convergence rates for no-regret learning in multi-player games. In Proceedings of the Anmual Conference on Neural Information Processing Systems (NeurIPS), 2020.
[47] E. Gorbunov, A. B. Taylor, and G. Gidel. Last-iterate convergence of optimistic gradient method for monotone variational inequalities. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2022.
[48] K. Harris, I. Anagnostides. G. Farina, M. Khodak, S. Wu, and T. Sandholm. Meta-learning in games. In The Kleventh International Conference on Learning Representations, ICLR. OpenReview.net, 2023.
[49] S. Hart and A. Mas-Colell. A simple adaptive procedure leading to correlated equilibrium. Econometrica, 68:1 18:11071 2000.
[50] S. Hart and D. Schmeidler. Existence of correlated equilibria. Mathematics of Operations Research, 14(1):18-25 1989.
[51] E. Hazan and C. Seshadhri. Efficient learning algorithms for changing environments. In Inter- national Conference on Machine Learning (ICML), page 393-400. Association for Computing Machinery, 2009.
13

---

[52] Y. Hsich, F. lutzeler, J. Malick, and P. Mertikopoulos. On the convergence of single-call stochas- tic extra-gradient methods. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), pages 6936-6946, 2019.
[53] A. Jadbabaie, A. Rakhlin, S. Shahrampour, and K. Sridharan. Online Optimization : Competing with Dynamic Comparators. In Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, pages 398 406, 2015.
[54] D. S. Kalhan, A. S. Bedi, A. Koppel, K. Rajawat, H. Hassani, K. Gupta, and A. Banerjee. Dynamic online learning via frank-wolfe algorithm. IEEE Trans. Signal Process., 69:932-947) 2021.
[55] T. Lykouris, V. Syrgkanis, and É. Tardos. Learning and efficiency in games with dynamic population. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 120-129. SIAM, 2016.
[56] O. Mangoubi and N. K. Vishnoi. Greedy adversarial equilibrium: an efficient alternative to nonconvex-nonconee min-max optimization. In Proceedings of the Annual Symposium on Thheory of Computing (STOC), pages
ACM, 2021.
[57] E. Mazumdar, L. J. Ratliff, and S. S. Sastry, On gradient -bsee learning in continuous games. SIAM J. Math. Data Sei., pages 103-131, 2020.
[58] I. Menache and A. E. Ozdaglar. Network Games: Theory, Models, and Dynamics. Synthesis Lectures on Communication Networks. Morgan & Claypool Publishers, 2011.
[59] Mertikopoulos and M. Staudigl. Equilibrium tracking and convergence in dynamic games. In 202/ 60th IEEE Conference on Decision and Control (CDC), pages 930-935. IEEE, 2021.
[60] P. Mertikopoulos, C. H. Papadimitriou, and G. Piliouras. Cycles in adversarial regularized learning. In Anmual ACM-SIAM Symposium Discrete Algorithms (SODA), pages 2703-2711 SIAM, 2018
[61] P. Mertikopoulos, B. Lecouat, H. Zenati, C. Foo, V. Chandrasekhar, and G. Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In 7th International Conference on Learning Representations, ICLR. OpenReview.net, 2019.
[62] A. Mokhtari, S. Shahrampour, A. Jadbabaie, and A. Ribeiro. Online optimization in dynamic environments: Improved regret rates for strongly convex problems. In 55th IEEE Conference on Decision and Control, CDC 2016, pages 7195-7201. IEEE, 2016.
[63] H. Moulin and J.PP. Vial. Strategically zero-sum games: The class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory, 7(3-4): 201-221, 1978.
[64] J. Nash. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences, 36:48 1950.
[65] A. Nemirovski. mex--d with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1), 2004.
[66] M. Nouiched, M. Sanjabi, T. Huang, J. D. Lee, and M. Razaviyayn. Solving class of non- convex min-max games using iterative first order methods. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), pages 14905-14916, 2019.
[67] C. H. Papadimitriou, G. Pierrakos, A. Psomas, and A. Rubinstein. On the complexity of dynamic mechanism design. Games and Economic Behavior, 134:399 2022.
[68] G. Piliouras, R. Sim, and S. Skoulakis. Beyond time-average convergence: Near-optimal uncoupled online learning via clairvoyant multiplicative weights update. In Proceedings of the Annual Conference Neural Information Processing Systems (NeurIPS), 2022.
14

---

[69] J. I. Poveda, M. Krstic, and T. Basar. Fixed-time seeking and tracking of time-varying varying nash equilibria noncooperative games. In American Control Conference, ACC 2022, Atlanta, GA, USA, June 8- 8-10, 2022, pages 794-799. IEEF, 2022.
[70] J. Rahme, S. Jelassi, and S. M. Weinberg. Auction learning two-player game. In 9th International Conference on Learning Representations, ICLR, 2021.
[71] A. A. Raja and S. Grammatico. Payoff distribution in robust coalitional games on time-varying networks. IEEE Trans. Control. Netw Syst., 9(1):111-52) 2022.
[72] A. Rakhlin and K. Sridharan. Optimization, learning, and games with predictable sequences. In Advances in Neural Information Processing Systems, pages 3066-3074, 2013.
[73] A. Rubinstein. Settling the complexity of computing approximate two-player nash equilibria.
In Proceedings of the Anmual Symposiun on Foundations of Computer Science (FOCS), pages 258-265, IEEE Computer Society, 2016.
[74] Y. Sato, E. Akiyama, and J. D. Farmer. Chaos in learning simple two-person game. Proceedings of the National Academy of Sciences, 99(7):4748 2002.
[75] Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4, 2012.
[76] C. Song, Z. Zhou, Y. Zhou, Y. Jiang, and Y. Ma. Optimistic dual extrapolation for coherent non-monotone variational inequalities. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2020.
[77] D. Sychrovsky, M. Sustr, E. Davoodi, M. Lanetot, and M. Schmid. Learning not to regret. CoRR, abs/2303.01074, 2023.
[78] V. Syrgkamis, A. Agarwal, H. Luo, and R. E. Schapire. Fast convergence of regularized learning in games. In Advances in Neural Information Processing Systems, pages 9989-2997, 2015.
[79] A. Taha, K. Rokade, and Parise. Gradient dynamics in linear quadratic network games with time-varying connectivity and population fluctuation. CoRR, abs/2300.00871 2023.
[80] E. van Damme. Stability and perfection of Nash equilibria, volume 339. Springer, 1991.
[81] N. Van Long. A survey of dynamic games in economics, volume 1. World Scientific, 2010.
[82] X. Venel. Regularity of dynamic opinion games. Games and Economic Behavior, 126:305-334,
2021.
[83] E. Tlaakkis-Gaarggkouniis L. Flokas, T. Lianeas, P. Mertikopoulos, and G. Piliouras. No-regret learning and mixed nash equilibria: They do not mix. Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2020.
[84] B. Von Stengel. Game theory basics. Cambridge University Press, 2021.
[85] Z. Wang, Y. Shen, M. Zavlanos, and K. H. Johansson. No-regret learning in strongly monotone games converges to a nash equilibrium, 2022.
[86] Y. Yan, P. Zhao, and Z. Zhou. Fast rates in time-varying strongly monotone games. In International Conference Machine Learning (ICML), volume 202 of Proceedings Machine Learning Research, pages 391 39138-39164. PMLR, 2023.
[87] J. Yang, N. Kiyavash, and N. He. Global convergence and variance-reduced optimization for a class of nonconvex-nonconcan minimax problems. CoRR, abs/2002.09621, 2020.
[88] Y. Yang and Ma. O(T convergence of wwwmmisiiifolloww----rrraaaaaaae player zero-sum markov games. In The Eleventh International Conference on Learning Repre- sentations, ICLR. OpenReview.net, 2023.
in two-
[89] M. Ye and G. Hu. Distributed seeking of time-varying nash equilibrium for non-cooperative games. IEEE Trans. Autom. Control., 30300))3000-0055 2015.
15

---

[90] Т. Yoon and E. K. Ryu. Accelerated algorithms for smooth convex concave minimax problems with (1/k²² rate on squared gradient norm. International Conference on Machine Learning (ICML), volume 139 of Proceedings of Machine Learning Research, pages 12098-12109. PMLR, 2021.
[91] B. H. Zhang. G. Farina, I. Anagnostides, F. Cacciamani, S. M. McAleer, A. A. Haupt, A. Celli, N. Gatti, V. Conitzer, and T. Sandholm. Steering no-regret learners to optimal equilibria. CoRR, abs/2306.05221, 2023.
[92] L. Zhang, T. Yang, J. Yi, R. Jin, and Z. Zhou. Improved dynamic regret for non-degenerate functions. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), pages 732-741, 2017.
[93] M. Zhang, P. Zhao, H. Luo, and Z. Zhou. No-regret learning in time-varying zero-sum games. In International Conference on Machine Learning (ICML), volume 162 of Proceedings of Machine Learning Research, pages 26772 26808. PMLR, 2022.
[94] P. Zhao, Y. Zhang, L. Zhang, and Z. Zhou. Dynamic regret of convex and smooth functions. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2020.
[95] M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In International Conference on Machine Learning (ICML), pages 928-936, 2003.
16

---

A Omitted proofs
In this section, we provide the proofs from the main body (Section 3).
A.1 Proofs from Section 3.1
First, we start with the proofs of the dynamic RVU bounds (Lemmas A. and A.2 below). Before we proceed, it will be useful to express the update rule (OGD) in the following equivalent form:
x (1) = arg max ZEA
(x) = (e, m
- Ba (a a )00))
"
(5)
1 B. ( || d((1))
á (1+1) = arg max &EN
(x) = (ir, (
"i
Here, Ba (- || denotes the Bregman divergence induced by the (squared) Euclidean regularizer Φx x 1> 2 | namely, B5, (xr I| æ') = ((x) - o(xr' (Vo(='), x²) 211= xx x'112 for
a, x' E X. The update rule (5) for general Bregman divergences will be referred to as optimistic mirror descent (OMD).
A.1.1 Dynamic RVU bounds
The first key ingredient that we need for the proof of Theorem 3.3 is the property of regret bounded by variation in utilities (RVU), in the sense of Syrgkanis et al. [78], but with respect to dynamic regret; such a bound is established below, and is analogous to that obtained by Zhang et al. [93].
Lemma A.1 (RVU bound for dynamic regret). Consider any sequence of utilities (u up to time T E N. The dynamic regret (1) of OGD with respect to any sequence of comparators (1,)),))
x (TT))) X2 can be bounded by
D2
Dx
T-1
+
(1+1,+)
(1,t)) 12 m7
(1(
!0
2m
- - (1xx10)))())
+ [|xx 11(+1111))
(6)
2m
In the special case of external regret-ar (1,+) = x. (2,+)
x: (T,)) (6) recovers the bound for
OGD of Syrgkanis et al. [78]. The key takeaway from Lemma A.1 is that the overhead of dynamic
regret in (6) grows with the first-order variation of the sequence of comparators.
Proof of Lemma A.I. First, by (1/n))-trong convexity of the function (!) (defined in (5)) for any time E [T], we have that
(1) mm())
110000
x 10 11 (1(1+1) m (1) + 2n
1 [| 10 2
1 [
((+1) 11 (7)
21
2n
where we used [75, Lemma 2.8; p. 135]. Similarly, by -trrong convexity of the function (!( (defined in (5)) for any time E [T], we have that for any comparator (*.,)) X,
(a(++1) (
a (++1) a00 (x(()))
u (3)
x (t+e) - (2) 1
2m
2n
(++1]) (1:)))
(8)
211
Thus, adding (7) and (8),
(t..) - (1+1), ( + (++1) - (0) mm())
(0) <
(10(0) - (t - - (c. (
||
2y
1
(|x((1) 2001 ( ( 11) (9)
2m
17

---

We further see that
(x - (.(0),e!0) = (xx(() - =((+1), m = (xel1it) - (((+1) u (
+ (ale+1)) w0()) m (1)
(10)
Now the first term on the right-hand side can be upper bounded using the fact that, by (7) and (8),
(ax(1) (1+ m (A) ( 2 - (|(((++11) 10 = ||x((++1)) (0 S m/lmm u 2|,
by Cauchy-Schwarz, in turn implying that (ax(1) ((++1), m (2) u S ///mm
(2) u. u013 Thus,
the proof follows by combining this bound with (9) and (10), along with the fact that
(| 11 -12 20!,;)13) = 11(00) 11
- -2 (ctt..)) -11011111111111111
||x((++1)) -2 (1,))
T-1
$ Dz + 2Dx
Σ
x (1+1,+)) (l2.
where the last bound follows since
[[((+11) 11 | (++1)
< 2Dx ||0((+1) - (1
( (0( 16:(1+11 x (1.t)))
2D (2((+1,,)) - 20(11))
where we recall that Dxx denotes the fz-diameter of X.
As aside, remark that assuming that m (1) 0 and lu. 1a S 1 for any E [2] Lemma A.1
implies that dynamic regret can be upper bounded by O
E [| 1,x) x |12)
for any (bounded) potentially adversarially selected selected-sequenee sequence of utilities (u ut (T)) for
D3 Dx Dx [u(+++.))_((+))>1 which is well-known result in online optimization [95];
" =
while that requires setting the learning rate based the first-order variation of the (optimal) com- parators, there are standard techniques that would allow bypassing that assumption.
Next, we provide extension of Lemma A.1 to the more general OMD algorithm under broad class of regularizers.
Lemma A.2 (Extension of Lemma A. beyond Euclidean regularization). Consider a 1-strongly convex continuously differentiable regularizer ó with respect norm I| such that (i) [|V S G for any x. and (ii) Bs, (x || x') S L|(x 1 x'1l for any x, x'. Then, for any sequence of utilities (u (1) Uz (T) up to time T N the dynamic regret (1) of OMD with respect to any sequence of comparators (1x)),, (alli,),...,.. ,...,, (T.)) E XT can be bounded as
Bo. (20() || ((1))
L + 2G T-1
T
+
(++1,,) - (((,t)]]
||
7
7
t=1
(l2(0)) - (0(0) (|x(1) (22+)))22)
2n
The proof is analogous to that of Lemma A. and relies on the well-known three-point identity for the Bregman divergence:
Bg (x || x²) Bo. (x || x²")
|| x²) (x.
(x x". Vo(x') volx")).
(11)
18

---

In particular, along with the assumptions of Lemma A.2 imposed on the regularizer Φz. (11) implies BB (x0(:-)) || x((+)))) is equal to
T that the term Ii (Bs, (xx(+1,,*) || (((+t))-
T Bo, (zx
|| coll.))) - (arlit1,n) - s!liit) Vo( - {o((z!(()))))
S (I++2G) Σ [=((++1+)) -x ,.(".")|,
since BB, (x:(++1,+) || all))))) < L|| - x((hi)|| (by assumption) and
(x((t+)))) - wllirt, Vola((+1))
V ))(()())))
| (((11)))) - ((() vo( - vo(z(())))
(12)
V (o(xx(+))) )1)) [|z((+2,,+) - x(()t)]| (13)
S 2G|| - (.(.,))|
(14)
where (12) follows from the Cauchy-Schwarz incquality: (13) uses the triangle inequality for the dual norm || -Il:: and (14) follows from the assumption of Lemma A.2 that ||Vo(-))l G. The rest of the proof of Lemma A.2 is analogous to Lemma 1, and is therefore omitted. One important question here is whether Lemma A.2 can be extended under broader class of regularizers; explain in Section 3.4, this is related to improving Theorem 3.13.
A.1.2 Nonnegativity of dynamic regret
We next proceed with the proof of Property 3.1. For completeness, we first prove the following special case [93]: the proof of Property 3.1 is then analogous.
Property A.3 (Special case of Property 3.1). Suppose that 2 3 (11.a) = (ar(1it), g(o.)) Nash equilibrium of the t-th game, for any time t E [T]. Then, for sz
(T) (x(())) and
(T) (1+))) SESTT.
By
DReg. (T) (((T) + DReg,
(T (s 2 O.
Proof. Let v(0) (anllit), A (0 ((+)) be the value of the 1-th game, for some E [T]] Then, we have that o(t) = (alltr),, A (4) ((,))) < (x, A(y for any x E X, since x (f.+) is a best
response to ((l+t); similarly, (1)) (we(),) A Z (wlthtt A A y) for any y E Y. Hence, (z:(1), A A00 (t.x)) - (ax(t,)), A (1) (t)) 2 0, or equivalently, (a(tt)) (0)) + (ty(t.)) uy (t)) 2 0. But
given that the game is zero-sum, it holds that (xx()), ( + (1((0) (e)) = 0, so the last inequality can be in turn cast as
( (0) ( + (y (*x7) (1))) ( ( > 0.
for any & [T]. As a result, summing over all E [7] we have shown that DReg (T) (x)()))) ,..., x (T+)) DReg!
(1,+) ..... y (T:))
T
Σ (tre), (l!)) - (z))) + (( - 2 0.
Property 3.1. Suppose that 2 (t(i)) = (ax()))), ((in)) is an e0 approximmate Nash equilibrium of the t-th game. Then, for s = (e(l::)) and sy
(T) )
DReg (c( + DReg (3) (6( 2 2 T
(1)
19

---

Proof. Given that (xl()*), (elitt),y((itt) y(litt) E Z is an clt) -pprooixoee Nash equilibrium of the t-th game, it follows that (altit), A ((()))))))
( ((t)))) + co and (al(iin,, A A00g y(tr))))) 2
(x(l>>) (0)) Ey for some & .6 I el Thus, we have that (x((), , ( 2
(x (xll.") A (0) (1) o or equivalently, (all4)),, u > (yy(",), u - (t) Ey z -2e
As result,
(zl _ (zl u + (g u!!)
(y ( 2 2e
(15)
for any & [T'] and the statement follows by summing (15) over all E [T]]
O
In fact, as we show below (in Property A.4), Property A.3 is a more general consequence of the minimax theorem. In partieular, for a nonlinear online learning problem, define dynamic regret with respect to sequence of comparators (ax(1.)),
(TT,)) Xx' follows:
T
DRegi
(T) (a (1.4)
x (T.))
= Σ
(0) (1 (x!1)))
uh (0) (z.((.t) u
(16)
or
where Uz could be in general nonconcave, and (xx*) ( SiST is the sequence of strategies produced by the learner; (16) generalizes the notion of dynamic regret (I) in online linear optimization, that is, when u x + (x, u!")), where u E Rd for any time E [T].
+ R are the continuous utility functions observed by the learner, which
Property A.4. Suppose that f()) X y + R is a continuous function such that for any t E [T].
min max ((t) (xx. v) max min (x,
#EX yEY
yEY æex'
Let also (f.**) E arg min max f()) (a, y) and ((t+)) E arg max mingex (x) for any E [T]] Then, for 8/ = (x(t. Igger and sy (y)l))))ssen
DReg. (T) (T) + DReg, ( (s (T) 2
Proof. By definition of dynamic regret (16), it suffices to show that (0)( y (x)ltt)) ()) for any time t E [7]. Indeed,
2
(000)) (())))
min (x, y(t)) =EX
(17)
max
min ( (2r, y) #cx
(18)
min max (xx y) =ex yEy
(19)
max (()) (b+))) ,
(20)
wEY
2 ( (t,x)) (t))
(21)
where (17) and (21) are obvious: (18) and (20) follow from the definition of y (t+*) e y and
(t++) E X, respectively; and (19) holds by assumption. This concludes the proof.
O
A.1.3 Variation of the Nash equilibria
In our next example, we point out the standard observation that an arbitrarily small change in the entries of the payoff matrix can lead to a substantial deviation in the Nash equilibrium.
Example A.5. Consider a 2 x 2 (two-player) zero-sum game, where X' = 2 == 2 described by the payoff matrix
25 0 0
A
(22)
5
for some 8 0. Then, it easy to see that the unique Nash equilibrium of this game such that x², ,yy" = ( ?) e A Suppose now that the original payoff matrix (22) is perturbed to new matrix
=
0
25
(23)
20

---

The new (unique) Nash equilibrium now reads x", = (3 33) E A We conclude that an arbitrarily small deviation in the entries of the payoff matrix can lead to a non-trivial change in the Nash equilibrium.
Next, we leverage the simple observation of the example above to establish Proposition 3.2, the statement of which is recalled below.
Proposition 3.2. For any T 2 4, there is a sequence of T games such that v!T) I for any 8 O.
( NE
2
T while 2
Proof. We consider sequence of T 2 games such that N. A and
i mod 2 = 1,
A (0)
A'' ift mod 2 = 0,
where A, A' are the payoff matrices defined in (22) and (23), and are parameterized by 8 > 0 (Example A.5). Then, the exact Nash equilibria read
ift mod 1,
a: all,,) (1,+)
3 if mod 2 = 0.
As a result, it follows that (7) = EE= (2(++.))) - 2|1,)||2 = ( 1) 2 T for T 2 4.
2.
C-NN S C8T, which follows by simply considering the sequence of strategies wherein both players are always selecting actions uniformly at random; we recall that
In contrast, it is clear that V (TT))
5' C > 0 here is the value that parameterizes ((T) VE-NE- Thus, taking = CT for some arbitrarily small > 0, concludes the proof.
In the above sequence of games, the variation measure W(T) (T) is in fact also arbitrarily small as 6 + O; this reflects the fact that, although the exact Nash equilibria change abruptly, the sequence of payoff matrices exhibits small variation. Nevertheless, we next point out a modified sequence of games where NE remains small even though both w(T) and NE can be unbounded.
Proposition A.6. For any T 2 4, there is sequence of games such that ()T w = (T( while ((T) C--NE S for any 5 0.
NE A
Proof. We consider sequence of T 2 games such that X, 2 and
[ A + 12x2
if mod = 1,
(0)
A'
if mod 2 = O,
where A'
A' are the payoff matrices defined in (22) and (23), and 12x2 denotes the all-ones 2 x 2 matrix. Given that x (A + 12x2)y = x Ay + 1, for any æ, y E A follows that the set of e-approximate Nash equilibria of each game coincides with the set of e-approximate Nash equilibria
of the corresponding game in Proposition 3.2. Thus, by the same argument as in Proposition 3.2
earlier, we have that (TT) the proof.
NE 2 T' and (T)
C-NE S C8T. It is also clear that (XT) -)T), concluding 2
In words, the phenomenon identified above occurs because W(T) is affected by perturbations in the payoff matrices that do not strategically alter the game-namely, the addition of the matrix 12x2-
A.1.4 Proof of Theorem 3.3
Next, we proceed with the proof of one of our main results, namely Theorem 3.3. The key ingredient is Theorem A.7 below, which bounds the second-order path length of OGD in terms of the considered variation measures.
Theorem A.7. Suppose that both players employ OGD with learning rate S AL in a time-varying bilinear saddle-poin problem, where L maxigIST ||A
19 112. Then, for any time horizon T E N,
(1=(0- 220013 + +1((0) - g((+)))13)) < 2D2 + 4n L 212 + M!T) NE + 8/ 12
21

---

Proof of Theorem A.7. First, for any L 2 2 we have that |/ (1) mm (1) 11 is equal to
|| y A y
- 2 (0) (y (t) - () 2 2 (0) - A (t
( 12
(24)
s 2|
(1) 11 2 (0) - A ((-1)
1 (25)
- 22L 11 + 21 A (0) - -1
(26)
where (24) uses the triangle inequality for the norm || |l2 along with the inequality 2ab S a² + 62
for any a, 6 E 1R; (25) follows from the definition of the operator norm; and (26) uses the assumption
that | 10/2222 I L and l|vll2 - ||>i|l2 for any y E V. A similar derivaiton shows that for 2 2,
|| ( m
( 112 - 2L 2l (t-11)
112 + +211211B11 (4)
(1 11-
(27)
Further, for 1 we have that 11 m 1|2 1 | A y o S 2|D and ||u!] m. 2 ||22 = | (1) 11 I 11 Next, we will use the following simple corollary, which follows similarly to Lemma A.I.
Corollary A.8. For any sequence " == (2(++)))sss) the dynamic regret DRegz (T) (s!T) =
DReg (T)
(sx)) DReg (s(! can be bounded by
D2
Dz
2((.t)) 11 Σ
|/
m00112
+
2n
"1
1=1
(1200) 200 -1100++1-0000 1(()111))
21
(1) (t) = (mz mm and us = (uz uy where m
(t)
for any t E [T].
As result, combining (27) and (26) with Corollary A.8 applied for the dynamic regret of both players with respect to the sequence of comparators ((x(t.*), y)++))) yields that (Reg(()
(M (x) ((()))))...,,,))))))))) + DReg, (y!l.t)........ (((:))) is upper bounded by
(()+)))
D2
Dz T-1
+ +, 2n
(1,))) ||2 + 2nl 21335
T
1
Σ
(1x00) - 200 + -|0(0) 20(+21133)
4n 1=1
where we used the fact that
T
T Σ
1
1|
(012))
(1200) - =(0) 112 + +1|2(0) - 2
4n 1=1
2
1 112(0) 200-1) 112 S 0,
2n 2
8n)
for any leaning rate n S 41. Finally, using the fact that DReg (T (2) (T+))
DReg("(y (M,) ..... (T.) 2 - (1)) for a suitable sequence of ((t) apprroxxiee Nash
equilibria (Property one that attains the variation measure ((T) -
yields that
D3 0 < 27
+n
Dz pT 1
+ + 2
1 An
(1 200) 1|2 + || 2(0+1) 112
where in the above derivation it suffices if the parameter C' of y:T) y--NE such that
2 Dz Dzc -
2n
C = C(r) 2
(28)
1
Dz
Thus, rearranging the last displayed inequality concludes the proof.
22

---

Next, we refine this theorem in vare-ng games in which the deviation of the payoff matrices is bounded by the deviation of the players' strategies, in the following formal sense.
Corollary A.9. Suppose that both players employ OGD with learning rate v S min J1 4T. swil
in a time-varying bilinear paddle-point problem, where L == maxigisT ||A 1l and VATT 1
W - || - =0. for some parameter W Rz0. Then, for any time horizon T E N.
T
(1=(0) =00 + 11 - 2(++1113) < <4D2 + 8121,112112 + 8D2VEE
Proof. Following the proof of Theorem A.7, we have that for any S 1
47,
D2
Dz (TT + 21/231/4 4n
50 + nTT
(1 - - + -| - 11)
27
7
Further, for S
2
1
(2(00)
=00011 || - 2((+1)113
8n
2/112//222
|| (1(1) 201 S
16n
Thus, we have shown that
D2 < 2m
+ +1 +
Dz (T)
T
(|=10] - 12(00 + =1
NE
8n
t=l
and rearranging concludes the proof.
Thus, in such time-varying games it is the first-order variation term, (T7) that will drive our convergence bounds.
Now before proving Theorem 3.3, we state the connection between the equilibrium gap and the
deviation of the players' strategies (I)=(() 2 [|2 + [|2(()) -(++1) l|2).. particular, the following claim can be extracted by [2, Claim A.14]. (We caution that we use a slightly different indexing for
the secondary sequence (i!") in the definition of OMD (5) compared to [2].)
Claim A.10. Suppose that the sequences (x! I and (&(1) S1 are produced by OMD under G-smooth regularizer 1-strongly convex with respect norm || -|. Then, for any time t te [T] and any x E E.
GDx [0((+)) - - 11.1o) ((+11)].
(a
(0) (z. (())
7
We are now ready prove Theorem 3.3, the precise version of which is stated below.
Theorem A.11 (Detailed version of Theorem 3.3). Suppose that both players employ OGD with learn- 1 ing rate 17 TZ in time-varying bilinear saddle-point problem, where == maxi || (9//22 Then,
T
Σ (Z(GA 221 (2D*) + 4112 AAD + 8 11711217777)
where (2(1)) is the sequence of joint strategy profiles produced by OGD.
Proof. Let us fix t E [T]. For convenience, we denote by (R(((()(())) = max { (wt u(² (x) ux (t), the best response gap of Player's a strategy (1) E X, and similarly for BRJ" (z(1))
23

---

By definition, it holds that (QGAP(((2()) = max m (z(*),, ( ()). By Claim A.10, we have that
Dx |((((1) 1 + ||u - |2|1 (1) - 111
(x!0)) -
1
(29)
11
- (11xx + L|1 x0 - -0 112
(30)
- L (4Dz + +122112 [|x((t) 11 + ||x - =1(t)11))
(31)
where (29) follows from Claim A.10 for G (since the squared Euclidean regularizer Φ2 a: H> ||a)) is trivially 1-smooth; (30) uses the fact that == IT, and | ( ||2 || A (0)00 < L|
and (31) follows from the triangle inequality. similar derivation shows that
BR (g) L(4Dz [| (l1( 11 1l 1((11)122
(32)
Thus.
T
T max (B (xx(1)) (R(O()(())) ?
(=()))(0(((0))=
(BR (x())) 2 + (Q)))
S 22L Σ (1=10- + - 11|1110-0((1)))0 =((+ (33)
where the last bound uses (31) and (32). Combining (33) with Theorem A.7 concludes the proof.
A.1.5
Variatioon-eepndent regret bounds
Here we state for completeness an implication of Theorem 3.3 for deriving variation-dependent regret bounds in time-varying bilinear saddle-point problems; cf. [93]. Corollary A.12. In the setup of Theorem A.7. it holds that
Reg (T) s D3 + SnLLD2 + nn + 167 2 16nL
7
+ +2n 32
and
D2 + 1nII. D2 + + 16,2141211 +17211113+1 + 16n Dz (T))
Reg (T) < n
+ (2ml x122+ + 32m L 13113113117
Proof. First, applying Lemma A.1 under x (1.+) = -.. (T:+), we have
D& + TT? + 2n
T
T Σ
Reg (T) <
(T)
(1) (t) (t- (1 + 2n11
| (0)
A (34)
t=2
and similarly,
T D2 + n 22 Σ (1) (01-1)) + 2n| Reg (T) <
T Σ
A (4) A (35)
1=2
Now, by Theorem A.7 we have
(1=00 -190-2100 200 + (|=(00 200+1)13)
14 (36)
24

---

Further,
(120) - 12 ||= 20+
[1x00) - 11 + ||x - 11++11)))
1111-1113
Combining this bound with (36) and (35) gives the claimed regret bound on Reg (2) and a similar derivation also gives the claimed bound on Reg(?)
(v 1 V + + bound on the individ-
Hence, selecting optimally the learning rate gives O
ual regret of each player; while that optimal value depends on the variation measures, which are not known to the learners, there are techniques that would allow bypassing this [93]. Corollary A.12 can also be readily parameterized in terms of the improved variation measure y(T) NE-
A.1.6 Meta-learning
We next provide the implication of Theorem 3.3 the meta-learning setting. We first make a remark regarding the effect of the prediction of OGD to Theorem 3.3, and how that relates to an assumption present in earlier work on this problem [48]. Remark A.13 (Improved predictions). Throughout Section 3.1, we have considered the standard prediction m = ur (t-1) - (t-1) y for t 2 2, and similarly for Player y. It is easy to see that using the predictions
m (1) = A 1 (1-1) and m (0) = (A (1)) (t-1)
(37)
for t > 1 (where z = 2))) entirely removes the dependency on VLT)) on all our convergence bounds. While such prediction cannot be implemented in the standard online learning model, there are settings in which we might, for example, know the sequence of matrices in advance; the meta-learning setting offers such examples, and indeed, Harris [48] use the improved prediction of (37).
Proposition A.14 (Meta-learning). Suppose that both players employ OGD with learning rate 1 47. where L max H ||A (A) l|,, and the prediction of (37) in meta- meta-learning bilinear saddle-poni problem with H e N games, each repeated for m E I consecutive iterations. Then, for an average game,
P
P'V
+1
(38)
He
H
iterations suffice reach an e-approximate Nash equilibrium, where P := 4L2(4D2 11 p' = (AD + |1 and
H-1 Σ hml
(H)) NE
=
inf Z
|| (b+ - -2 (1
The proof is a direct application of Theorem A. where we remark that the term depending on ((T
and the term 41/² T.2 2112 from Theorem A. are eliminated because the improved prediction of Remark A.13. More precisely, we let (h) E N be the number of iterations required so that the equilibrium gap is at most at the h-th game, then Theorem A.11 implies that
P+ P+P'L (H)
Σ (EOGAP(((()))
é²
(m (m) 1).
Solving with respect to 1 E (h) thus yields Proposition A.14.
25

---

The first term in the iteration complexity bound (38) vanishes in the meta-learning regime- as V(
the number of games increases H w-while the second term is proportional to H natural similarity measure; (38) always recovers the m- rate, but offers significant gains if the games as similar, the sense that
1 < It is worth noting that, unlike the similarity measure derived H
by Harris et al. [48], Vis arises in settings where the sequence of games is known in advance is to optimize the order of the
depends on the order of the games. As result. natural problem that
games so as minimize >EEE the key challenge of course is to minimize ( without actually
solving each game since that without defeat the purpose. We further remark that Proposition A.14 can be readily extended even if each game in the meta-learning sequence is not repeated for the same number iterations.
Another natural question in this context is to compare the similarity metric of Proposition A.14 compared to that obtained by Harris et al. [48]-namely millezz > 1 || - =112. where
assume here that 2 (h,+)) is the unique Nash equilibrium of the h-th game. Below, observe that v( can be arbitrarily smaller.
Proposition A.15. There exists a sequence of H games such that vith min E [1x((..+) - 2112 S.H).
O(1) while
Proof. We let X, = A We consider sequence of H games so that (hh,,)) (1.,)) for all h E [H]. and the sequence of points (x (=((+=)) forms a aregular H-gon within the relative interior of A with a constant radius. We note that unique fully-mixed equilibrium ((a, B, 7), (a, B, 7))
A x A can be obtained by considering the diagonal payoff matrix
1 1/a
0
0
1/8
0
0
1/71
is easy to see that the above sequence of games establishes the claim.
A.1.7 Polymatrix zero-sum games
As we claimed earlier in Section 3.1.1, Theorem 3.3 can be extended to more general time-varying Vis as long as the MVI property holds. For concreteness, here we focus on a multi-player generalization of two-player zero-sum games, namely polymatrix zero-sum games [15]. More precisely, here it is assumed that there is an underlying n-node graph so that each player is uniquely associated with node in the graph. The utility of each player E [n]] can be expressed as EVEN; x! A,, where N₁ denotes the set of neighbors of Player i and A E Rdixd,, It also assumed that AT 1 -A for any edge (i,t'. If (EI....,T,,) E Z. the corresponding operator is defined as
F(z)=
Σ A VEN
Σ An, i,,,
is easy to see that F is monotone, in that (z z', F(z) F(z')) 2 for any 2, x' Z. Now, for any e-approximate Nash equilibrium 2 it holds, by definition, that (z zt, F(*)) 2 -nc, for any z E Z. Thus, by monotonicity, (z - ==, F())) 2 (z- z², F(=*)) -ne, for any z E Z. In other words, approximate Nash equilibria approximately satisfy the MVI property. This suffices to directly extend Property 3.1 to vareingy polymatrix zero-sum games. The rest of the argument of Theorem 3.3 is analogous, leading to the following result. Below, we define (T)
NE as in (2), for 1.2
suitable parameter C > 0, and V = -E Σn EVEN,
||A (t+1)
Theorem A.16. Suppose that each player employs OGD with a sufficiently small learning rate
a sequence of time-varying polymatrix zero-sum games. Then, ΣT (22)))()(2(1))
o (1 (1+ V(T) + V1T)). where 12(5)) is the sequence joint strategies produced by OGD.
26

---

A.1.8 General variational inequalities
Although our main focus in this paper is on the convergence of learning algorithms in time-varying games, our techniques could also be of interest for solving (static) general variational inequality (VI) problems.
In particular, let F : 2 + E be single-valued operator. Solving general VIs is well-known to be computationally intractable, and so instead focus has been on identifying broad subclasses that elude those intractabilityy barriers (see the references below). Our framework in Section 3.1 motivates introducing the following measure of complexity for VI problem:
C(F)= =
inf
|| 22(.,)
(39)
subject to
T Σ (2 2(t,)) F(2))) 2 0.
DRegi (T (2 (T+)) 20
(40)
In words, (39) expresses the infimum first-order variation that a sequence of comparators must have in order to guarantee nonnegative dynamic regret (40); it is evident that (40) always admits a feasible sequence, namely s!²) = (z( ISSST. We note that, accordance to our results in Section 3.1, one can also consider an approximate version of the complexity measure (39), which could behave much more favorably (recall Proposition 3.2).
Now in a (static) bilinear saddle-point problem, it holds that C(F) = 0 given that there exists a static comparator that guarantees nonnegativity of the dynamic regret. More broadly, our techniques imply ((poly(1/a ctoppeion bounds for any VI problem such that ((F) I CT for time-independent parameter C' and (0, 1]:
Proposition A.17. Consider a variational inequality problem described with the operator F F Z + Z such that F is T--Lipschitz continuous, in the sense that [[F(z) F(z')1l S Ll| 2/112, and ((F) S CT 1- for C > () and E (0, 1]. Then, OGD with learning rate 1) = 4T. reaches an c-strong solution z' E Z in (2=w/) iteration;; that is, (z z", F(2*)) 2 -e for any
2.
This result should be viewed part of an ongoing effort to characterize the class of variational inequalities (VIs) that are amenable to efficient algorithms; see [33, 13, 4, 7, 21, 23, 56, 57, 66, 76, 87, 24], and the many references therein.
It is worth comparing (39) with another natural complexity measure, namely inf ΣL (z(1)
z", F(z(")); the latter measures how negative (external) regret can be, and has already proven useful in certain settings that go bilinear saddle-point problems [88], although unlike (39) it does not appear to be of much use in characterizing time-varying bilinear saddle-point problems. In this context, (poly(1//e) iteration-com complixxt bounds can also be established whenever
infzrez Ei (x(0) =((F(2(0)) 2 - CT1-w for a time-invariant C > 0, or
inf D (z(1) 2" =((1() 2 -C T-1 (1+1) =00) for a sufficiently small C>0.
Following [88], identifying VIs that satisfy those relaxed conditions but not the MVI property is an interesting direction. In particular, is important to understand if those relaxations can shed led more light into the convergence properties of OGD in Shapley's 's two-player zero-sum stochastic games.
A.2 Proofs from Section 3.2
In this subsection, we provide the proofs from Section 3.2, leading to our main result in Theorem 3.5.
Let us first introduce some additional notation. We let f()) X x y + E be a continuously differentiable function for any [T]] We recall that in Section 3.2 it is assumed that the objective
'In case the interior (X' ) is empty, here and throughout this paper we tacitly posit differentiability on a closed and convex neighborhood A y' such that X C X² and y C 5º. This assumption suffices for our arguments; see, for example, the treatment of Daskalakis et al. [28].
27

---

function changes only after m E IN (consecutive) repetitions, which is akin to the meta- veta-learning setting. Analogously to our setup for bilinear saddle-point problems (Section 3.1), it assumed that Player is endeavoring to minimizing the objective function, while Player y is trying to maximize it. We
will denote by Regg, (e (xx)) Ei= (z x², - and Reg2. (v*) = Ei=("" y( uy (
where u vaf(x))) . y (1) and ui! V f(("), (()) for any & E [ similar notation is used for DRegg... (T) DRege. (T)
Furthermore, we let 8 ((7) = ((x) (((iit) ISEST so that (t+,+) = xhh+ and y(x+)) = y for any E [[T] such that [(t - 1)/ml = E [H]. The first important step in our analysis is that, following the proof of Lemma A.1,
H
T
DReg (s (TT) S
1
[+
(,,+) 11 (1)+m - 21 +
1
(t) - m
20
t=1
1 T (1x((0) -100112 + +1xx!1) -e (1+2) 113
(41)
2n
where (((..))) == _(((h-1xxm++)) for any (h, k)) E [M] x [m]] @(h.m+)) = ((++1.1)) for h E [H - 1].
and a (H.m+1)) = xz (T++)) Similarly,
H
T
DReg (T) (1)) I 2m hml
10 (h,11)
(h,,)
11 [lghh.++11 y0h + 17
|/ mm!
1 2n
(1
5000 + +1, -g g((+ 112
(42)
Next, we will use the following key observation, which lower bounds the sum of the players' (external) regrets under strong convexity- conccvity..n..vity..
Lemma A.18. Suppose that f X y + BR is p-stroongyy convex-concave function with respect to || 212 Then, for any Nash equilibrium z" = (x y²" E Z,
(m) Regg, (x") + Regg, (m)
(y²)
Proof. First, by p-strong convexity of f(x, -), we have that for any time t E [m]]
(x -"" (xx((() ()) 2 2 f( (h)) f(x", y (*)) + // (1 -000)x111
(43)
Similarly, by p-strong concavity of f(: v). we have that for any time / E [m].
y (1) (x)() yy ()))
2 (x) 3²* - (xx(
(t), y (1) + ~リ 11 (1)
y y-1
(44)
Further, for any Nash equilibrium y²) E 2 it holds that f(x()) ,,² 2 f(x((1) ()) 2
f(",, (())) Combining this fact with (43) and (44) and summing over all t E [m] gives the statement.
In turn, this readily implies the following lower bound for the dynamic regret.
Lemma A.19. Suppose that f(h)) x + R is a p-strongly convex-concave function with
respect to - -122. for any h [H]. Consider sequence s ((x((.+),,((t*+)) ISSTT, that
((t+)) (hit) and ylt.*) -y(h for any t [T] such that L(t - 1)/ml h E [H]. If
(arthtt), y(tht) E Z is Nash equilibrium of f(h)
H (1.bk z (h.+))
DReg (T) (s(T)) + DReg (s
(T)
(T)
hm km
where (hi,k) = ( =(01-1xxm)+H) for any (h, [H] x [m]]
28

---

We next combine this with the following monotonicity property of OGD: If x" is a Nash equilibrium.
||x(0] x" 1l2 is decreasing function in t [48, Proposition C.10]. This leads to the following refinement of Lemma 1.
Lemma A.20. Under the assumptions of Lemma A.19, if additionally n S 2p
T
H
(T) (s + DRege. (5 DReg
(T) +
1
1| (1)
20+
um
1 (h.m++)
2 (bxx)) 12.
47 t=1
4
Proof. By Lemma A.19,
DReg (64 DReg T (.)
|z - 2((11) l/
Av
H
T
(h,13) - 201 +
(t) 2 2(+
2
4.7
1=
(h, - 201,0)1
(45)
uum
[l) - 20
(46)
where (45) uses that 1 2 5 along with Young's 's inequality and triangle inequality, and (46) follows Σy from [48, Proposition C.10].
Armed with this important lemma, we are ready to establish our main result (Theorem 3.5), the detailed version of which is given below. We first recall that the function f X' x y - IR is said to be L-smooth if [z) F2z')ll2 S L||z- 2' l12, where F(z) = (V y). -V fff y)).
Theorem A.21 (Detailed version of Theorem 3.5). Let f(k); X y be a j-strongly convex-concave and T--smoohh function, for h E [H] Suppose that both players employ OGD with learning rate 1. } for T repetitions, where T m x H and m 2 2. Then, 8L 2p
n min
mp
(1=()) 2 + +1((00) -200)111 S <DD2 + +n7111((2())) 112 8S + +167 1 v
(H) Thus, El (EQGAP(*( 0(1 SNF + v(H))
Proof. Combining Lemma A.20 with (41) and (42),
H
[|2(0.1)
+ qum ((hm++1) - =0hh2))12
00
21)
2
h=1
T
+1
(t)
191
1
(12(0)- - -2(1113 1lx(0) s(c=1))13)
4n
for a sequence of Nash equilibria (z(h.))) ) Jsshs where we used the notation u0! = (u (t) (
and m (1)
= (ml)) (!) (())). Now we bound the first term of the right-hand side above as
(1 -2 2(h,)) (h.mmm z 20hx0)13) S
21 h=1
1
(1.1) - 2 =2(1x) + 2/1 h=1
[| _ 20++1,0) -2| =(hx=) 113)
21
29

---

where we used the fact that m 2 from above,
2.
and ((hm+1)) = 1(h+1111, for h E [H 1]. Hence, continuing
my
- 21 (1(hh1)-2
(0 - 2 -
2n | -z (1.1)) 12
1
2n h=1
|| (2(++ 211it))
"1
since || - x 2 13 < (1( 21(x,))13 + 2| 2 (h,tt) x ( (1+1, by the triangle
inequality and Young's inequality. Moreover, for 2 [ u ( = [[((0 - F(t-1)(x1111)
>12 v 21 10) - x 201211113
+ 2 (2 F(t (2
by L-smoothness. As result,
T
- S 2L
|| - (1-1 12 + 2V (1)
and the claimed bound on the second-order path length follows. Finally, the second claim of the theorem follows from Claim A.10 using convexity-concavity, analogously to Theorem 3.3. O
We conclude this subsection by pointing out an improved variation-dependent regret bound, which follows directly from Theorem A.21 (cf. Corollary A.1
Corollary A.22. In the setup of Theorem A.21, the maximum of the two players' regrets, (T) (T)) can be upper bounded by max [Reg... Regg.yy.
D2 + 16n1, + (321/11² ()) 3. (64n) 1,² 21)
"
(T) ( = (V1+ SK (V1+s V41 Thus, setting the learning rate optimally implies that Regg, Regg.
+1(
A.3 Proofs from Section 3.3
In this subsection, we provide the proofs from Section 3.3.
A.3.1 Potential games
We first characterize the behavior of (online) gradient descent (GD) in time-varying potential games; we recall that GD equivalent to OGD under the prediction m 0 for all Below we give the formal definition of a potential game.
Definition A.23 (Potential game). An n-player game admits a potential there exists a function Φ X X3 + R such that for any player i [n]. any joint strategy profile æ_, E Xxax Xy, and any pair of strategies F,, x/ E X,
+ (xx, x) ( x-)) = u, (2;; x_.)) - Us u1 x-s).
The key ingredient in the proof of Theorem 3.7 is the following bound on the second-order path length of the dynamics.
Proposition A.24. Suppose that each player employs GD with a sufficiently small learning rate 1j > and initialization (x:
(1) ....,.!!! x!!l) E X"=1 X, in sequence of time-varying potential games. Then,
T
n
T
(t+1)
(1)
(t+1)
....,. ((+1)) - $ (1 20 (47)
x
2
30

---

This bound can be derived from [2. Theorem 4.3]. Now, we note that if ((1) = 4
the fight-hand side of (47) telescops, thereby implying that the second-order path-length is bounded. More generally, the right-hand side of (47) can be upper bounded by
24 max
T (z((t))
(x(+))(x))))) (x)++))
2 (t))
- 24 max + V97 (48)
where Paax is an upper bound on (.) for any / E [7], and V is the variation measure of the potential functions we introduced in Section 3.3. Namely, D == E d( p((+1), where d: ( Φ') - max X, (0(z) - ('))). Furthermore, similarly to Claim A.10, we know that
the Nash equilibrium gap in the 1-th potential game can be bounded in terms of >x ||=! (f++1 -xx 12 As result, combining this property with Proposition A.24 and (48) establishes Theorem 3.7, the statement of which is recalled below.
Theorem 3.7. Suppose that each player employs (online) GD with a sufficiently small learning rate in sequence of time-varying potential games. Then, Et= (xGGAP(((2 0 mas V V\T))
where mar is such that (a)())))) S & maa
A.3.2 General-sum games
We next turn out attention to general-sum multi-player games in normal form using the well-known bilinear formulation of correlated equilibria (Section 3.3). More precisely, this zero-sum game is played between a mediator, who selects strategies from the set of correlated distributions = A(X A:), and the players. Per the usual description of correlated equilibria, mediator recommends to each player i [m] an action in A: and then that player selects action that could be different from the one recommended by the mediator. As a result, each pure strategy of Player i corresponds to a different mapping from A; A., Player wants maximize the deviation benefit, while the mediator wants to minimize it. We let X; be the set of (mixed) strategies of Player i. The identity mapping d; A; 3 a + a; will be referred to as the direct (or obedient) strategy, prescribes following the recommendation of the mediator, As result, this game can be naturally cast as the bilinear saddle-point problem in the form of (4). By the existence of correlated equilibria [50]. it follows that there exists a mediator strategy μ* E E such that o; A, 14* < 0, for any player i [n] and क E R₁ words, there is no benefit for any player to deviate from the recommendation of the mediator.
Now, to establish Property 3.8, let first define the regret of any player E [n]
T (z) x (A( ()))
Regi (z)) = Σ
1=1
where 2; E Xr so that Σ = Further, the dynamic regret of the mediator-Plast min in (4)-can can be expressed as
Reg!"! is easily seen to be equal to the regret of Player max in (4),
DReg (p
(Tt)
Σ (
(4) (()).
The key idea in the proof of Property 3.8 is that the time-invariant direct strategy (di,..., d,.)
suffices to guarantee Property 3.1 as long as the mediator is selecting a sequence of CE.
Property 3.8. Suppose that 3 pe(t.t) is correlated equilibrium of the game any time t [T].
Then, DReg (T) (u
(T+)) + Σn= Regi (T)) > 0.
Proof. We have that
12
T
T
n A
DReg (T)
Reg (T)
(x;)
(1)) a (A (1) T
Σ
(0)
(1)
1=1
31

---

Now for any correlated equilibrium fu(t,x) of the I-th game, we have that (p(l,,) x0
x:!)) S
O for any player i E [n]. C; L, and time E [7], which in turn implies that
EL (t),, Ei=1 A x
0. Moreover, Σ m E (क) ( 2
0, by definition of the direct strategy d, E L. This concludes the ΣL_1 E t= (di, (A. T ( = proof.
Property 3.8 in conjunction with the argument of Theorem 3.3 readily imply Theorem 3.9. We should note here that the variation measure 112") = - Σ/=1 || (++1) - A is also immediately bounded in terms the second-order variation of the sum of the players' utility tensors. It is also worth noting that the description of the bilinear formulation (4) grows exponentially with the number players; this is unavoidable in explicitly represented (normal-form) games, but is worth investigating whether more compact representations exist in succinct classes of games, such as multi-player polymatrix.
Next, we provide the main implication of Theorem 3.9 in the meta-learning setting, which is similar to the meta-learning guarantee of Proposition A. 14 we established earlier in two-player zero-sum games. Below, denote by (hh+)) the set of correlated equilibria of the h-th game in the meta-learning sequence.
Corollary A.25 (Meta-learning in general games), Suppose that each player employs OGD in (4) with suitable learning rate 1j > 0 and the prediction of (37) in meta-learning general-sue -ume problem with E N games, each repeated for m E N consecutive iterations. Then, for an average game,
1
V
(H)
CF
(49)
2H
iterations suffice so that the mediator reaches an e-approximate correlated equilibrium, where
((H) inf gg(h.)
||
1 (1.a*) 12-
In particular, in the meta-learning regime, H > 1, the iteration-complextty bound (49) is dominated by the (algoritmm-inneeeendent)) similarity metric of the correlated equilibria y(#) (N) establishes significant gains when <
Corollary A.25
Finally, we conclude this subsection by providing a variation-dependent regret bound in general-sum multi-player games. To do so, combine Corollary A.12 with Theorem 3.9, leading the following guarantee.
Corollary A.26 (Regret general-sum games). In the setup of Theorem 3.9,
Reg. Reg; (T) = (4 + " v + +
for any player i [n]].
In particular, if one selects optimally the learning rate, Corollary A.26 implies that the individual
regret of each player is bounded by O (VI+ D(T (T)) We note again that there are techniques
that would allow (nearly) recovering such regret guarantees without having to know the variation measures advance [93].
A.4 Proofs from Section 3.4
Finally, in this subsection we present the proofs omitted from Section 3.4. We begin with Proposi- tion 3.10, the statement of which is recalled below. We first recall that regularizer Φz. 1-strongly convex with respect to a norm || |], is said to be G-smooth if | ( (w)- V (=)) < Gl| ||.
for all x, x'.
Proposition 3.10. Suppose that both players in a (static) two-player zero-sum game employ OMD with smooth regularizer. Then, DReg!!) DReg (T)
O(VT).
32

---

Proof. First, using Claim A. it follows that the dynamic regret DReg." (T) of Player up to time T can be bounded as
. (ox(1)
max xl
GDx llla|"1l1 ||x(0)
)l()))l(())) -x ((+11) +
GDx ||,00 -000==(0))) (50)
2001).
7
77
where G > is the smoothness parameter of the regularizer, and 17 >> 0 is the learning rate. We further know that Σ (Iax(() ' [| || 11²) (()) for any instance of OMD in a two- player zero-sum game [2], which in turn implies that Σi= (I|= - | + ||x((t) (++ =
((VT) by Cauchy-Schward Thus, combining with (50) we have shown that DReg. (T) O(VT).
Similar reasoning yields that DReg, (T) = O(VT), concluding the proof.
Let us next make a certain refinement of Observation 3.11. Staying (static) bilinear saddle point problems, we consider the unconstrained setting where X' = TR and y = Rdy, and we focus on the following update rule for E N.
x (r+1) = (1) -
+ An (T)
(- -
(51)
y (++))= = (()) + 2n/A T Tn(T) A
T (T(11)
where (0), (-1) X' and y (0) - E y. This an instance of optimistic follow the regularized leader ( (OFTRL) [78], although our discussion here also covers the corresponding OMD variant. Then, summing (51) for = 1, .,,, we have
x (++1)
Σ (T) 21/A
Σ
(T)
+
1A
Σ -
r=1
Σ
y
(++)
Σ
y (r) + 2nIAA T
Σ x7)
-AA T
Σ xr--
r=1
turn implying that
a ((+1)
1
(1)
+
A
1
(0)
(1)
2n1
Ag
17
t
(g
1+1
(+]
1
1
(52)
1
n T
1
(0)
t
7()) 2m
t
T (0
t A x (1-1)
t+1
t+1
t
(()) (T). That is, the update rule (52) describes the evolution of the time average of (51). As a result, this implies that (52) converges in last-iterate sense with 7 rate, simply because OFTRL incurs 0(1) regret [78]. This is conceptually interesting as it suggests a simple way to analyze the convergence of the last iterate solely through a regret-based analysis. In fact, (52) is variant of the so-called Halpern's 's iteration [32]-a classical technique in optimization- incorporates optimism; a similar update rule was recently shown to exhibit a new form of acceleration by Yoon and Ryu [90], and has engendered considerable interest ever since. Returning to Observation 3, one can use (52) to guarantee Ollo T') dynamic regret in the standard feedback model, although it not clear how to extend this argument in the constrained setting (cf. [14]).
Above, we define ((1) = 1 - x
and 9()) -
General-sum games We next extend our scope beyond bilinear saddle-point problems. We first observe that obtaining sublinear dynamic regret is precluded in general-sum games. In particular, we note that the computational hardness result below (Proposition 3.12) holds beyond the online learning setting. It should be stressed that, at least in normal-form games, without imposing computational or memory restrictions there are trivial online algorithms that guarantee even O(1) dynamic regret by first exploring the payoff tensors and then computing a Nash equilibrium [26]. We suspect that under the memory limitations imposed by Daskalakis al. [26] there could be unconditional information toommation-theorttie lower bounds, but that is left for future work.
samputational-haddeess
33

---

Proposition 3.12. Any polynomial-tin algorithm incurs Di=1 DReg." 2 CT for any polynomial T E N, even if = 2 and >> 0 an absolute constant, unless ETH for PPAD is false [73].
(T)
Proof. We will make use of the fact that computing Nash equilibrium in two-player (normal- form) games to a sufficiently small accuracy < = O(1) requires superpolynomial time, unless the exponential-tima hypothesis for PPAD fails [73]. Indeed, suppose that there exist polynomial-time algorithms that always guarantee that Σi=1 DReg,"
(T) < Ell for some polynomial E N, where := 2. Then, this implies that there exists time t E [T'] such that
(t)) max (f+t)) (t)) (20 u1
(4) + max (a)) (1t 222) - (x) 2
S E
1 (3,4) EX1
m ".EE
which in turn implies that (m]²)
(0) _ is an e-approximate Nash equilibrium. Further, such a time
t E [ can be identified in polynomial time since T' s poly([Ai),|Apg This concludes the proof.
We also note the following computational hardness result, which rests on the more standard complexity assumption that PPAD is not contained in P. As in Proposition 3.12, below we tacitly assume that the underlying algorithm is deterministic.
Proposition A.27. Unless PPAD S P, no polynomial-time algorithm guarantees Ex= DReg, (T) S
poly([A1), [Aa))T] wu for all T E N. where (0, 1] is an absolute constant, even if 2.
The proof follows directly from the PPAD-hardnen result of Chen et al. [19]. Of course, if we do not operate the online learning model, is computationally trivial to come up with algorithms that guarantee that one of the two players will have 0 dynamic regret by simply best responding to the strategy of the other player.
Finally, we provide the proof of Theorem 3.13, the detailed version of which is provided below.
Theorem A.28 (Detailed version of Theorem 3.13). Consider an n-player game such that ||V x; uz(z) - Va, "=(2')l2 < T.|l 2'112, where z,z' E X Xr for any player i [n]] Then, if all players employ OGD with learning rate 1j > holds that
1. ΣE K-DReg (T) O(K OLVVLLD2) if =
LVv
KWADY
2. K-DRog (T) O0030(K//1/) 1/4 1//2 for any i E [m], if=
Proof. First, applying Lemma A. subject the constraint that ΣT=1 ((a((et110)) gives that for any Player i E [n]].
(e+1,a) + z (((ttt))/ s K-1
D2s (2K 1) + mlu
K-DReg ( <
11
1
((+1) - (2)
2m
t=1
||
(t-1)
xx 10
(53)
4n
Further, by L-smoothness we have that
n
| (1t(+)) (2,1 V2, ((((())))) -2),)(z)))) >12
2
|
(1+1)
x 22.0113
for any tE E [T' 1], where (z) ................................ (1)) z(t) x== X, is the joint strategy profile time
t. Thus, summing (53) over all E [n]] and taking S 2T./ implies that Σ K-DReg (T) <
2 ΣR D3, + Em= |/ (2) 11, yielding the first part of the statement since D3 = E D2
24
where recall the notation Z X" Xr The second part follows directly from (53) using the stability property of DGD: | ((+1) x (211 O(1), for any time t [T-1] 1].
34

---

Remark A.29. is not hard to show that Item 2 above can be improved to (K) using clairvoyant mirror descent (CMD) [68], but under a stronger feedback model. In particular, using the (squared) Fuclidean regularizer it is direct to show (see [39, 651) that the dynamic regret of CMD is bounded solely by the first-order variation of the sequence of comparators, which suffices for this claim. open whether similar results can be obtained in the standard feedback model.
B Experimental examples
Finally, although the focus of this paper is theoretical, in this section we provide some illustrative experimental examples. In particular, Appendix B.1 contains experiments time-varying potential games, while Appendix B.2 focuses on time-varying (two-player) zero-sum games. For simplicity, will be assuming that each game is represented in normal form.
B.1 Time-varying potential games
Here we consider time-varying 2-player identical inttrresttt games. We point out that such games potential games (recall Definition A.23), and as such, they are indeed amenable to our theory in Section 3.3.
In our first experiment, we first sampled two matrices A, A.P. E Rdxxdy, where dN = dy = 1000. Then, we defined each payoff matrix A (O) == A (t-1) + P for 2 1, where A (0) = A. Here, > a parameter that controls the variation of the payoff matrices. In this varying setup, we let each player employ (online) GD with learning rate 77 0.1. The results obtained under different random initializations of matrices A and P are illustrated in Figure 1.
Next, we operate in the same time-varying setup but each player is now employing multiplicative weights update (MWU), instead of gradient descent, with r7 0.1. As shown Figure 2, while the cumulative equilibrium gap is much larger compared to using GD (Figure 1), the dynamics still appear to approaching equilibria, although our theory does not cover MWU. We suspect that theoretical results such as Theorem 3.7 should hold for MWU as well, but that has been left for future work.
In third experiment for identical-inese interest games, we again first sampled two matrices A,P Rdaxdy, where d, dy 1000. Then, we defined A = (t-1) cP for 2 1, where (0) = A. Here, 0 is the parameter intended capture the variation of the payoff matrices. The results obtained under different random initializations of and are illustrated in Figure 3. As an aside, it worth pointing out that this particular setting can be thought of game which the variation in the payoff matrices is controlled by another learning agent. In particular, our theoretical results could be helpful for characterizing the convergence properties of two-timescale learning algorithms, in which the deviation of the game is controlled by a player constrained to be updating its strategies with much smaller learning rate.
B.2 Time-varying zero-sum games
We next conduct experiments on time-varying bilinear saddle-point problems when players are employing OGD. Such problems were studied extensively earlier in Section 3.1 from theoretical standpoint.
First, we sampled two matrices A, A.P. E Bdaxdy, where d, = dy 10: here consider lower- dimensional payoff matrices compared to the experiments in Appendix B.1 for convenience in the graphical illustrations. Then, we defined each payoff matrix as A (4) = (t-1) + Pt-a for 2 1, where A (1) A. The results obtained under different random initializations are illustrated in Figure 4.
35

---

0.5
330.0
0.4
0.0
00
100
100
2000
30
1000
1.00
200
0.00
2.4
100%
0.0
300
150
200
50
1000
180
200
0.5
0.2
(Reg) 2 2y
Dolo
0.4
0.2
150
100)
1.50
200
100
1100
0.5
0.5
0.4
0.2
1.0
Iteration
(1)
Iteration (5)
Ieeaaionn (t)
The equilibrium gap and the players' regrets 2-player time-varying identical-interest games when both players are employing (online) with learning rate 7 == 0.1 for T 200 itcrations. Each row corresponds to a different random initialization of the matrices A, E Rd Xd,, which in turn induces different time-varying game. Further, each figure contains trajectories corresponding to three different values of a {0.1, 0.2, 0.5), but under the same initialization of A and P. As expected, smaller values generally increase the equilibrium gap since the variation of the games is more significant. Nevertheless, for all games we observe that the players are gradually approaching equilibria.
Figure 1:
36

---

YV (B0gt))e
2010
100
(RGm)
2000
100
0-
0
60
100
150
200
00
100
150
200
100
Rogg
2000
100
50
100
130
200
50
100
150
200
100
300
02
100
50
1000
150
300
50
100
150
200
40
100
Figure 2: The equilibrium gap and the players' regrets 2-player time-varying identical-interest games when both players are employing (online) GD with learning rate 7 = 0.1 for T = 200 iterations. Each row corresponds a different random initialization of the matrices A, A.P. E TR xd, which in turn induces different vire-ng game. Further, each figure contains trajectories corresponding to three different values of a E (0.1, 0.2, 0.5), but under the same initialization A and P. The MWU dynamics still appear to be approaching equilibria, although the cumulative gap is much larger compared to GD (Figure 1).
37

---

0.01
1.0
01.2
0.5
0.0
0.0
100
200
300
600
600
100
200
300
600
600
100
100
200
1.0
0.2
0.01
0.5
0.1
100
200
200
400
500
100
200
300
400
500
50
100
150
200
0.3
(009g)
0.01
130-10
0.1
100
0.001
0.01
0.2
TXCT
0.1
Eterotions
[tecations
[terations
The equilibrium gap and the players' regrets 2-player time-varying identical-interest games when both players employing (online) GD with learning / == 0.1 for 7 500 iterations. Each row corresponds to a different random initialization of the matrices A, P E 12 xdy, which in turn induces different time-vrrying game. Further, each figure contains trajectories from three different values of {0.1, 0.001]. but under the same initialization of A and P. As expected, larger values of e generally increase the equilibrium gap since the variation of the games is more significant. Yet, even for the larger value 0.1, the dynamics are still appear to be approaching Nash equilibria.
Figure 3:
38

---

20
(Bocl" (1)
20000
0,6
0.4
20
10000
100000
40
Bogs
2000
30
0.7
10-
2010
00.0
8000
1000
2010
600
800)
1000
2010
1000
8000
1000
30
0.8
0.6
20000
1.0
0.2
2000
100
0000
8000
1000
200
100
6000
800
1000
0
2010
100
0000
800
1000
2 (Bimm)
10000
dl 2
20
7500
10
0.2
2000
0.0
2011
400
000
800
1000
200
400
600
800
1000
200
400
000
800
1000
Figure 4: The equilibrium gap and players' regrets in 2-player time- varying zero-sum games when both players are employing OGD with lcarning rate 77 0.01 and T = 1000 iterations. Each row corresponds to a different random initialization of the matrices A, P gd, xd,, which in turn induces different varying game. Further, each figure contains trajectories from three different values a E (0.7, 1, 2), but under the same initialization of A and P. The OGD dynamics appear to be approaching equilibria, albeit with much slower rate compared to the ones observed earlier for potential games (Figure l).
39


Reviews:
[{"review_id": "XOV0NwQ5P9", "reviewer": "Reviewer_PhTp", "summary": "The paper studies optimistic gradient descent for time-varying games.  Authors prove convergence bounds for zero sum games involving the first order variation of approximate nash equilibrium, which can be significantly tigher than variation bounds involving exact nash equilibria and second order bounds in payoff matrices. The paper also includes refined convergence bounds involving second-order variation for strongly-convex-concave games.  The results also have implications for meta-learning, where games are repeated many times.\n\nThe authors also extend results to time-varying general-sum multiplayer games with correlated equilibria, extending exisiting meta-learning similarity measures to general sum games and proving new single-player regret bounds. Techniques are applied to static games, improving our understanding of dynamic regret.", "questions": "Typo 88: accelerates-> accelerated", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Nonstationarity is an important and challenging area of study for learning in games, and is under-explored.\n\nBounds involving approximate nash equilibrium variation can be significantly tighter than existing bounds involving variation in exact nash equilibria.\n\nThe results for general sum games solving two independent open problems.\n\nIdeas provide improved understanding of dynamic regret for static games, including both positive and negative result.\n\nThe paper is well written, including a variety of results while still providing technical exposition on insights behind the proofs and contextualizing the result.", "weaknesses": "Observation 3.11 requires two point feedback, so it's less clear this is a significant improvement.\n\nThe paper could probably be a bit more self contained.  The paper borrows ideas from [60], like a dynamic RVU bound but it is hard to follow without additional context.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for their feedback.\n\nWe will make sure to provide further background in order to make the paper more self-contained in the revised version. We also thank the reviewer for spotting a typo; we will fix it in the revised version. \n"}, {"review_id": "hvq0uzoLur", "reviewer": "Reviewer_PH29", "summary": "This paper studies learning dynamics in games that change over time. This is a similar setting to [60], but while [60] focuses on regret guarantees, this paper focuses on iterate convergence to NE.\n\nThe main result states that for bilinear zero-sum games, running optimistic OGD guarantees that,\n$$\n\\sum_{t=1}^T EqGap_t = O(V_{NE-\\epsilon}^T + V_A^T),\n$$\nwhere $EqGap_t$ is the NE gap (i.e., the difference between the player utility and best response), $V_{NE-\\epsilon}^T$ is the variation of $\\epsilon$-approximate NEs of the games $+\\epsilon T$ (in fact they allow different $\\epsilon$ for each $T$), and $V_A^T$ measures the variation of the game matrices. $V_{NE-\\epsilon}^T$ can be much smaller compared to the variation of the exact NEs.\n\nThe paper continues by providing variation-dependent bound for strongly convex games. Next, they provide a bound on the sum of NE gaps for general sum-potential games (which depends on some notion of variation of the potential function), as well as bound on the sum of CE gaps in general games. Finally, they present results for *dynamic* regret in static games.", "questions": "What is the difference between the sum NE gaps (Corollary 3.4) and dynamic regret (line 342)?\n\nSee additional questions in the Weaknesses part.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper provides a set of interesting results. These include,\n- Various results on the sum of NE gaps. Specifically, I find the notion of $V_{NE-\\epsilon}^T$ very elegant, and indeed, it seems like a much more reasonable notion for characterizing the complexity of time-varying-games instance.\n- Bounds on the dynamic regret in static games - even though this is a basic question, according to the authors these are the first results that show $\\sqrt{T}$ dynamic regret in games (they also show $\\log T$ dynamic regret under a stronger feedback model)\n", "weaknesses": "- The main text lacks proofs/proof sketches. So it is impossible to understand the main ideas and techniques, even at a high level, without diving into the full technical proofs in the appendix (+ it makes it hard to evaluate the technical contribution of the paper).\n\n- In several places, it is quite hard to follow the text. Specifically, section 1.1 is rather technical, given that it is part of the intro. In addition, the section on general games that starts in line 287 was not sufficiently clear to me. For example, the authors mention that *\"there exist matrices\n$A_1, . . . , A_n$, with each matrix $A_i$ depending solely on the utility of Player i...\"* but what are exactly these matrices represent? What does the value of the optimization problem in (3) represents? Why does *\"incorporating the 0 vector will be useful\"*? and why does there exist $\\mu^\\star$ that satisfy the condition in line 300?\n\n- Lack of comparison to previous work: what is the result of [30] and how is it compars to your result in \"meta-learning\"? How does Corollary 3.4(2) compares to the result in [60] (except for the difference between $V_{NE-\\epsilon}^T$ and $V_{NE}^T$)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for their feedback. \n\n*“The main text lacks proofs/proof sketches. So it is impossible to understand the main ideas and techniques, even at a high level, without diving into the full technical proofs in the appendix”*\n\nWe will make sure to provide high-level proof sketches in the main body, so that the main body is self-contained in the revised version. \n\n*“the section on general games that starts in line 287 was not sufficiently clear to me.”*\n\nWe will provide a more self-contained presentation regarding the derivation of the bilinear formulation of correlated equilibria in the revised version; a textbook treatment can be found, for example, in Chapter 12 in the book “Game Theory Basics” by Von Stengel. Below, we address the reviewer’s questions regarding the bilinear formulation.\n\nThis bilinear formulation represents a game between an additional player (namely, the mediator) and the set of players. Each player tries to optimally deviate from the mediator strategy, while the mediator is trying to find a strategy so that no player has an incentive to deviate, which is by definition a correlated equilibrium. So, each matrix $A_i$ encodes the deviation benefit of player $i$ (assuming that all other players are following the mediator's recommendation), and the value of the optimization problem (3) is the sum of the players’ deviation benefits. Notice that since a correlated equilibrium exists, there exists a mediator strategy $\\mu^\\star$ such that $(\\mu^\\star)^\\top A_i x_i \\leq 0$, for any player $i$. The same of course holds by allowing players to select strategies in conv$(X_i, 0)$ (since we just multiply by a nonnegative scalar). So, the bilinear formulation remains legitimate after taking the convex hull with $0$, and it proves that a $\\mu^\\star$ satisfying the condition of Line 300 indeed exists.\n\n*“Lack of comparison to previous work: what is the result of [30] and how is it compars to your result in \"meta-learning\"?”*\n\n\nCompared to the results in [30], we note that our guarantees depend on different similarity metrics, which are in general incomparable; yet, we remark that there are settings in which our similarity metric can be arbitrarily smaller than the one in [30], even in zero-sum games. Furthermore, for general-sum games, we obtain algorithm-independent similarity metrics, which was left open in that work. \n\nThe algorithms we employ are also different. In particular, unlike [30], our approach is essentially agnostic to the meta-learning in that we do not need to know the boundaries of each game. Instead, our meta-learning guarantees are byproducts of our results for time-varying games, which is a more general problem than meta-learning. \n\n\n*“How does Corollary 3.4(2) compares to the result in [60]”*\n\nFirst, the authors of [60] focus on regret minimization in time-varying games, while Corollary 3.4 provides guarantees of iterate-convergence to Nash equilibria. Those two problems are in general unrelated; for example, even in static games an algorithm can have vanishing regret but at the same time all iterates can have a large Nash equilibrium gap. Moreover, all of our results concern the behavior of optimistic mirror descent (OMD), while the algorithm in [60] is more complicated. Given the tremendous amount of interest OMD has received in recent years, understanding its behavior is a question of independent interest. Finally, leveraging the connection we make with the MVI property (Remark A.5), our Corollary 3.4 directly applies to time-varying variational inequality problems as well, such as time-varying zero-sum polymatrix games, not just time-varying bilinear saddle-point problems.\n\n\n*“What is the difference between the sum NE gaps (Corollary 3.4) and dynamic regret (line 342)?”*\n\nThose are indeed the same; as such, notice that Line 342 is in fact a direct consequence of Corollary 3.4.\n"}, {"review_id": "wmKc9beim3", "reviewer": "Reviewer_jL2o", "summary": "In this work the authors consider no-regret learning in multiagent games where the underlying game varies across different rounds. They study several classes of games and various learning algorithms that the agents can use. Naturally, the results they obtained are parametrized by variation measures of the underlying game that the agents participate in. To be more precise:\n* For time varying zero-sum games, they focus on the setting where both of the agents are using optimistic gradient descent (OGD),  which is a variant of gradient descent that puts a bias on more recent rounds of the game. Interestingly, they show that almost all iterates of OGD are approximate Nash equilibria provided that some variation measures related to changes in the set of approximate equilibria of the games and the underlying payoff matrices are $o(T)$.\n* Then, they consider sequences of games where the games in each round are strongly convex-concave. For this class of games, they are able to show a similar result as above, but under weaker variation conditions for the underlying sequence of games.\n* Finally, they consider time-varying general-sum games. Naturally, since Nash equilibria are not tractable in this setting, they consider convergence to correlated equilibria. They prove similar results as above, but now the variation measure they use is related to the set of correlated equilibria of the game.\nTheir results have implications to other settings as well such as meta-learning and dynamic regret guarantees in static games.", "questions": "* What are the technical challenges to generalize the results to the bandit or some other partial feedback model?\n* Would there be any benefit if you considered a variational measure wrt approximate correlated equilibria in general sum games instead of exact correlated equilibria?\n* To what extent do you think that the results are tight?\n* Do the results for two-player zero-sum games generalize to multiagent zero-sum polymatrix games? I don't see any inherent obstacles to do that using your approach, but I might be missing something.\n* Another class of general sum games that is tractable in the single-shot setting are games in which the underlying matrices are rank-1. Is there any hope to obtain similar results for this class of games? I would imagine that the techniques would need to be substantially different from your approach.\n* In Theorem 3.3 (and similar results) if the parameter $L$ is not known does the usual guess-and-double trick work to get the bound?", "limitations": "n/a", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* The paper studies a very natural problem and provides strong results under various settings of interest, which also have implications in other settings, as I mentioned in the summary.\n* For the most part, the paper is easy to follow and the authors have done a good job placing their work in the literature. \n* The authors are not trying to oversell the proof technique, which is heavily inspired by prior works, but uses some natural and clever modifications. For example, instead of letting the variation measure to depend on variations of the set of exact Nash equilibria which would make the problem very difficult to handle since this set is very sensitive to any changes of the payoff matrices, the authors consider variations of the set of approximate Nash equilibria, which behaves much nicer. Since the results are strong and general, I don't think that the authors should be penalized for the fact that the proof techniques are not very novel.\n", "weaknesses": "* Some parts of the paper might be a bit hard to follow for non-experts, especially in Section 1.1. For example, the MVI property and the RVU bound were not defined. I think the authors could make the transition to this section a bit smoother, although I understand that the space limitations are making it trickier.\n* Even though the variation measures the authors use are intuitive and it makes sense that the regret should scale with these quantities, there are no lower bounds to show the extent to which these results are optimal.\n\n\nSome minor comments:\n* In Proposition 3.10, it might be useful to state which dynamic benchmark you consider for their dynamic regret bound.\n* With this bibliography style it is a bit hard to keep track of the references, although I understand that it saves some valuable space.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for their feedback. \n\n*“Some parts of the paper might be a bit hard to follow for non-experts, especially in Section 1.1.”*\n\nWe will make sure to introduce further background in the revised version of the introduction.\n\n*“What are the technical challenges to generalize the results to the bandit or some other partial feedback model?”*\n\nAn important challenge beyond the full-feedback setting is that it is not known whether RVU-type properties hold, which is crucial for our analysis; see, for example, the paper “More Adaptive Algorithms for Adversarial Bandits” by Luo and Wei. So it seems that an entirely different approach is needed beyond the full-feedback setting.\n\n*“Would there be any benefit if you considered a variational measure wrt approximate correlated equilibria in general sum games instead of exact correlated equilibria?”*\n\nIndeed, Theorem 3.9 can be more generally expressed with respect to approximate correlated equilibria (as Theorem 3.3). In light of Proposition 3.2, this can lead to a substantial improvement in the convergence bounds; we will point this out in the revised version.\n\n*“To what extent do you think that the results are tight?”*\n\nWe believe that the dependence on the variation measure $\\mathcal{V}^{(T)}_{\\epsilon-NE}$ is unavoidable for any online learning algorithm, but it is less clear whether the dependence on $\\mathcal{V}_A^{(T)}$ is necessary; closing the upper and lower bounds here requires further work.\n\n*“Do the results for two-player zero-sum games generalize to multiagent zero-sum polymatrix games? I don't see any inherent obstacles to do that using your approach, but I might be missing something.”*\n\nIndeed, as we point out in Remark A.5, Property 3.1 can be generalized to any time-varying variational inequality problem that satisfies the MVI property, which includes zero-sum polymatrix games. As such, our analysis readily carries over; we will point this out in the revised version. \n\n*“Another class of general sum games that is tractable in the single-shot setting are games in which the underlying matrices are rank-1. Is there any hope to obtain similar results for this class of games? I would imagine that the techniques would need to be substantially different from your approach.”*\n\nThis is an interesting question. We believe that the MVI property no longer holds when the sum of the matrices is only known to be rank-1. So we agree that it seems to require very different techniques.\n\n*“In Theorem 3.3 (and similar results) if the parameter $L$  is not known does the usual guess-and-double trick work to get the bound?”*\n\nDepending on the normalization assumptions that we make, $L$ can be upper bounded by a parameter that depends on the number of actions of each player, and it is a mild assumption that this is known to the players. Alternatively, one could also use the doubling trick, as the reviewer suggested. \n"}, {"review_id": "MG0n51FGZ6", "reviewer": "Reviewer_3wR1", "summary": "This paper considers the problem of online learning in time-varying games under different setups. Specifically, the authors consider the case where all the players apply optimistic gradient descent (OGD) algorithm with a certain choice of learning rate. The main results that in the two-player bilinear game setup, the sum of squared duality gap is bounded by $O(1+V_{\\epsilon-NE}+V_A)$, recovering the best-known result in the stationary game setup. This result is based on the bounded second-order path length of the learning dynamic and the important observation that sum of dynamic regret with respect to (approximated) Nash is (almost) non-negative. Next, they extend this result to the strongly convex-concave game with multiple steps and obtain similar duality gap guarantees. The author also consider the potential game and general-sum game setup with guarantees on the duality gap and CEgap bound respectively. Experiments are also done to support their theoretical results. ", "questions": "- As mentioned in the above section, can the authors explain more in detail on the main technical difficulties and challenges compared to the analysis shown in [60]. \n- In Property 3.1, the authors argue that this extends the exact NE path-length in [60] to the approximated NE path-length. In [60], they also provide a bound with respect to W_T, which is the variance of the game matrix. Can the authors explain more on the comparison between the epsilon-NE path-length and W_T? Is there a case where both the exact NE path-length and the W_T are large but the epsilon-NE path-length is very small?\n", "limitations": "See Weakness section.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The problem considered in this paper is important and the authors show that the classic OGD algorithm achieves desirable average duality-gap and other equilibrium-related gap bound with provable guarantees.\n- The authors also do experiments on time-varying potential games and time-varying zero-sum games to verify their obtained NEgap bound.", "weaknesses": "The main concern is the novelty of this paper. Specifically, this paper shares similarity to the results in [60] in many perspectives, although the authors explain in many places in the paper that how their results are different from [60].\n- One of the main lemma Lemma A.1 is the same as the DRVU property shown in [60].\n- Property A.3 is very similar to Eq.(32) shown in [60].\n- Example shown in Proposition 3.2 is almost the same as the example shown in Appendix C, case 2 in [60].\n- From the technical perspective, I feel like the analysis is very similar to the one shown in [60]. While [60] does not consider the approximated NE path-length, it is not hard to extend their analysis to the approximated NE path-length by replacing P_T with \\epsilon-NE path-length +T\\epsilon. Also, the boundedness of the second-order dynamic is also shown in Lemma 16/18 in [60].\n- In addition, as mentioned by the authors, there are parameter-tuning issues in achieving better individual regret guarantees in bilinear and  strongly convex-concave games, which is also handled by the meta-base structure proposed in [60].\n\nThe authors also derive results for general-sum games and potential games. Given Property 3.8 that the sum of regret with respect to CE is positive, it seems that the average CEgap bound is also not very hard to obtain given the bounded second-order dynamic of OGD.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for their constructive feedback. Below, we stress the key differences between our results and the ones in [60].\n\nStarting from Section 3.1, we indeed build on a number of ingredients from [60], as we carefully acknowledge throughout the paper; this includes the dynamic RVU bound (Lemma A.1) and using second-order path lengths, as the reviewer points out. We stress, however, that using RVU-type bounds and second-order path lengths is very standard in this line of work, so we do not believe that those similarities weaken our contribution. Indeed, we provide a number new insights that are of interest, leading to our main result in Theorem 3.3 that is different from the results in [60] in many aspects. First, we use a variation measure depending on an approximate sequence of NE; note that while the example in Proposition 3.2 is similar to that in Appendix C of [60], as the reviewer points out, it serves a different purpose in our context. Furthermore, we connect nonnegativity of dynamic regret with the MVI property from variational inequalities. This allows extensions to settings such as polymatrix zero-sum games and convex-concave games; given the tremendous interest such settings have received, we believe that those extensions are important. Our results are also based on a simpler algorithm: simply run optimistic gradient descent (OGD)—or variants of optimistic mirror descent—with a time-invariant (constant) learning rate. We believe that this has an independent interest given how well-studied those algorithms are in the static setting, and it is also worth noting that several prior papers have motivated using a constant learning rate—which has not been done in this context. In contrast, the algorithm of [60] has further layers of complications, which are of course there to handle issues such as parameter tuning; while such issues are crucial in the setup of [60] in order to minimzie regret, they are not present in our setting precisely because our focus is different. Namely, our focus (in Section 3.1) is to characterize the equilibrium gap of OGD.\n\nWe also want to highlight that our results and our technical approach beyond Section 3.1, namely in Sections 3.2-3.4, are in general different from those in [60]; this includes time-varying potential games, general-sum games, and strongly convex-concave settings. Each of those settings introduces their own challenges that are in general different from the ones encountered for bilinear saddle-point problems. \n\nSo, despite a number of similarities with [60] that we carefully point out throughout the paper, most of those similarities are technical tools used consistently in this line of work (such as RVU-type properties and second-order path lengths), and we do not believe that they weaken our contribution. We believe that we provide a number of new insights beyond what was known in prior work, and our results are overall complementary with [60].\n\nWe finally answer the reviewer's following question.\n\n*“Is there a case where both the exact NE path-length and the $W_T$ are large but the epsilon-NE path-length is very small?”*\n\nYes. Consider the sequence of matrices $A^{(1)}, \\dots, A^{(T)}$ provided in Proposition 3.2. Now let us instead take the sequence $A^{(1)} + c^{(1)} I, \\dots, A^{(T)} + c^{(T)} I$, where $c^{(1)}, \\dots, c^{(T)} \\in \\mathbb{R}$ and $I$ is the all-ones matrix. It is clear that the variation measures that depend on the Nash equilibrium are exactly the same no matter how $c^{(1)}, \\dots, c^{(T)}$ are chosen. On the other hand, by suitably selecting the sequence of $c^{(1)}, \\dots, c^{(T)}$ we can make $W_T$ to be arbitrarily large. This is a quite trivial example, but demonstrates the volatility of $W_T$ as a variation measure since it is not robust to transformations that retain (approximate) Nash equilibria.\n"}]

Author rebuttal:

Meta-review: A paper with overall nice results on learning eps-Nash, and in my view, a good contribution to the growing no-regret learning in games literature that has been receiving increasing attention. In the accepted camera-ready version, please incorporate one of the reviewers' comments in the introduction by clearly describing the diff with respect to [60] and [Anagnostides et al., 2022]: what set of techniques are combined to lead to what new results that were previously unknown.
Decision: Accept (poster)