Boosting Perturbed Gradient Ascent for Last-Iterate Convergence in Games

## Abstract

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.

## 1 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 as concave-convex games, zero-sum polymatrix games (Cai and Daskalakis, ; Cai et al., ), $\lambda$-cocoercive games (Lin et al., ), and Cournot competition (Monderer and Shapley, ).
Due to their wide-ranging applications, there has been growing interest in developing learning algorithms to compute Nash equilibria in monotone games.

Typical learning algorithms such as Gradient Ascent (Zinkevich, ) and Multiplicative Weights Update (Bailey and Piliouras, ) have been extensively studied and shown to converge to equilibria in an average-iterate sense, which is termed average-iterate convergence.
However, averaging the strategies can be undesirable because it can lead to additional memory or computational costs in the context of training Generative Adversarial Networks (Goodfellow et al., ) and preference-based fine-tuning of large language models (Munos et al., ; Swamy et al., ).
In contrast, last-iterate convergence, in which the updated strategy profile itself converges to a Nash equilibrium, has emerged as a stronger notion than average-iterate convergence.

Payoff-perturbed algorithms have recently been regaining attention in this context (Sokota et al., ; Liu et al., ).
Payoff perturbation, a classical technique referenced in Facchinei and Pang (), 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 a Nash equilibrium of the underlying game, the magnitude of perturbation requires careful adjustment. As a remedy, it is adjusted by the distance from an anchoring or reference strategy.
Koshal et al. () and Tatarenko and Kamgarpour () simply decay the magnitude in each iteration, and their methods asymptotically converge, since the perturbed function gradually loses strong convexity.
In response to this, recent studies (Perolat et al., ; Abe et al., , )
re-initialize the anchoring strategies periodically, or in a predefined interval, so that they keep the perturbed function strongly convex and achieve non-asymptotic convergence.

We should also mention the optimistic family of learning algorithms, which incorporates recency bias and exhibits last-iterate convergence (Daskalakis et al., ; Daskalakis and Panageas, ; Mertikopoulos et al., ; Wei et al., ).
Unfortunately, the property has mainly been proven in the full feedback setting.
Although it might empirically work with noisy feedback, the convergence is slower, as demonstrated in Section 6.
The fast convergence in the noisy feedback setting is another reason why payoff-perturbed algorithms have been gaining renewed interest.

The most recent payoff-perturbed algorithm, Adaptively Perturbed Mirror Descent (APMD) (Abe et al., ), achieves $\tilde{\mathcal{O}}(1/\sqrt{T})$(^1^11We use $\tilde{\mathcal{O}}$ to denote a Landau notation that disregards a polylogarithmic factor.) and $\tilde{\mathcal{O}}(1/T^{\frac{1}{10}})$ last-iterate convergence rates in the full/noisy feedback 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 a novel payoff-perturbed 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 $\tilde{\mathcal{O}}(1/T)$ and $\tilde{\mathcal{O}}(1/T^{\frac{1}{7}})$ last-iterate convergence rates to a Nash equilibrium with full and noisy feedback, respectively(^2^22For a more detailed comparison of our rates with other works, please refer to Table 2 in Appendix E.2.).
To derive these rates, we utilize the concept of the potential function used in Cai and Zheng (). Specifically, the potential function we employ is customized for handling noisy feedback.
We further show that each player’s individual regret is at most $\mathcal{O}\left((\ln T)^{2}\right)$ 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., ; Wei et al., ), the Accelerated Optimistic Gradient algorithm (Cai and Zheng, ), and APMD in concave-convex games, irrespective of the presence of noise.

## 2 Preliminaries

#### Monotone games.

In this study, we focus on a continuous multi-player game, which is denoted as $\left([N],(\mathcal{X}_{i})_{i\in[N]},(v_{i})_{i\in[N]}\right)$.
$[N]=\{1,2,\cdots,N\}$ denotes the set of $N$ players.
Each player $i\in[N]$ chooses a strategy $\pi_{i}$ from a $d_{i}$-dimensional compact convex strategy space $\mathcal{X}_{i}$, and we write $\mathcal{X}=\prod_{i\in[N]}\mathcal{X}_{i}$.
Each player $i$ aims to maximize her payoff function $v_{i}:\mathcal{X}\to\mathbb{R}$, which is differentiable on $\mathcal{X}$.
We denote $\pi_{-i}\in\prod_{j\neq i}\mathcal{X}_{j}$ as the strategies of all players except player $i$, and $\pi=(\pi_{i})_{i\in[N]}\in\mathcal{X}$ as the strategy profile.
This paper particularly studies learning in smooth monotone games, where the gradient operator $V(\cdot)=(\nabla_{\pi_{i}}v_{i}(\cdot))_{i\in[N]}$ of the payoff functions is monotone: $\forall\pi,\pi^{\prime}\in\mathcal{X}$,

$$ $\displaystyle\left\langle V(\pi)-V(\pi^{\prime}),\pi-\pi^{\prime}\right\rangle \leq 0,$ (1) $$

and $L$-Lipschitz for $L>0$,

$$ $\displaystyle\left\|V(\pi)-V(\pi^{\prime})\right\|\leq L\left\|\pi-\pi^{\prime }\right\|,$ (2) $$

where $\|\cdot\|$ denotes the $\ell_{2}$-norm.

Many common and well-studied games, such as concave-convex games, zero-sum polymatrix games (Cai et al., ), $\lambda$-cocoercive games (Lin et al., ), and Cournot competition (Monderer and Shapley, ), are included in the class of monotone games.

###### Example 2.1 (Concave-convex games) .

Consider a game defined by $(\{1,2\},(\mathcal{X}_{1},\mathcal{X}_{2}),(v,-v))$, where $v:\mathcal{X}_{1}\times\mathcal{X}_{2}\to\mathbb{R}$.
In this game, player $1$ wishes to maximize $v$, while player $2$ aims to minimize $v$.
If $v$ is concave in $\pi_{1}\in\mathcal{X}_{1}$ and convex in $\pi_{2}\in\mathcal{X}_{2}$, the game is called a concave-convex game or minimax optimization problem, and it is not hard to see that this game is a special case of monotone games.

###### Example 2.2 (Cournot Competition) .

Consider a Cournot competition model with a linear price function.
There are $N$ firms in competition, and each independently and simultaneously chooses a quantity $\pi_{i}\in\mathcal{X}_{i}:=[0,C_{i}]$ to produce certain goods, where $C_{i}$ is a constant greater than 0.
The price of the goods is determined by a linear function $P(\pi)=a-b\sum_{i\in[N]}\pi_{i}$, where $a$ and $b$ are constants greater than 0.
The payoff for each firm $i$ is calculated as the total revenue from producing $\pi_{i}$ units of the goods, minus the associated production cost, i.e., $v_{i}(\pi)=\pi_{i}P(\pi)-c_{i}\pi_{i}$.
This game has been shown to satisfy the property of monotone games as defined in Eq. (1) (Bravo et al., ).

###### Example 2.1 (Concave-convex games) .

###### Example 2.2 (Cournot Competition) .

#### Nash equilibrium and gap function.

A Nash equilibrium (Nash, ) is a widely used solution concept for a game, which is a strategy profile where no player can gain by changing her own strategy.
Formally, a strategy profile $\pi^{\ast}\in\mathcal{X}$ is called a Nash equilibrium, if and only if $\pi^{\ast}$ satisfies the following condition:

$$ $\displaystyle\forall i\in[N],\forall\pi_{i}\in\mathcal{X}_{i},~{}v_{i}(\pi_{i} ^{\ast},\pi_{-i}^{\ast})\geq v_{i}(\pi_{i},\pi_{-i}^{\ast}).$ $$

We define the set of all Nash equilibria to be $\Pi^{\ast}$.
It has been shown that there exists at least one Nash equilibrium (Debreu, ) for any smooth monotone games.

To quantify the proximity to Nash equilibrium for a given strategy profile $\pi\in\mathcal{X}$, we use the gap function, which is defined as:

$$ $\displaystyle\mathrm{GAP}(\pi):=\max_{\tilde{\pi}\in\mathcal{X}}\left\langle V (\pi),\tilde{\pi}-\pi\right\rangle.$ $$

Additionally, we use another measure of proximity to Nash equilibrium, referred to as the tangent residual.
This measure is defined as:

$$ $\displaystyle r^{\mathrm{tan}}(\pi):=\min_{a\in N_{\mathcal{X}}(\pi)}\left\|-V (\pi)+a\right\|,$ $$

where $N_{\mathcal{X}}(\pi)=\{(a_{i})_{i\in[N]}\in\prod_{i=1}^{N}\mathbb{R}^{d_{i}}~{
}|~{}\sum_{i=1}^{N}\langle a_{i},\pi_{i}^{\prime}-\pi_{i}\rangle\leq 0,~{}
\forall\pi^{\prime}\in\mathcal{X}\}$ is the normal cone at $\pi\in\mathcal{X}$.
It is easy to see that $\mathrm{GAP}(\pi)\geq 0$ (resp. $r^{\mathrm{tan}}(\pi)\geq 0$) for any $\pi\in\mathcal{X}$, and the equality holds if and only if $\pi$ is a Nash equilibrium.
Defining $D:=\sup_{\pi,\pi^{\prime}\in\mathcal{X}}\left\|\pi-\pi^{\prime}\right\|$ as the diameter of $\mathcal{X}$, the gap function for any given strategy profile $\pi\in\mathcal{X}$ is upper bounded by its tangent residual:

###### Lemma 2.3 (Lemma 2 of Cai et al. ( 2022a ) ) .

For any $\pi\in\mathcal{X}$, we have:

$$ $\displaystyle\mathrm{GAP}(\pi)\leq D\cdot r^{\mathrm{tan}}(\pi).$ $$

The gap function and the tangent residual are standard measures of proximity to Nash equilibrium; e.g., it has been used in Cai and Zheng (); Abe et al. ().

###### Lemma 2.3 (Lemma 2 of Cai et al. ( 2022a ) ) .

#### 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\in[N]$ chooses her strategy $\pi_{i}^{t}\in\mathcal{X}_{i}$, based on previously observed feedback;
(ii) Each player $i$ receives the (noisy) gradient vector $\widehat{\nabla}_{\pi_{i}}v_{i}(\pi^{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 $\widehat{\nabla}_{\pi_{i}}v_{i}(\pi^{t})=\nabla_{\pi_{i}}v_{i}(\pi^{t})$.
In the noisy feedback setting, each player’s gradient feedback $\nabla_{\pi_{i}}v_{i}(\pi^{t})$ is contaminated by an additive noise vector $\xi_{i}^{t}$, i.e., $\widehat{\nabla}_{\pi_{i}}v_{i}(\pi^{t})=\nabla_{\pi_{i}}v_{i}(\pi^{t})+\xi_{i
}^{t}$, where $\xi_{i}^{t}\in\mathbb{R}^{d_{i}}$.
Throughout the paper, we assume that $\xi_{i}^{t}$ is the zero-mean and bounded-variance noise vector at each iteration $t$.

#### Payoff-perturbed learning algorithms.

To facilitate the convergence in the online learning setting, recent studies have utilized a payoff perturbation technique, where payoff functions are perturbed by strongly convex functions (Sokota et al., ; Liu et al., ; Abe et al., ).
However, while the addition of these strongly convex functions leads learning algorithms to converge to a stationary point, this stationary point may be significantly distant from a Nash equilibrium.
Therefore, the magnitude of perturbation requires careful adjustment.
Perolat et al. (); Abe et al. (, ) have introduced a scheme in which the magnitude is determined by the distance (or divergence function) from an anchoring strategy $\sigma_{i}$, which is periodically re-initialized.
Specifically, Adaptively Perturbed Mirror Descent (APMD) (Abe et al., ) perturbs each player’s payoff function by a strongly convex divergence function $G(\pi_{i},\sigma_{i}):\mathcal{X}_{i}\times\mathcal{X}_{i}\to[0,\infty)$, where the anchoring strategy $\sigma_{i}$ is periodically replaced by the current strategy $\pi_{i}^{t}$ every predefined iterations $T_{\sigma}$.

Let us denote the number of updates of $\sigma_{i}$ up to iteration $t$ as $k(t)$, and the anchoring strategy after $k(t)$ updates as $\sigma_{i}^{k(t)}$.
Since $\sigma_{i}$ is overwritten every $T_{\sigma}$ iterations, we can write $k(t)=\lfloor(t-1)/T_{\sigma}\rfloor+1$ and $\sigma_{i}^{k(t)}=\pi_{i}^{T_{\sigma}(k(t)-1)+1}$.
Except for the payoff perturbation and the update of the anchor strategy, APMD updates each player $i$’s strategy in the same way as standard Mirror Descent algorithms:

$$ $\displaystyle\pi_{i}^{t+1}=\mathop{\rm arg~{}max}\limits_{x\in\mathcal{X}_{i}} \left\{\eta_{t}\left\langle\widehat{\nabla}_{\pi_{i}}v_{i}(\pi^{t})-\mu\nabla_ {\pi_{i}}G(\pi_{i}^{t},\sigma_{i}^{k(t)}),x\right\rangle-D_{\psi}(x,\pi_{i}^{t })\right\},$ $$

where $\eta_{t}$ is the learning rate at iteration $t$, $\mu\in(0,\infty)$ is the perturbation strength, and $D_{\psi}(\pi_{i},\pi_{i}^{\prime})=\psi(\pi_{i})-\psi(\pi_{i}^{\prime})-
\langle\nabla\psi(\pi_{i}^{\prime}),\pi_{i}-\pi_{i}^{\prime}\rangle$ is the Bregman divergence associated with a strictly convex function $\psi:\mathcal{X}_{i}\to\mathbb{R}$.
When both $G$ and $D_{\psi}$ is set to the squared $\ell^{2}$-distance, this algorithm can be equivalently written as:

$$ $\displaystyle\pi_{i}^{t+1}=\mathop{\rm arg~{}max}\limits_{x\in\mathcal{X}_{i}} \left\{\eta_{t}\left\langle\widehat{\nabla}_{\pi_{i}}v_{i}(\pi^{t})-\mu\left( \pi_{i}^{t}-\sigma_{i}^{k(t)}\right),x\right\rangle-\frac{1}{2}\left\|x-\pi_{i }^{t}\right\|^{2}\right\}.$ $$

We refer to this version of APMD as Adaptively Perturbed Gradient Ascent (APGA).
Abe et al. () have shown that APGA exhibits the convergence rates of $\tilde{\mathcal{O}}(1/\sqrt{T})$ and $\tilde{\mathcal{O}}(1/T^{\frac{1}{10}})$ with full and noisy feedback, respectively.

Figure: Algorithm 1 GABP for player $i$.

## 3 Gradient ascent with boosting payoff perturbation

This section proposes a novel payoff-perturbed learning algorithm, Gradient Ascent with Boosting Payoff Perturbation (GABP).
The pseudo-code of GABP is outlined in Algorithm 1.
At each iteration $t\in[T]$, GABP receives the gradient feedback $\widehat{\nabla}_{\pi_{i}}v_{i}(\pi^{t})$, and updates each player’s strategy by the following update rule:

$$ $\displaystyle\pi_{i}^{t+1}=\mathop{\rm arg~{}max}\limits_{x\in\mathcal{X}_{i}} \Bigg{\{}\eta_{t}\left\langle\widehat{\nabla}_{\pi_{i}}v_{i}(\pi^{t})- \underbrace{\mu\frac{\sigma_{i}^{k(t)}-\sigma_{i}^{1}}{k(t)+1}}_{(*)}-\mu\left (\pi_{i}^{t}-\sigma_{i}^{k(t)}\right),x\right\rangle-\frac{1}{2}\left\|x-\pi_{ i}^{t}\right\|^{2}\Bigg{\}}.$ (3) $$

$\sigma_{i}$ is overwritten every $T_{\sigma}$ iterations, and thus $\sigma_{i}^{k(t)}$ is define as $\sigma_{i}^{k(t)}=\pi_{i}^{T_{\sigma}(k(t)-1)+1}$.
The term ($*$) in Eq. (3) is our proposed additional perturbation term.
It shrinks as $k(t)$, the number of updates of $\sigma_{i}^{k(t)}$, increases.

For a more intuitive explanation of the proposed perturbation term, we present the following update rule, which is equivalent to Eq. (3):

$$ $\displaystyle\pi_{i}^{t+1}=\mathop{\rm arg~{}max}\limits_{x\in\mathcal{X}_{i}} \left\{\eta_{t}\left\langle\widehat{\nabla}_{\pi}v_{i}(\pi^{t})-\mu\left(\pi_{ i}^{t}-\frac{k(t)\sigma_{i}^{k(t)}+\sigma_{i}^{1}}{k(t)+1}\right),x\right \rangle-\frac{1}{2}\left\|x-\pi_{i}^{t}\right\|^{2}\right\}.$ $$

According this formula, it is evident that GABP perturbs the gradient vector $\widehat{\nabla}_{\pi}v_{i}(\pi^{t})$ so that $\pi^{t}$ approaches $\frac{k(t)\sigma_{i}^{k(t)}+\sigma_{i}^{1}}{k(t)+1}$, instead of $\sigma_{i}^{k(t)}$.
This gradual evolution of the anchoring strategy in GABP, compared to $\sigma^{k(t)}$ 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)+1)$ achieves a faster convergence rate, and we believe that this represents the optimal balance for this trade-off.
We remark that the term ($*$) bears a resemblance to the update rule of the Accelerated Optimistic Gradient (AOG) algorithm (Cai and Zheng, ). 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 is discussed in Appendix E.1.

## 4 Last-iterate convergence rates

This section provides the last-iterate convergence rates of GABP.
Specifically, we derive $\tilde{\mathcal{O}}(1/T)$ and $\tilde{\mathcal{O}}(1/T^{\frac{1}{7}})$ 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 $t$, i.e., $\widehat{\nabla}_{\pi_{i}}v_{i}(\pi^{t})=\nabla_{\pi_{i}}v_{i}(\pi^{t})$.
Theorem 4.1 shows that the last-iterate strategy profile $\pi^{T}$ updated by GABP converges to a Nash equilibrium with an $\tilde{\mathcal{O}}(1/T)$ rate in the full feedback setting.

###### Theorem 4.1 .

If we use the constant learning rate $\eta_{t}=\eta\in(0,\frac{\mu}{(L+\mu)^{2}})$ and the constant perturbation strength $\mu>0$, and set $T_{\sigma}=c\cdot\max(1,\frac{6\ln 3(T+1)}{\ln(1+\eta\mu)})$ for some constant $c\geq 1$, then the strategy $\pi^{t}$ updated by GABP satisfies for any $t\in\{1,2,\cdots,T\}$:

$$ $\displaystyle\mathrm{GAP}(\pi^{t+1})\leq D\cdot r^{\mathrm{tan}}(\pi^{t+1}) \leq\frac{17cD^{2}\left(\frac{6\ln 3(T+1)}{\ln(1+\eta\mu)}+1\right)}{t}\left( \mu+\frac{1+\eta L}{\eta}\right).$ $$

This rate is competitive compared to the previous state-of-the-art rate of $\mathcal{O}(1/T)$ (Yoon and Ryu, ; Cai and Zheng, ).
Note that the rate in Theorem 4.1 holds for any fixed $\mu>0$.

###### Theorem 4.1 .

### 4.2 Noisy feedback setting

Next, we establish the last-iterate convergence rate in the noisy feedback setting, where each player $i$ observes a noisy gradient vector contaminated by an additive noise vector $\xi_{i}^{t}\in\mathbb{R}^{d_{i}}$: $\widehat{\nabla}_{\pi_{i}}v_{i}(\pi^{t})=\nabla_{\pi_{i}}v_{i}(\pi^{t})+\xi_{i
}^{t}$.
We assume that the noisy vector $\xi_{i}^{t}$ is zero-mean and its variance is bounded.
Formally, defining the sigma-algebra generated by the history of the observations as $\mathcal{F}_{t}:=\sigma\left((\widehat{\nabla}_{\pi_{i}}v_{i}(\pi^{1}))_{i\in[
N]},\ldots,(\widehat{\nabla}_{\pi_{i}}v_{i}(\pi^{t-1}))_{i\in[N]}\right)$, $\forall t\geq 1$, the noisy vector $\xi_{i}^{t}$ is assumed to satisfy the following conditions:

###### Assumption 4.2 .

$\xi^{t}_{i}$ satisfies the following properties for all $t\geq 1$ and $i\in[N]$: (a) Zero-mean: $\mathbb{E}[\xi^{t}_{i}|\mathcal{F}_{t}]=(0,\cdots,0)^{\top}$; (b) Bounded variance: $\mathbb{E}[\|\xi^{t}_{i}\|^{2}|\mathcal{F}_{t}]\leq C^{2}$ with some constant $C>0$.

Assumption 4.2 is standard in online learning in games with noisy feedback (Mertikopoulos and Zhou, ; Hsieh et al., ; Abe et al., ) and stochastic optimization (Nemirovski et al., ; Nedić and Lee, ).
Under Assumption 4.2 and a decreasing learning rate sequence $\eta_{t}$, we can obtain a faster last convergence rate $\tilde{\mathcal{O}}(1/T^{\frac{1}{7}})$ than $\tilde{\mathcal{O}}(1/T^{\frac{1}{10}})$ of APGA (Abe et al., ).

###### Theorem 4.3 .

Let $\kappa=\frac{\mu}{2},\theta=\frac{3\mu^{2}+8L^{2}}{2\mu}$.
Suppose that Assumption 4.2 holds and $V(\pi)\leq\zeta$ for any $\pi\in\mathcal{X}$.
We also assume that $T_{\sigma}$ is set to satisfy $T_{\sigma}=c\cdot\max(T^{\frac{6}{7}},1)$ for some constant $c\geq 1$.
If we use the constant perturbation strength $\mu>0$ and the decreasing learning rate sequence $\eta_{t}=\frac{1}{\kappa(t-T_{\sigma}(k(t)-1))+2\theta}$, then the strategy $\pi^{T+1}$ satisfies:

$$ $\displaystyle\mathbb{E}\left[\mathrm{GAP}(\pi^{T+1})\right]=\mathcal{O}\left( \frac{\ln T}{T^{\frac{1}{7}}}\right).$ $$

###### Assumption 4.2 .

###### Theorem 4.3 .

### 4.3 Proof sketch of Theorems 4.1 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 A and B.

We define the stationary point $\pi^{\mu,\sigma^{k(t)}}$, which satisfies the following condition: $\forall i\in[N]$,

$$ $\displaystyle\pi_{i}^{\mu,\sigma^{k(t)}}=\mathop{\rm arg~{}max}\limits_{x\in \mathcal{X}_{i}}\left\{v_{i}(x,\pi_{-i}^{\mu,\sigma^{k(t)}})-\frac{\mu}{2} \left\|x-\hat{\sigma}^{k(t)}\right\|^{2}\right\},$ $$

where $\hat{\sigma}_{i}^{k(t)}=\frac{k(t)\sigma_{i}^{k(t)}+\sigma_{i}^{1}}{k(t)+1}$.
The primary technical challenge in deriving the last-iterate convergence rates lies in the construction of the following potential function $P^{k(t)}$, which can be utilized in the proofs for both full and noisy feedback settings:

$$ $\displaystyle P^{k(t)}$ $\displaystyle\!:=\!k(t)(k(t)+1)\!\left(\!\frac{\left\|\pi^{\mu,\sigma^{k(t)-1} }-\hat{\sigma}^{k(t)-1}\right\|^{2}}{2}+\left\langle\hat{\sigma}^{k(t)}-\pi^{ \mu,\sigma^{k(t)-1}},\pi^{\mu,\sigma^{k(t)-1}}-\hat{\sigma}^{k(t)-1}\right \rangle\!\right).$ $$

Specifically, we demonstrate that this potential function is approximately non-increasing regardless of the presence of noise.
Although the potential function $P^{k(t)}$ is inspired by one in Cai and Zheng (), their potential function contains the term $\eta^{2}\sum_{i\in[N]}\left\|\widehat{\nabla}v_{i}(\pi^{t})-\widehat{\nabla}v_
{i}(\pi^{t-\frac{1}{2}})\right\|^{2}$, which could have a high value in the noisy feedback setting even if $\pi^{t}=\pi^{t-\frac{1}{2}}$ holds(^3^33The comparison of the potential function of Cai and Zheng () with ours can be found in Appendix E.1.).
This complicates providing a last-iterate convergence result for the noisy feedback setting via their potential function.
In contrast, our potential function $P^{k(t)}$ does not include the term dependent on $\widehat{\nabla}v_{i}(\pi^{t})$.
This enables us to provide the last-iterate convergence rates even for the noisy feedback setting.

#### (1) Potential function for bounding the distance between π μ , σ k ⁢ ( t ) superscript 𝜋 𝜇 superscript 𝜎 𝑘 𝑡 \pi^{\mu,\sigma^{k(t)}} italic_π start_POSTSUPERSCRIPT italic_μ , italic_σ start_POSTSUPERSCRIPT italic_k ( italic_t ) end_POSTSUPERSCRIPT end_POSTSUPERSCRIPT and σ k ⁢ ( t ) superscript 𝜎 𝑘 𝑡 \sigma^{k(t)} italic_σ start_POSTSUPERSCRIPT italic_k ( italic_t ) end_POSTSUPERSCRIPT .

As mentioned above, our main technical contribution is proving that $P^{k(t)}$ is approximately non-increasing (as shown in Lemma A.3).
That is, we have for any $t\geq 1$ such that $k(t)\geq 2$:

$$ $\displaystyle P^{k(t)+1}\leq P^{k(t)}+(k(t)+1)^{2}\cdot\mathcal{O}\left(\left \|\pi^{\mu,\sigma^{k(t)}}-\sigma^{k(t)+1}\right\|+\left\|\pi^{\mu,\sigma^{k(t) -1}}-\sigma^{k(t)}\right\|\right).$ (4) $$

By telescoping of Eq. (4) and the first-order optimality condition for $\pi^{\mu,\sigma^{k(t)}}$, we can derive the following upper bound on the distance between $\pi^{\mu,\sigma^{k}}$ and $\hat{\sigma}^{k(t)}$:

$$ $\displaystyle\frac{(k(t)+1)(k(t)+2)}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\hat{ \sigma}^{k(t)}\right\|^{2}\leq\mathcal{O}(1)+(k(t)+1)^{2}\sum_{l=1}^{k(t)} \mathcal{O}\left(\left\|\pi^{\mu,\sigma^{l}}-\sigma^{l+1}\right\|\right).$ $$

Applying the definition of $\hat{\sigma}^{k(t)}$ and Cauchy-Schwarz inequality to this inequality, we obtain:

$$ $\displaystyle\!\!\!\!\!\!\left\|\pi^{\mu,\sigma^{k(t)}}\!-\sigma^{k(t)}\right \|^{2}\!\leq\!\frac{\mathcal{O}\!\left(\left\|\pi^{\mu,\sigma^{k(t)}}-\sigma^{ k(t)}\right\|\right)}{k(t)+1}\!+\mathcal{O}\!\left(\frac{1}{(k(t)+1)^{2}} \right)\!+\!\sum_{l=1}^{k(t)}\mathcal{O}\!\left(\left\|\pi^{\mu,\sigma^{l}}- \sigma^{l+1}\right\|\right)\!.$ (5) $$

Note that the non-increasing property of our potential function, as 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 σ k ⁢ ( t ) + 1 superscript 𝜎 𝑘 𝑡 1 \sigma^{k(t)+1} italic_σ start_POSTSUPERSCRIPT italic_k ( italic_t ) + 1 end_POSTSUPERSCRIPT to the stationary point π μ , σ k ⁢ ( t ) superscript 𝜋 𝜇 superscript 𝜎 𝑘 𝑡 \pi^{\mu,\sigma^{k(t)}} italic_π start_POSTSUPERSCRIPT italic_μ , italic_σ start_POSTSUPERSCRIPT italic_k ( italic_t ) end_POSTSUPERSCRIPT end_POSTSUPERSCRIPT .

Leveraging the strong convexity of the perturbation payoff function, $\frac{\mu}{2}\|x-\hat{\sigma}_{i}^{k(t)}\|^{2}$, we show that $\pi^{t}$ converges to $\pi^{\mu,\sigma^{k(t)}}$ exponentially fast in the full feedback setting (as shown in Lemma A.1).
Specifically, we have for any $t\geq 1$:

$$ $\displaystyle\begin{aligned} &\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{t+1}\right\| ^{2}\leq\left(\frac{1}{1+\eta\mu}\right)^{t-(k(t)-1)T_{\sigma}}\left\|\pi^{\mu ,\sigma^{k(t)}}-\sigma^{k(t)}\right\|^{2}.\end{aligned}$ (6) $$

By using Eq. (6) and the assumption that $T_{\sigma}\geq\frac{6\ln 3(T+1)}{\ln(1+\eta\mu)}$ in the full feedback setting, we can easily show that $\left\|\pi^{\mu,\sigma^{l}}-\sigma^{l+1}\right\|=\left\|\pi^{\mu,\sigma^{l}}-
\pi^{T_{\sigma}l+1}\right\|\leq\mathcal{O}(k(t)^{-3})$ for any $l\leq k(t)$.
Hence, from Eq. (5), we can derive the following convergence rate of the distance between $\pi^{\mu,\sigma^{k(t)}}$ and $\sigma^{k(t)}$ with respect to $k(t)$ (as shown in Lemma A.2):

$$ $\displaystyle\left\|\pi^{\mu,\sigma^{k(t)}}-\sigma^{k(t)}\right\|\leq\mathcal{ O}(1/k(t)).$ (7) $$

#### (3) Decomposition of the gap function of the last-iterate strategy profile π T + 1 superscript 𝜋 𝑇 1 \pi^{T+1} italic_π start_POSTSUPERSCRIPT italic_T + 1 end_POSTSUPERSCRIPT .

Let us define $K:=\lfloor T/T_{\sigma}\rfloor$.
From Cauchy-Schwarz inequality and Lemma 2.3, we can decompose the gap function $\mathrm{GAP}(\pi^{T+1})$ as follows:

$$ $\displaystyle\mathrm{GAP}(\pi^{T+1})$ $\displaystyle\leq\mathrm{GAP}(\pi^{\mu,\sigma^{K}})+\mathcal{O}\left(\left\| \pi^{\mu,\sigma^{K}}-\pi^{T+1}\right\|\right)$ $\displaystyle\leq D\cdot\min_{a\in N_{\mathcal{X}}(\pi^{\mu,\sigma^{K}})}\left \|-V(\pi^{\mu,\sigma^{K}})+a\right\|+\mathcal{O}\left(\left\|\pi^{\mu,\sigma^{ K}}-\pi^{T+1}\right\|\right).$ $$

From the first-order optimality condition for $\pi^{\mu,\sigma^{K}}$, we can see that $V(\pi^{\mu,\sigma^{K}})-\mu(\pi^{\mu,\sigma^{K}}-\hat{\sigma}^{K})\in N_{
\mathcal{X}}(\pi^{\mu,\sigma^{K}})$.
Thus, from the triangle inequality and $L$-smoothness of the gradient operator in Eq. (2), the gap function $\mathrm{GAP}(\pi^{T+1})$ can be bounded as:

$$ $\displaystyle\mathrm{GAP}(\pi^{T+1})$ $\displaystyle\leq\mathcal{O}(1/K)+\mathcal{O}\left(\left\|\pi^{\mu,\sigma^{K}} -\sigma^{K}\right\|\right)+\mathcal{O}\left(\left\|\pi^{\mu,\sigma^{K}}-\pi^{T +1}\right\|\right).$ (8) $$

#### (4) Putting it all together: last-iterate convergence rate of π T + 1 superscript 𝜋 𝑇 1 \pi^{T+1} italic_π start_POSTSUPERSCRIPT italic_T + 1 end_POSTSUPERSCRIPT .

By combining Eq. (6), Eq. (7), and Eq. (8), it holds that $\mathrm{GAP}(\pi^{T+1})\leq\mathcal{O}(1/K)$ in the full feedback setting.
Hence, given $K=\lfloor T/T_{\sigma}\rfloor$, we can deduce that $\mathrm{GAP}(\pi^{T+1})\leq\mathcal{O}(T_{\sigma}/T)$.
Finally, taking $T_{\sigma}=\Theta(\ln T)$, we obtain the upper bound on the gap function for the full feedback setting:
$\mathrm{GAP}(\pi^{T+1})\leq\mathcal{O}(\ln 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 $\pi^{\mu,\sigma^{k(t)}}$ instead of Eq. (6) (as shown in Lemma B.1):

$$ $\displaystyle\mathbb{E}\left[\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{t+1}\right\|^ {2}\right]\leq\mathcal{O}\left(\frac{\ln t}{t-(k(t)-1)T_{\sigma}}\right).$ (9) $$

By using Eq. (9) and the assumption that $T_{\sigma}=\Theta(T^{\frac{6}{7}})$, we can still derive Eq. (7) and Eq. (8) for the noisy feedback setting.
Therefore, we conclude that:
$\mathbb{E}\left[\mathrm{GAP}(\pi^{T+1})\right]\leq\mathcal{O}(\ln T/T^{\frac{1
}{7}})$.

## 5 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, ).
The external regret is a conventional measure in online learning.
In online learning in games, the external regret for player $i$ is defined as the gap between the player’s realized cumulative payoff and the cumulative payoff of the best fixed strategy in hindsight:

$$ $\displaystyle\mathrm{Reg}_{i}(T):=\max_{x\in\mathcal{X}_{i}}\sum_{t=1}^{T} \left(v_{i}(x,\pi_{-i}^{t})-v_{i}(\pi^{t})\right).$ $$

The dynamics regret is a much stronger performance metric, which is given by:

$$ $\displaystyle\mathrm{DynamicReg}_{i}(T):=\sum_{t=1}^{T}\left(\max_{x\in \mathcal{X}_{i}}v_{i}(x,\pi_{-i}^{t})-v_{i}(\pi^{t})\right).$ $$

We show in Theorem 5.1 that the individual regret is at most $\mathcal{O}\left((\ln T)^{2}\right)$ if each player $i\in[N]$ plays according to GABP in the full feedback setting.
The proof is given in Appendix C.

###### Theorem 5.1 .

In the same setup of Theorem 4.1, we have for any player $i\in[N]$ and $T\geq 2$:

$$ $\displaystyle\mathrm{Reg}_{i}(T)\leq\mathrm{DynamicReg}_{i}(T)$ $\displaystyle\leq\mathcal{O}\left((\ln T)^{2}\right).$ $$

This regret bound is significantly superior to the $\mathcal{O}(\sqrt{T})$ regret bound of the Optimistic Gradient (OG) algorithm, and it is slightly inferior to the $\mathcal{O}(\ln T)$ regret bound of AOG (Cai and Zheng, ).

###### Theorem 5.1 .

## 6 Experiments

In this section, we present the empirical results of our GABP, comparing its performance with APGA (Abe et al., ), OG (Daskalakis et al., ; Wei et al., ), and AOG (Cai and Zheng, ).
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.e., $\mathcal{X}_{1}=\mathcal{X}_{2}=\Delta^{d}$.
All entries of the payoff matrix are drawn independently from a uniform distribution over the interval $[-1,1]$.
We set $d=50$ and the initial strategies are set to $\pi_{1}^{1}=\pi_{2}^{1}=\frac{1}{d}\mathbf{1}$.
The other is a hard concave-convex game (Ouyang and Xu, ), formulated as the following max-min optimization problem:
$\max_{x\in\mathcal{X}_{1}}\min_{y\in\mathcal{X}_{2}}f(x,y)$,
where $f(x,y)=-\frac{1}{2}x^{\top}Hx+h^{\top}x+\langle Ax-b,y\rangle$.
Following the setup in Cai and Zheng (), we choose $\mathcal{X}_{1}=\mathcal{X}_{2}=[-200,200]^{d}$ with $d=100$.
The precise terms of $H\in\mathbb{R}^{d\times d},A\in\mathbb{R}^{d\times d},b\in\mathbb{R}^{d}$, and $h\in\mathbb{R}^{d}$ are provided in Appendix D.2.
All algorithms are executed with initial strategies $\pi_{1}^{1}=\pi_{2}^{1}=\frac{1}{d}\mathbf{1}$.
The detailed hyperparameters of the algorithms, tuned for best performance, are shown in Table 1 in Appendix D.3.

Figure 1 illustrates the logarithmic $\mathrm{GAP}$ or $r^{\mathrm{tan}}$ values per iteration for two games with each feedback.
For the random payoff games with full or 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 $\xi_{i}^{t}$ is generated from the multivariate Gaussian distribution $\mathcal{N}(0,~{}0.1^{2}\mathbf{I})$ in an i.i.d. manner for both games.
In the former game with full feedback, GABP performs almost as 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 a substantial advantage over the others.

Figure 2 illustrates the dynamic regret in 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.

Figure: Figure 1: Performance of $\pi^{t}$ for GABP, APGA, OG, and AOG with full and noisy feedback in the random payoff and hard concave-convex games, respectively. The shaded area represents the standard errors. Note that we report the gap function for the random payoff game, while the tangent residual is reported for the hard concave-convex game.
Refer to caption: x1.png

Figure: Figure 2: Dynamic regret for GABP, APGA, OG, and AOG with full and noisy feedback.
Refer to caption: x2.png

## 7 Related literature

No-regret learning algorithms have been extensively studied with the intent of achieving key objectives such as average-iterate convergence or last-iterate convergence.
Recently, learning algorithms introducing optimism (Rakhlin and Sridharan, , ), such as optimistic Follow the Regularized Leader (Shalev-Shwartz and Singer, ) and optimistic Mirror Descent (Zhou et al., ; Hsieh et al., ), 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 convergence in various classes of games, including bilinear games (Daskalakis et al., ; Daskalakis and Panageas, ; Liang and Stokes, ; de Montbrun and Renault, ), cocoercive games (Lin et al., ), and saddle point problems (Daskalakis and Panageas, ; Mertikopoulos et al., ; Golowich et al., ; Wei et al., ; Lei et al., ; Yoon and Ryu, ; Lee and Kim, ; Cevher et al., ).
Recent studies have provided finite convergence rates for monotone games (Golowich et al., ; Cai et al., , ; Gorbunov et al., ; Cai and Zheng, ).

Compared to the full feedback setting, there are significant challenges in learning with noisy feedback.
For example, a learning algorithm must estimate the gradient from feedback that is contaminated by noise.
Despite the challenge, a vast literature has successfully achieved last-iterate convergence with noisy feedback in specific classes of games, including potential games (Cohen et al., ), strongly monotone games (Giannou et al., , ), and two-player zero-sum games (Abe et al., ).
These results have often leveraged unique structures of their payoff functions, such as strict (or strong) monotonicity (Bravo et al., ; Kannan and Shanbhag, ; Hsieh et al., ; Anagnostides and Panageas, ) and strict variational stability (Mertikopoulos and Zhou, ; Mertikopoulos et al., , ; Azizian et al., ).
Without these restrictions, convergence is mainly demonstrated in an asymptotic manner, with no quantification of the rate (Hsieh et al., , ; Abe et al., ).
Consequently, an exceedingly large number of iterations might be necessary to reach an equilibrium.

There have been several studies focusing on payoff-regularized learning, where each player’s payoff or utility function is perturbed or regularized via strongly convex functions (Cen et al., , ; Pattathil et al., ).
Previous studies have successfully achieved convergence to stationary points, which are approximate equilibria.
For instance, Sokota et al. () have demonstrated that their perturbed mirror descent algorithm converges to a quantal response equilibrium (McKelvey and Palfrey, , ). Similar results have been obtained with the Boltzmann Q-learning dynamics (Tuyls et al., ) and penalty-regularized dynamics (Coucheney et al., ) in continuous-time settings (Leslie and Collins, ; Abe et al., ; Hussain et al., ).
To ensure convergence toward a Nash equilibrium of the underlying game, the magnitude of perturbation requires careful adjustment.
Several learning algorithms have been proposed to gradually reduce the perturbation strength $\mu$ in response to this (Bernasconi et al., ; Liu et al., ; Cai et al., ).
These include well-studied methods such as iterative Tikhonov regularization (Facchinei and Pang, ; Koshal et al., , ; Yousefian et al., ; Tatarenko and Kamgarpour, ).
Alternatively, Perolat et al. () and Abe et al. () have employed a payoff perturbation scheme, where the magnitude of perturbation is determined by the distance from an anchoring strategy, which is periodically re-initialized by the current strategy.
Recently, Abe et al. () have established $\tilde{\mathcal{O}}(1/\sqrt{T})$ and $\tilde{\mathcal{O}}(1/T^{\frac{1}{10}})$ last-iterate convergence rates for the payoff perturbation scheme in the full/noisy feedback setting, respectively.
Our algorithm achieves faster $\tilde{\mathcal{O}}(1/T)$ and $\tilde{\mathcal{O}}(1/T^{\frac{1}{7}})$ last-iterate convergence rates by modifying the periodically re-initializing anchoring strategy scheme so that the anchoring strategy evolves more gradually.

## 8 Conclusion

This study proposes a novel payoff-perturbed algorithm, Gradient Ascent with Boosting Payoff Perturbation, which achieves $\tilde{\mathcal{O}}(1/T)$ and $\tilde{\mathcal{O}}(1/T^{\frac{1}{7}})$ 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.

## Appendix A Proofs for Theorem 4.1

### A.1 Proof of Theorem 4.1

###### Proof of Theorem 4.1 .

From the first-order optimality condition for $\pi^{t}$, we have for any $x\in\mathcal{X}$:

$$ $\displaystyle\left\langle V(\pi^{t-1})-\mu\left(\pi^{t-1}-\frac{k(t-1)\sigma^{ k(t-1)}+\sigma^{1}}{k(t-1)+1}\right)-\frac{1}{\eta}\left(\pi^{t}-\pi^{t-1} \right),\pi^{t}-x\right\rangle\geq 0,$ $$

and then $V(\pi^{t-1})-\mu\left(\pi^{t-1}-\frac{k(t-1)\sigma^{k(t-1)}+\sigma^{1}}{k(t-1)
+1}\right)-\frac{1}{\eta}\left(\pi^{t}-\pi^{t-1}\right)\in N_{\mathcal{X}}(\pi
^{t})$.
Thus, the tangent residual for $\pi^{t}$ can be bounded as:

$$ $\displaystyle r^{\mathrm{tan}}(\pi^{t})$ $\displaystyle=\min_{a\in N_{\mathcal{X}}(\pi^{t})}\left\|-V(\pi^{t})+a\right\|$ $\displaystyle\leq\left\|-V(\pi^{t})+V(\pi^{t-1})-\mu\left(\pi^{t-1}-\frac{k(t- 1)\sigma^{k(t-1)}+\sigma^{1}}{k(t-1)+1}\right)-\frac{1}{\eta}\left(\pi^{t}-\pi ^{t-1}\right)\right\|.$ $$

Letting us define

$$ $\displaystyle\pi_{i}^{\mu,\sigma^{k}}=\mathop{\rm arg~{}max}\limits_{\pi_{i} \in\mathcal{X}_{i}}\left\{v_{i}(\pi_{i},\pi_{-i}^{\mu,\sigma^{k}})-\frac{\mu}{ 2}\left\|\pi_{i}-\frac{k\sigma_{i}^{k}+\sigma_{i}^{1}}{k+1}\right\|^{2}\right\},$ $$

then we get by triangle inequality:

$$ $\displaystyle r^{\mathrm{tan}}(\pi^{t})$ $\displaystyle\leq\left\|-V(\pi^{t})+V(\pi^{t-1})-\frac{\mu}{k(t-1)+1}(\sigma^{ k(t-1)}-\sigma^{1})\right.$ $\displaystyle\left.\phantom{=}-\mu(\pi^{\mu,\sigma^{k(t-1)}}-\pi^{\mu,\sigma^{ k(t-1)}}+\pi^{t-1}-\sigma^{k(t-1)})-\frac{1}{\eta}(\pi^{t}-\pi^{t-1})\right\|$ $\displaystyle\leq\left\|-V(\pi^{t})+V(\pi^{t-1})\right\|+\frac{\mu}{k(t-1)+1} \left\|\sigma^{k(t-1)}-\sigma^{1}\right\|$ $\displaystyle\phantom{=}+\mu\left\|\pi^{\mu,\sigma^{k(t-1)}}-\sigma^{k(t-1)} \right\|+\mu\left\|\pi^{\mu,\sigma^{k(t-1)}}-\pi^{t-1}\right\|+\frac{1}{\eta} \left\|\pi^{t}-\pi^{t-1}\right\|$ $\displaystyle\leq\frac{1+\eta L}{\eta}\left\|\pi^{t}-\pi^{t-1}\right\|+\frac{ \mu D}{k(t-1)+1}$ $\displaystyle\phantom{=}+\mu\left\|\pi^{\mu,\sigma^{k(t-1)}}-\sigma^{k(t-1)} \right\|+\mu\left\|\pi^{\mu,\sigma^{k(t-1)}}-\pi^{t-1}\right\|$ $\displaystyle\leq\frac{1+\eta L}{\eta}\left\|\pi^{\mu,\sigma^{k(t-1)}}-\pi^{t} \right\|+\frac{\mu D}{k(t-1)+1}+\mu\left\|\pi^{\mu,\sigma^{k(t-1)}}-\sigma^{k( t-1)}\right\|$ $\displaystyle\phantom{=}+\left(\mu+\frac{1+\eta L}{\eta}\right)\left\|\pi^{\mu ,\sigma^{k(t-1)}}-\pi^{t-1}\right\|.$ (10) $$

In terms of upper bound on $\left\|\pi^{\mu,\sigma^{k(t-1)}}-\pi^{t}\right\|$ and $\left\|\pi^{\mu,\sigma^{k(t-1)}}-\pi^{t-1}\right\|$, we introduce the following lemma:

###### Lemma A.1 .

If we use the constant learning rate $\eta_{t}=\eta\in(0,\frac{\mu}{(L+\mu)^{2}})$, we have for any $t\geq 1$:

$$ $\displaystyle\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{t}\right\|^{2}\leq\left(\frac {1}{1+\eta\mu}\right)^{t-(k(t)-1)T_{\sigma}-1}\left\|\pi^{\mu,\sigma^{k(t)}}- \sigma^{k(t)}\right\|^{2},$ $\displaystyle\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{t+1}\right\|^{2}\leq\left( \frac{1}{1+\eta\mu}\right)^{t-(k(t)-1)T_{\sigma}}\left\|\pi^{\mu,\sigma^{k(t)} }-\sigma^{k(t)}\right\|^{2}.$ $$

Combining Eq. (10) and Lemma A.1, we have:

$$ $\displaystyle r^{\mathrm{tan}}(\pi^{t})\leq 2\left(\mu+\frac{1+\eta L}{\eta} \right)\left\|\pi^{\mu,\sigma^{k(t-1)}}-\sigma^{k(t-1)}\right\|+\frac{\mu D}{k (t-1)+1}.$ (11) $$

Next, we derive the following upper bound on $\left\|\pi^{\mu,\sigma^{k(t-1)}}-\sigma^{k(t-1)}\right\|$:

###### Lemma A.2 .

If we set $\eta_{t}=\eta\in(0,\frac{\mu}{(L+\mu)^{2}})$ and $T_{\sigma}\geq\max(1,\frac{6\ln 3(T+1)}{\ln(1+\eta\mu)})$, we have for any $t\geq 1$:

$$ $\displaystyle\left\|\pi^{\mu,\sigma^{k(t)}}-\sigma^{k(t)}\right\|\leq\frac{8D} {k(t)+1}.$ $$

By combining Eq. (11) and Lemma A.2, we get:

$$ $\displaystyle r^{\mathrm{tan}}(\pi^{t})$ $\displaystyle\leq\frac{16D}{k(t-1)+1}\left(\mu+\frac{1+\eta L}{\eta}\right)+ \frac{\mu D}{k(t-1)+1}$ $\displaystyle\leq\frac{17D}{k(t-1)+1}\left(\mu+\frac{1+\eta L}{\eta}\right).$ $$

Therefore, since $k(t)=\lfloor\frac{t-1}{T_{\sigma}}\rfloor+1$, it holds that:

$$ $\displaystyle r^{\mathrm{tan}}(\pi^{t})$ $\displaystyle\leq\frac{17DT_{\sigma}}{t+T_{\sigma}-2}\left(\mu+\frac{1+\eta L} {\eta}\right).$ $$

Finally, taking $T_{\sigma}=c\cdot\max(1,\frac{6\ln 3(T+1)}{\ln(1+\eta\mu)})$, we have:

$$ $\displaystyle r^{\mathrm{tan}}(\pi^{t})$ $\displaystyle\leq\frac{17cD\left(\frac{6\ln 3(T+1)}{\ln(1+\eta\mu)}+1\right)}{ t-1}\left(\mu+\frac{1+\eta L}{\eta}\right).$ $$

∎

###### Proof of Theorem 4.1 .

###### Lemma A.1 .

###### Lemma A.2 .

### A.2 Proof of Lemma A.1

###### Proof of Lemma A.1 .

First, we have for any three vectors $a,b,c$:

$$ $\displaystyle\frac{1}{2}\left\|a-b\right\|^{2}-\frac{1}{2}\left\|a-c\right\|^{ 2}+\frac{1}{2}\left\|b-c\right\|^{2}=\left\langle c-b,a-b\right\rangle.$ $$

Thus, we have for any $t\geq 1$:

$$ $\displaystyle\frac{1}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{t+1}\right\|^{2}- \frac{1}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{t}\right\|^{2}+\frac{1}{2}\left \|\pi^{t+1}-\pi^{t}\right\|^{2}=\left\langle\pi^{t}-\pi^{t+1},\pi^{\mu,\sigma^ {k(t)}}-\pi^{t+1}\right\rangle.$ (12) $$

Here, let us define $\hat{\sigma}^{k(t)}=\frac{k(t)\sigma^{k(t)}+\sigma^{1}}{k(t)+1}$.
Then, from the first-order optimality condition for $\pi^{t+1}$, we have for any $t\geq 1$:

$$ $\displaystyle\left\langle\eta\left(V(\pi^{t})-\mu\left(\pi^{t}-\hat{\sigma}^{k (t)}\right)\right)-\pi^{t+1}+\pi^{t},\pi^{t+1}-\pi^{\mu,\sigma^{k(t)}}\right \rangle\geq 0.$ (13) $$

Similarly, from the first-order optimality condition for $\pi^{\mu,\sigma^{k(t)}}$, we get:

$$ $\displaystyle\left\langle V(\pi^{\mu,\sigma^{k(t)}})-\mu\left(\pi^{\mu,\sigma^ {k(t)}}-\hat{\sigma}^{k(t)}\right),\pi^{\mu,\sigma^{k(t)}}-\pi^{t+1}\right \rangle\geq 0.$ (14) $$

Combining Eq. (12), Eq. (13), and Eq. (14) yields:

$$ $\displaystyle\frac{1}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{t+1}\right\|^{2}- \frac{1}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{t}\right\|^{2}+\frac{1}{2}\left \|\pi^{t+1}-\pi^{t}\right\|^{2}$ $\displaystyle\leq\eta\left\langle V(\pi^{t})-\mu\left(\pi^{t}-\hat{\sigma}^{k( t)}\right),\pi^{t+1}-\pi^{\mu,\sigma^{k(t)}}\right\rangle$ $\displaystyle=\eta\left\langle V(\pi^{t+1})-\mu\left(\pi^{t+1}-\hat{\sigma}^{k (t)}\right),\pi^{t+1}-\pi^{\mu,\sigma^{k(t)}}\right\rangle$ $\displaystyle\phantom{=}+\eta\left\langle V(\pi^{t})-V(\pi^{t+1})-\mu\left(\pi ^{t}-\pi^{t+1}\right),\pi^{t+1}-\pi^{\mu,\sigma^{k(t)}}\right\rangle$ $\displaystyle\leq\eta\left\langle V(\pi^{\mu,\sigma^{k(t)}})-\mu\left(\pi^{t+1 }-\hat{\sigma}^{k(t)}\right),\pi^{t+1}-\pi^{\mu,\sigma^{k(t)}}\right\rangle$ $\displaystyle\phantom{=}+\eta\left\langle V(\pi^{t})-V(\pi^{t+1})-\mu\left(\pi ^{t}-\pi^{t+1}\right),\pi^{t+1}-\pi^{\mu,\sigma^{k(t)}}\right\rangle$ $\displaystyle=\eta\left\langle V(\pi^{\mu,\sigma^{k(t)}})-\mu\left(\pi^{\mu, \sigma^{k(t)}}-\hat{\sigma}^{k(t)}\right),\pi^{t+1}-\pi^{\mu,\sigma^{k(t)}} \right\rangle-\eta\mu\left\|\pi^{t+1}-\pi^{\mu,\sigma^{k(t)}}\right\|^{2}$ $\displaystyle\phantom{=}+\eta\left\langle V(\pi^{t})-V(\pi^{t+1})-\mu\left(\pi ^{t}-\pi^{t+1}\right),\pi^{t+1}-\pi^{\mu,\sigma^{k(t)}}\right\rangle$ $\displaystyle\leq-\eta\mu\left\|\pi^{t+1}-\pi^{\mu,\sigma^{k(t)}}\right\|^{2}+ \eta\left\langle V(\pi^{t})-V(\pi^{t+1})-\mu\left(\pi^{t}-\pi^{t+1}\right),\pi ^{t+1}-\pi^{\mu,\sigma^{k(t)}}\right\rangle,$ (15) $$

where the second inequality follows from Eq. (1).
From Cauchy-Schwarz inequality and Young’s inequality, the second term in the right-hand side of this inequality can be bounded by:

$$ $\displaystyle\eta\left\langle V(\pi^{t})-V(\pi^{t+1})-\mu\left(\pi^{t}-\pi^{t+ 1}\right),\pi^{t+1}-\pi^{\mu,\sigma^{k(t)}}\right\rangle$ $\displaystyle=\eta\left\langle V(\pi^{t})-V(\pi^{t+1}),\pi^{t+1}-\pi^{\mu, \sigma^{k(t)}}\right\rangle-\eta\mu\left\langle\pi^{t}-\pi^{t+1},\pi^{t+1}-\pi ^{\mu,\sigma^{k(t)}}\right\rangle$ $\displaystyle\leq\eta\left(\left\|V(\pi^{t})-V(\pi^{t+1})\right\|+\mu\left\| \pi^{t}-\pi^{t+1}\right\|\right)\cdot\left\|\pi^{t+1}-\pi^{\mu,\sigma^{k(t)}}\right\|$ $\displaystyle\leq\eta(L+\mu)\left\|\pi^{t}-\pi^{t+1}\right\|\cdot\left\|\pi^{t +1}-\pi^{\mu,\sigma^{k(t)}}\right\|$ $\displaystyle\leq\frac{1}{2}\left\|\pi^{t}-\pi^{t+1}\right\|^{2}+\frac{\eta^{2 }(L+\mu)^{2}}{2}\left\|\pi^{t+1}-\pi^{\mu,\sigma^{k(t)}}\right\|^{2}$ $\displaystyle\leq\frac{1}{2}\left\|\pi^{t}-\pi^{t+1}\right\|^{2}+\frac{\eta\mu }{2}\left\|\pi^{t+1}-\pi^{\mu,\sigma^{k(t)}}\right\|^{2},$ (16) $$

where the second inequality follow from Eq. (2), and the last inequality follows from the assumption that $\eta\leq\frac{\mu}{(L+\mu)^{2}}$.
By combining Eq. (15) and Eq. (16), we get:

$$ $\displaystyle\frac{1}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{t+1}\right\|^{2}- \frac{1}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{t}\right\|^{2}+\frac{1}{2}\left \|\pi^{t+1}-\pi^{t}\right\|^{2}$ $\displaystyle\leq-\frac{\eta\mu}{2}\left\|\pi^{t+1}-\pi^{\mu,\sigma^{k(t)}} \right\|^{2}+\frac{1}{2}\left\|\pi^{t}-\pi^{t+1}\right\|^{2}.$ $$

Thus,

$$ $\displaystyle\frac{1+\eta\mu}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{t+1}\right \|^{2}\leq\frac{1}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{t}\right\|^{2}.$ $$

Therefore, we have for any $t\geq 1$:

$$ $\displaystyle\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{t+1}\right\|^{2}$ $\displaystyle\leq\frac{1}{1+\eta\mu}\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{t} \right\|^{2}.$ $$

Furthermore, since $k(s)=k(t)$ for $s\in[(k(t)-1)T_{\sigma}+1,t]$, we have for such $s$ that:

$$ $\displaystyle\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{s+1}\right\|^{2}$ $\displaystyle\leq\frac{1}{1+\eta\mu}\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{s} \right\|^{2}.$ $$

Therefore, by applying this inequality from $t,t-1,\cdots,(k(t)-1)T_{\sigma}+1$, we get for any $t\geq 1$:

$$ $\displaystyle\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{t+1}\right\|^{2}$ $\displaystyle\leq\left(\frac{1}{1+\eta\mu}\right)^{t-(k(t)-1)T_{\sigma}}\left \|\pi^{\mu,\sigma^{k(t)}}-\pi^{(k(t)-1)T_{\sigma}+1}\right\|^{2}$ $\displaystyle=\left(\frac{1}{1+\eta\mu}\right)^{t-(k(t)-1)T_{\sigma}}\left\| \pi^{\mu,\sigma^{k(t)}}-\sigma^{k(t)}\right\|^{2}.$ (17) $$

Here, since $k(t)=k(t+1)$ when $t$ satisfies that $t\neq T_{\sigma}\left\lfloor\frac{t}{T_{\sigma}}\right\rfloor$, we have for such $t$ that:

$$ $\displaystyle\left\|\pi^{\mu,\sigma^{k(t+1)}}-\pi^{t+1}\right\|^{2}$ $\displaystyle\leq\left(\frac{1}{1+\eta\mu}\right)^{t-(k(t+1)-1)T_{\sigma}} \left\|\pi^{\mu,\sigma^{k(t+1)}}-\sigma^{k(t+1)}\right\|^{2}.$ (18) $$

On the other hand, when $t$ satisfies that $t=T_{\sigma}\left\lfloor\frac{t}{T_{\sigma}}\right\rfloor$:

$$ $\displaystyle k(t+1)=\left\lfloor\frac{T_{\sigma}\left\lfloor\frac{t}{T_{ \sigma}}\right\rfloor+1-1}{T_{\sigma}}\right\rfloor+1=\left\lfloor\frac{t}{T_{ \sigma}}\right\rfloor+1$ $\displaystyle\Rightarrow(k(t+1)-1)T_{\sigma}=T_{\sigma}\left\lfloor\frac{t}{T_ {\sigma}}\right\rfloor=t$ $\displaystyle\Rightarrow\pi^{t+1}=\pi^{(k(t+1)-1)T_{\sigma}+1}=\sigma^{k(t+1)}.$ $$

Therefore, we have for any $t\geq 1$ such that $t=T_{\sigma}\left\lfloor\frac{t}{T_{\sigma}}\right\rfloor$:

$$ $\displaystyle\left\|\pi^{\mu,\sigma^{k(t+1)}}-\pi^{t+1}\right\|^{2}$ $\displaystyle=\left\|\pi^{\mu,\sigma^{k(t+1)}}-\sigma^{k(t+1)}\right\|^{2}$ $\displaystyle=\left(\frac{1}{1+\eta\mu}\right)^{t-(k(t+1)-1)T_{\sigma}}\left\| \pi^{\mu,\sigma^{k(t+1)}}-\sigma^{k(t+1)}\right\|^{2}.$ (19) $$

By combining Eq. (17), Eq. (18), and Eq. (19), we have for any $t\geq 1$:

$$ $\displaystyle\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{t+1}\right\|^{2}$ $\displaystyle\leq\left(\frac{1}{1+\eta\mu}\right)^{t-(k(t)-1)T_{\sigma}}\left \|\pi^{\mu,\sigma^{k(t)}}-\sigma^{k(t)}\right\|^{2},$ $\displaystyle\left\|\pi^{\mu,\sigma^{k(t+1)}}-\pi^{t+1}\right\|^{2}$ $\displaystyle\leq\left(\frac{1}{1+\eta\mu}\right)^{t-(k(t+1)-1)T_{\sigma}} \left\|\pi^{\mu,\sigma^{k(t+1)}}-\sigma^{k(t+1)}\right\|^{2}.$ $$

∎

###### Proof of Lemma A.1 .

### A.3 Proof of Lemma A.2

###### Proof of Lemma A.2 .

First, we have for any Nash equilibrium $\pi^{\ast}\in\Pi^{\ast}$ and $t\geq 1$ such that $k(t)\geq 1$:

$$ $\displaystyle\frac{(k(t)+1)(k(t)+2)}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\hat{ \sigma}^{k(t)}\right\|^{2}+(k(t)+1)(k(t)+2)\left\langle\hat{\sigma}^{k(t)+1}- \pi^{\mu,\sigma^{k(t)}},\pi^{\mu,\sigma^{k(t)}}-\hat{\sigma}^{k(t)}\right\rangle$ $\displaystyle=\frac{(k(t)+1)(k(t)+2)}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\hat{ \sigma}^{k(t)}\right\|^{2}$ $\displaystyle\phantom{=}+(k(t)+1)\left\langle(k(t)+1)\sigma^{k(t)+1}+\sigma^{1 }-(k(t)+2)\pi^{\mu,\sigma^{k(t)}},\pi^{\mu,\sigma^{k(t)}}-\hat{\sigma}^{k(t)}\right\rangle$ $\displaystyle=\frac{(k(t)+1)(k(t)+2)}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\hat{ \sigma}^{k(t)}\right\|^{2}+(k(t)+1)\left\langle\sigma^{1}-\sigma^{k(t)+1},\pi^ {\mu,\sigma^{k(t)}}-\hat{\sigma}^{k(t)}\right\rangle$ $\displaystyle\phantom{=}+(k(t)+1)(k(t)+2)\left\langle\sigma^{k(t)+1}-\pi^{\mu, \sigma^{k(t)}},\pi^{\mu,\sigma^{k(t)}}-\hat{\sigma}^{k(t)}\right\rangle$ $\displaystyle=\frac{(k(t)+1)(k(t)+2)}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\hat{ \sigma}^{k(t)}\right\|^{2}+(k(t)+1)\left\langle\sigma^{1}-\pi^{\mu,\sigma^{k(t )}},\pi^{\mu,\sigma^{k(t)}}-\hat{\sigma}^{k(t)}\right\rangle$ $\displaystyle\phantom{=}+(k(t)+1)^{2}\left\langle\sigma^{k(t)+1}-\pi^{\mu, \sigma^{k(t)}},\pi^{\mu,\sigma^{k(t)}}-\hat{\sigma}^{k(t)}\right\rangle$ $\displaystyle=\frac{(k(t)+1)(k(t)+2)}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\hat{ \sigma}^{k(t)}\right\|^{2}+(k(t)+1)\left\langle\sigma^{1}-\pi^{\ast},\pi^{\mu, \sigma^{k(t)}}-\hat{\sigma}^{k(t)}\right\rangle$ $\displaystyle\phantom{=}+(k(t)+1)\left\langle\pi^{\ast}-\pi^{\mu,\sigma^{k(t)} },\pi^{\mu,\sigma^{k(t)}}-\hat{\sigma}^{k(t)}\right\rangle+(k(t)+1)^{2}\left \langle\sigma^{k(t)+1}-\pi^{\mu,\sigma^{k(t)}},\pi^{\mu,\sigma^{k(t)}}-\hat{ \sigma}^{k(t)}\right\rangle.$ $$

Here, the first-order optimality condition for $\pi^{\mu,\sigma^{k(t)}}$:

$$ $\displaystyle\left\langle V(\pi^{\mu,\sigma^{k(t)}})-\mu\left(\pi^{\mu,\sigma^ {k(t)}}-\hat{\sigma}^{k(t)}\right),\pi^{\mu,\sigma^{k(t)}}-\pi^{\ast}\right \rangle\geq 0$ $\displaystyle\Rightarrow\left\langle\pi^{\mu,\sigma^{k(t)}}-\hat{\sigma}^{k(t) },\pi^{\ast}-\pi^{\mu,\sigma^{k(t)}}\right\rangle\geq\frac{1}{\mu}\left\langle V (\pi^{\mu,\sigma^{k(t)}}),\pi^{\ast}-\pi^{\mu,\sigma^{k(t)}}\right\rangle\geq \frac{1}{\mu}\left\langle V(\pi^{\ast}),\pi^{\ast}-\pi^{\mu,\sigma^{k(t)}} \right\rangle\geq 0,$ $$

where we use Eq. (1) and the fact that $\pi^{\ast}$ is a Nash equilibrium.
Combining these inequalities yields:

$$ $\displaystyle\frac{(k(t)+1)(k(t)+2)}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\hat{ \sigma}^{k(t)}\right\|^{2}+(k(t)+1)(k(t)+2)\left\langle\hat{\sigma}^{k(t)+1}- \pi^{\mu,\sigma^{k(t)}},\pi^{\mu,\sigma^{k(t)}}-\hat{\sigma}^{k(t)}\right\rangle$ $\displaystyle\geq\frac{(k(t)+1)(k(t)+2)}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\hat {\sigma}^{k(t)}\right\|^{2}+(k(t)+1)\left\langle\sigma^{1}-\pi^{\ast},\pi^{\mu ,\sigma^{k(t)}}-\hat{\sigma}^{k(t)}\right\rangle$ $\displaystyle\phantom{=}+(k(t)+1)^{2}\left\langle\sigma^{k(t)+1}-\pi^{\mu, \sigma^{k(t)}},\pi^{\mu,\sigma^{k(t)}}-\hat{\sigma}^{k(t)}\right\rangle.$ $$

From Young’s inequality, we have for any $\rho_{1},\rho_{2}>0$:

$$ $\displaystyle\frac{(k(t)+1)(k(t)+2)}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\hat{ \sigma}^{k(t)}\right\|^{2}+(k(t)+1)(k(t)+2)\left\langle\hat{\sigma}^{k(t)+1}- \pi^{\mu,\sigma^{k(t)}},\pi^{\mu,\sigma^{k(t)}}-\hat{\sigma}^{k(t)}\right\rangle$ $\displaystyle\geq\frac{(k(t)+1)(k(t)+2)}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\hat {\sigma}^{k(t)}\right\|^{2}-\frac{\rho_{1}(k(t)+1)}{2}\left\|\sigma^{1}-\pi^{ \ast}\right\|^{2}-\frac{(k(t)+1)}{2\rho_{1}}\left\|\pi^{\mu,\sigma^{k(t)}}- \hat{\sigma}^{k(t)}\right\|^{2}$ $\displaystyle\phantom{=}-\frac{\rho_{2}(k(t)+1)^{2}}{2}\left\|\sigma^{k(t)+1}- \pi^{\mu,\sigma^{k(t)}}\right\|^{2}-\frac{(k(t)+1)^{2}}{2\rho_{2}}\left\|\pi^{ \mu,\sigma^{k(t)}}-\hat{\sigma}^{k(t)}\right\|^{2}$ $\displaystyle=\left(\frac{(k(t)+1)(k(t)+2)}{2}-\frac{k(t)+1}{2\rho_{1}}-\frac{ (k(t)+1)^{2}}{2\rho_{2}}\right)\left\|\pi^{\mu,\sigma^{k(t)}}-\hat{\sigma}^{k( t)}\right\|^{2}$ $\displaystyle\phantom{=}-\frac{\rho_{1}(k(t)+1)}{2}\left\|\sigma^{1}-\pi^{\ast }\right\|^{2}-\frac{\rho_{2}(k(t)+1)^{2}}{2}\left\|\sigma^{k(t)+1}-\pi^{\mu, \sigma^{k(t)}}\right\|^{2}.$ $$

By setting $\rho_{1}=\frac{4}{k(t)+2},\rho_{2}=\frac{4(k(t)+1)}{k(t)+2}$, we obtain:

$$ $\displaystyle\frac{(k(t)+1)(k(t)+2)}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\hat{ \sigma}^{k(t)}\right\|^{2}+(k(t)+1)(k(t)+2)\left\langle\hat{\sigma}^{k(t)+1}- \pi^{\mu,\sigma^{k(t)}},\pi^{\mu,\sigma^{k(t)}}-\hat{\sigma}^{k(t)}\right\rangle$ $\displaystyle\geq\frac{(k(t)+1)(k(t)+2)}{4}\left\|\pi^{\mu,\sigma^{k(t)}}-\hat {\sigma}^{k(t)}\right\|^{2}-\frac{2(k(t)+1)}{k(t)+2}\left\|\sigma^{1}-\pi^{ \ast}\right\|^{2}$ $\displaystyle\phantom{=}-\frac{2(k(t)+1)^{3}}{k(t)+2}\left\|\sigma^{k(t)+1}- \pi^{\mu,\sigma^{k(t)}}\right\|^{2}$ $\displaystyle\geq\frac{(k(t)+1)(k(t)+2)}{4}\left\|\pi^{\mu,\sigma^{k(t)}}-\hat {\sigma}^{k(t)}\right\|^{2}-2\left\|\sigma^{1}-\pi^{\ast}\right\|^{2}-2(k(t)+1 )^{2}\left\|\sigma^{k(t)+1}-\pi^{\mu,\sigma^{k(t)}}\right\|^{2}.$ (20) $$

Here, we introduce the following lemma:

###### Lemma A.3 .

For any $t\geq 1$ such that $k(t)\geq 2$, we have:

$$ $\displaystyle\frac{(k(t)+1)(k(t)+2)}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\hat{ \sigma}^{k(t)}\right\|^{2}+(k(t)+1)(k(t)+2)\left\langle\hat{\sigma}^{k(t)+1}- \pi^{\mu,\sigma^{k(t)}},\pi^{\mu,\sigma^{k(t)}}-\hat{\sigma}^{k(t)}\right\rangle$ $\displaystyle\leq\frac{k(t)(k(t)+1)}{2}\left\|\pi^{\mu,\sigma^{k(t)-1}}-\hat{ \sigma}^{k(t)-1}\right\|^{2}+k(t)(k(t)+1)\left\langle\hat{\sigma}^{k(t)}-\pi^{ \mu,\sigma^{k(t)-1}},\pi^{\mu,\sigma^{k(t)-1}}-\hat{\sigma}^{k(t)-1}\right\rangle$ $\displaystyle\phantom{=}+(k(t)+1)\left\langle(k(t)+1)(\pi^{\mu,\sigma^{k(t)}}- \sigma^{k(t)+1})+k(t)(\sigma^{k(t)}-\pi^{\mu,\sigma^{k(t)-1}}),\hat{\sigma}^{k (t)}-\pi^{\mu,\sigma^{k(t)}}\right\rangle.$ $$

By combining Eq. (20) and Lemma A.3, we get:

$$ $\displaystyle\frac{(k(t)+1)(k(t)+2)}{4}\left\|\pi^{\mu,\sigma^{k(t)}}-\hat{ \sigma}^{k(t)}\right\|^{2}$ $\displaystyle\leq\frac{(k(t)+1)(k(t)+2)}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\hat {\sigma}^{k(t)}\right\|^{2}+(k(t)+1)(k(t)+2)\left\langle\hat{\sigma}^{k(t)+1}- \pi^{\mu,\sigma^{k(t)}},\pi^{\mu,\sigma^{k(t)}}-\hat{\sigma}^{k(t)}\right\rangle$ $\displaystyle\phantom{=}+2\left\|\sigma^{1}-\pi^{\ast}\right\|^{2}+2(k(t)+1)^{ 2}\left\|\sigma^{k(t)+1}-\pi^{\mu,\sigma^{k(t)}}\right\|^{2}$ $\displaystyle\leq 3\left\|\pi^{\mu,\sigma^{1}}-\hat{\sigma}^{1}\right\|^{2}+6 \left\langle\hat{\sigma}^{2}-\pi^{\mu,\sigma^{1}},\pi^{\mu,\sigma^{1}}-\hat{ \sigma}^{1}\right\rangle+2\left\|\sigma^{1}-\pi^{\ast}\right\|^{2}+2(k(t)+1)^{ 2}\left\|\sigma^{k(t)+1}-\pi^{\mu,\sigma^{k(t)}}\right\|^{2}$ $\displaystyle\phantom{=}+\sum_{l=2}^{k(t)}(l+1)\left\langle(l+1)(\pi^{\mu, \sigma^{l}}-\sigma^{l+1})+l(\sigma^{l}-\pi^{\mu,\sigma^{l-1}}),\hat{\sigma}^{l }-\pi^{\mu,\sigma^{l}}\right\rangle$ $\displaystyle=3\left\|\pi^{\mu,\sigma^{1}}-\sigma^{1}\right\|^{2}+2\left \langle 2\sigma^{2}+\sigma^{1}-3\pi^{\mu,\sigma^{1}},\pi^{\mu,\sigma^{1}}- \sigma^{1}\right\rangle+2\left\|\sigma^{1}-\pi^{\ast}\right\|^{2}$ $\displaystyle\phantom{=}+2(k(t)+1)^{2}\left\|\sigma^{k(t)+1}-\pi^{\mu,\sigma^{ k(t)}}\right\|^{2}+\sum_{l=2}^{k(t)}(l+1)\left\langle(l+1)(\pi^{\mu,\sigma^{l} }-\sigma^{l+1})+l(\sigma^{l}-\pi^{\mu,\sigma^{l-1}}),\hat{\sigma}^{l}-\pi^{\mu ,\sigma^{l}}\right\rangle$ $\displaystyle=3\left\|\pi^{\mu,\sigma^{1}}-\sigma^{1}\right\|^{2}+2\left \langle\sigma^{1}-\pi^{\mu,\sigma^{1}},\pi^{\mu,\sigma^{1}}-\sigma^{1}\right \rangle+4\left\langle\sigma^{2}-\pi^{\mu,\sigma^{1}},\pi^{\mu,\sigma^{1}}- \sigma^{1}\right\rangle$ $\displaystyle\phantom{=}+2\left\|\sigma^{1}-\pi^{\ast}\right\|^{2}+2(k(t)+1)^{ 2}\left\|\sigma^{k(t)+1}-\pi^{\mu,\sigma^{k(t)}}\right\|^{2}$ $\displaystyle\phantom{=}+\sum_{l=2}^{k(t)}(l+1)\left\langle(l+1)(\pi^{\mu, \sigma^{l}}-\sigma^{l+1})+l(\sigma^{l}-\pi^{\mu,\sigma^{l-1}}),\hat{\sigma}^{l }-\pi^{\mu,\sigma^{l}}\right\rangle$ $\displaystyle=\left\|\pi^{\mu,\sigma^{1}}-\sigma^{1}\right\|^{2}+4\left\langle \sigma^{2}-\pi^{\mu,\sigma^{1}},\pi^{\mu,\sigma^{1}}-\sigma^{1}\right\rangle+2 \left\|\sigma^{1}-\pi^{\ast}\right\|^{2}+2(k(t)+1)^{2}\left\|\sigma^{k(t)+1}- \pi^{\mu,\sigma^{k(t)}}\right\|^{2}$ $\displaystyle\phantom{=}+\sum_{l=2}^{k(t)}(l+1)\left\langle(l+1)(\pi^{\mu, \sigma^{l}}-\sigma^{l+1})+l(\sigma^{l}-\pi^{\mu,\sigma^{l-1}}),\hat{\sigma}^{l }-\pi^{\mu,\sigma^{l}}\right\rangle$ $\displaystyle=\left\|\pi^{\mu,\sigma^{1}}-\sigma^{1}\right\|^{2}+2\left\| \sigma^{1}-\pi^{\ast}\right\|^{2}+2(k(t)+1)^{2}\left\|\sigma^{k(t)+1}-\pi^{\mu ,\sigma^{k(t)}}\right\|^{2}$ $\displaystyle\phantom{=}+\sum_{l=1}^{k(t)}(l+1)^{2}\left\langle\pi^{\mu,\sigma ^{l}}-\sigma^{l+1},\hat{\sigma}^{l}-\pi^{\mu,\sigma^{l}}\right\rangle+\sum_{l= 2}^{k(t)}l(l+1)\left\langle\sigma^{l}-\pi^{\mu,\sigma^{l-1}},\hat{\sigma}^{l}- \pi^{\mu,\sigma^{l}}\right\rangle$ $\displaystyle\leq 3D^{2}+2(k(t)+1)^{2}\left\|\sigma^{k(t)+1}-\pi^{\mu,\sigma^{ k(t)}}\right\|^{2}+2D(k(t)+1)^{2}\sum_{l=1}^{k(t)}\left\|\pi^{\mu,\sigma^{l}}- \sigma^{l+1}\right\|.$ $$

Therefore, we have for any $t\geq 1$ such that $k(t)\geq 2$:

$$ $\displaystyle\left\|\pi^{\mu,\sigma^{k(t)}}-\hat{\sigma}^{k(t)}\right\|^{2} \leq\frac{12D^{2}}{(k(t)+1)^{2}}+8\left\|\sigma^{k(t)+1}-\pi^{\mu,\sigma^{k(t) }}\right\|^{2}+8D\sum_{l=1}^{k(t)}\left\|\pi^{\mu,\sigma^{l}}-\sigma^{l+1} \right\|.$ $$

By the definition of $\hat{\sigma}^{k(t)}$,

$$ $\displaystyle\left\|\pi^{\mu,\sigma^{k(t)}}-\sigma^{k(t)}\right\|^{2}+\frac{ \left\|\sigma^{k(t)}-\sigma^{1}\right\|^{2}}{(k(t)+1)^{2}}+\frac{2}{k(t)+1} \left\langle\pi^{\mu,\sigma^{k(t)}}-\sigma^{k(t)},\sigma^{k(t)}-\sigma^{1}\right\rangle$ $\displaystyle\leq\frac{12D^{2}}{(k(t)+1)^{2}}+8\left\|\sigma^{k(t)+1}-\pi^{\mu ,\sigma^{k(t)}}\right\|^{2}+8D\sum_{l=1}^{k(t)}\left\|\pi^{\mu,\sigma^{l}}- \sigma^{l+1}\right\|.$ $$

Therefore, from Cauchy-Schwarz inequality, we have:

$$ $\displaystyle\left\|\pi^{\mu,\sigma^{k(t)}}-\sigma^{k(t)}\right\|^{2}$ $\displaystyle\leq\frac{2}{k(t)+1}\left\langle\pi^{\mu,\sigma^{k(t)}}-\sigma^{k (t)},\sigma^{1}-\sigma^{k(t)}\right\rangle+\frac{12D^{2}}{(k(t)+1)^{2}}$ $\displaystyle\phantom{=}+8\left\|\sigma^{k(t)+1}-\pi^{\mu,\sigma^{k(t)}}\right \|^{2}+8D\sum_{l=1}^{k(t)}\left\|\pi^{\mu,\sigma^{l}}-\sigma^{l+1}\right\|$ $\displaystyle\leq\frac{2D}{k(t)+1}\left\|\pi^{\mu,\sigma^{k(t)}}-\sigma^{k(t)} \right\|+\frac{12D^{2}}{(k(t)+1)^{2}}+8\left\|\sigma^{k(t)+1}-\pi^{\mu,\sigma^ {k(t)}}\right\|^{2}+8D\sum_{l=1}^{k(t)}\left\|\pi^{\mu,\sigma^{l}}-\sigma^{l+1 }\right\|.$ (21) $$

Furthermore, from Lemma A.1, we have for any $k\geq 1$:

$$ $\displaystyle\left\|\pi^{\mu,\sigma^{k}}-\sigma^{k+1}\right\|^{2}$ $\displaystyle\leq\left(\frac{1}{1+\eta\mu}\right)^{T_{\sigma}}\left\|\pi^{\mu, \sigma^{k}}-\sigma^{k}\right\|^{2}.$ (22) $$

Combining Eq. (21) nad Eq. (22), we have for any $t\geq 1$ such that $k(t)\geq 2$:

$$ $\displaystyle\left\|\pi^{\mu,\sigma^{k(t)}}-\sigma^{k(t)}\right\|^{2}$ $\displaystyle\leq\frac{2D}{k(t)+1}\left\|\pi^{\mu,\sigma^{k(t)}}-\sigma^{k(t)} \right\|+\frac{12D^{2}}{(k(t)+1)^{2}}$ $\displaystyle\phantom{=}+8\left(\frac{1}{1+\eta\mu}\right)^{T_{\sigma}}\left\| \pi^{\mu,\sigma^{k(t)}}-\sigma^{k(t)}\right\|^{2}+8D^{2}k(t)\left(\frac{1}{1+ \eta\mu}\right)^{\frac{T_{\sigma}}{2}}.$ $$

Therefore, since $T_{\sigma}\geq\max(1,\frac{6\ln 3(T+1)}{\ln(1+\eta\mu)})\Rightarrow\left(\frac
{1}{1+\eta\mu}\right)^{T_{\sigma}}\leq\frac{(k(t)+1)^{3}}{(1+\eta\mu)^{T_{
\sigma}}}\leq\frac{1}{16}$, we have for $k(t)\geq 2$:

$$ $\displaystyle\frac{1}{2}\left(\left\|\pi^{\mu,\sigma^{k(t)}}-\sigma^{k(t)} \right\|-\frac{2D}{k(t)+1}\right)^{2}\leq\frac{2D^{2}}{(k(t)+1)^{2}}+\frac{12D ^{2}}{(k(t)+1)^{2}}+\frac{D^{2}}{2(k(t)+1)^{2}}\leq\frac{16D^{2}}{(k(t)+1)^{2}},$ $$

and then:

$$ $\displaystyle\left\|\pi^{\mu,\sigma^{k(t)}}-\sigma^{k(t)}\right\|\leq\frac{2D} {k(t)+1}+\frac{4\sqrt{2}D}{k(t)+1}\leq\frac{8D}{k(t)+1}.$ $$

On the other hand, for $k(t)=1$, we have:

$$ $\displaystyle\left\|\pi^{\mu,\sigma^{1}}-\sigma^{1}\right\|\leq D\leq\frac{8D} {1+1}.$ $$

In summary, for any $t\geq 1$, we have:

$$ $\displaystyle\left\|\pi^{\mu,\sigma^{k(t)}}-\sigma^{k(t)}\right\|\leq\frac{8D} {k(t)+1}.$ $$

∎

###### Proof of Lemma A.2 .

###### Lemma A.3 .

### A.4 Proof of Lemma A.3

###### Proof of Lemma A.3 .

From the first-order optimality condition for $\pi^{\mu,\sigma^{k(t)}}$, we have:

$$ $\displaystyle\left\langle V(\pi^{\mu,\sigma^{k(t)}})-\mu(\pi^{\mu,\sigma^{k(t) }}-\hat{\sigma}^{k(t)}),\pi^{\mu,\sigma^{k(t)}}-\pi^{\mu,\sigma^{k(t)-1}} \right\rangle\geq 0.$ $$

Similarly, from the first-order optimality condition for $\pi^{\mu,\sigma^{k(t)-1}}$, we have:

$$ $\displaystyle\left\langle V(\pi^{\mu,\sigma^{k(t)-1}})-\mu(\pi^{\mu,\sigma^{k( t)-1}}-\hat{\sigma}^{k(t)-1}),\pi^{\mu,\sigma^{k(t)-1}}-\pi^{\mu,\sigma^{k(t)} }\right\rangle\geq 0.$ $$

Summing up these inequalities, we get for any $t\geq 1$ such that $k(t)\geq 2$:

$$ $\displaystyle 0$ $\displaystyle\leq\left\langle V(\pi^{\mu,\sigma^{k(t)}})-V(\pi^{\mu,\sigma^{k( t)-1}}),\pi^{\mu,\sigma^{k(t)}}-\pi^{\mu,\sigma^{k(t)-1}}\right\rangle-\mu \left\langle\pi^{\mu,\sigma^{k(t)}}-\hat{\sigma}^{k(t)},\pi^{\mu,\sigma^{k(t)} }-\pi^{\mu,\sigma^{k(t)-1}}\right\rangle$ $\displaystyle\phantom{=}+\mu\left\langle\hat{\sigma}^{k(t)-1}-\pi^{\mu,\sigma^ {k(t)-1}},\pi^{\mu,\sigma^{k(t)-1}}-\pi^{\mu,\sigma^{k(t)}}\right\rangle$ $\displaystyle\leq-\mu\left\langle\pi^{\mu,\sigma^{k(t)}}-\hat{\sigma}^{k(t)}, \pi^{\mu,\sigma^{k(t)}}-\pi^{\mu,\sigma^{k(t)-1}}\right\rangle+\mu\left\langle \hat{\sigma}^{k(t)-1}-\pi^{\mu,\sigma^{k(t)-1}},\pi^{\mu,\sigma^{k(t)-1}}-\pi^ {\mu,\sigma^{k(t)}}\right\rangle$ $\displaystyle=-\mu\left\langle\pi^{\mu,\sigma^{k(t)}}-\sigma^{k(t)}+\sigma^{k( t)}-\hat{\sigma}^{k(t)},\pi^{\mu,\sigma^{k(t)}}-\sigma^{k(t)}+\sigma^{k(t)}- \pi^{\mu,\sigma^{k(t)-1}}\right\rangle$ $\displaystyle\phantom{=}+\mu\left\langle\hat{\sigma}^{k(t)-1}-\pi^{\mu,\sigma^ {k(t)-1}},\pi^{\mu,\sigma^{k(t)-1}}-\pi^{\mu,\sigma^{k(t)}}\right\rangle$ $\displaystyle=-\mu\left\|\pi^{\mu,\sigma^{k(t)}}-\sigma^{k(t)}\right\|^{2}-\mu \left\langle\pi^{\mu,\sigma^{k(t)}}-\sigma^{k(t)},\sigma^{k(t)}-\pi^{\mu, \sigma^{k(t)-1}}\right\rangle$ $\displaystyle\phantom{=}-\mu\left\langle\sigma^{k(t)}-\hat{\sigma}^{k(t)},\pi^ {\mu,\sigma^{k(t)}}-\pi^{\mu,\sigma^{k(t)-1}}\right\rangle+\mu\left\langle\hat {\sigma}^{k(t)-1}-\pi^{\mu,\sigma^{k(t)-1}},\pi^{\mu,\sigma^{k(t)-1}}-\pi^{\mu ,\sigma^{k(t)}}\right\rangle$ $\displaystyle=-\mu\left\|\pi^{\mu,\sigma^{k(t)}}-\sigma^{k(t)}\right\|^{2}-\mu \left\langle\pi^{\mu,\sigma^{k(t)}}-\sigma^{k(t)},\sigma^{k(t)}-\pi^{\mu, \sigma^{k(t)-1}}\right\rangle$ $\displaystyle\phantom{=}+\mu\left\langle\pi^{\mu,\sigma^{k(t)}}-\pi^{\mu, \sigma^{k(t)-1}},\pi^{\mu,\sigma^{k(t)-1}}-\sigma^{k(t)}\right\rangle+\mu\left \langle\hat{\sigma}^{k(t)-1}-\hat{\sigma}^{k(t)},\pi^{\mu,\sigma^{k(t)-1}}-\pi ^{\mu,\sigma^{k(t)}}\right\rangle.$ $$

Here, for any vectors $a,b,c$, it holds that:

$$ $\displaystyle\langle a-b,b-c\rangle$ $\displaystyle=\frac{1}{2}\|a-c\|^{2}-\frac{1}{2}\|b-c\|^{2}-\frac{1}{2}\|a-b\| ^{2},$ $\displaystyle\langle a-b,c-d\rangle$ $\displaystyle=\frac{1}{2}\|a-b\|^{2}+\frac{1}{2}\|c-d\|^{2}-\frac{1}{2}\|d-c+a -b\|^{2}.$ $$

Thus, we have:

$$ $\displaystyle 0$ $\displaystyle\leq-\mu\left\|\pi^{\mu,\sigma^{k(t)}}-\sigma^{k(t)}\right\|^{2}- \frac{\mu}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{\mu,\sigma^{k(t)-1}}\right\|^ {2}$ $\displaystyle\phantom{=}+\frac{\mu}{2}\left\|\pi^{\mu,\sigma^{k(t)-1}}-\sigma^ {k(t)}\right\|^{2}+\frac{\mu}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\sigma^{k(t)} \right\|^{2}$ $\displaystyle\phantom{=}+\frac{\mu}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\sigma^{k (t)}\right\|^{2}-\frac{\mu}{2}\left\|\pi^{\mu,\sigma^{k(t)-1}}-\sigma^{k(t)} \right\|^{2}-\frac{\mu}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{\mu,\sigma^{k(t) -1}}\right\|^{2}$ $\displaystyle\phantom{=}+\frac{\mu}{2}\left\|\hat{\sigma}^{k(t)-1}-\hat{\sigma }^{k(t)}\right\|^{2}+\frac{\mu}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{\mu, \sigma^{k(t)-1}}\right\|^{2}$ $\displaystyle\phantom{=}-\frac{\mu}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{\mu, \sigma^{k(t)-1}}+\hat{\sigma}^{k(t)-1}+\hat{\sigma}^{k(t)}\right\|^{2}$ $\displaystyle=-\frac{\mu}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{\mu,\sigma^{k( t)-1}}\right\|^{2}+\frac{\mu}{2}\left\|\hat{\sigma}^{k(t)}-\hat{\sigma}^{k(t)- 1}\right\|^{2}$ $\displaystyle\phantom{=}-\frac{\mu}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{\mu, \sigma^{k(t)-1}}+\hat{\sigma}^{k(t)-1}+\hat{\sigma}^{k(t)}\right\|^{2}$ $\displaystyle\leq-\frac{\mu}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{\mu,\sigma^ {k(t)-1}}\right\|^{2}+\frac{\mu}{2}\left\|\hat{\sigma}^{k(t)}-\hat{\sigma}^{k( t)-1}\right\|^{2}$ $\displaystyle=-\frac{\mu}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{\mu,\sigma^{k( t)-1}}\right\|^{2}+\frac{\mu}{2}\left\|\hat{\sigma}^{k(t)}-\pi^{\mu,\sigma^{k( t)-1}}+\pi^{\mu,\sigma^{k(t)-1}}-\hat{\sigma}^{k(t)-1}\right\|^{2}$ $\displaystyle=\frac{\mu}{2}\left\|\pi^{\mu,\sigma^{k(t)-1}}-\hat{\sigma}^{k(t) -1}\right\|^{2}+\frac{\mu}{2}\left\|\hat{\sigma}^{k(t)}-\pi^{\mu,\sigma^{k(t)- 1}}\right\|^{2}-\frac{\mu}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{\mu,\sigma^{k (t)-1}}\right\|^{2}$ $\displaystyle\phantom{=}+\mu\left\langle\hat{\sigma}^{k(t)}-\pi^{\mu,\sigma^{k (t)-1}},\pi^{\mu,\sigma^{k(t)-1}}-\hat{\sigma}^{k(t)-1}\right\rangle.$ (23) $$

Here, from the definition of $\hat{\sigma}^{k(t)}$, we have:

$$ $\displaystyle\frac{1}{2}\left\|\hat{\sigma}^{k(t)}-\pi^{\mu,\sigma^{k(t)-1}} \right\|^{2}-\frac{1}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{\mu,\sigma^{k(t)-1 }}\right\|^{2}$ $\displaystyle=\frac{1}{2}\left\|\frac{k(t)\sigma^{k(t)}+\sigma^{1}}{k(t)+1}- \pi^{\mu,\sigma^{k(t)-1}}\right\|^{2}-\frac{1}{2}\left\|\pi^{\mu,\sigma^{k(t)} }-\pi^{\mu,\sigma^{k(t)-1}}\right\|^{2}$ $\displaystyle=\frac{1}{2}\left\langle\frac{k(t)\sigma^{k(t)}+\sigma^{1}}{k(t)+ 1}-\pi^{\mu,\sigma^{k(t)-1}}+\pi^{\mu,\sigma^{k(t)}}-\pi^{\mu,\sigma^{k(t)-1}} ,\frac{k(t)\sigma^{k(t)}+\sigma^{1}}{k(t)+1}-\pi^{\mu,\sigma^{k(t)-1}}-\pi^{ \mu,\sigma^{k(t)}}+\pi^{\mu,\sigma^{k(t)-1}}\right\rangle$ $\displaystyle=\frac{1}{2}\left\langle\frac{\sigma^{1}+(k(t)+1)\pi^{\mu,\sigma^ {k(t)}}-2(k(t)+1)\pi^{\mu,\sigma^{k(t)-1}}+k(t)\sigma^{k(t)}}{k(t)+1},\hat{ \sigma}^{k(t)}-\pi^{\mu,\sigma^{k(t)}}\right\rangle$ $\displaystyle=\frac{1}{2k(t)}\left\langle 2(k(t)+1)\sigma^{k(t)+1}+2\sigma^{1} -2(k(t)+2)\pi^{\mu,\sigma^{k(t)}},\hat{\sigma}^{k(t)}-\pi^{\mu,\sigma^{k(t)}}\right\rangle$ $\displaystyle\phantom{=}+\frac{1}{2k(t)}\left\langle-\frac{k(t)+2}{k(t)+1} \sigma^{1}+(3k(t)+4)\pi^{\mu,\sigma^{k(t)}}-2(k(t)+1)\sigma^{k(t)+1}\hat{ \sigma}^{k(t)}-\pi^{\mu,\sigma^{k(t)}}\right\rangle$ $\displaystyle\phantom{=}+\frac{1}{2k(t)}\left\langle-2k(t)\pi^{\mu,\sigma^{k(t )-1}}+\frac{k(t)^{2}}{k(t)+1}\sigma^{k(t)},\hat{\sigma}^{k(t)}-\pi^{\mu,\sigma ^{k(t)}}\right\rangle$ $\displaystyle=\frac{k(t)+2}{k(t)}\left\langle\hat{\sigma}^{k(t)+1}-\pi^{\mu, \sigma^{k(t)}},\hat{\sigma}^{k(t)}-\pi^{\mu,\sigma^{k(t)}}\right\rangle$ $\displaystyle\phantom{=}+\frac{1}{2k(t)}\left\langle-\frac{k(t)+2}{k(t)+1} \sigma^{1}-\frac{k(t)(k(t)+2)}{k(t)+1}\sigma^{k(t)}+(k(t)+2)\pi^{\mu,\sigma^{k (t)}},\hat{\sigma}^{k(t)}-\pi^{\mu,\sigma^{k(t)}}\right\rangle$ $\displaystyle\phantom{=}+\frac{1}{2k(t)}\left\langle 2(k(t)+1)(\pi^{\mu,\sigma ^{k(t)}}-\sigma^{k(t)+1})+2k(t)(\sigma^{k(t)}-\pi^{\mu,\sigma^{k(t)-1}}),\hat{ \sigma}^{k(t)}-\pi^{\mu,\sigma^{k(t)}}\right\rangle$ $\displaystyle=-\frac{k(t)+2}{k(t)}\left\langle\hat{\sigma}^{k(t)+1}-\pi^{\mu, \sigma^{k(t)}},\pi^{\mu,\sigma^{k(t)}}-\hat{\sigma}^{k(t)}\right\rangle$ $\displaystyle\phantom{=}-\frac{k(t)+2}{2k(t)}\left\langle\frac{k(t)\sigma^{k(t )}+\sigma^{1}}{k(t)+1}-\pi^{\mu,\sigma^{k(t)}},\hat{\sigma}^{k(t)}-\pi^{\mu, \sigma^{k(t)}}\right\rangle$ $\displaystyle\phantom{=}+\frac{1}{k(t)}\left\langle(k(t)+1)(\pi^{\mu,\sigma^{k (t)}}-\sigma^{k(t)+1})+k(t)(\sigma^{k(t)}-\pi^{\mu,\sigma^{k(t)-1}}),\hat{ \sigma}^{k(t)}-\pi^{\mu,\sigma^{k(t)}}\right\rangle$ $\displaystyle=-\frac{k(t)+2}{k(t)}\left\langle\hat{\sigma}^{k(t)+1}-\pi^{\mu, \sigma^{k(t)}},\pi^{\mu,\sigma^{k(t)}}-\hat{\sigma}^{k(t)}\right\rangle-\frac{ k(t)+2}{2k(t)}\left\|\hat{\sigma}^{k(t)}-\pi^{\mu,\sigma^{k(t)}}\right\|^{2}$ $\displaystyle\phantom{=}+\frac{1}{k(t)}\left\langle(k(t)+1)(\pi^{\mu,\sigma^{k (t)}}-\sigma^{k(t)+1})+k(t)(\sigma^{k(t)}-\pi^{\mu,\sigma^{k(t)-1}}),\hat{ \sigma}^{k(t)}-\pi^{\mu,\sigma^{k(t)}}\right\rangle.$ (24) $$

Combining Eq. (23) and Eq. (24) yields for any $t\geq 1$ such that $k(t)\geq 2$:

$$ $\displaystyle\frac{k(t)+2}{2k(t)}\left\|\pi^{\mu,\sigma^{k(t)}}-\hat{\sigma}^{ k(t)}\right\|^{2}+\frac{k(t)+2}{k(t)}\left\langle\hat{\sigma}^{k(t)+1}-\pi^{ \mu,\sigma^{k(t)}},\pi^{\mu,\sigma^{k(t)}}-\hat{\sigma}^{k(t)}\right\rangle$ $\displaystyle\leq\frac{1}{2}\left\|\pi^{\mu,\sigma^{k(t)-1}}-\hat{\sigma}^{k(t )-1}\right\|^{2}+\left\langle\hat{\sigma}^{k(t)}-\pi^{\mu,\sigma^{k(t)-1}},\pi ^{\mu,\sigma^{k(t)-1}}-\hat{\sigma}^{k(t)-1}\right\rangle$ $\displaystyle\phantom{=}+\frac{1}{k(t)}\left\langle(k(t)+1)(\pi^{\mu,\sigma^{k (t)}}-\sigma^{k(t)+1})+k(t)(\sigma^{k(t)}-\pi^{\mu,\sigma^{k(t)-1}}),\hat{ \sigma}^{k(t)}-\pi^{\mu,\sigma^{k(t)}}\right\rangle.$ $$

Multiplying both sides by $k(t)(k(t)+1)$, we have:

$$ $\displaystyle\frac{(k(t)+1)(k(t)+2)}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\hat{ \sigma}^{k(t)}\right\|^{2}+(k(t)+1)(k(t)+2)\left\langle\hat{\sigma}^{k(t)+1}- \pi^{\mu,\sigma^{k(t)}},\pi^{\mu,\sigma^{k(t)}}-\hat{\sigma}^{k(t)}\right\rangle$ $\displaystyle\leq\frac{k(t)(k(t)+1)}{2}\left\|\pi^{\mu,\sigma^{k(t)-1}}-\hat{ \sigma}^{k(t)-1}\right\|^{2}+k(t)(k(t)+1)\left\langle\hat{\sigma}^{k(t)}-\pi^{ \mu,\sigma^{k(t)-1}},\pi^{\mu,\sigma^{k(t)-1}}-\hat{\sigma}^{k(t)-1}\right\rangle$ $\displaystyle\phantom{=}+(k(t)+1)\left\langle(k(t)+1)(\pi^{\mu,\sigma^{k(t)}}- \sigma^{k(t)+1})+k(t)(\sigma^{k(t)}-\pi^{\mu,\sigma^{k(t)-1}}),\hat{\sigma}^{k (t)}-\pi^{\mu,\sigma^{k(t)}}\right\rangle.$ $$

∎

###### Proof of Lemma A.3 .

## Appendix B Proofs for Theorem 4.3

### B.1 Proof of Theorem 4.3

###### Proof of Theorem 4.3 .

Let us define $K:=\frac{T}{T_{\sigma}}$.
We can decompose the gap function for $\pi^{T+1}$ as follows:

$$ $\displaystyle\mathrm{GAP}(\pi^{T+1})$ $\displaystyle=\max_{x\in\mathcal{X}}\left\langle V(\pi^{T+1}),x-\pi^{T+1}\right\rangle$ $\displaystyle=\max_{x\in\mathcal{X}}\left(\left\langle V(\pi^{\mu,\sigma^{K}}) ,x-\pi^{\mu,\sigma^{K}}\right\rangle-\left\langle V(\pi^{\mu,\sigma^{K}}),x- \pi^{\mu,\sigma^{K}}\right\rangle+\left\langle V(\pi^{T+1}),x-\pi^{T+1}\right \rangle\right)$ $\displaystyle=\max_{x\in\mathcal{X}}\left(\left\langle V(\pi^{\mu,\sigma^{K}}) ,x-\pi^{\mu,\sigma^{K}}\right\rangle-\left\langle V(\pi^{\mu,\sigma^{K}})-V( \pi^{T+1}),x-\pi^{T+1}\right\rangle+\left\langle V(\pi^{\mu,\sigma^{K}}),\pi^{ \mu,\sigma^{K}}-\pi^{T+1}\right\rangle\right)$ $\displaystyle\leq\max_{x\in\mathcal{X}}\left(\left\langle V(\pi^{\mu,\sigma^{K }}),x-\pi^{\mu,\sigma^{K}}\right\rangle+D\left\|V(\pi^{\mu,\sigma^{K}})-V(\pi^ {T+1})\right\|+\zeta\left\|\pi^{\mu,\sigma^{K}}-\pi^{T+1}\right\|\right)$ $\displaystyle\leq\mathrm{GAP}(\pi^{\mu,\sigma^{K}})+(LD+\zeta)\left\|\pi^{\mu, \sigma^{K}}-\pi^{T+1}\right\|$ $\displaystyle\leq D\cdot\min_{c\in N_{\mathcal{X}}(\pi^{\mu,\sigma^{K}})}\left \|-V(\pi^{\mu,\sigma^{K}})+c\right\|+(LD+\zeta)\left\|\pi^{\mu,\sigma^{K}}-\pi ^{T+1}\right\|,$ $$

where the last inequality follows from Lemma 2.3.
From the first-order optimality condition for $\pi^{\mu,\sigma^{K}}$, we have for any $x\in\mathcal{X}$:

$$ $\displaystyle\left\langle V(\pi^{\mu,\sigma^{K}})-\mu\left(\pi^{\mu,\sigma^{K} }-\frac{K\sigma^{K}+\sigma^{1}}{K+1}\right),\pi^{\mu,\sigma^{K}}-x\right \rangle\geq 0,$ $$

and then $V(\pi^{\mu,\sigma^{K}})-\mu\left(\pi^{\mu,\sigma^{K}}-\frac{K\sigma^{K}+\sigma
^{1}}{K+1}\right)\in N_{\mathcal{X}}(\pi^{\mu,\sigma^{K}})$.
Thus, the gap function for $\pi^{T+1}$ can be bounded by:

$$ $\displaystyle\mathrm{GAP}(\pi^{T+1})$ $\displaystyle\leq\mu D\cdot\left\|\pi^{\mu,\sigma^{K}}-\frac{K\sigma^{K}+ \sigma^{1}}{K+1}\right\|+(LD+\zeta)\left\|\pi^{\mu,\sigma^{K}}-\pi^{T+1}\right\|$ $\displaystyle=\mu D\cdot\left\|\frac{\sigma^{K}-\sigma^{1}}{K+1}+\pi^{\mu, \sigma^{K}}-\sigma^{K}\right\|+(LD+\zeta)\left\|\pi^{\mu,\sigma^{K}}-\pi^{T+1}\right\|$ $\displaystyle\leq\mu D\cdot\left(\frac{D}{K+1}+\left\|\pi^{\mu,\sigma^{K}}- \sigma^{K}\right\|\right)+(LD+\zeta)\left\|\pi^{\mu,\sigma^{K}}-\pi^{T+1} \right\|.$ $$

Taking its expectation yields:

$$ $\displaystyle\mathbb{E}\left[\mathrm{GAP}(\pi^{T+1})\right]$ $\displaystyle\leq\frac{\mu D^{2}}{K+1}+\mu D\cdot\mathbb{E}\left[\left\|\pi^{ \mu,\sigma^{K}}-\sigma^{K}\right\|\right]+(LD+\zeta)\cdot\mathbb{E}\left[\left \|\pi^{\mu,\sigma^{K}}-\pi^{T+1}\right\|\right]$ $\displaystyle\leq\frac{\mu D^{2}}{K+1}+\mu D\cdot\mathbb{E}\left[\left\|\pi^{ \mu,\sigma^{K}}-\sigma^{K}\right\|\right]+(LD+\zeta)\cdot\sqrt{\mathbb{E}\left [\left\|\pi^{\mu,\sigma^{K}}-\pi^{T+1}\right\|^{2}\right]}.$ (25) $$

Here, we derive the following upper bound on $\mathbb{E}\left[\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{t+1}\right\|^{2}\right]$:

###### Lemma B.1 .

Let $\kappa=\frac{\mu}{2},\theta=\frac{3\mu^{2}+8L^{2}}{2\mu}$.
Suppose that Assumption 4.2 holds.
If we set $\eta_{t}=\frac{1}{\kappa(t-T_{\sigma}(k(t)-1))+2\theta}$, we have for any $t\geq 1$:

$$ $\displaystyle\mathbb{E}\left[\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{t+1}\right\|^ {2}\right]\leq\frac{2\theta}{\kappa\left(t-(k(t)-1)T_{\sigma}\right)+2\theta} \left(D^{2}+\frac{C^{2}}{\kappa\theta}\ln\left(\frac{\kappa\left(t-(k(t)-1)T_{ \sigma}\right)}{2\theta}+1\right)\right).$ $$

Setting $t=T=KT_{\sigma}$, we can write $k(t)=\lfloor\frac{KT_{\sigma}-1}{T_{\sigma}}\rfloor+1=K$.
Therefore, from Lemma B.1, we have:

$$ $\displaystyle\mathbb{E}\left[\left\|\pi^{\mu,\sigma^{K}}-\pi^{T+1}\right\|^{2} \right]\leq\frac{2\theta}{\kappa T_{\sigma}+2\theta}\left(D^{2}+\frac{C^{2}}{ \kappa\theta}\ln\left(\frac{\kappa T_{\sigma}}{2\theta}+1\right)\right).$ (26) $$

On the other hand, in terms of $\mathbb{E}\left[\left\|\pi^{\mu,\sigma^{k(t)}}-\sigma^{k(t)}\right\|\right]$, we introduce the following lemma:

###### Lemma B.2 .

If we set $\eta_{t}=\frac{1}{\kappa(t-T_{\sigma}(k(t)-1))+2\theta}$ and $T_{\sigma}\geq\max(1,T^{\frac{6}{7}})$, we have for any $t\geq 1$:

$$ $\displaystyle\mathbb{E}\left[\left\|\pi^{\mu,\sigma^{k(t)}}-\sigma^{k(t)} \right\|\right]\leq\frac{6\left(\sqrt{\kappa}+\sqrt{\theta}+\sqrt{D\theta}+ \sqrt{D}\right)}{k(t)}\left(\sqrt{\frac{1}{\kappa}\left(D^{2}+\frac{C^{2}}{ \kappa\theta}\ln\left(\frac{\kappa T}{2\theta}+1\right)\right)}+1\right).$ $$

By setting $t=KT_{\sigma}$ in this lemma, we get:

$$ $\displaystyle\mathbb{E}\left[\left\|\pi^{\mu,\sigma^{K}}-\sigma^{K}\right\| \right]\leq\frac{6\left(\sqrt{\kappa}+\sqrt{\theta}+\sqrt{D\theta}+\sqrt{D} \right)}{K}\left(\sqrt{\frac{1}{\kappa}\left(D^{2}+\frac{C^{2}}{\kappa\theta} \ln\left(\frac{\kappa T}{2\theta}+1\right)\right)}+1\right).$ (27) $$

Combining Eq. (25), Eq. (26), and Eq. (27), we have:

$$ $\displaystyle\mathbb{E}\left[\mathrm{GAP}(\sigma^{K+1})\right]$ $\displaystyle\leq\frac{\mu D^{2}}{K+1}+\mu D\cdot\frac{6\left(\sqrt{\kappa}+ \sqrt{\theta}+\sqrt{D\theta}+\sqrt{D}\right)}{K}\left(\sqrt{\frac{1}{\kappa} \left(D^{2}+\frac{C^{2}}{\kappa\theta}\ln\left(\frac{\kappa T}{2\theta}+1 \right)\right)}+1\right)$ $\displaystyle\phantom{=}+(LD+\zeta)\cdot\sqrt{\frac{2\theta}{\kappa T_{\sigma} +2\theta}\left(D^{2}+\frac{C^{2}}{\kappa\theta}\ln\left(\frac{\kappa T_{\sigma }}{2\theta}+1\right)\right)}$ $\displaystyle\leq\mu D^{2}\frac{T_{\sigma}}{T}+\mu D\cdot\frac{6T_{\sigma} \left(\sqrt{\kappa}+\sqrt{\theta}+\sqrt{D\theta}+\sqrt{D}\right)}{T}\left( \sqrt{\frac{1}{\kappa}\left(D^{2}+\frac{C^{2}}{\kappa\theta}\ln\left(\frac{ \kappa T}{2\theta}+1\right)\right)}+1\right)$ $\displaystyle\phantom{=}+(LD+\zeta)\cdot\sqrt{\frac{2\theta}{\kappa T_{\sigma} }\left(D^{2}+\frac{C^{2}}{\kappa\theta}\ln\left(\frac{\kappa T}{2\theta}+1 \right)\right)},$ $$

where the second inequality follows from $K=\frac{T}{T_{\sigma}}$.
Finally, since $T_{\sigma}=c\cdot\max(1,T^{\frac{6}{7}})$, we have for any $T\geq T_{\sigma}$:

$$ $\displaystyle\mathbb{E}\left[\mathrm{GAP}(\sigma^{K+1})\right]$ $\displaystyle\leq\frac{c\mu D^{2}}{T^{\frac{1}{7}}}+\frac{6c\mu D\left(\sqrt{ \kappa}+\sqrt{\theta}+\sqrt{D\theta}+\sqrt{D}\right)}{T^{\frac{1}{7}}}\left( \sqrt{\frac{1}{\kappa}\left(D^{2}+\frac{C^{2}}{\kappa\theta}\ln\left(\frac{ \kappa T}{2\theta}+1\right)\right)}+1\right)$ $\displaystyle\phantom{=}+\frac{(LD+\zeta)}{T^{\frac{3}{7}}}\sqrt{\frac{2\theta }{\kappa}\left(D^{2}+\frac{C^{2}}{\kappa\theta}\ln\left(\frac{\kappa T}{2 \theta}+1\right)\right)}$ $\displaystyle\leq\frac{6c\mu D\left(\sqrt{\kappa}+\sqrt{\theta}+\sqrt{D\theta} +\sqrt{D}+D\right)}{T^{\frac{1}{7}}}\left(\sqrt{\frac{1}{\kappa}\left(D^{2}+ \frac{C^{2}}{\kappa\theta}\ln\left(\frac{\kappa T}{2\theta}+1\right)\right)}+1\right)$ $\displaystyle\phantom{=}+\frac{(LD+\zeta)\sqrt{2\theta}}{T^{\frac{1}{7}}}\left (\sqrt{\frac{1}{\kappa}\left(D^{2}+\frac{C^{2}}{\kappa\theta}\ln\left(\frac{ \kappa T}{2\theta}+1\right)\right)}+1\right)$ $\displaystyle\leq\frac{9c\left(\mu D+LD+\zeta\right)\left(\sqrt{\kappa}+\sqrt{ \theta}+\sqrt{D\theta}+\sqrt{D}+D\right)}{T^{\frac{1}{7}}}\left(\sqrt{\frac{1} {\kappa}\left(D^{2}+\frac{C^{2}}{\kappa\theta}\ln\left(\frac{\kappa T}{2\theta }+1\right)\right)}+1\right).$ $$

Since $T=T_{\sigma}K$, we have finally:

$$ $\displaystyle\mathbb{E}\left[\mathrm{GAP}(\pi^{T+1})\right]$ $\displaystyle\leq\frac{9c\left(\mu D+LD+\zeta\right)\left(\sqrt{\kappa}+\sqrt{ \theta}+\sqrt{D\theta}+\sqrt{D}+D\right)}{T^{\frac{1}{7}}}\left(\sqrt{\frac{1} {\kappa}\left(D^{2}+\frac{C^{2}}{\kappa\theta}\ln\left(\frac{\kappa T}{2\theta }+1\right)\right)}+1\right)$ $\displaystyle=\frac{9c\left(D(\mu+L)+\zeta\right)\left(\sqrt{\kappa}+(\sqrt{D} +1)(\sqrt{D}+\sqrt{\theta})\right)}{T^{\frac{1}{7}}}\left(\sqrt{\frac{1}{ \kappa}\left(D^{2}+\frac{C^{2}}{\kappa\theta}\ln\left(\frac{\kappa T}{2\theta} +1\right)\right)}+1\right)$ $\displaystyle\leq\frac{18c\left(D(\mu+L)+\zeta\right)\left(\sqrt{\kappa}+\sqrt {(D+1)(D+\theta)}\right)}{T^{\frac{1}{7}}}\left(\sqrt{\frac{1}{\kappa}\left(D^ {2}+\frac{C^{2}}{\kappa\theta}\ln\left(\frac{\kappa T}{2\theta}+1\right)\right )}+1\right)$ $\displaystyle\leq\frac{26c\left(D(\mu+L)+\zeta\right)\sqrt{(D+1)(D+\theta)+ \kappa}}{T^{\frac{1}{7}}}\left(\sqrt{\frac{1}{\kappa}\left(D^{2}+\frac{C^{2}}{ \kappa\theta}\ln\left(\frac{\kappa T}{2\theta}+1\right)\right)}+1\right).$ $$

∎

###### Proof of Theorem 4.3 .

###### Lemma B.1 .

###### Lemma B.2 .

### B.2 Proof of Lemma B.1

###### Proof of Lemma B.1 .

From the first-order optimality condition for $\pi^{t+1}$, we have for $t\geq 1$:

$$ $\displaystyle\left\langle\eta_{t}\left(\hat{V}(\pi^{t})-\mu(\pi^{t}-\hat{ \sigma}^{k(t)})\right)-\pi^{t+1}+\pi^{t},\pi^{t+1}-\pi^{\mu,\sigma^{k(t)}} \right\rangle\geq 0.$ (28) $$

Combining Eq. (28), Eq. (12), and Eq. (14), we have:

$$ $\displaystyle\frac{1}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{t+1}\right\|^{2}- \frac{1}{2}\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{t}\right\|^{2}+\frac{1}{2}\left \|\pi^{t+1}-\pi^{t}\right\|^{2}$ $\displaystyle\leq\eta_{t}\left\langle\hat{V}(\pi^{t})-\mu(\pi^{t}-\hat{\sigma} ^{k(t)}),\pi^{t+1}-\pi^{\mu,\sigma^{k(t)}}\right\rangle$ $\displaystyle=\eta_{t}\left\langle V(\pi^{t+1})-\mu(\pi^{t+1}-\hat{\sigma}^{k( t)}),\pi^{t+1}-\pi^{\mu,\sigma^{k(t)}}\right\rangle+\eta_{t}\left\langle\hat{V }(\pi^{t})-V(\pi^{t+1})-\mu(\pi^{t}-\pi^{t+1}),\pi^{t+1}-\pi^{\mu,\sigma^{k(t) }}\right\rangle$ $\displaystyle\leq\eta_{t}\left\langle V(\pi^{\mu,\sigma^{k(t)}})-\mu(\pi^{t+1} -\hat{\sigma}^{k(t)}),\pi^{t+1}-\pi^{\mu,\sigma^{k(t)}}\right\rangle+\eta_{t} \left\langle\hat{V}(\pi^{t})-V(\pi^{t+1})-\mu(\pi^{t}-\pi^{t+1}),\pi^{t+1}-\pi ^{\mu,\sigma^{k(t)}}\right\rangle$ $\displaystyle=\eta_{t}\left\langle V(\pi^{\mu,\sigma^{k(t)}})-\mu(\pi^{\mu, \sigma^{k(t)}}-\hat{\sigma}^{k(t)}),\pi^{t+1}-\pi^{\mu,\sigma^{k(t)}}\right \rangle-\eta_{t}\mu\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{t+1}\right\|^{2}$ $\displaystyle\phantom{=}+\eta_{t}\left\langle V(\pi^{t})-V(\pi^{t+1}),\pi^{t+1 }-\pi^{\mu,\sigma^{k(t)}}\right\rangle-\eta_{t}\mu\left\langle\pi^{t}-\pi^{t+1 },\pi^{t+1}-\pi^{\mu,\sigma^{k(t)}}\right\rangle+\eta_{t}\left\langle\xi^{t}, \pi^{t+1}-\pi^{\mu,\sigma^{k(t)}}\right\rangle$ $\displaystyle\leq-\eta_{t}\mu\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{t+1}\right\|^ {2}+\eta_{t}\mu\left\langle\pi^{t+1}-\pi^{t},\pi^{t+1}-\pi^{\mu,\sigma^{k(t)}}\right\rangle$ $\displaystyle\phantom{=}+\eta_{t}\left\langle V(\pi^{t})-V(\pi^{t+1}),\pi^{t+1 }-\pi^{\mu,\sigma^{k(t)}}\right\rangle+\eta_{t}\left\langle\xi^{t},\pi^{t+1}- \pi^{\mu,\sigma^{k(t)}}\right\rangle$ $\displaystyle=-\eta_{t}\mu\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{t+1}\right\|^{2} +\frac{\eta_{t}\mu}{2}\left\|\pi^{t+1}-\pi^{t}\right\|^{2}+\frac{\eta_{t}\mu}{ 2}\left\|\pi^{t+1}-\pi^{\mu,\sigma^{k(t)}}\right\|^{2}-\frac{\eta_{t}\mu}{2} \left\|\pi^{t}-\pi^{\mu,\sigma^{k(t)}}\right\|^{2}$ $\displaystyle\phantom{=}+\eta_{t}\left\langle V(\pi^{t})-V(\pi^{t+1}),\pi^{t+1 }-\pi^{\mu,\sigma^{k(t)}}\right\rangle+\eta_{t}\left\langle\xi^{t},\pi^{t+1}- \pi^{\mu,\sigma^{k(t)}}\right\rangle$ $\displaystyle=-\frac{\eta_{t}\mu}{2}\left\|\pi^{t+1}-\pi^{\mu,\sigma^{k(t)}} \right\|^{2}-\frac{\eta_{t}\mu}{2}\left\|\pi^{t}-\pi^{\mu,\sigma^{k(t)}}\right \|^{2}+\frac{\eta_{t}\mu}{2}\left\|\pi^{t+1}-\pi^{t}\right\|^{2}$ $\displaystyle\phantom{=}+\eta_{t}\left\langle V(\pi^{t})-V(\pi^{t+1}),\pi^{t+1 }-\pi^{\mu,\sigma^{k(t)}}\right\rangle+\eta_{t}\left\langle\xi^{t},\pi^{t+1}- \pi^{\mu,\sigma^{k(t)}}\right\rangle,$ (29) $$

where the third inequality follows from Eq. (1).
From Cauchy-Schwarz inequality and Young’s inequality, the fourth term on the right-hand side of this inequality can be bounded by:

$$ $\displaystyle\left\langle V(\pi^{t})-V(\pi^{t+1}),\pi^{t+1}-\pi^{\mu,\sigma^{k (t)}}\right\rangle$ $\displaystyle\leq\left\|V(\pi^{t})-V(\pi^{t+1})\right\|\cdot\left\|\pi^{t+1}- \pi^{\mu,\sigma^{k(t)}}\right\|$ $\displaystyle\leq L\left\|\pi^{t}-\pi^{t+1}\right\|\cdot\left\|\pi^{t+1}-\pi^{ \mu,\sigma^{k(t)}}\right\|$ $\displaystyle\leq\frac{2L^{2}}{\mu}\left\|\pi^{t}-\pi^{t+1}\right\|^{2}+\frac{ \mu}{8}\left\|\pi^{t+1}-\pi^{\mu,\sigma^{k(t)}}\right\|^{2}$ $\displaystyle\leq\frac{2L^{2}}{\mu}\left\|\pi^{t}-\pi^{t+1}\right\|^{2}+\frac{ \mu}{4}\left\|\pi^{t}-\pi^{\mu,\sigma^{k(t)}}\right\|^{2}+\frac{\mu}{4}\left\| \pi^{t+1}-\pi^{t}\right\|^{2}$ $\displaystyle=\left(\frac{4L^{2}}{\mu}+\frac{\mu}{2}\right)\frac{\left\|\pi^{t }-\pi^{t+1}\right\|^{2}}{2}+\frac{\mu}{2}\frac{\left\|\pi^{t}-\pi^{\mu,\sigma^ {k(t)}}\right\|^{2}}{2}.$ (30) $$

By combining Eq. (29) and Eq. (30), we have:

$$ $\displaystyle\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{t+1}\right\|^{2}$ $\displaystyle\leq-\eta_{t}\mu\left\|\pi^{t+1}-\pi^{\mu,\sigma^{k(t)}}\right\|^ {2}+\left(1-\frac{\eta_{t}\mu}{2}\right)\left\|\pi^{t}-\pi^{\mu,\sigma^{k(t)}} \right\|^{2}$ $\displaystyle\phantom{=}-\left(1-\eta_{t}\left(\frac{3\mu}{2}+\frac{4L^{2}}{ \mu}\right)\right)\left\|\pi^{t+1}-\pi^{t}\right\|^{2}+2\eta_{t}\left\langle \xi^{t},\pi^{t+1}-\pi^{\mu,\sigma^{k(t)}}\right\rangle$ $\displaystyle\leq\left(1-\frac{\eta_{t}\mu}{2}\right)\left\|\pi^{t}-\pi^{\mu, \sigma^{k(t)}}\right\|^{2}-\left(1-\eta_{t}\left(\frac{3\mu}{2}+\frac{4L^{2}}{ \mu}\right)\right)\left\|\pi^{t+1}-\pi^{t}\right\|^{2}$ $\displaystyle\phantom{=}+2\eta_{t}\left\langle\xi^{t},\pi^{t}-\pi^{\mu,\sigma^ {k(t)}}\right\rangle+2\eta_{t}\left\langle\xi^{t},\pi^{t+1}-\pi^{t}\right\rangle$ $\displaystyle=\left(1-\eta_{t}\kappa\right)\left\|\pi^{t}-\pi^{\mu,\sigma^{k(t )}}\right\|^{2}-\left(1-\eta_{t}\theta\right)\left\|\pi^{t+1}-\pi^{t}\right\|^ {2}$ $\displaystyle\phantom{=}+2\eta_{t}\left\langle\xi^{t},\pi^{t}-\pi^{\mu,\sigma^ {k(t)}}\right\rangle+2\eta_{t}\left\langle\xi^{t},\pi^{t+1}-\pi^{t}\right\rangle.$ $$

By taking the expectation conditioned on $\mathcal{F}_{t}$ for both sides and using Assumption 4.2 (a) and (b),

$$ $\displaystyle\mathbb{E}\left[\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{t+1}\right\|^ {2}~{}|~{}\mathcal{F}_{t}\right]$ $\displaystyle\leq\left(1-\eta_{t}\kappa\right)\mathbb{E}\left[\left\|\pi^{t}- \pi^{\mu,\sigma^{k(t)}}\right\|^{2}~{}|~{}\mathcal{F}_{t}\right]-\left(1-\eta_ {t}\theta\right)\mathbb{E}\left[\left\|\pi^{t+1}-\pi^{t}\right\|^{2}~{}|~{} \mathcal{F}_{t}\right]$ $\displaystyle\phantom{=}+2\eta_{t}\left\langle\mathbb{E}\left[\xi^{t}~{}|~{} \mathcal{F}_{t}\right],\pi^{t}-\pi^{\mu,\sigma^{k(t)}}\right\rangle+2\eta_{t} \mathbb{E}\left[\left\langle\xi^{t},\pi^{t+1}-\pi^{t}\right\rangle~{}|~{} \mathcal{F}_{t}\right]$ $\displaystyle=\left(1-\eta_{t}\kappa\right)\left\|\pi^{t}-\pi^{\mu,\sigma^{k(t )}}\right\|^{2}-\left(1-\eta_{t}\theta\right)\mathbb{E}\left[\left\|\pi^{t+1}- \pi^{t}\right\|^{2}~{}|~{}\mathcal{F}_{t}\right]+2\eta_{t}\mathbb{E}\left[ \left\langle\xi^{t},\pi^{t+1}-\pi^{t}\right\rangle~{}|~{}\mathcal{F}_{t}\right]$ $\displaystyle\leq\left(1-\eta_{t}\kappa\right)\left\|\pi^{t}-\pi^{\mu,\sigma^{ k(t)}}\right\|^{2}-\left(1-\eta_{t}\theta\right)\mathbb{E}\left[\left\|\pi^{t+ 1}-\pi^{t}\right\|^{2}~{}|~{}\mathcal{F}_{t}\right]$ $\displaystyle\phantom{=}+\frac{\eta_{t}^{2}}{1-\eta_{t}\theta}\mathbb{E}\left[ \left\|\xi^{t}\right\|^{2}~{}|~{}\mathcal{F}_{t}\right]+\left(1-\eta_{t}\theta \right)\mathbb{E}\left[\left\|\pi^{t+1}-\pi^{t}\right\|^{2}~{}|~{}\mathcal{F}_ {t}\right]$ $\displaystyle\leq\left(1-\eta_{t}\kappa\right)\left\|\pi^{t}-\pi^{\mu,\sigma^{ k(t)}}\right\|^{2}+\frac{\eta_{t}^{2}}{1-\eta_{t}\theta}\mathbb{E}\left[\left \|\xi^{t}\right\|^{2}~{}|~{}\mathcal{F}_{t}\right]$ $\displaystyle\leq\left(1-\eta_{t}\kappa\right)\left\|\pi^{t}-\pi^{\mu,\sigma^{ k(t)}}\right\|^{2}+2\eta_{t}^{2}\mathbb{E}\left[\left\|\xi^{t}\right\|^{2}~{}| ~{}\mathcal{F}_{t}\right]$ $\displaystyle\leq\left(1-\eta_{t}\kappa\right)\left\|\pi^{t}-\pi^{\mu,\sigma^{ k(t)}}\right\|^{2}+2\eta_{t}^{2}C^{2}.$ $$

Therefore, under the setting where $\eta_{t}=\frac{1}{\kappa(t-T_{\sigma}(k(t)-1))+2\theta}$, we have for any $t\geq 1$:

$$ $\displaystyle\mathbb{E}\left[\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{t+1}\right\|^ {2}~{}|~{}\mathcal{F}_{t}\right]\leq\left(1-\frac{1}{t-T_{\sigma}(k(t)-1)+2 \theta/\kappa}\right)\left\|\pi^{t}-\pi^{\mu,\sigma^{k(t)}}\right\|^{2}+2\eta_ {t}^{2}C^{2}.$ $$

Rearranging and taking the expectations, we get:

$$ $\displaystyle\left(t-T_{\sigma}(k(t)-1)+2\theta/\kappa\right)\mathbb{E}\left[ \left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{t+1}\right\|^{2}\right]$ $\displaystyle\leq\left(t-1-T_{\sigma}(k(t)-1)+2\theta/\kappa\right)\mathbb{E} \left[\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{t}\right\|^{2}\right]+\frac{2C^{2}}{ \kappa\left(\kappa(t-T_{\sigma}(k(t)-1))+2\theta\right)}.$ $$

Since $k(s)=k(t)$ for any $s\in[(k(t)-1)T_{\sigma}+1,T]$, telescoping the sum yields:

$$ $\displaystyle\left(t-T_{\sigma}(k(t)-1)+2\theta/\kappa\right)\mathbb{E}\left[ \left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{t+1}\right\|^{2}\right]$ $\displaystyle\leq\left(s-1-T_{\sigma}(k(t)-1)+2\theta/\kappa\right)\mathbb{E} \left[\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{s}\right\|^{2}\right]+\sum_{m=s}^{t} \frac{2C^{2}}{\kappa\left(\kappa(m-T_{\sigma}(k(t)-1))+2\theta\right)}.$ $$

Defining $s=(k(t)-1)T_{\sigma}+1$,

$$ $\displaystyle\left(t-T_{\sigma}(k(t)-1)+2\theta/\kappa\right)\mathbb{E}\left[ \left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{t+1}\right\|^{2}\right]$ $\displaystyle\leq\frac{2\theta}{\kappa}\mathbb{E}\left[\left\|\pi^{\mu,\sigma^ {k(t)}}-\pi^{(k(t)-1)T_{\sigma}+1}\right\|^{2}\right]+\frac{2C^{2}}{\kappa} \sum_{m=(k(t)-1)T_{\sigma}+1}^{t}\frac{1}{\kappa(m-T_{\sigma}(k(t)-1))+2\theta}.$ $$

Therefore,

$$ $\displaystyle\mathbb{E}\left[\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{t+1}\right\|^ {2}\right]$ $\displaystyle\leq\frac{2\theta}{\kappa\left(t-T_{\sigma}(k(t)-1)\right)+2 \theta}\mathbb{E}\left[\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{(k(t)-1)T_{\sigma}+ 1}\right\|^{2}\right]$ $\displaystyle\phantom{=}+\frac{2C^{2}}{\kappa\left(t-T_{\sigma}(k(t)-1)\right) +2\theta}\sum_{m=1}^{t-(k(t)-1)T_{\sigma}}\frac{1}{\kappa m+2\theta}.$ (31) $$

Here, we have:

$$ $\displaystyle\sum_{m=1}^{t-(k(t)-1)T_{\sigma}}\frac{1}{\kappa m+2\theta}$ $\displaystyle\leq\int_{0}^{t-(k(t)-1)T_{\sigma}}\frac{1}{\kappa x+2\theta}dx= \frac{1}{\kappa}\ln\left(\frac{\kappa\left(t-(k(t)-1)T_{\sigma}\right)}{2 \theta}+1\right).$ (32) $$

Combining Eq. (31), Eq. (32), and the fact that $\pi^{(k(t)-1)T_{\sigma}+1}=\sigma^{k(t)}$, we have:

$$ $\displaystyle\mathbb{E}\left[\left\|\pi^{\mu,\sigma^{k(t)}}-\pi^{t+1}\right\|^ {2}\right]$ $\displaystyle\leq\frac{2\theta}{\kappa\left(t-(k(t)-1)T_{\sigma}\right)+2 \theta}\left(\mathbb{E}\left[\left\|\pi^{\mu,\sigma^{k(t)}}-\sigma^{k(t)} \right\|^{2}\right]+\frac{C^{2}}{\kappa\theta}\ln\left(\frac{\kappa\left(t-(k( t)-1)T_{\sigma}\right)}{2\theta}+1\right)\right)$ $\displaystyle\leq\frac{2\theta}{\kappa\left(t-(k(t)-1)T_{\sigma}\right)+2 \theta}\left(D^{2}+\frac{C^{2}}{\kappa\theta}\ln\left(\frac{\kappa\left(t-(k(t )-1)T_{\sigma}\right)}{2\theta}+1\right)\right).$ $$

∎

###### Proof of Lemma B.1 .

### B.3 Proof of Lemma B.2

###### Proof of Lemma B.2 .

First, from Lemma B.1, we have for any $k\geq 1$:

$$ $\displaystyle\mathbb{E}\left[\left\|\pi^{\mu,\sigma^{k}}-\sigma^{k+1}\right\|^ {2}\right]\leq\frac{2\theta}{\kappa T_{\sigma}+2\theta}\left(D^{2}+\frac{C^{2} }{\kappa\theta}\ln\left(\frac{\kappa T_{\sigma}}{2\theta}+1\right)\right).$ $$

Moreover, by taking the expectation of Eq. (21), we have for any $t\geq 1$ such that $k(t)\geq 2$:

$$ $\displaystyle\mathbb{E}\left[\left\|\pi^{\mu,\sigma^{k(t)}}-\sigma^{k(t)} \right\|^{2}\right]$ $\displaystyle\leq\frac{2D}{k(t)+1}\mathbb{E}\left[\left\|\pi^{\mu,\sigma^{k(t) }}-\sigma^{k(t)}\right\|\right]+\frac{12D^{2}}{(k(t)+1)^{2}}$ $\displaystyle\phantom{=}+8\mathbb{E}\left[\left\|\sigma^{k(t)+1}-\pi^{\mu, \sigma^{k(t)}}\right\|^{2}\right]+8D\sum_{l=1}^{k(t)}\mathbb{E}\left[\left\| \pi^{\mu,\sigma^{l}}-\sigma^{l+1}\right\|\right].$ $$

Combining these inequalities, we get for any $t\geq 1$ such that $k(t)\geq 2$:

$$ $\displaystyle\mathbb{E}\left[\left\|\pi^{\mu,\sigma^{k(t)}}-\sigma^{k(t)} \right\|^{2}\right]\leq\frac{2D}{k(t)+1}\mathbb{E}\left[\left\|\pi^{\mu,\sigma ^{k(t)}}-\sigma^{k(t)}\right\|\right]+\frac{12D^{2}}{(k(t)+1)^{2}}$ $\displaystyle\phantom{=}+\frac{16\theta}{\kappa T_{\sigma}}\left(D^{2}+\frac{C ^{2}}{\kappa\theta}\ln\left(\frac{\kappa T_{\sigma}}{2\theta}+1\right)\right)+ 8Dk(t)\sqrt{\frac{2\theta}{\kappa T_{\sigma}}\left(D^{2}+\frac{C^{2}}{\kappa \theta}\ln\left(\frac{\kappa T_{\sigma}}{2\theta}+1\right)\right)}.$ $$

Since $T_{\sigma}\geq\max(1,T^{\frac{6}{7}})\Rightarrow\frac{k(t)^{3}}{\sqrt{T_{
\sigma}}}\leq 1$, we have:

$$ $\displaystyle\mathbb{E}\left[\left(\left\|\pi^{\mu,\sigma^{k(t)}}-\sigma^{k(t) }\right\|-\frac{D}{k(t)+1}\right)^{2}\right]$ $\displaystyle\leq\frac{13D^{2}}{k(t)^{2}}+\frac{16\theta}{\kappa k(t)^{2}} \left(D^{2}+\frac{C^{2}}{\kappa\theta}\ln\left(\frac{\kappa T}{2\theta}+1 \right)\right)$ $\displaystyle\phantom{=}+\frac{8D}{k(t)^{2}}\sqrt{\frac{2\theta}{\kappa}\left( D^{2}+\frac{C^{2}}{\kappa\theta}\ln\left(\frac{\kappa T}{2\theta}+1\right) \right)}.$ $$

Since $\mathbb{E}[X]^{2}\leq\mathbb{E}[X^{2}]$ for any random variable $X$, we get:

$$ $\displaystyle\frac{13D^{2}}{k(t)^{2}}+\frac{16\theta}{\kappa k(t)^{2}}\left(D^ {2}+\frac{C^{2}}{\kappa\theta}\ln\left(\frac{\kappa T}{2\theta}+1\right)\right )+\frac{8D}{k(t)^{2}}\sqrt{\frac{2\theta}{\kappa}\left(D^{2}+\frac{C^{2}}{ \kappa\theta}\ln\left(\frac{\kappa T}{2\theta}+1\right)\right)}$ $\displaystyle\geq\mathbb{E}\left[\left(\left\|\pi^{\mu,\sigma^{k(t)}}-\sigma^{ k(t)}\right\|-\frac{D}{k(t)+1}\right)^{2}\right]$ $\displaystyle\geq\mathbb{E}\left[\left\|\pi^{\mu,\sigma^{k(t)}}-\sigma^{k(t)} \right\|-\frac{D}{k(t)+1}\right]^{2}$ $\displaystyle=\left(\mathbb{E}\left[\left\|\pi^{\mu,\sigma^{k(t)}}-\sigma^{k(t )}\right\|\right]-\frac{D}{k(t)+1}\right)^{2}.$ $$

Then, we have:

$$ $\displaystyle\mathbb{E}\left[\left\|\pi^{\mu,\sigma^{k(t)}}-\sigma^{k(t)} \right\|\right]$ $\displaystyle\leq\frac{D}{k(t)}+\frac{4D}{k(t)}+\frac{4\sqrt{\theta}}{\sqrt{ \kappa}k(t)}\sqrt{D^{2}+\frac{C^{2}}{\kappa\theta}\ln\left(\frac{\kappa T}{2 \theta}+1\right)}+\frac{3\sqrt{D}}{k(t)}\left(\frac{2\theta}{\kappa}\left(D^{2 }+\frac{C^{2}}{\kappa\theta}\ln\left(\frac{\kappa T}{2\theta}+1\right)\right) \right)^{\frac{1}{4}}$ $\displaystyle\leq\frac{5(\sqrt{\kappa}+\sqrt{\theta})}{k(t)\sqrt{\kappa}}\sqrt {D^{2}+\frac{C^{2}}{\kappa\theta}\ln\left(\frac{\kappa T}{2\theta}+1\right)}+ \frac{6\sqrt{D}(\sqrt{\theta}+1)}{k(t)}\left(\sqrt{\frac{1}{\kappa}\left(D^{2} +\frac{C^{2}}{\kappa\theta}\ln\left(\frac{\kappa T}{2\theta}+1\right)\right)}+ 1\right)$ $\displaystyle\leq\frac{6\left(\sqrt{\kappa}+\sqrt{\theta}+\sqrt{D\theta}+\sqrt {D})\right)}{k(t)}\left(\sqrt{\frac{1}{\kappa}\left(D^{2}+\frac{C^{2}}{\kappa \theta}\ln\left(\frac{\kappa T}{2\theta}+1\right)\right)}+1\right).$ $$

Furthermore, for $k(t)=1$, we have:

$$ $\displaystyle\mathbb{E}\left[\left\|\pi^{\mu,\sigma^{1}}-\sigma^{1}\right\| \right]\leq D\leq\frac{6\left(\sqrt{\kappa}+\sqrt{\theta}+\sqrt{D\theta}+\sqrt {D})\right)}{1}\left(\sqrt{\frac{1}{\kappa}\left(D^{2}+\frac{C^{2}}{\kappa \theta}\ln\left(\frac{\kappa T}{2\theta}+1\right)\right)}+1\right).$ $$

Therefore, we have for any $t\geq 1$:

$$ $\displaystyle\mathbb{E}\left[\left\|\pi^{\mu,\sigma^{k(t)}}-\sigma^{k(t)} \right\|\right]\leq\frac{6\left(\sqrt{\kappa}+\sqrt{\theta}+\sqrt{D\theta}+ \sqrt{D})\right)}{k(t)}\left(\sqrt{\frac{1}{\kappa}\left(D^{2}+\frac{C^{2}}{ \kappa\theta}\ln\left(\frac{\kappa T}{2\theta}+1\right)\right)}+1\right).$ $$

∎

###### Proof of Lemma B.2 .

## Appendix C Proof of Theorem 5.1

###### Proof of Theorem 5.1 .

By the definition of dynamic regret, we have:

$$ $\displaystyle\mathrm{DynamicReg}_{i}(T)$ $\displaystyle=\sum_{t=1}^{T}\left(\max_{x\in\mathcal{X}_{i}}v_{i}(x,\pi_{-i}^{ t})-v_{i}(\pi^{t})\right)$ $\displaystyle\leq\mathcal{O}(1)+\sum_{t=3}^{T}\sum_{i=1}^{N}\left(\max_{x\in \mathcal{X}_{i}}v_{i}(x,\pi_{-i}^{t})-v_{i}(\pi^{t})\right).$ $$

Here, we introduce the following lemma:

###### Lemma C.1 (Lemma 2 of Cai et al. [ 2022a ] ) .

For any $\pi\in\mathcal{X}$, we have:

$$ $\displaystyle\sum_{i=1}^{N}\left(\max_{\tilde{\pi}_{i}\in\mathcal{X}_{i}}v_{i} (\tilde{\pi}_{i},\pi_{-i})-v_{i}(\pi)\right)\leq\mathrm{GAP}(\pi)\leq D\cdot \max_{\tilde{\pi}\in\mathcal{X}}\langle V(\pi),\tilde{\pi}-\pi\rangle.$ $$

Therefore, we have:

$$ $\displaystyle\mathrm{DynamicReg}_{i}(T)$ $\displaystyle\leq\mathcal{O}(1)+\sum_{t=2}^{T}\mathrm{GAP}(\pi^{t}).$ $$

Thus, from Theorem 4.1:

$$ $\displaystyle\mathrm{DynamicReg}_{i}(T)$ $\displaystyle\leq\mathcal{O}(1)+\sum_{t=2}^{T}\mathcal{O}\left(\frac{\ln T}{t}\right)$ $\displaystyle\leq\mathcal{O}\left((\ln T)^{2}\right).$ $$

∎

###### Proof of Theorem 5.1 .

###### Lemma C.1 (Lemma 2 of Cai et al. [ 2022a ] ) .

## Appendix D Experimental details

### D.1 Information on the computer resources

The experiments were conducted on macOS Sonoma 14.4.1 with Apple M2 Max and 32GB RAM.

### D.2 Hard concave-convex game

Following the setup in Ouyang and Xu [], Cai and Zheng [], we choose

$$ $\displaystyle A=\frac{1}{4}\begin{bmatrix}&&&-1&1\\ &&\cdots&\cdots&\\ &-1&1&&\\ -1&1&&&\\ 1&&&&\end{bmatrix}\in\mathbb{R}^{n\times n},\quad b=\frac{1}{4}\begin{bmatrix} 1\\ 1\\ \cdots\\ 1\\ 1\end{bmatrix}\in\mathbb{R}^{n},\quad h=\frac{1}{4}\begin{bmatrix}0\\ 0\\ \cdots\\ 0\\ 1\end{bmatrix}\in\mathbb{R}^{n},$ $$

and $H=2A^{\top}A$.

### D.3 Hyperparameters

For each game, we carefully tuned the hyperparameters for each algorithm to ensure optimal performance.
The specific parameters for each game and setting are summarized in Table 1.

**Table 1: Hyperparameters**
| Game | Algorithm | $\eta$ | $T_{\sigma}$ | $\mu$ |
| --- | --- | --- | --- | --- |
| Random Payoff (Full Feedback) | OG | 0.05 | - | - |
| AOG | 0.05 | - | - |  |
| APGA | 0.05 | 20 | 1.0 |  |
|  | GABP | 0.05 | 10 | 1.0 |
| Random Payoff (Noisy Feedback) | OG | 0.001 | - | - |
| AOG | 0.001 | - | - |  |
| APGA | 0.001 | 2000 | 1.0 |  |
|  | GABP | 0.001 | 1000 | 1.0 |
| Hard Concave-Convex (Full Feedback) | OG | 1.0 | - | - |
| AOG | 1.0 | - | - |  |
| APGA | 1.0 | 20 | 0.1 |  |
|  | GABP | 1.0 | 20 | 0.1 |
| Hard Concave-Convex (Noisy Feedback) | OG | 0.5 | - | - |
| AOG | 0.5 | - | - |  |
| APGA | 0.5 | 50 | 0.1 |  |
|  | GABP | 0.1 | 100 | 0.1 |

## Appendix E Comparison with Existing Learning Algorithms

### E.1 Relationship with accelerated optimistic gradient algorithm

Our GABP bears some relation to Accelerated Optimistic Gradient (AOG) [Cai and Zheng, ], which updates the strategy by:

$$ $\displaystyle\pi_{i}^{t+\frac{1}{2}}$ $\displaystyle=\mathop{\rm arg~{}max}\limits_{x\in\mathcal{X}_{i}}\left\{\left \langle\eta\widehat{\nabla}_{\pi_{i}}v_{i}(\pi^{t-\frac{1}{2}})+\frac{\pi_{i}^ {1}-\pi_{i}^{t}}{t+1},x\right\rangle-\frac{1}{2}\left\|x-\pi_{i}^{t}\right\|^{ 2}\right\},$ $\displaystyle\pi_{i}^{t+1}$ $\displaystyle=\mathop{\rm arg~{}max}\limits_{x\in\mathcal{X}_{i}}\left\{\left \langle\eta\widehat{\nabla}_{\pi_{i}}v_{i}(\pi^{t+\frac{1}{2}})+\frac{\pi_{i}^ {1}-\pi_{i}^{t}}{t+1},x\right\rangle-\frac{1}{2}\left\|x-\pi_{i}^{t}\right\|^{ 2}\right\}.$ $$

This can be equivalently written as:

$$ $\displaystyle\pi_{i}^{t+\frac{1}{2}}$ $\displaystyle=\mathop{\rm arg~{}max}\limits_{x\in\mathcal{X}_{i}}\left\{\eta \left\langle\widehat{\nabla}_{\pi_{i}}v_{i}(\pi^{t-\frac{1}{2}}),x\right \rangle-\frac{1}{2}\left\|x-\frac{t\pi_{i}^{t}+\pi_{i}^{1}}{t+1}\right\|^{2} \right\},$ $\displaystyle\pi_{i}^{t+1}$ $\displaystyle=\mathop{\rm arg~{}max}\limits_{x\in\mathcal{X}_{i}}\left\{\eta \left\langle\widehat{\nabla}_{\pi_{i}}v_{i}(\pi^{t+\frac{1}{2}}),x\right \rangle-\frac{1}{2}\left\|x-\frac{t\pi_{i}^{t}+\pi_{i}^{1}}{t+1}\right\|^{2} \right\}.$ $$

This means that AOG employs a convex combination $\frac{t\pi_{i}^{t}+\pi_{i}^{1}}{t+1}$ of the current strategy $\pi_{i}^{t}$ and initial strategy $\pi_{i}^{1}$ as the proximal point in gradient ascent.
However, our GABP diverges from AOG in that it uses a convex combination $\frac{k(t)\sigma_{i}^{k(t)}+\sigma_{i}^{1}}{k(t)+1}$ of $\sigma_{i}^{k(t)}$ and $\sigma_{i}^{1}$ as the reference strategy for the perturbation term.

In terms of proof for a last-iterate convergence result, Cai and Zheng [] have employed the following potential function for the full feedback setting:

$$ $\displaystyle P^{t}$ $\displaystyle:=\frac{t(t+1)}{2}\left(\eta^{2}\left\|-\widehat{V}(\pi^{t})+c^{t }\right\|^{2}+\eta^{2}\left\|\widehat{V}(\pi^{t})-\widehat{V}(\pi^{t-\frac{1}{ 2}})\right\|^{2}\right)+t\eta\langle-\widehat{V}(\pi^{t})+c^{t},\pi^{t}-\pi^{1 }\rangle,$ $$

where $c^{t}=\frac{\pi^{t-1}+\eta\widehat{V}(\pi^{t-\frac{1}{2}})+\frac{1}{t}(\pi^{1}
-\pi^{t-1})-\pi^{t}}{\eta}$ and $\widehat{V}(\cdot)=(\widehat{\nabla}_{\pi_{i}}v_{i}(\cdot))_{i\in[N]}$.
Compared to our potential function $P^{k(t)}$, their potential function includes the term of $\eta^{2}\left\|\widehat{V}(\pi^{t})-\widehat{V}(\pi^{t-\frac{1}{2}})\right\|^{2}$.
In the noisy feedback setting, the value of this term could remain high even if $\pi^{t}=\pi^{t-\frac{1}{2}}$.
Therefore, this term complicates providing a last-iterate convergence result for the noisy feedback setting.
In contrast, our potential function $P^{k(t)}$ does not contain the term depending on $\widehat{\nabla}v_{i}(\pi^{t})$:

$$ $\displaystyle P^{k(t)}$ $\displaystyle:=\frac{k(t)(k(t)+1)}{2}\left\|\pi^{\mu,\sigma^{k(t)-1}}-\hat{ \sigma}^{k(t)-1}\right\|^{2}$ $\displaystyle\phantom{=}+k(t)(k(t)+1)\left\langle\hat{\sigma}^{k(t)}-\pi^{\mu, \sigma^{k(t)-1}},\pi^{\mu,\sigma^{k(t)-1}}-\hat{\sigma}^{k(t)-1}\right\rangle.$ $$

This allows us to provide the last-iterate convergence rates both for full and noisy feedback settings.

### E.2 Comparison of Last-Iterate Convergence Results

In this section, we provide Table 2 for comparison with last-iterate convergence results of existing representative learning algorithms in monotone games.

**Table 2: Existing results on last-iterate convergence in monotone games. (*) means the result holds only under bandit feedback.**
| Algorithm | Full Feedback | Noisy Feedback |
| --- | --- | --- |
| Extragradient | $\mathcal{O}(1/\sqrt{T})$ | N/A |
| [Cai et al., , ] |  |  |
| Optimistic Gradient | $\mathcal{O}(1/\sqrt{T})$ | N/A |
| [Golowich et al., , Gorbunov et al., , Cai et al., ] |  |  |
| Extra Anchored Gradient | $\mathcal{O}(1/T)$ | N/A |
| [Yoon and Ryu, ] |  |  |
| Accelerated Optimistic Gradient | $\mathcal{O}(1/T)$ | N/A |
| [Cai and Zheng, ] |  |  |
| Iterative Tikhonov Regularization | N/A | Asymptotic${}^{\text{*}}$ |
| [Koshal et al., , Tatarenko and Kamgarpour, ] |  |  |
| Adaptively Perturbed Gradient Ascent | $\tilde{\mathcal{O}}(1/\sqrt{T})$ | $\tilde{\mathcal{O}}(1/T^{\frac{1}{10}})$ |
| [Abe et al., ] |  |  |
| Ours | $\tilde{\mathcal{O}}(1/T)$ | $\tilde{\mathcal{O}}(1/T^{\frac{1}{7}})$ |

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 6
presentation: 2
questions: (1) According to the definition, $\sigma_i^1=\pi^1$. Am I missing anything?

(2) Why are we not using the Nash Gap as a metric, which seems more natural?
soundness: 3
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.
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.
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?

(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?

---

confidence: 2
contribution: 3
initial_rating: 8
presentation: 3
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?
soundness: 4
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.
- The paper is well-written. Proof sketches are shown for main theorems.
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.
weaknesses: The paper does not discuss limitations.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: * It would be better to give more explanation on the intuition for the perturbation term (*) in Eq (3).
* 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)?
soundness: 2
strengths: * The GABP algorithm leverages a perturbation term to enhance the stability and convergence rate.
* Theoretical analysis covers both full and noisy feedback settings.
* The study includes diverse game settings and benchmarks against state-of-the-art algorithms.
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.
weaknesses: * The proof strategy seems standard, and the technical contribution is not clarified in this paper.

---

confidence: 3
contribution: 2
initial_rating: 6
presentation: 3
questions: See Weaknesses.
soundness: 3
strengths: Using the carefully constructed perturbation, the newly proposed GABP achieves a faster convergence rate compared to APMD. A good contribution to the literature.

The related literature is detailed and explains the
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.
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}$.

Although 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.

The 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.

Meta-review: The paper introduces a modifed perturbed scheme called GABP and show last iterate convergence with rate of 1/T and 1/T^1/7 for full feedback and noisy feedback models on monotone games. The reviewers agree that the paper has merits/novelty and all of them were positive or slightly positive about the contributions. We recommend a weak acceptance of this paper.

Decision: Accept (Poster)