Boosting Perturbed Gradient Ascent for Last-Iterate Convergence in Games
Authors: Kenshi Abe
Mitsuki Sakamoto
Kaito Ariu
Atsushi Iwasaki
Venue: ICLR 2025 Poster (2025)
Keywords: Last-Iterate Convergence
Learning in Games
Noisy Feedback
Primary area: optimization
TL;DR: This paper proposes a novel payoff-perturbed Gradient Ascent that achieves fast last-iterate convergence rates.

Abstract: This paper presents a payoff perturbation technique, introducing a strong convexity to players' payoff functions in games. This technique is specifically designed for first-order methods to achieve last-iterate convergence in games where the gradient of the payoff functions is monotone in the strategy profile space, potentially containing additive noise. Although perturbation is known to facilitate the convergence of learning algorithms, the magnitude of perturbation requires careful adjustment to ensure last-iterate convergence. Previous studies have proposed a scheme in which the magnitude is determined by the distance from a periodically re-initialized anchoring or reference strategy. Building upon this, we propose Gradient Ascent with Boosting Payoff Perturbation, which incorporates a novel perturbation into the underlying payoff function, maintaining the periodically re-initializing anchoring strategy scheme. This innovation empowers us to provide faster last-iterate convergence rates against the existing payoff perturbed algorithms, even in the presence of additive noise.

Published as a conference paper at ICLR 2025
BOOSTING PERTURBED GRADIENT ASCENT FOR LAST-ITERATE CONVERGENCE IN GAMES
Kenshi Abe 1. Mitsuki Sakamoto'
Kaito Ariu' Atsushi Iwasaki
'CyberAgent
The University of Poccro-Commmuicatiinn
{abe kenshi, sakamoto mit suki, kaito ariu)eyberageeettt atsushi. iwasak euec.ac.
ABSTRACT
This paper presents a payoff perturbation technique, introducing strong convex- ity to players' payoff functions in games. This technique is specifically designed for first-order methods to achieve last-iterate convergence games where the gra- dient of the payoff functions is monotone in the strategy profile space, potentially containing additive noise. Although perturbation is known to facilitate the con- vergence of learning algorithms, the magnitude of perturbation requires careful adjustment to ensure last-iterate convergence. Previous studies have proposed a scheme in which the magnitude is determined by the distance from periodi- cally re-initialized anchoring or reference strategy. Building upon this, we pro- pose Gradient Ascent with Boosting Payoff Perturbation, which incorporates a novel perturbation into the underlying payoff' function, maintaining the periodi- cally re-initializing anchoring strategy scheme. This innovation empowers us provide faster last-iterate convergence rates against the existing payoff perturbed algorithms, even the presence of additive noise.
INTRODUCTION
This study considers online learning in monotone games, where the gradient of the payoff function is monotone in the strategy profile space. Monotone games encompassed diverse well-studied games as special instances, such concave-convex games, zero-sum polymatrix games (Cai & Daskalakis, 2011; Cai et al., 2016), X-cocoercive games (Linn al., 2020), and Cournot competition (Monderer & Shapley, 1996). Due to their wide-ranging applications, there has been growing interest in devel- oping learning algorithms to compute Nash equilibria monotone games.
Typical learning algorithms such as Gradient Ascent (Zinkevich, 2003) and Multiplicative Weights Update (Bailey & Piliouras, 2018) have been extensively studied and shown to converge to equilibria in wverage-iterate sense, which is termed average-iterate iteraae convergence. However, averaging the strategies can be undesirable because can lead to additional memory or computational costs in the context of training Generative Adversarial Networks (Goodfellow et al., 2014) and preference- based fine-tuning of large language models (Munos et al., 2024; Swamy et al., 2024). In contrast, last-iterate convergence, in which the updated strategy profile itself converges a Nash equilibrium, has emerged as stronger notion than average-iterate convergence.
Payoff-perturbed algorithms have recently been regaining attention in this context (Sokota et al., 2023; Liu et al., 2023). Payoff perturbation, a classical technique referenced in Facchinei & Pang (2003), introduces a strongly convex penalty to the players' payoff functions to stabilize learning. This leads to convergence toward approximate equilibria, not only in the full feedback setting where the perfect gradient vector of the payoff function can be used to update strategies, but also in the noisy feedback setting where the gradient vector is contaminated by noise.
However, to ensure convergence toward Nash equilibrium of the underlying game, the magnitude of perturbation requires careful adjustment. As remedy, it is adjusted by the distance from an anchoring or reference strategy. Koshal et al. (2010) and Tatarenko & Kamgarpour (2019) simply decay the magnitude in each iteration, and their methods asymptotically converge, since the per- turbed function gradually loses strong convexity. In response to this, recent studies (Perolat et al., 2021; Abe al., 2023; 2024) re-initialize the anchoring strategies periodically, in predefined

---

Published as a conference paper at ICLR 2025
interval, so that they keep the perturbed function strongly convex and achieve non-asymptotic con- vergence.
We should also mention the optimistic family of learning algorithms, which incorporates recency bias and exhibits last-iterate convergence (Daskalakis et al., 2018; Daskalakis & Panageas, 2019; Mertikopoulos et al., 2019; Wei et al., 2021). Unfortunately, the property has mainly been proven in the full feedback setting. Although it might empirically work with noisy feedback, the convergence slower, as demonstrated in Section 6. The fast convergence in the noisy feedback setting is another algorithms have been gaining renewed interest.
reason why
The most recent payoff-pe perturbed algorithm, Adaptively Perturbed Mirror Descent (APMD) (Abe al., 2024), achieves O11/ (T) and Ó(1/T to) last-iterate convergence rates in the full/noisy feed- back setting, respectively. The motivation of this study lies in improving these convergence rates. We propose an elegant one-line modification of APMD, which effectively accelerates convergence. In fact, we just add the difference between the current anchoring strategy and the initial anchoring strategy to the payoff perturbation function in APMD.
Our contributions are manifold. Firstly. we propose novel peyoff-petturbed learning algorithm named Gradient Ascent with Boosting Payoff Perturbation" (GABP). This method incorporates a unique perturbation payoff function, enabling it to achieve fast convergence. Subsequently, we prove that GABP exhibits accelerated (1/TT) and O(1/T)) last-iterate convergence rates to Nash equilibrium with full and noisy feedback, respectively' To derive these rates, we utilize the concept of the potential function used in Cai & Zheng (2023). Specifically, the potential function employ is customized for handling noisy feedback. We further show that each player's 's individual regret is most O ((In 2)) in the full feedback setting, provided all players play according to GABP. Finally, through our experiments, we demonstrate the competitive or superior performance of GABP over the Optimistic Gradient algorithm (Daskalakis et al., 2018; Wei al., 2021), the Accelerated Optimistic Gradient algorithm (Cai & Zheng, 2023), and APMD in concave-convex games, irrespective of the presence of noise.
PRELIMINARIES
Monotone games. In this study, we focus continuous multi-player game, which is denoted as ([N], (X))EIN); (1))se[N))- [N] = (1,2, NN denotes the set of N players. Each player i E [N] chooses a strategy Ty from d,-dimensional compact convex strategy space X, and we write X' [hEI X. Each player aims to maximize her payoff function v X R, which differentiable on X. We denote x_, II I X2 as the strategies of all players except player i, and x = (TT)SEIN) E X as the strategy profile. This paper particularly studies learning in smooth monotone games, where the gradient operator V(-) (V.,", (:)()E[( of the payoff functions is monotone: YT, T' E X.
(+(=- - ). n') 00
and L-Lipschitz for L > O,
- V(=')l || S T. || 1|
where || denotes the no-mmmm.
Many common and well-studied games, such as concave-convex games, zero-sum polymatrix games (Cai et al., 2016), X-cocoercive games (Lin et al., 2020), and Cournot competition (Monderer & Shapley, 1996), are included in the class of monotone games.
Example 2.1 (Concave-convex games). Consider a game defined by ((1,2), (Ki, (v, -))), where e : X x X2 IR is the payoff function. In this game, player 1 wishes to maximize v, while player 2 aims to minimize v. If is concave in я E X1 and convex in T2 E X2 the game is called concave-convex game or minimax optimization problem, and it is not hard to that this game is a special case of monotone games.
Wee use Ô to denote a Landau notation that disregards polylogarithmic factor. 2 implementation boost in www-ppertonn perrurbedeedeee ga For detailed comparison of our rates with other works, please refer Table 3 in Appendix F.2.
our method is available at https: //gi com/ wwwptttwww..c.....teeeeeeeeottee AgentA 1 liab/
2

---

Published as a conference paper at ICLR 2025
Example 2.2 (Cournot Competition). Consider Cournot competition model with linear price function. There are N firms in competition, and each independently and simultaneously chooses a quantity π; E X, = [0, C,] to produce certain goods. where C₁ is constant greater than O. The price of the goods is determined by a linear function P(T) a - LieNN] Ti where a and b are constants greater than O. The payoff' for each firm i is calculated as the total revenue from producing Ty units of the goods, minus the associated production cost, i.e., ( TT TTP(m) C,TT This game has been shown to satisfy the property of monotone games as defined in Eq. (1) (Bravo et al., 2018).
Nash equilibrium and gap function. A Nash equilibrium (Nash, 1951) a widely used solution concept for game, which is strategy profile where player can gain by changing her own strategy. Formally, a strategy profile x² E is called a Nash equilibrium, and only if π satisfies the following condition:
Vi E [N]. VT, E X,, U/ U2(TT, (1;) 2 U/ (T m-))
We define the set of all Nash equilibria to be II.. It has been shown that there exists at least one Nash equilibrium (Debreu, 1952) for any smooth monotone games.
To quantify the proximity to Nash equilibrium for given strategy profile E X, we use the gap function, which is defined as:
GAP(T): == max (V(T), x) #Ex
Additionally, we use another measure of proximity to Nash equilibrium, referred to the tangent residual. This measure is defined as:
fan (T) = min ( + aal,, xENx(F)
II R4 Ex (a:, ग.. - n,) S 0, Va' E X I is the normal cone at π E X. It is easy to see that GAP(z)) 2 (resp. (T) 2 0) for any π E X. and the equality holds if and only if is Nash equilibrium. Defining D s'p,,x'ex || x'll the diameter of X. the gap function for any given strategy profile π E X' is upper bounded by its tangent residual:
where (T) = {(as)EeNN) E
Lemma 2.3 (Lemma 2 of Cai et al. (2022a)). For any π E X, we have:
GAP(T) S D tan (T)).
The gap function and the tangent residual are standard measures of proximity to Nash equilibrium; e.g., it has been used in Cai & Zheng (2023); Abe et al. (2024).
Problem setting. This study focuses on the online learning setting in which the following process repeats from iterations t = 1 to T: (i) Each player i E [N]] chooses her strategy xf E X, based on previously observed feedback; (ii) Each player i receives the (noisy) gradient vector R,,,,, (T²) as feedback. This study examines two feedback models: full feedback and noisy feedback. In the full feedback setting, each player observes the perfect gradient vector xx,x((T') V,, (TT)). In the noisy feedback setting, each player's gradient feedback V,, (x(x)) contaminated by an additive noise vector t,. i.c., vx, (T²) V,, (TT') + c, where & E Rd,, Throughout the paper, we assume that ş is the zero-mean and bounded-varian noise vector at each iteration t.
learning algorithms. To facilitate the convergence in the online learning set- ting. recent studies have utilized a payoff perturbation technique, where payoff functions are per- turbed by strongly convex functions (Sokota et al., 2023; Liu et al.. 2023; Abe et al., 2022). However, while the addition of these strongly convex functions leads learning algorithms to converge tionary point, this stationary point may be significantly distant from a Nash equilibrium. Therefore, the magnitude of perturbation requires careful adjustment. Perolat et al. (2021); Abe et al. (2023; 2024) have introduced scheme in which the magnitude is determined by the distance (or divergence function) from an anchoring strategy o,. which is periodically re- re-intiaalized Specifically. Adaptively Perturbed Mirror Descent (APMD) (Abe et al., 2024) perturbs each player's 's payoff function by strongly convex divergence function G(T,, o.)) X, x X, + [0, oo), where the anchoring strategy a, is periodically replaced by the current strategy n/ every predefined iterations T.-
sta-
3

---

Published as a conference paper at ICLR 2025
Algorithm GABP for player i.
Require: Learning rates 120 perturbation strength μ4, update interval To, initial strategy m!!
1: k - 1, T +
2: af f
3: for 1,, do
4: Receive the gradient feedback v,,";(TT))
5: Update the strategy by
[+1 arg max ZER:
71 V (.
o -
/ ( - of) x
| x..
k
2
6:
T T ++
7:
if - then
8:
h: k +1 T 0
9:
of + m
10: end if
11: end for
Let denote the number of updates of a; up to iteration t as k(t), and the anchoring strategy after k(() updates as a;
k(t)_ Since o; overwritten every Ta iterations, we can write k(t) = [(|
1)/T,| + 1 and of k(t) T (k(t))11))+ Except for the payoff perturbation and the update of the anchoring strategy, APMD updates each player i's strategy in the same way as standard Mirror Descent algorithms:
arg max The (()))(()) NV,, N G (M Dela, m;)
n
=EX;
where 7/2 the learning rate iteration i, μ (0, oo) is the perturbation strength, and (T,, m() (T;)) - ((m()) - (Vu((T)) ग. T() is the Bregman divergence associated with strictly convex function &b X + R. When both G and Du is set the squared (i-distance, this algorithm can be equivalently written as:
(1 (x) .x) - T!'
arg max T/ TEX:
We refer to this version of APMD as Adaptively Perturbed Gradient Ascent (APGA). Abe et al. (2024) have shown that APGA exhibits the convergence rates of ((1VVT) and Ó(1/T' with full and noisy feedback, respectively.
3 GRADIENT ASCENT WITH BOOSTING PAYOFF PERTURBATION
This section proposes novel sayoff-perturbed learning algorithm, Gradient Ascent with Boosting Payoff Perturbation (GABP). The pseudo-code of GABP outlined Algorithm At each iter- ation E [T). GABP receives the gradient feedback V (T(T)), and updates each player's strategy by the following update rule:
1)t (Vm
A(1)) o1 d
|| x x/ll3 }
n
.+1 arg max ZEXt
k(t) +1 11 (xt
0 b(t)) x
(3)
k(t) 0 is overwritten every T~ iterations, and thus a, is define a; x;
A(0
To (x(e)))) 1)+1 The term
(*) in Eq. (3) is our proposed additional perturbation term. shrinks as k(t), the number updates 1(0) of a increases.

---

Published as a conference paper at ICLR 2025
For more intuitive explanation of the proposed perturbation term, we present the following update rule, which is equivalent to Eq. (3):
(TL (VaC((TT) - k(t) k(r) k(t) -1
to
+
arg max The
x
=EA;
According this formula, is evident that GABP perturbs the gradient vector V ( so that नं
approaches k(t)) instead of o; ((tt), This gradual evolution of the anchoring strategy in GABP,
k(0)+1
compared to d; k(()) itself, is anticipated to contribute to the stabilization of the learning dynamics. There is a tradeoff between the shrinking speed of the term (*) and the stabilizing impact on the last- iterate convergence rate of GABP. The shrinking speed of 1/(k(t)++]) + achieves a faster convergence rate, and we believe that this represents the optimal balance for this trade-off. We remark that the term (+) bears resemblance to the update rule of the Accelerated Optimistic Gradient (AOG) algorithm (Cai & Zheng, 2023). However, AOG differs in the sense that it actually modifies the proximal point in gradient ascent, instead of perturbing the gradient vector. A detailed comparison discussed in Appendix F.I.
4 LAST-ITERATE CONVERGENCE RATES
This section provides the last-iterate convergence rates of GABP. Specifically, we derive Ö(L/T) and D(1/Tt) rates for the full/noisy feedback setting, respectively.
4.1 FULL FEEDBACK SETTING
First, we demonstrate the last-iterate convergence rate of GABP with full feedback where each player receives the perfect gradient vector as feedback at each iteration f, i.e., V (,T') = Vn, (r("). Theorem 4.1 shows that the last-iterate strategy profile x² updated by GABP converges to a Nash equilibrium with an (1/TT) rate in the full feedback setting.
Theorem 4.1. If we use the constant learning rate T}: - 1] (0, (TFpA)) and the constant perturba-
tion strength μ >> 0, and sei T6 = e max(1, ((T for some constant e 2 1, then the strutegy In(1+np)) n² updated by GABP satisfies for any t [T]:
17cD² 6 6lm3(+1))
+1)
GAP( SD pa S
In(1+nps)
(1
1 nL
This rate competitive compared to the previous state-of-the-art rate of OII/T) (Yoon & Ryu, 2021: Cai & Zheng, 2023). Note that the rate in Theorem 4.1 holds for any fixed μ > 0.
4.2 NOISY FEEDBACK SETTING
Next, we establish the last-iterate convergence rate in the noisy feedback setting, where each player observes noisy gradient vector contaminated by an additive noise vector & E Rd:: V (T²') = V,,"(()) ) + ç.. We assume that the noisy vector e is zero-mean and its variance is bounded. Formally, defining the sigma-algebra generated by the history of the observations as F. = (7,,)(("))))))))) (V (f',,((""")))) )EEMM)) Vt 2 1, the noisy vector & is assumed to satisfy the following conditions:
Assumption 4.2. et satisfies the following properties for all 1 and i E [N]: (a) Zero-mean: [ (0, ,0) (b) Bounded variance: [B[[) < C with some constant C' >
Assumption 4.2 is standard in online learning in games with noisy feedback (Mertikopoulos & Zhou, 2019; Hsieh et al., 2019; Abe et al., 2024) and stochastic optimization (Nemirovski et al., 2009; Nedić & Lee, 2014). Under Assumption 4.2 and decreasing learning rate sequence n)s obtain faster last convergence rate Õ / than Õ (T of APGA (Abe al., 2024).
5

---

Published as a conference paper at ICLR 2025
Theorem 4.3. Let K 2.0
34 +8L2
Suppose that Assumption 4.2 holds and V( I
2
for any π E X. We also assume that To is set to satisfy To c max for some constant c 2 1. Ifwe use the constant perturbation strength >> 0 and the decreasing learning rate sequence ?) k(t-Io ((--To(k()) (k()))(()))))) 1))+20 then the strategy xt" TT satisfies:
In T 7
[AP(
4.3 PROOF SKETCH OF THEOREMS 4. AND 4.3
This section outlines the sketch of the proofs for Theorems 4.1 and 4.3. The complete proofs are placed in Appendix B and C.
We define the stationary point TH,(() which satisfies the following condition: Vi E [N].
k(t) arg max aEX,
14
#(s)
2
where of k(tja +o]
+o!
The primary technical challenge in deriving the last-iterate convergence
k(t)+1
rates lies in the construction of the following potential function pk((), which can be utilized in the proofs for both full and noisy feedback settings:
-212 (0h(0) -( xu.((t)-1 -
pk(1) = k()((()))))))) +1)
2
Specifically, demonstrate that this potential function is approximately non-increasing regard- less of the presence of noise. Although the potential function pR(1) is inspired by in Cai Zheng (2023), their potential function contains the term v/² EiE[N] [Vo((=') (
which could have a high value in the noisy feedback setting even if n² = holds*. This com- plicates providing a last-iterate convergence result for the noisy feedback setting via their potential function. In contrast, our potential function pk(() does not include the term dependent on (r,(*'). As result, we can provide the last-iterate convergence rates even for the noisy feedback setting.
Furthermore, compared to Abe al. (2024), our potential function pk(() allows to improve the convergence rate with respect to the distance between the k(t))th anchoring strategy profile k(t)
and the corresponding stationary point (²)((() i.e., || ['t)(t) - (+) | In fact, our analysis enhances
this rate from O(1/ kk(t) (1/kktt)) This improvement leads to faster last-iterate convergence results, further demonstrating the effectiveness of our approach.
(1) Potential function for bounding the distance between z(,((t) and k(t) As mentioned above, our main technical contribution is proving that pk(t) is approximately non-increasing (as shown in Lemma B.3). That is, we have for any 2 I such that k(t) 2:
pk(1+1 < pk(t) (k(t) + 1)2. (00
b(t++
||
(4)
By telescoping of Eq. (4) and the first-order optimality condition for nH)k(1), we can derive the following upper bound on the distance between quak and (kt)
k(x)
(k(t) + ()(()) + 2) mak000 - g4/0 00 + (N(1) + 1)2
Σ (1] - 11)
2
Applying the definition of (A()) and Cauchy- Schwarz inequality to this inequality, we obtain:
(nnk(t) =000| ([[ (0( ol (k(1)
k(t)
(1H() 1)2
o1| - (5)
k(1) +1
*The comparison of the potential function of Cai & Zheng (2023) with he found in Appendix F.1.

---

Published as a conference paper at ICLR 2025
Note that the non-increasing property of our potential function, described in Eq. (4), holds even in the noisy feedback setting. This implies that a similar proof technique for deriving Eq. (5) can be utilized to provide last-iterate convergence results both in full and noisy feedback settings.
(2) Convergence rate of ( to the stationary point nH.k(t) Leveraging the strong convexity of the perturbation payoff function, 5 ş|| a, k(t) 11? we show that x' converges to T(.((t) expo- nentially fast in the full feedback setting (as shown in Lemma B. Specifically, we have for any t 1:
1)7,
T - π x'11|1
(6)
1 + Tpp
3lT+(111) in the full feedback setting, we can easily By using Eq. (6) and the assumption that Tg 2 In (n(1+mp))
show that || - -o'+||| = || - S
(k(() 3) for any S k(t). Hence, from Eq. (5), we can derive the following convergence rate of the distance between (T(,((()) and (a(() with respect to k(t) (as shown in Lemma B.2):
( -ok0) 2 OLL/K())
(3) Decomposition of the gap function of the last-iterate strategy profile T++1 Let us define K == (T/Ta] From Cauchy-Schwarz inequality and Lemma 2.3, we can decompose the gap function GAP +1 as follows:
GAP(T S GAP(T" (1|TH. - x T+111) || [T(h + all O
SD. min
(1| T[ x I1])
(TM.()
From the first-order optimality condition for T..K we can see that ((T** - M(T - gk) E Nx (m=.K). Thus, from the triangle inequality and T-ssmotthness of the gradient operator in Eq. (2), the gap function GAP(x?+3 can be bounded as:
GAP(TT+1) s O(I/K)+ +
+ (|]T - xx1l) + O -
- - T+1
(8)
(4) Putting it all together: last-iterate convergence rate of TT By combining Eq. (6), Eq. (7), and Eq. (8). it holds that GAP(x*+1) < O(I/K) in the full feedback setting. Hence, given K = [T/ToJ. we can deduce that GAP( S OTT,/T). Finally, taking T, O (T), we obtain the upper bound on the gap function for the full feedback setting: GAP( (++1 < O(In T/T). Note that using a similar proof technique, we can also derive an upper bound on the tangent residual for the full feedback setting.
In the context of the noisy feedback setting, we achieve the following convergence rate to (r.((() instead of Eq. (6) (as shown in Lemma C.I):
Int E 1 - n x 11] S 5 (k(()()- (k(1)- 1)T,
(k(1)
By using Eq. (9) and the assumption that T3 = O(T we can still derive Eq, (7) and Eq, (8) for the noisy feedback setting. Therefore, we conclude that: IE [GAP( S T/TT).
INDIVIDUAL REGRET BOUND
In this section, we present an upper bound on an individual regret for each player. Specifically, our study examines two performance measures: the external regret and the dynamic regret (Zinkevich, 2003). The external regret is a conventional measure in online learning. In online learning in games, the external regret for player is defined the gap between the player's realized cumulative payoff and the cumulative payoff of the best fixed strategy in hindsight:
Reg, (T) == max
Σ
(u(x,xL))) vx()))).
7

---

Published as a conference paper at ICLR 2025
The dynamics regret is much stronger performance metric, which is given by:
DynamicReg, (T) = Σ
max (1 - 02(2²))
ZER;
We show in Theorem 5.1 that the individual regret is most O ((In (I²) if each player [N] plays according to GABP in the full feedback setting. The proof is given in Appendix D.
Theorem 5.1. In the same setup of Theorem 4.1, we have for any player E [M] and T 2 2:
Reg,(T) DynamicReg, (T) s S0 ((InT)))
This regret bound is significantly superior to the ((VT) regret bound of the Optimistic Gradient (OG) algorithm, and it slightly inferior to the OIn () regret bound of AOG (Cai & Zheng, 2023).
6 EXPERIMENTS
In this section, we present the empirical results of our GABP, comparing its performance with APGA (Abe et al., 2024), OG (Daskalakis et al., 2018; Wei al., 2021), and AOG (Cai & Zheng, 2023)- We conduct experiments on two classes of concave-convex games. One is random payoff games, which are two-player zero-sum normal-form games with payoff matrices of size d. Each player's strategy space is represented by the d-dimensional probability simplex, i.c., X1 X2 A All entries of the payoff matrix are drawn independently from a uniform distribution over the interval [-,, We set d 50 and the initial strategies set to πt = T2 1. The other is hard concave-conve game (Ouyang & Xu, 2021), formulated as the following max-min optimization problem: maxzex;; minye J [(x, y), where [xx y) - 2 Hx + hTx (Ax b, v)- Following the setup in Cai & Zheng (2023), we choose X1 X2 = [-200, 200 with d 100. The precise
terms of H E Rd A E dxd b E IRd, and h E Rd are provided in Appendix E.2. All algorithms
are executed with initial strategies ां = Tे 11. The detailed hyperparameters of the algorithms, tuned for best performance, are shown in Table 2 in Appendix E.3.
Figure/ illustrates the logarithmic GAP values per iteration for each of the two games under each type of feedback. For the random payoff games with full noisy feedback, 50 payoff matrices are generated using different random seeds. Likewise, for the hard concave-convex games, we use 10 different random seeds. We assume that the noise vector ę is generated from the multivariate Gaussian distribution (0, I in an i.i.d. manner for both games. In the former game with full feedback, GABP performs almost well as the others. With noisy feedback, GABP outperforms the others, although the margin from APGA is slight. In the latter game, under the full feedback setting, GABP is competitive against AOG, whereas, under the noisy feedback setting, it demonstrates substantial advantage over the others.
Figure 2 illustrates the dynamic regret the hard concave-convex game. GABP exhibits lower regret than APGA and OG with both feedback, demonstrating its efficiency and robustness. Note that APGA and OG exhibit almost identical trajectories with full feedback, with their plots overlapping completely. In addition, GABP achieves competitive regret in comparison to AOG.
7 RELATED LITERATURE
No-regret learning algorithms have been extensively studied with the intent of achieving key objec- tives such as average-iterate convergence or last-iterate convergence. Recently, learning algorithms introducing optimism (Rakhlin & Sridharan, 2013a;b), such as optimistic Follow the Regularized Leader (Shalev-Shwartz & Singer, 2006) and optimistic Mirror Descent (Zhou et al., 2017; Hsieh et al., 2021), have been introduced to admit last-iterate convergence in a broad spectrum of game settings. These optimistic algorithms with full feedback have been shown to achieve last-iterate con- vergence in various classes games, including bilinear games (Daskalakis et al., 2018; Daskalakis & Panageas, 2019; Liang & Stokes, 2019; de Montbrun & Renault, 2022), cocoercive games (Lin et al., 2020), and saddle point problems (Daskalakis & Panageas, 2018; Mertikopoulos et al., 2019; Golowich al., 2020b; Wei et al., 2021; Lei et al., 2021; Yoon & Ryu, 2021; Lee & Kim, 2021;
8

---

Published as a conference paper at ICLR 2025
0G
ADG
APGA
GABP
Random Payoff (Full)
Random Payoff (Noisy)
Hard Concave Convex (Full)
Hard Concave Convex (Noisy)
legor (CAP))))
0.5
-1.0
-1.5
3.0
-3
10
10
10
10
16a
10
10a
10a
10"
16a
10"
10" 10"
10
10
10a
10"
10a 10
10
10
Iterations
Iterations
Iterations
Iterations
Figure 1: The gap function for N' of GABP, APGA, OG, and AOG with full and noisy feedback. The shaded area represents the standard emrors.
OG
AOG
APGA
GABP
x10?
Hard Concave-Convex (Full)
x10?
Hard Concave-Convex (Noisy)
2.0
1.00
DynamicRes
1.5
0.50
1.0
0.25
0.00
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Iterations
x10
Iterations
x10
Figure 2: Dynamic regret for GABP, APGA, OG, and AOG with full and noisy feedback.
Cevher et al., 2023). Recent studies have provided finite convergence rates for monotone games (Golowich et al., 2020a; Cai et al., 2022a;b; Gorbunov et al., 2022; Cai & Zheng, 2023).
Compared to the full feedback setting, there significant challenges in learning with noisy feed- back. For example, learning algorithm must estimate the gradient from feedback that is contam- inated by noise. Despite the challenge, vergence with noisy feedback in specific classes of games, including potential games (Cohen et al., 2017), strongly monotone games (Giannou et al., 2021b:a), and two-player zero-sum games (Abe et al., 2023). These results have often leveraged unique structures of their payoff functions, such as strict (or strong) monotonicity (Bravo et al., 2018; Kannan Shanbhag. 2019; Hsieh et al., 2019; Anagnostides & Panageas, 2022) and strict variational stability (Mertikopoulos & Zhou, 2019; Mer- tikopoulos et al., 2019; 2022; Azizian et al., 2021). Without these restrictions, convergence is mainly demonstrated in asymptotic manner, with no quantification of the rate (Hsieh et al., 2020; 2022; Abe et al., 2023). Consequently, an exceedingly large number iterations might be necessary to reach equilibrium.
literature has successfully achieved last-iterate con-
There have been several studies focusing on payoff-regularize learning, where each player's pay- off utility function is perturbed regularized via strongly convex functions (Cen et al., 2021; 2023; Pattathil et al., 2023). Previous studies have successfully achieved convergence to stationary points, which are approximate equílibria. For instance, Sokota et al. (2023) have demonstrated that their perturbed mirror descent algorithm converges to a quantal response equilibrium (McKelvey & Palfrey, 1995; 1998). Similar results have been obtained with the Boltzmann Q-learning dynam- ies (Tuyls et al., 2006) and regularze dynamics (Coucheney et al., 2015) in continuous- time settings (Leslie Collins, 2005; Abe al., 2022; Hussain al., 2023). To ensure convergence toward a Nash equilibrium of the underlying game, the magnitude of perturbation requires careful adjustment. Several learning algorithms have been proposed gradually reduce the perturbation strength y in response to this (Bernasconi et al., 2022: Liu et al., 2023; Cai et al., 2023). These include well-studied methods such as iterative Tikhonov regularization (Facchinei Pang. 2003; Koshal al., 2010; 2013; Yousefian al., 2017; Tatarenko & Kamgarpour, 2019). Alternatively, Perolat et al. (2021) and Abe et al. (2023) have employed a payoff perturbation scheme, where the magnitude of perturbation is determined by the distance from anchoring strategy, which is period- ically re-initialized by the current strategy. Recently, Abe al. (2024) have established ((1VVT)

---

Published as a conference paper at ICLR 2025
and Ob//Tib last-iterate convergence rates for the payoff perturbation scheme in the full/noisy feedback setting, respectively. Our algorithm achieves faster (LL/T) and O(1/T*) last-iterate convergence rates by modifying the periodically re-initializing anchoring strategy scheme so that the anchoring strategy evolves more gradually.
CONCLUSION
This study proposes novel payoff-perturbe algorithm, Gradient Ascent with Boosting Payoff Per- turbation, which achieves ((1/T) and O(1/T+) last-iterate convergence rates in monotone games with full/noisy feedback, respectively. Extending our results in settings where each player only observes bandit feedback is an intriguing and challenging future direction.
ACKNOWLEDGMENTS
Kaito Ariu is supported by JSPS KAKENHI Grant Number 23K19986. Atsushi Iwasaki is supported by JSPS KAKENHI Grant Numbers 21H04890 and 23K 13517
REFERENCES
Kenshi Abe, Mitsuki Sakamoto, and Atsushi Iwasaki. Mutation-driven follow the regularized leader for last-iterate convergence in zero-sum games. In UAI, pp. 1-10, 2022.
Kenshi Abe, Kaito Ariu, Mitsuki Sakamoto, Kentaro Toyoshima, and Atsushi Iwasaki. Last-iterate convergence with full and noisy feedback in two-player zero-sum games. In AISTATS, pp. 7999- 2023.
Kenshi Abe, Kaito Ariu, Mitsuki Sakamoto, and Atsushi Iwasaki. Adaptively perturbed mirror descent for learning in games. In ICML, pp. 31-80, 2024.
loannis Anagnostides and loannis Panageas. Frequency-domain representation of first-order meth- ods: A simple and robust framework of analysis. In SOSA, pp. 131-160, 2022.
Waiss Azizian, Franck Iutzeler, Jérôme Malick, and Panayotis Mertikopoulos. The last-iterate vergence rate of optimistic mirror descent stochastic variational inequalities. In COLT, pp- 326-358, 2021.
James P Bailey and Georgios Piliouras. Multiplicative weights update in zero-sum games. In EC, pp. 321-338, 2018.
Martino Bernasconi, Alberto Marchesi, and Francesco Trovò. Last-iterate convergence to trembling- hand perfect equilibria. arXiv preprint wxxi::2088.082388 2022.
Mario Bravo, David Leslie, and Panayotis Mertikopoulos. Bandit learning in concave N-person games. In NeurlPS, pp. 5666-5676, 2018
Yang Cai and Constantinos Daskalakis. On minmax theorems for multiplayer games. SODA, pp. 217-234, 2011.
Yang Cai and Weiqiang Zheng. Doubly optimal no-regret learning in monotone games. In ICML, pp. 3507-3522 2023.
Yang Cai, Ozan Candogan, Constantinos Daskalakis, and Christos Papadimitriou. Zero-sum poly- matrix games: A generalization of minmax. Mathematics of Operations Research, 41(2):648- 655, 2016.
Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Finite-time last-iterate convergence for learn- ing in multi-player games. In NeurlPS, pp. 03900433991, 2022a.
Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Tight last-iterate convergence of the extragra- dient method for constrained monotone variational inequalities. arXiv preprint arXiv:2204.0977 09928,, 2022b.
10

---

Published as a conference paper at ICLR 2025
Yang Cai, Haipeng Luo, Chen- Yu Wei, and Weiqiang Zheng. Uncoupled and convergent learning in two-player zero-sum markov games with bandit feedback. In NewrlPS, pp. 10364-364400 2023.
Shicong Cen, Yuting Wei, and Yuejie Chi. Fast policy extragradient methods for competitive games with entropy regularization. In NeurlPS, pp. 27952- 27964, 2021.
Shicong Cen, Yuejie Chi, Simon S Du, and Lin Xiao. Faster last-iterate convergence of policy optimization in zero-sum Markov games. In ICLR, 2023.
Volkan Cevher, Georgios Piliouras, Ryann Sim, and Stratis Skoulakis. Min-max optimization made simple: Approximating the proximal point method via contraction maps. In Symposium on Sim- plicity in Algorithms (SOSA), pp. 192-206, 2023.
Johanne Cohen, Amélie Héliou, and Panayotis Mertikopoulos. Learning with bandit feedback in potential games. In NeurIPS, pp. 6372-6381, 2017.
Pierre Coucheney, Bruno Gaujal, and Panayotis Mertikopoulos. Penalty-regulated dynamics and robust learning procedures in games. Mathematics of Operations Research, (0(3)6611-633 2015.
Constantinos Daskalakis and loannis Panageas. The limit points of (optimistic) gradient descent in
min-max optimization. In NeurIPS, pp. 9256-9266, 2018.
Constantinos Daskalakis and Ioannis Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. In ITCS, pp. 27:1-27:18, 2019.
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training GANs with optimism. In ICLR, 2018
Étienne de Montbrun and Jérôme Renault, Convergence of optimistic gradient descent ascent in bilinear games. arXiv preprint arXiv:2208. 03005, 2022.
Gerard Debreu. social equilibrium existence theorem. Proceedings of the National Academy of Sciences, 38(10))886-89,, 1952.
Francisco Facchinei and Jong-Shi Pang. Finite-dimensionall variational inequalities and comple- mentarity problems. Springer, 2003.
Angeliki Giannou, Emmanouil Vasileios Vlatakis-Gkaragkouni and Panayotis Mertikopoulos. Sur- vival of the strictest: Stable and unstable equilibria under regularized learning with partial infor- mation. In COLT, pp. 2147-2148, 2021a.
Angeliki Giannou, Emmanouil- Vasileios Watakis-Gkaragkoul and Panayotis Mertikopoulos. On the rate of convergence of regularized learning in games: From bandits and uncertainty to opti- mism and beyond. In NeurlPS, pp. 22655 -2666, 2021b.
Noah Golowich, Sarath Pattathil, and Constantinos Daskalakis. Tight last-iterate convergence rates for no-regret learning in multi-player games. In NeurlPS, pp. 20766-20778, 2020a.
Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, and Asuman Ozdaglar. Last iterate is slower than averaged iterate in smooth convex-coneave saddle point problems. In COLT, pp- 1758-1784, 2020b.
Ian J. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In NeurlPS, pp. 2672-2680, 2014.
Eduard Gorbunov, Adrien Taylor, and Gauthier Gidel. Last-iterate convergence of optimistic gradi- ent method for monotone variational inequalities. In NeurlPS, pp. 21858 -18700, 2022.
Yu-Guan Hsieh, Franck Iutzeler, Jérôme Malick, and Panayotis Mertikopoulos. On the convergence of single-call stochastic extra-gradient methods. In NeurlPS, pp. 6938-6948, 2019.
Yu-Guan Hsich, Franck lutzeler, Jérôme Malick, and Panayotis Mertikopoulos. Explore aggres- sively, update conservatively: Stochastic extragradient methods with variable stepsize scaling. In NeurlPS, pp. 16223-16234, 2020.
11

---

Published as a conference paper at ICLR 2025
Yu-Guan Hsieh, Kimon Antonakopoulos, and Panayotis Mertikopoulos. Adaptive learning in tinuous games: Optimal regret bounds and convergence to Nash equilibrium. In COLT, pp. 2388- 2422, 2021.
Yu-Guan Hsieh, Kimon Antonakopoulos, Volkan Cevher, and Panayotis Mertikopoulos. No-regret learning in games with noisy feedback: Faster rates and adaptivity via learning rate separation. In NewrIPS, pp. 6544 6556, 2022.
Aamal Abbas Hussain, Francesco Belardinelli, and Georgios Piliouras. Asymptotic convergence and performance of multi-agent q-learning dynamics. In AAMAS, pp. 1578-1588 2023.
Aswin Kannan and Uday V. Shanbhag. Optimal stochastic extragradient schemes for pseudomono- tone stochastic variational inequality problems and their variants. Computational Optimization and Applications, 74(3):779-82)) 2019.
Jayash Koshal, Angelia Nedić, and Uday V Shanbhag. Single timescale regularized stochastic ap- proximation schemes for monotone nash games under uncertainty. In CDC, pp. 231-236, 2010.
Jayash Koshal, Angelia Nedic, and Uday V. Shanbhag. Regularized iterative stochastic approxi- mation methods for stochastic variational inequality problems. IEEE Transactions on Automatic Control, 58(3):594-609, 2013.
Sucheol Lee and Donghwan Kim. Fast extra gradient methods for smooth structured nonconvex- nonconcave minimax problems. In NeurlPS, pp. 22588-2260M 2021.
Qi Lei, Sai Ganesh Nagarajan, Ioannis Panageas, et al. Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes. In AISTATS, pp. 1441-1449, 2021.
David S Leslie and Edmund Collins. Individual g-laannig in normal form games. SIAM Journal
on Control and Optimization, 44(2):495-514, 2005.
Tengyuan Liang and James Stokes. Interaction matters: A note non-asymptotic local convergence of generative adversarial networks. In AISTATS, pp. 907-915, 2019.
Tianyi Lin, Zhengyuan Zhou, Panayotis Mertikopoulos, and Michael Jordan. Finite-time last-iterate convergence for multi-agent learning in games. In ICMI., pp. 6161-6171, 2020.
Mingyang Liu, Asuman Ozdaglar, Tiancheng Yu, and Kaiqing Zhang. The power of regularization in solving extensive-form games. In ICLR, 2023.
Richard D McKelvey and Thomas R Palfrey, Quantal response equilibria for normal form games. Games and economic behavior, 10(1):6-38 1995.
Richard D McKelvey and Thomas R Palfrey. Quantal response equilibria for extensive form games. Experimental economics, 1:9-41, 1998.
Panayotis Mertikopoulos and Zhengyuan Zhou. Learning in games with continuous action sets and unknown payoff functions. Mathematical Programminng 173(1):465-50) -0076,57777 2019.
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chan- drasekhar, and Georgios Piliouras. Optimistic mirror descent saddle-point problems: Going the extra (gradient) mile. In ICLR, 2019.
Panayotis Mertikopoulos, Ya-Ping Hsieh, and Volkan Cevher. Learning in games from stochastic approximation viewpoint. arXiv preprint arXiv:2206.0399 039222200.92.......222222222..0. 2022.
Dov Monderer and Lloyd Shapley. Potential games. Games and economic behavior, 14(1):124- 143, 1996.
Remi Munos, Michal Valko, Daniele Calandriello, Mohammad Gheshlaghi Azar, Mark Rowland, Zhaohan Daniel Guo, Yunhao Tang, Matthieu Geist, Thomas Mesnard, Côme Fiegel, Andrea Michi, Marco Selvi, Sertan Girgin, Nikola Momchev, Olivier Bachem, Daniel J Mankowitz, Doina Precup, and Bilal Piot. Nash learning from human feedback. ICML, pp. 36743-36766 2024.
12

---

Published as a conference paper at ICLR 2025
John Nash. Non-cooperative games. Annals of mathematicc, pp- 286-29865599922 1951.
Angelia Nedić and Soomin Lee. On stochastic subgradient mirrorrdescen algorithm with weighted averaging. SIAM Journal on Optimization, 24(1):84-007, 2014.
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574-166)) 1609, 2009.
Yuyuan Ouyang and Yangyang Xu. Lower complexity bounds of first-order methods for convex- concave bilinear saddle-point problems. Mathematical Programming, 185(1):1-35, 2021.
Sarath Pattathil, Kaiqing Zhang, and Asuman Ozdaglar. Symmetric (optimistic) natural policy gra- dient for multi-agent learning with parameter convergence. In AISTATS, pp. 5641-5685, 2023.
Julien Perolat, Remi Munos, Jean-Baptiste Lespiau, Shayegan Omidshafiei, Mark Rowland, Pedro Ortega, Neil Burch, Thomas Anthony, David Balduzzi, Bart De Vylder, al. From Poincaré re- currence to convergence in imperfect information games: Finding equilibrium via regularization. In ICMI, pp. 8525-8535, 2021.
Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In COLT, pp. 993-19999 2013a.
Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable quences. In NeurIPS, pp. 3066-3074, 2013b.
Shai Shalev-Shwart and Yoram Singer. Convex repeated games and fenchel duality. In NeurlPS, pp. 1265-1272, 2006.
Samuel Sokota, Ryan D'Orazio, J Zico Kolter, Nicolas Loizou, Marc Lanctot, loannis Mitliagkas, Noam Brown, and Christian Kroer. A unified approach to reinforcement learning, quantal re- sponse equilibria, and two-player zero-sum games. ICLR, 2023.
Gokul Swamy, Christoph Dann, Rahul Kidambi, Zhiwei Steven Wu, and Alekh Agarwal. A minimaximalist approach to reinforcement learning from human feedback. arXiv preprint arXiv:2401.04056 2024.
Tatiana Tatarenko and Maryam Kamgarpour: Learning Nash equilibria in monotone games. In CDC, pp. 3104-3109, 2019.
Karl Tuyls, Picter Jan Hoen, and Bram Vanschoenwinkel. An evolutionary dynamical analysis of multi-agent learning in iterated games. Autonomous Agents and Multi-Agent Systems, 12(1): 115-153, 2006.
Chen-Yo Yu Wei, Chung-Wad Wei Lee, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate convergence in constrained saddle-point optimization. In ICLR, 2021.
TaeHo Yoon and Ernest K Ryu. Accelerated algorithms for smooth convex-concave minimax prob- lems with (1/k2² rate on squared gradient norm. In ICML., pp. 12098-12109, 2021.
Farzad Yousefian, Angelia Nedić, and Uday V Shanbhag. On smoothing, regularization, and aver- aging in stochastic approximation methods for stochastic variational inequality problems. Math- ematical Progranming, 165:391-431, 2017.
Zhengyuan Zhou, Panayotis Mertikopoulos, Aris L. Moustakas, Nicholas Bambos, and Peter Glynn. Mirror descent learning in continuous games. In CDC, pp. 5783,,583, 2017.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In ICML, pp. 928-936, 2003.
13

---

Published as a conference paper at ICLR 2025
A
NOTATIONS
In this section, we summarize the notations we use in Table 1.
Table I: Notations
Symbol
Description Number of players
N
X
Strategy space for player i
X
Joint strategy space: X' I X²
Payoff function for player
Strategy for player i
i
Strategy profile: π (TT))E[[
π
Nash equilibrium
IIO
Set of Nash equilibria
GAP(T)
Gap function of π: GAP((T) = max Ex (V.,, (((T), -
tan (x)
Tangent residual of æ: p (r) mi) V +al
R. (T)
Gradient vector 0; with respect to T
(T(TT)
Noisy gradient vector of 1; with respect to mę: V (T(T)) = Vn, (T) + E
Noise vector for player at iteration t
V()
Gradient operator of the payoff functions: V(.) (V n; U/ (1))))))) IEEN
T
Total number of iterations Learning rate at iteration &
T p T r! k(t)
Perturbation strength Update interval for the anchoring strategy Strategy profile at iteration /
Number of updates of the anchoring strategy up to iteration
K
Total number of the updates of the anchoring strategy
k())
Anchoring strategy profile at iteration t
gk(()
convex combination of k(t) and a²: gk(()) k(t) 400 +o"
+()++
Stationary point satisfies:
Vi E [N], T.
[(,((t)) arg max [1, n", =.((()))) - - || - o4(01113
=EA; Smoothness parameter of (U:)se(N)
L
B PROOFS FOR THEOREM 4.
B. PROOF OF THEOREM 4.1
Proof of Theorem 4.1. From the first-order optimality condition for π", we have for any x E X' and
1 12.5 2:
V(T
x--1_ k(t () + 0!)
k(t - +1 - _ (5² x²1)) nT x 20,
1
1)
and then ((T--1)- 1
(-'-1_
k(t k(t 1) 100000100000
(TT 1n'-x"" -111 Nx Thus, the tangent
k(t-1)+1
residual for T can be bounded as:
r .lan
min
| ((T*)++))) all
)
V( + +V
---1
k(t k) 1ot
1 (T' -1-1 |
k(1 1) +
"
Letting us define
kot + o 12
T arg max T.
U,(TT, 1
k
14

---

Published as a conference paper at ICLR 2025
then get by triangle inequality:
p tan ( ( -
V(TT) + (1=-11)-
k(t - 1) + +1 (o - -0-)
1
1( (1) + -ーー (b1-1
(
& -V + v(='-1)|| + k(t - 1) +1
0 c(( 13
+ pl | 1 - [ + μ xak(t-1) x"
x
1 + 7
μ.
1| +
"1
k(t - 1) +
+ /4 T(iR(t-1) 1) - k((-1)
+ x - 7-11
1 n [ 
1D
+ 1 I/ - o k(e-1)
+ k(l - 1) -11
+ -u+ 1t / T--1| ||.
(10)
In terms of upper bound on || x²|| and || - x² ---l|| 2|| we introduce the following lemma:
P Lemma B.1. we use the constant learning rate 17- = 17 E (0, (I. ). we have for any t 2 1:
(kkk())
(a)(()) n²" 1| 1
m// ok(())
1 17p2
n muk(() - ,l
1
ma.k())) o4ro0112
Combining Eq. (10) and Lemma B.I, we have for any 2 2:
pa S 2
1 1 nL ) |
- 0 (1-
+ k(l - 11+1
MD
(1I)
7
Next, we derive the following upper bound on [Ta((t-1) -th(t-1)||
Lemma B.2. If we set = 17 E (0, ( and Ta 2 max 6lna(T+1)), ), we have for any & 2 1:
Im(1+mp)
1ukk - /tt k(1)+ +I
8D
By combining Eq. (11) and Lemma B.2, we get:
16D
+ nL
HD
tan (x²)
11
k(1 1) +1
"
1) +1
17D
1 1 mL
< k-t 1) +1
"
Therefore, since k(t)= = | | + 1, it holds that:
17DI,
1+ 1+n nL
tan (7') < To
p
1
Finally, taking T3 = c max
6ln3(+11) ), we have for any t t2 2: [m(1+nH)
17cD
6 3(T+1) +1) In([+np)
1 nL |
t (Ta)) <
t-1
15

---

Published as a conference paper at ICLR 2025
B.2 PROOF OF LEMMA B.1
Proof of Lemma B.I. First, we have for any three vectors a, b, C:
2 ||a b11²
2 1 -ll²= + 2 1b - clf = (c- b.a
Thus, have for any
2 1:
x(ah(())) -x x"" 7--111 1|2
1
rt11² - - x111 (
=0p=((t - n241 , n²+1)
2
2
(12)
Here, let us define gh(()
Then, from the first-order optimality condition for x++1
k(0+1
we have for any 2 1:
(v((t)-- (x' x(11 T", ntth ++ T(zk(tt) 2 0.
(13)
Similarly, from the first-order optimality condition for TT*,(t),, we get:
(v(Tuk((1) / (TT - ob(tt) nu.k(t) xtt1) 2
(14)
Combining Eq. (12), Eq. (13), and Eq. (14) yields:
2 T(i((1) ++1 2 1
2 [ x²| + 2
|++1 n² !1?
I (((T') (x'- -0((()) x {())(())
" (v(Tt)) (x - gb(1) , - xmi((e))
+ + - V(T(t1)- - 11 (x' - -x(-1) - x()
S "/ (V(auM 11 (x - -o4(t)) - - r(e)
+ 17 (V(TT) v(T(t1)= r1 (TT - -x(-1) - - xuidcc))
11 (V(Tuu(()) - 11 (T)))(()) - gk((t) و - a(1) ) 11/4 | k(0)
+ +n (v(T)) ((+(+1)= - 1 (x' - x(1)) - - st.c)e))
< <n - xuAro) I|² + + (V(T)) (( (T* x(+1) x+1 anAl()))
(15)
where the second inequality follows from Eq. (I). From Sauchy-Schware inequality and Young's inequality, the second term in the right-hand side of this inequality can be bounded by:
(V ((*++1) - / (T² - xz t1) n - x())()
(v(T') - ( ) +11 - x/ mp (TT - n e+1 x c-1 - nh m(t))
10/000 (1]( - (( ||| + #4 || x(+11))
S 111 + 1e) -| x + ||| | 1 x0/ ||
|/ 11| 12(L
11)2
21
n/
| 1+1
n
x(1) 2
|
(16)
2
16

---

Published as a conference paper at ICLR 2025
where the second inequality follow from Eq. (2), and the last inequality follows from the assumption that 17 I [(+N)= By combining Eq. (15) and Eq. (16), we get:
n
++1
|
n
7
||
+
n
++1
71'"
77
π ++1 R(t)
|T' π
1+1
Thus,
+ m
((ik((t)))))))))))))
n111
2
S T,,((1)
n²/
Therefore, we have for any 2 1:
maa((t)) - x1 S
1
+ 1711
Furthermore, since k(s) ktt) for E [(k(tt) 1)T's + 1, have for such s that:
nua(()) (0o4())~=+11 1| 5 1 mp
1
Therefore, by applying this inequality from t,t 1....
(k((t) L)To + 1, we get for any t 2 1:
mii((t)) ++1 || s + Tp
n au - x (R(e) 117
(-()())-)TT
mu oA(D)
(17)
1 np
Here, since k(() = le(t. + 1) when i satisfies that 1 + To
we have for such / that:
{u,(((+1) - x - s 1 17/4
(((x((+1)-1)T
7ub((11) obcctt)
(18)
On the other hand, when satisfies that / = To
t
To
1
T
k(t+1)
+ 1
+ 1
To
To
(k(1+1) 1) 1)Ta = =Ta
=1
To
x++ = - (k((t--))1)T-
σ k(t+1)
Therefore, we have for any t 2 1 such that t = Tg
To
[x - x++1 || ((tk()+)))
1
1
(19)
+ mp
By combining Eq. (17), Eq. (18), and Eq. (19), have for any 2 1:
(-(k(()-11)) 1)T,
(.)((() x++1 1/
1
(Ttk(()))) - olco)12
5
1 + 1/4
((((((+))) - x <
1
1-(6((1))-1)T
m= ob(c+z))??
mp
17

---

Published as a conference paper at ICLR 2025
B.3 PROOF OF LEMMA B.2
Proof of Lemma B.2. First, we have for any Nash equilibrium n²" E II and 2 1 such that k(t) 2
1:
(R((1) ()()(()) + +2)
04100 + +k((t) ((())+100) 1)(((t) + +2) (840041-170
(2)000))))2) qlik()) sui((t)) gb(11)
2 (k((t) + 1)(((t) +2) | - =/co
+ (k:(t) + 1) ( (16(t) + +1)04(++1 +o² -Ax(t) + 2) su.k(t) - gbico)
(k(1) + ()((()))+++))))))))))))))) 2)
1 S4/0 + (b((t) + 1) (0 - - xuu(()) gh(c))
2
+ (A:(t) + ())(tt + 2)
- (OM10)+1 Tma(()) -m)(()) - gh((1)
(R(()) + ()(((()) + 2)
+ +k((t) + 1) (0t - ku,k()) ( mLM()) =m)(()) - )M(())
nu. - gh(c))
+ (A:11) + 1)² (oM(0)+
(n(t)) + 1)(k(t) +2) 2)
|aakk())) - //10 (k(t) + 1) (o'- --, TT)10) - gb(())
+ (A:(1) +1) (T* ktt) mL)(())) ok(()) (k(1) + +12 (oMO14 mll()))) mtic(()) - -OM(1)
Here, the first-order optimality condition for ,,,)())
(((aa)())) 1 (3)))(()) - -oh(1)) .T() - x³) ) 20
1 + (Trik(t) - gkit), n - -aud(() 2 (V(Truk(t)) x-- - -auk(t)) 2 #
1
(v(+"),* - 2 0,
where we use Eq. (1) and the fact that xt' is Nash equilibrium. Combining these inequalities yields:
(ke(t) + ()k((t) + +2)
( - g 2 + (k(()) + 1)(k(t) + +2) (BM()++1 - k1))(1), aMI)(1) gk(1)
2
(k((1) + 1)(((()) + +2) |
- -4100/² + (k(1) + 1) () 00 - xT.)((1) , -
gkc())
2
+ (1:(t) + 1)2 (0100+1-uukkn aak(()) - gk(()
From Young's 's inequality, we have for any PL, P2 > 0:
(k(t) + 1)(((t) + 22
-9(00) |
12
2 + (k(1) + 1)(((t) + +2)
(oh(t)+1 -((k(() xl) - ob(1))
2 (k(()) + ()(((t +2) (QVAACO-AAC0) - - [ +1)
1100 |0112-112
(R<(t) + 1) puickc gb/co
2
2p1
p2(k((t) + 1)²
||
(k(t) + 1)²
|,, -x(0)] 1
2
2p2
(K(() + ()(((() +2)
k(t)+1
(k:(1) + +)3²
|
-Aaro11
2
2p1
2pz
(I(((t) + 1)
||o| - n" 1| p2(k(t) + 1)²
|/
-
2
18

---

Published as a conference paper at ICLR 2025
By setting P1 k(1)+2+ P2
4
4(R(t)++) k(1)+2
we obtain:
(k(t) + ()(( 2)
/xuk(00 }k(e)
+ (k(t)) + ()(((t) + +2) - ( - ob(t))
- THik(t),
2 (k(t) + ()) 22
- 1= |
2(k(t) + +1)
k(1) +2 110¹ 1-11
-
2(x((t) + 1)@² (000))4--HAA00)
k(t) + 2
(k(()) + +)((ttt) +2)
| - 24co
-x012- -2100 -
2 21|0
-2(((1) + 1)² 1)311000 0 x (() 2
(20)
Here, we introduce the following lemma:
Lemma B.3. For any t Z 1 such that k(t) 2 2, we have:
(k(t) + ()(((t + 2)
| gk(e)] 12
+ (k(1) + 1)(((L) + 2) -
gHik(t) alik(t) - gk(())
(k((t + 1)
+ -4000_11
())( (())((()+)))() ( TM/R()))
k(t)(((t)) +
- -1000)00000000000000000000000000 -4(0-1)
+ (A:(1) + 1) ( (A:(1) + 1)) - + (00(() -00004002HHN00-111 (u(0) - -
By combining Eq. (20) and Lemma B.3, we get: (R:(1) ()()(tt) + 2) maak(0 gk(0)|
(k(t) + ()(t(t) +2) | | 1| + (k((t) + 1)(k(t) + 2) -0600)1-774(10) xui(t)
(k(t))
+ 22||0t x=| +2(((t) + 1)² ||010001 - =akkee)
+
I 3 3||Thil - 8-11 + 60² - -hil xuall - -
-b + 2 2110-- - -111² + 2(k(t) + +)) - A())) 2
+ Σ (1+ 1) (11 + 1)(T7)) - + +l(o' - -1l- ),0²' - alll)
3 3|| ol2 + 2 (20" + o - 37t11 a ) + +2110² 1-1
k(t)
+ +((k(1) + 1)2 0 [(()) - m///00
Σ
1) (1l +1)((T - olt2) + +lo' - -(il-1), 0 -til
1=2
=31[ 0'|| + 22(10 - THi1 7 - o0)) + 4 (02 - 1 - 04)
+ +2|10-- -1 + 2(k(t) + 1)² ||0000+1 1 - =01kco) ?
k00
+ Σ (1+ 1) ((1 + 1) d(t1) + +((o' - 1 - =
1=2
|| - 0-||² + (02 THil nh od) + 2 2/10t - -1²1²² + +2(k(t) + 1)2 | mpakcess
k(0)
(1+ 1) (11 + 1) - )(t) + +l'o - n//d- - thilt)
2
|| - 02||² +2||0= x-1 + 2(k(() + 1)²
- - |
k(()
k(t)
+
Σ 1=1
(1 + 1)² (
- g4| / + Σ
1(++1)(o - -1/--11 00 - 7i1)
19

---

Published as a conference paper at ICLR 2025
k(O)
3D - 2(k(tt) 1)² | m +2D(k(t) + +1)
Σ
||
/ 0lt2
1=1
Therefore, we have for any L 2 1 such that k(1) 2 2:
k(t)
b4th(( - / -
1202
+8 1 -
+ 8D
| 0'11l1
(k(1) +12
By the definition of gh((t)
+ |04(0) 011
( - okccoll
2
(Tui((1) - k(t) _ kkt)) - )²)
+
(k((t + 1)2
k(t) +
12D2 $ (k(t) + 1)2
+ +8
88100041--7
8D
k(()
| d'+111
Therefore, from Cauchy-Schward inequality, we have:
Tt,((() - -
$ k(t) +1 (Tetibie)) - oh(1),0' -0'10((1) - + (k(t) + 1)2²
2
12D2
k(t)
+ 8
- m(ck(t) 1|
2
+
+DD
T 1|
1=1
k(t)
S k(t) +1
2D
nTuk(() - xk00]] |
12D2
+ +8 +8|10 -
8D
Σ
1+1
(A:(t) + 1)2
(21)
Furthermore, from Lemma B.,, we have for any k 2 1:
|| - σ 2t2 <
||a/ti - 011
(22)
1 + mp
Combining Eq. (21) nad Eq. (22), we have for any 2 such that k(t) 2 2:
m01R(00 221:(00 - |
2D
12D2
<
k(t) +
(k(t) 1)2
1
To
occo +8D2%(tt)
4
1 m/44
1 np
Therefore, since T₂ 2 max 6 3(T+(1)1))
Im(1+mps)
1+1j
(k(()+1)) (Itma)"
S
16 we have for k(() 2 2:
|| - k10)
2D 2
2D2
12D2
D
16D2
2(k(t) + 1)2 <
k:(t) +
(k(t)) + 1)2
(A:(t) + 1)2
(Ii(t) + 1)2
and then:
- |
2D
4v2D
8D
k((1) +1
h((1) +1
k(1) +1
On the other hand, for k-(t) 1, we have:
8D
|
o21| <
D
1+1
20

---

Published as a conference paper at ICLR 2025
In summary, for any t 1, we have:
8D k(t) +
B.4 PROOF OF LEMMA B.3
Proof of Lemma B.3. From the first-order optimality condition for xu,,(t), we have:
(TTtib()t)) p(TT)k(t))) - -Ok()), 7T.((t)) ,T(, 2 0.
Similarly, from the first-order optimality condition for nu),-1)- have:
(V(T =( (b(())1),, =() - x(ih(tt) 2 0.
Summing up these inequalities, we get for any 2 1 such that k(t) 2 2:
V (T (TT T(. )( 10 (Tttk(()) xb()), Tt -(.(())-))
+ 11 (1)-11 xu-(()) xuh())-1 -m))
$ 1 m.)() g4(0) maa(()) -u + 1 (04(0)- -7)k(()- -(1 x x((0)
1 MM)) 4(0) + M() (110) m))(()) ((1)) x01)) - x
+ ( ( k1)(1-11 -1 =10 )m.()))
/ m())) okco / (ou
)4( .01()) - xma(0-1)
11 x() (00) m((() ]-k(1)11 11 -1 x1/((0111 - x )m((()))
14 m. obco)]l il ( (m gh(() ok1)) - -x0A((0-1)
+ 11 ( =m)())- -()(())) -b(()) + p (g((0)-1 - -o((1), - - x()()))
Here, for any vectors a, b, e, it holds that:
(a b, b c) 2 la c||2
2 b1b - c||2 2
2 [la bll2
(a - b.c d) 2
|a b1b
+ マ |||c b|c- - d|
ld c + 1--b) b11..
2
Thus, have:
π n k(e A10 2
11
k(1) -m((()--1 2
0 5 11
n
2
14
kk(()) k(0)
2
k(() -110 l|²
2
14
-())))
A())
2
1t
1111 - o/1o
- /|=
/1
k()) - -0
2
2
14
(0) #(e)
2
n k()) =11
+ 2
2
/4
(.)()) -1)(()-1 (() + @acoop2
2
/1
((A(()))) -,,((0)-
2 + d (2400)) g((()-11
2
2
21

---

Published as a conference paper at ICLR 2025
14
xuk(()) -0k(0-11 + + +at10/1
2
14 [(k(())) ]))(())1 2
(k(()) 0b(()-112
+
2
2
/
(Tub(())) Tu
+ 2
+ - -
2
14 2
1 GA())
11
(b(()) - =
2
1
p..k(() - -1
2
2
(ah(0) - - -
(23)
Here, from the definition of g we have:
ab((1) - -0
1 | m m11
2
1
h(t) + 0¹
2 1 | x(:((1)-1
2
k(t)= +1 1
2
1
k(t)a +o
ma)(1)-1 + TH.b(()) x()) k(t)a + +o¹ xukk(1) - mai(()) -aah()) + x(lb(0)-1)
2
k(t) +1
ktt) +1
1
o + (R(() + 1) - 2(t(tt) + 1)T" k(t)o (1)
gk((t) ((((()
2
k:(t) +1
(2(b(1) + 1)0 + 20 - -1))(() + 2) 2) gh0)) - -
2k(()
<- k(() + 0- + +31((t) + 4) 2(k((t) + 1)0 gk(z) ((1)
21(t))
(((()= +1
1
2k(()) MAA)) 1 + k(t) + 0 k(1)) ,k(1), (000) -M.A(C)
k(t)2
2A(())
k(t)+ 2
(2kW))1 - m,. (kt)) )(i((t))
k(t)
1
k(t) + 03 (k((( + 2) (b(0) + (k((t) + 2) - -70.
+ 2x(t)
k(t) +1
k(t) +
1
(2(k(() ()( x((++)) (2²()) =mM(0) I(((C))
21:(1)
k(()=
+2
(AM0S1-atUKK) sH)(()) -u)(()) )k(1)
1(tt)
k(t)+2
((t))M()) +o- a()(
k(1) +1 (a0(()),Mi0) gh(()) mad())
2k(())
1
(16(t) + ((( 040++)) + k(t)((A(()) - -xHAA(0-1), 24/(10) )
+ k(t)
k(t)= +2 (J40511 -H,K(()) -U/R(()- - ok()) k(t) 2
2k((t 1800-x'00 -
A(t))
+ k(I) ((6(t) + (T - ((++) + k(t)(o A() - =m)(()) 04(00 -auA(())
1
(24)
Combining Eq. (23) and Eq. (24) yields for any & 2 such that k(t) 2 2:
a(t) +2 T (()((()))) - 84/0/ + k(t) + (2(())+1 - =m)(()) ka) - gH(())
2k(()
A(1)
mm 1,:00-1-4400-11
- nm -1
$ 2
1
((5(0) + 1)( xb(+))) + - k(()(a - =mA(0-11 1,, mack(t))
k(t)
22

---

Published as a conference paper at ICLR 2025
Multiplying both sides by (+t(()((t) 1), we have:
(k((t) + (t((tt) + 2)
Tu - - gh(1) 1
+ (k(1) + ()((()) + 2) ( (6N(O)41 T(/(() Tu.(()) - xb((1)
((((()(()))))))))()))))())))(() 1) | -0:00-11 +()((((())) + +1) ( TMA(1-1 - 84(0)-1)
+ (k((t +1) ( (1((t)+ + 11)77)000)000 + - )k(1)) -zth)))))
-
C PROOFS FOR THEOREM 4.3
C.I PROOF OF THEOREM 4.3
Proof of Theorem 4.3. Let us define K == T T."
We can decompose the gap function for T++1 as
follows:
GAP(
max (V(T +1) ) x" +
=EA'
max ((( =EX
), ) (V(TH..)) ), TH.K) + (VV (V(x"++)) x
max ((T
), K),
k> (V(TMiK) - V(TT+1), ) क T+ + (V ) Tth x x+11)
*EX'
max ((V(T" ",, ), TK +D (TTM v(a ||| + S |||T - x
ZEX
GTP(T" + (LD + 5) || - T
$ D
min (x
V- c|| (LD () - 1T
where the last inequality follows from Lemma 2.3. From the first-order optimality condition for T..K have for any 2 E X::
V(Tu.K)- - 10 mak Ko* + +o!)
-.u x 2 0,
K+1
and then V(T" 1t (TViK Ko*+o") bounded by:
E (.). Thus, the gap function for π T++ can be
K+1
TUKKK Kor +o!
GAP( & LDD
+ + + 5) | 7111
K+1
oK ol
=D
+ THiK ok
+ (LD (LD+)) IT+1||
K +
D
SDD
+ +
+ +LDD ()) 1 IT|||
K +1
Taking its expectation yields:
μD²
E GAP(T T+)] <
+ PD E I - -
+ (LD + ()- - E a.u T+1
K K+1
nD
+ pD
E
x | - -
+ (LD + 5) VB ||
K + 1
(25)
Here, we derive the following upper bound on E - -
23

---

Published as a conference paper at ICLR 2025
Lemma C.1. Let K 5.
3 +8L2
Suppose that Assumption 4.2 holds. If we set n
2p
n(t-To ()) we have for any z
1:
m(.b(t)) - nt 19]
20
C
K (t (k(t) - -)
E
s x
D2 +
In
(k(t) 1)T')
20
k0
20
Setting t = = KTo we can write k(t) = KTa
+ = K. Therefore, from Lemma C.I, we
have:
EI
| π x
[|]
20
D2
C
In
RTo
+ 1
(26)
kTa + 20
x0
20
On the other hand, terms of E || o (t) we introduce the following lemma:
Lemma C.2. If we set ti x(t-To (k())((())11)++ 1) and To 2 max(1, T we have for any 1:
6 6V v0 VDB VD) k(1)
(V
E - ck(o S
D2
In
KT
+
1
+
K0
20
By setting t = KTo in this lemma, we get:
6 (Vi + V
DO VD)
(1
E [| - of - S
(V
D2
+
C²
In
KT
1
+1
K
n
K8
2A
(27)
Combining Eq. (25), Eq. (26), and Eq. (27), we have:
E [GAAP(K*)]] [+]]]
nD2
6 6VKR+ v0
VDD+VD)
VDO
C
kT
K +1 + DD.
(V
D2
+
+
+ +1
K
28
28
C
nTTo
+ (LD+
D2 +
In
+1
KT 20
k0
20
S n22 To
+ μD T
6To
VE + v0 + v DD0- + vD)
(V
D
+
C2
In
kT
+
+1 +1)
T
k0
20
20
C
RT
+ +11 1
+ (L.D (I.D+ ()
D2 +
In
RT,
R8
24
where the second inequality follows from K = T. for any 2 To:
T
Finally, since T~ = c max(1, 74), we have
E [+1](
quD2
GcuD
VK+ v0
VDO + VD)
C In
KT
+ 1 )
D2 +
+1)
T
T
KB
29
(LD +))
20
2
KT
+
D2 +
+
7
K
KB
28
6cpD
(vi + /0 + VD + VD+D)
C
KT
(V
D2
+
In
+ 1
+1)
k0
20
24

---

Published as a conference paper at ICLR 2025
(Vi
(LD + CW220 +
C²
KT
D2 +
In
+
+1
T
k
28
9c Dc(nD + LD+ ()
V vo DD + +VD+++
(
C²
kT
D2
In
+
+1
T
20
Since T T= T,,, we have finally:
E GAPP(T++1) Ic Dc + LD () VR + V0 VDB VD
(1
C
KT
D22 +
+
+1
Tt
K0
20
(Vr+ +5-+((e (VD+1>(VD+V 9c(D(x + L)+ + 5)
(v
C
KT
+ 1 )) +1
D2 +
In
T
K0
20
18c + L) + 5)
(VR+ V 1)
(V
C2
KT
D2
ln
1
1
T
n
KB
28
DD(H + L) + +)) + (v/
C2
nT
D2 +
In
+
1
+ 1
T
k0
20
C.2 PROOF OF LEMMA C.1
Proof of Lemma C.I. From the first-order optimality condition for x'+1, we have for t 2 1:
(m (v(+') u(aa - -ok(t)) n111 + n², + m..k(t) 2 0.
(28)
Combining Eq. (28), Eq. (12), and Eq. (14), we have:
ki(((t)) π ++1 2 nT/b(()) - - 2 + | - |13
S n (((2²) - m(a""= - -kt(t)), xtt1_ - =m))(())
m (V(x=t1) 1- 11I - gh(1)), x x1 - xu)(()) ) + 1/6 (V(TT) - V(*+t1) - -J((T' - T x2+11,, ), x+ - a.))(())
I m ( (V(Taa(l))) - |( gk(1)) xz +t+ - =mm(i)))
+ 1... (((T)) - V(x't2) - =M(T* x² x1+1 xlih(0)))
me (V(Tuk(1)) (( gk(t)), x(+1 mua())) mill (ly xt+1|? 1
+ '/ (V(T²) -V ) _111 xbb())) ) - mili (x'
1t1 111 xmb(e)) ) + 1/| (5', xt22 - m))()))
1/d" mk((() - x(+1|/ + 71j < 41 n² 1 )laiee )
+ n (V(T') ( ), x(+1 mub(t)) ) + 1/ (5', nh+ mm))(())
- k)(((())) - x ||
2 nef4
| - 1// + Map44 | - m(ck()) 12 12= Moff T n² 7..3
2
+ n (V(TT) ( +++1_
T(lb(())) ) + 1/
(8' [+] T,)(())
n111 |x(+1= - m0:c0o) |² 10144 x² x
2 + Tos4 | - 11'1
2
2
2
+ ne (V(nt) v( m _ mecblt)) + m (5', at -
(29)
25

---

Published as a conference paper at ICLR 2025
where the third inequality follows from Eq. (1). From Cauchy-Schwand inequality and Young's inequality, the fourth term on the right-hand side of this inequality can be bounded by:
(v(+)) - V (1*==11) x - =
< [T - |( | - x0.
12 |= - x || [+1
21
|| n/ x/+111 112 + 1
++1 TTt |
8
2L
||
-x
11
+ 14
1
|
x
1
4
ALL
1
||
n
++11
2
/1
|/
2
+
(30)
2
2
2
2
By combining Eq. (29) and Eq. (30), we have:
77//6
x [+1
xmm 1|
+(1- (1-2(1
+
2
|^' - 1-'-xaaA0 200
1 1)t
33
+
41,2
||
=
+ 20 (5' xt+1 ma)k)))))
2
nepl
|+
x" 20/2
- -(1- 17
(3)) 33
2 + 41.2)
H )) || - 11/
2
+ 2mp (5", TT - m(e + 20p <5", イ +++1_ - x²)
(5",
(1 nx1xi |xt nt k10 11 - (1 0) || x11
+ 27/ (5t n² - xukket) > + 2n (5", n- - x²))
By taking the expectation conditioned on Fr for both sides and using Assumption 4.2 (a) and (b),
E
m
F
(1 np)s) E
|T'0' xm)c
2 1| Fi (1- E [| - x²11 |||
1
2m a [8
FF] .. m(i(())
+ 1 [(5t m- - x²) | [F
(1 (/am
A(0)
(1 (0 R | ++1 m ||? Fz
+ 2 E2 [(5", n 7 - x²) [F
$ (1 27t
(1 () E
| - n" Fi
+ 1 1/l1 0
n E
|1551 2
Fe
+ (1 - 0) IE [|
++ x $1 [Fo]
E [115117 15.]
2 (1 k)
+ 1 m
2B E [16-1] [F]]
< (1 k
< (1 kb)
k00
+ C2
Therefore, under the setting where 7) =
we have for any t 2 1:
1/t 2
FF < 1 t- (k(((t) - 1) ---_(k())1))+211111
1
I1"" In' Amoo || + +2 C
E
-)
20/12)
26

---

Published as a conference paper at ICLR 2025
Rearranging and taking the expectations, get:
| - 1
(L - (k(() - 1) + 20/k) kx)
I [| T²/ x=1
20
$ -tt-1-Ta 1) 20/k) B
K. (n(t - (k((((t) 1)) + 20)
Since k(s) = k(t) for any E [(k(t) - 1)T6 + 1,7]. telescoping the sum yields:
(- 1) + 20/n) || n"+1
20 Σ n (m(m - (T((t) - 1)) + 20)
$ (s- 1--11-TT(kh 1) 20/1:) E
| | T-/
Defining (k(t) - 1)T's + 1,
(t - To (A((t) - 1) + 20/ 1x) IE MT/ - -
20 E x
x (x(0) (M0)-)) 27 | -
19]
20
Σ
+
k(m To(((t) 1)) 29"
m=(k(()- 11),
Therefore,
20
( (((0) 19
E
n kk(())
- -
(t To (k((t) 1)) + 28
-k(())1)7: 1)T.
202
(31)
18 (1 - (k((()) 1)) 20
km + 20
Here, we have: t- 1)T.
(1(())-177) 177.
KI 20 dr 1 In
( < (<(1- (k(l) 1)Ta)
+1). (32)
Km + 20
20
m=1
Combining Eq. (31), Eq. (32), and the fact that n (k(t)) ok((), we have:
E
x a.)(tt) - -
20
E | (00000000000 -0001/7
C²
<n(t (k(t) 1)Ta)
+
In
+1
(t - (k((t) 1)T,) + 28
K0
20
20
C In
< (6 - (k(()) 1)Ta) +1))
D2 +
R (k<(t) 1)T,)
28
K0
20
C.3 PROOF OF LEMMA C.2
Proof of Lemma C.2. First, from Lemma C.I, we have for any h: 2 1:
E [|| - o ++11"]]
20
D2
+ kfl
O
In
+ 1 1)
kT. + 20
20
Moreover, by taking the expectation of Eq.
(21), we have for any 2 such that k(1) 2:
[ab(())))) - |
2D k(t) +
E
Tu,(())
-
12D²
(A:(t) 1)2
k(x))
+ 8B
| | -110+--2uAA00111
SD
E 1 - 11
1=1
27

---

Published as a conference paper at ICLR 2025
Combining these inequalities, get for any 2 1 such that k(t) 2 2:
E n m00
2D
EE Tr [ - oA(1))
[]
12122
-
S 1:(1)
+
(k((t) + 112
+
160
D2
C²
In
KTa
+11 + +DK((t)
20
D2 +
C² In
<TTa
+ 1
kTo
kl
20
KIP
k0
20
Since T, 2 (1)
+
k(t) VT,
I 1, we have:
(I -b(())
D
21
13D²
160
C²
NT
E
D2 +
In
+1
1
k:(1) +1
1(t))
=X(())²
k0
20
8D
20
C
kT
D2 +
In
+
k(tt)
K
KB
28
Since B[X]²= < E[X²] for any random variable X, we get:
13D2
+
160
( D22
C²
In
KT
1)
+
8D
20
D2 +
C2 In
nT
29 + 11) )
k kt))
kk(t)2
N8
2A
k(t)2
kB
() - om(o
D
27
E
k(t)& +
D
2
2
k())) k(t)
k(()) + 1
[] 1000
D
2
E
k(t) +
Then, we have:
E (((t)) [c]|
D
+ 40
AV0
C²
KT
3VD 20
C2
kT
k((1) k(1)
+
Vrl((1) V
D2 +
In
2A
+
+
k(1)
K
D2
RB
In
20
+
5(vR+ v0)
122 C² In
KIT
6v D( D(V0 10)
C
KT
+1
+
(
D22 +
In
+
+
k(1V%
k0
20
k(()
k0
20
6 (VR+ V + v DD + vD))
C2
KT
+1 +1)) +1
( 1
D2 +
In
k(t)
kD
20
Furthermore, for k(t) = 1, we have:
E [ - -01l SDS 6 (Vi++ v0+ VDØ +
VD+VDD++VVV+VVV VDI)
(V
C2
KT
+1 1)
D2 +
In
+1)
k
k0
28
Therefore, we have for any t 2 1:
6 6VK v0 - + +VD)
E mk((() ckc/ 5
(1/1 AM
C In
kT
D2
+ 1
+1
1((1)
x0
20
28

---

Published as a conference paper at ICLR 2025
D PROOF OF THEOREM 5.1
Proof of Theorem 5.1. By the definition of dynamic regret, we have:
DynamieReg, (T)
Σ
(2 BEA.
max
2/8 (T²))
T
N
S 00(1)
max (x x (1, -((())) zERt
1=
Here, we introduce the following lemma:
Lemma D.1 (Lemma 2 of Cai al. (2022a)). For any X, have:
max (a m-1) - vr(TT) R.EM
GAP(T) D (V - -)x)
#EX
Therefore, we have:
T
(T) Σ GAP(#))
Thus, from Theorem 4.1:
IT
DynamicReg, (T) 0(1) + Σ 0 t=2 $ 0 (1n)))
E EXPERIMENTAL DETAILS
E. INFORMATION ON THE COMPUTER RESOURCES
The experiments were conducted on macOS Sonoma 14.4.1 with Apple M2 Max and 32GB RAM.
E.2
HARD CONCAVE-CONVEX GAME
Following the setup in Ouyang & Xu (2021); Cai & Zheng (2023), we choose
11
0
1
0
1
1
4
Raxn
b
E
R
4
...
E
R
-1
1
0
and = 2.AAA.
E.3
HYPERPARAMETERS
For each game, we carefully tuned the hyperparameters for each algorithm to ensure optimal perfor- mance. The specific parameters for each game and setting summarized in Table 2.
29

---

Published as a conference paper at ICLR 2025
Game
Algorithm
1/
1
OG
0.05
Random Payoff (Full Feedback)
AOG
0.05
APGA
0.05
20
1.0
GABP
0.05
10
1.0
OG
0.001
Random Payoff (Noisy Feedback)
AOG
0.001
APGA
0.001
2000
1.0
GABP
0.001
1000
1.0
OG
1.0
Hard Concave-Convex (Full Feedback)
AOG
1.0
APGA
1.0
20
0.1
GABP
1.0
20
0.1
0G
0.5
Hard Concave-Convex (Noisy Feedback)
AOG
0.5
APGA
0.5
50
0.1
GABP
0.1
100
0.1
Table Hyperparameters
F COMPARISON WITH EXISTING LEARNING ALGORITHMS
F.1 RELATIONSHIIP WITH ACCELERATED OPTIMISTIC GRADIENT ALGORITIM
Our GABP bears some relation to Accelerated Optimistic Gradient (AOG) (Cai & Zheng, 2023), which updates the strategy by:
++ à arg max :
x
TE::
1 1+1
arg max ZEA;
1
|
क.
2
++1
2
This can be equivalently written as:
++
V Vr, (
1
tπ + π
2
arg max REX,
+
ln +
++
arg max EEX.
V Ci( (
2),0)
1
2
++1
This means that AOG employs convex combination strategy mे the proximal point in gradient ascent. However, our GABP diverges from AOG in that uses a convex combination k(0) of o and of as the reference strategy for the perturbation term.
= of the current strategy oł and initial (+1
((())
k00+1
In terms of proof for last-iterate convergence result, Cai & Zheng (2023) have employed the following potential function for the full feedhack setting:
pt = E(t ((t+1)
9p -V + c + 11 [(TT)) - V( -(=- 111²²)
+ In in(-V( d' n
2
where c² = --1 (np 3)+ (3r - and V() = v.()) Compared to our potential
function pk((), their potential function includes the term of 7 ((r') -x }) } In the noisy
feedback setting, the value of this term could remain high even if की = # Therefore. this term complicates providing a last-iterate convergence result for the noisy feedback setting. In contrast,
30

---

Published as a conference paper at ICLR 2025
potential function pk(() does not contain the term depending Vu;(T"):
pk(t) = (kt)( + +1)
- -0k())-) gh(()-1 1|
( (()(((()) + 1) - ( (h(()-1)
This allows to provide the last-iterate convergence rates both for full and noisy feedback settings.
F.2 COMPARISON OF ITER-TE CONVERGENCE RESULTS
In this section, we provide Table 3 for comparison with last-iterate convergence results of existing representative learning algorithms in monotone games.
Algorithm
Full Feedback
Noisy Feedback
Extragradient
O(1/VT)
N/A
(Cai et al., 2022a:b)
Optimistic Gradient
O(1/VT)
N/A
(Golowich et al., 2020b; Gorbunov et al., 2022; Cai et al., 2022a)
Extra Anchored Gradient
O(L/T)
N/A
(Yoon & Ryu, 2021)
Accelcrated Optimistic Gradient
O(1/T)
N/A
(Cai & Zheng, 2023)
Iterative Tikhonov Regularization
N/A
Asymptotic
(Koshal et al., 2010; Tatarenko Kamgarpour, 2019)
Adaptively Perturbed Gradient Ascent
0(1/T))
k(1/T%)
(Abe et al., 2024)
Ours
Õ(1/T)
Ö(/T+)
Table 3: Existing results on last-iterate convergence in monotone games. only under bandit feedback.
(*) means the result holds
31


Reviews:
[{"review_id": "v2myp5tWcl", "reviewer": "Reviewer_tqic", "summary": "This paper considers multi-player monotone games and proposes a perturbed gradient ascent algorithm with improved performance in both deterministic and stochastic settings. Numerical simulations are provided.", "questions": "(1) According to the definition, $\\sigma_i^1=\\pi^1$. Am I missing anything?\n\n(2) Why are we not using the Nash Gap as a metric, which seems more natural?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper is well-organized and well-written. The proposed algorithm of Gradient Ascent with Boosting Payoff Perturbation is easy to implement and enjoys strong convergence guarantees. The numerical simulations are extensive and demonstrate the empirical performance of the proposed algorithm in various settings.", "weaknesses": "(1) Algorithmically, there is only one difference between the proposed algorithm and the Adaptively Perturbed Mirror Descent (APMD) from Abe et al. (2024): instead of directly using $\\sigma_i^k$ as the anchoring strategy, a convex combination of $\\sigma_i^k$ and $\\sigma_i^1$ is used as the anchoring strategy. Surprisingly, with this seemingly minor modification, the resulting algorithms achieve improved performance guarantees. I did not quite follow why such a modification results in improved performance, despite the illustration from line 216 to line 225. What is the intuition behind this modification? Why does it help improve the performance guarantees? Are there intuitive and technical explanations behind it?\n\n(2) In terms of the analysis, are there any major technical challenges in extending the approach from Abe et al. (2024) to that of this work? If so, how did the authors overcome it?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yTJ9AjVEtJ", "reviewer": "Reviewer_K3ym", "summary": "The paper focuses on last-iterate convergence on smooth, monotone games for both the full feedback and noisy feedback settings. The authors propose a novel payoff perturbation term that dynamically interpolates the current anchoring strategy and the initial anchoring strategy. The interpolation achieves a trade-off between convergence speed and stability to gradient noise. The authors proved that the proposed algorithm achieves state-of-the-art last-iterate convergence rates for both the exact and noisy gradient feedback settings. Through experiments, it’s shown that the proposed algorithm achieves comparable or superior convergence speed in random payoff and hard concave-convex games, in noiseless and noisy gradient settings.", "questions": "- In Figure 1, why is GAP shown for the random payoff game and the $r^{tan}$ shown for the hard concave-convex game? Can you show the other metric for these games as well?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The technical contribution is strong. The proposed GABP algorithm is well motivated and explained, and the authors have shown proof for the last iterate convergence rates.\n- The paper is well-written. Proof sketches are shown for main theorems.", "weaknesses": "The paper does not discuss limitations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Dl0u6wualq", "reviewer": "Reviewer_gYTD", "summary": "This paper introduces a novel algorithm, Gradient Ascent with Boosting Payoff Perturbation, designed to improve last-iterate convergence rates in monotone games. The research builds upon the existing framework of payoff perturbation methods, which aid in stabilizing convergence in multi-player games where strategy profiles evolve iteratively. The authors address challenges posed by noisy feedback in gradient-based learning environments and achieve enhanced convergence rates with a boosting approach that periodically re-initializes a reference strategy, thereby maintaining strong convexity in the payoff function.", "questions": "* It would be better to give more explanation on the intuition for the perturbation term (*) in Eq (3).\n* Regarding the Hard Concave-Convex games in Appendix D.3, is there any reason that GABP uses a different step size (0.1) compared with other algorithms (0.5)?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "* The GABP algorithm leverages a perturbation term to enhance the stability and convergence rate.\n* Theoretical analysis covers both full and noisy feedback settings.\n* The study includes diverse game settings and benchmarks against state-of-the-art algorithms.", "weaknesses": "* The proof strategy seems standard, and the technical contribution is not clarified in this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nQpPV8HthS", "reviewer": "Reviewer_d7d7", "summary": "This paper proposes GABP, which addresses the online learning tasks in games that are monotone with respect to gradient. The GABP algorithm uses a perturbation on policy update such that the policy anchors on a linear combination of the initial policy and the selected anchor policy, which is shown to accelerate convergence and stabilize performance. The last-iterate convergence to NE is provided.", "questions": "See Weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Using the carefully constructed perturbation, the newly proposed GABP achieves a faster convergence rate compared to APMD. A good contribution to the literature.\n\nThe related literature is detailed and explains the", "weaknesses": "The notations in this paper is a bit confusing to the readers, a subsection dedicated for notations could be helpful. In addition, the subscripts and superscripts in section 4 can be simplified, such as the stationary point as well as $\\hat{\\sigma}$.\n\nAlthough Section E.1 provided a discussion between the proposed GABP with AOG, with a different motivation, etc. However, the exact update still appears similar to the reviewer.\n\nThe experiments do not demonstrate a clear advantage of GABP compared to existing methods listed as benchmark. Perhaps more explanation could be helpful on why in some cases certain methods fail and why GABP is better overall.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)