Uncoupled and Convergent Learning in Monotone Games under Bandit Feedback

## Abstract

Abstract We study the problem of no-regret learning algorithms for general monotone and smooth games and their last-iterate convergence properties. Specifically, we investigate the problem under bandit feedback and strongly uncoupled dynamics, which allows modular development of the multi-player system that applies to a wide range of real applications. We propose a mirror-descent-based algorithm, which converges in O ⁢ ( T − 1 / 4 ) 𝑂 superscript 𝑇 1 4 O(T^{-1/4}) italic_O ( italic_T start_POSTSUPERSCRIPT - 1 / 4 end_POSTSUPERSCRIPT ) and is also no-regret. The result is achieved by a dedicated use of two regularizations and the analysis of the fixed point thereof.
The convergence rate is further improved to O ⁢ ( T − 1 / 2 ) 𝑂 superscript 𝑇 1 2 O(T^{-1/2}) italic_O ( italic_T start_POSTSUPERSCRIPT - 1 / 2 end_POSTSUPERSCRIPT ) in the case of strongly monotone games.
Motivated by practical tasks where the game evolves over time, the algorithm is extended to time-varying monotone games. We provide the first non-asymptotic result in converging monotone games and give improved results for equilibrium tracking games.

## 1 Introduction

We consider multi-player online learning in games.
In this problem, the cost function for each player is unknown to the player, and they need to learn to play the game through repeated interaction with other players. We focus on a class of monotone and smooth games, which was first introduced by Rosen, (). This encapsulates a wide array of common games, such as two-player zero-sum games, monotone-concave games, and zero-sum polymatrix games (Bregman and Fokin,, ). Our goal is to find algorithms that solve the problem under bandit feedback and strongly uncoupled dynamics. Within this context, each player can only access information regarding the cost function associated with their chosen actions without prior insight into their counterparts. This allows modular development of the multi-player system in real applications and leverages existing single-agent learning algorithms for reuse.

Many works have focused on the time-average convergence to Nash equilibrium on learning in monotone games (Even-Dar et al.,, ; Syrgkanis et al.,, ; Farina et al.,, ).
However, these works only guarantee the convergence of the time average of the joint action profile. Such convergence properties are less appealing, because while the trajectories of the players converge in the time-average sense, it may still exhibit cycling (Mertikopoulos et al.,, ). This jeopardizes the practical use of such algorithms.

Popular no-regret algorithms such as mirror descent have demonstrated convergence in the last iterate within specific scenarios, such as two-player zero-sum games (Cai et al.,, ) and strongly monotone games (Bravo et al.,, ; Drusvyatskiy et al.,, ; Lin et al.,, ).
Yet convergence to Nash equilibrium in monotone and smooth games is not available unless one assumes exact gradient feedback and coordination of players (Cai et al.,, ; Cai and Zheng,, ).
It remains open as to whether a no-regret algorithm can efficiently converge to a Nash equilibrium in monotone games with bandit feedback and strongly uncoupled dynamics. In this paper, we investigate the pivotal question:

How fast can no-regret algorithms converge (in the last iterate) to a Nash equilibrium in general monotone and smooth games with bandit feedback and strongly uncoupled dynamics?

In this work, we present a mirror-descent-based algorithm designed to converge to the Nash equilibrium in static monotone and smooth games. Our algorithm is uncoupled and convergent and is applicable to the general monotone and smooth game setting. Motivated by real applications, where many games are also time-varying, we extend our study to encompass time-varying monotone games. This allows the algorithm to be deployed in both stationary and non-stationary tasks.
We achieve state-of-the-art results in both monotone games and time-varying monotone games.

We summarize our main contributions as follows:

- •
In static monotone and smooth games:
–
Under bandit feedback and strongly uncoupled dynamics, we show our algorithm achieves a last-iterate convergence rate of $O(T^{-1/4})$.
–
In cases where the game exhibits strong monotoneity, our result improves to $O(T^{-1/2})$, matching the current best available convergence rates for strongly monotone games (Drusvyatskiy et al.,, ; Lin et al.,, ).
–
Our algorithm is no regret albeit players may be self-interested. The individual regret is at most $O(T^{1/4})$ in monotone games and at most $O(T^{1/2})$ in strongly monotone games.
- •
In time-varying monotone and smooth games:
–
If the game eventually converges to a static state within a time frame of $O(T^{\alpha})$, our algorithm achieves convergence in $O(T^{-1/4+\alpha})$.
–
If the game does not converge but experiences gradual changes in the Nash equilibrium that evolves in $O(T^{\psi})$, our algorithm exhibits convergence rates of $O\left(\max{T^{2\varphi/3-2/3},T^{(4\varphi+5)^{2}/72-9/8}}\right)$. The algorithm outperforms best available results of $T^{\varphi/5-1/5}$ by Duvocelle et al., () and $T^{\varphi/3-2/3}$ by Yan et al., ().

Table 1 and Table 2 summarize our results and the results of previous works.

## 2 Related Works

#### Monotone games

The convergence of monotone games has been studied in a significant line of research.
For a strongly monotone game under exact gradient feedback, the linear last-iterate convergence rate is known (Tseng,, ; Liang and Stokes,, ; Zhou et al.,, ). Under noisy gradient feedback, Jordan et al., () showed a last-iterate convergence rate of $O(T^{-1})$. Under bandit feedback, Bervoets et al., () proposed an algorithm that asymptotically converges to the equilibrium if it is unique. Bravo et al., () subsequently introduced an algorithm with a last-iterate convergence rate of $O(T^{-1/3})$, while also ensuring the no-regret property. Later works (Lin et al.,, ) further improved the last-iterate convergence rate to $O(T^{-1/2})$ under bandit feedback using the self-concordant barrier function. Jordan et al., () gave a result of the same rate, but with the additional assumption that the Jacobian of each player’s gradient is Lipschitz continuous. In the case of bandit but noisy feedback (with a zero-mean noise), Lin et al., () showed that the convergence rate is still $O(T^{-1/2})$.

For monotone but not strongly monotone games, Mertikopoulos and Zhou, () leveraged the dual averaging algorithm to demonstrate an asymptotic convergence rate under noisy gradient feedback. With access to the exact gradient information, Cai and Zheng, () gave a last-iterate convergence rate of $O(T^{-1})$. In the context of bandit feedback, Tatarenko and Kamgarpour, () proposed an algorithm that asymptotically converges to the Nash equilibrium. Table 1 provides a summary of the recent results.

#### Time-varying monotone games

Motivated by real-world applications such as Cournot competition, where multiple firms supply goods to the market and pricing is subject to fluctuations due to factors like weather, holidays, and politics. Duvocelle et al., () studied the strongly monotone game under a time-varying cost function. When the game converges to a static state, they propose an algorithm that achieves asymptotic convergence under bandit feedback. Assuming the cost function varies $O(T^{\phi})$ across a horizon $T$, Duvocelle et al., () provided an algorithm that attains a convergence rate of $O(T^{\phi/5-1/5})$ under bandit feedback. Subsequent work of Yan et al., () further improved this rate to $O(T^{\phi/3-2/3})$ under exact gradient feedback.

**Table 1: Summary of results for monotone games. ”E” stands for the result in expectation and ”P” stands for the result held in high probability. Strongly monotone games are abbreviated to ”StroM”, while monotone games are abbreviated to ”M”. We use ”linear*” to denote the two-player zero-sum game, which is a special case of the linear game. We use ”(N)” to remark that the results can also be obtained with noisy feedback.**
|  | Class of games | Feedback | Results |
| --- | --- | --- | --- |
| Bravo et al., () | StroM | bandit | $O(T^{-1/3})$ (E) |
| Drusvyatskiy et al., () | StroM | bandit | $O(T^{-1/2})$ (E) |
| Lin et al., () | StroM | bandit (N) | $O(T^{-1/2})$ (E) |
| Jordan et al., () | StroM | noisy gradient | $O(T^{-1})$ |
| Ours | StroM | bandit (N) | $O(T^{-1/2})$ (E & P) |
| Mertikopoulos and Zhou, () | M | noisy gradient | asymptotic |
| Cai and Zheng, () | M | exact gradient | $O(T^{-1})$ |
| Tatarenko and Kamgarpour, () | M | bandit | asymptotic |
| Ours | M | bandit (N) | $O(T^{-1/4})$ (E) |
| Cai et al., () | linear* | bandit | $O(T^{-1/6})$ (E) |
| Ours | linear | bandit | $O(T^{-1/6})$ (E) |

**Table 2: Summary of last-iterate convergence results for time-varying games. All results here are in expectation results. Strongly monotone games are abbreviated to ”StroM”, and monotone games are abbreviated to ”M”.**
|  | Class of<br>games | Time-varying property | Feedback | Results |
| --- | --- | --- | --- | --- |
| Duvocelle et al., () | StroM | converging in $O(T^{\alpha})$ | bandit | asymptotic |
| Ours | M | converging in $O(T^{\alpha})$ | bandit | $O(T^{-1/4+\alpha})$ |
| Duvocelle et al., () | StroM | $O(T^{\varphi})$ variation path | bandit | $O(T^{\varphi/5-1/5})$ |
| Yan et al., () | StroM | $O(T^{\varphi})$ variation path | exact<br>gradient | $O(T^{\varphi/3-2/3})$ |
| Ours | M | $O(T^{\varphi})$ variation path | bandit | $O\left(\max\{T^{2\varphi/3-2/3}\right.$<br>$\left.T^{(4\varphi+5)^{2}/72-9/8}\}\right)$ |

## 3 Preliminaries

We consider a multi-player game with $n$ players, with the set of players denoted as $\mathcal{N}$. Each player $i$ takes action on a compact and monotone set $\mathcal{X}_{i}\subseteq\mathbb{R}^{d}$ of $d$ dimensions, and has cost function $c_{i}(x_{i},x_{-i})$, where $x_{i}\in\mathcal{X}_{i}$ is the action of the $i$-th player and $x_{-i}\in\prod_{j\in[n],j\neq i}\mathcal{X}_{j}$ is the action of all other players. We assume the radius of $\mathcal{X}_{i}$ is bounded, i.e., $\|x-x^{\prime}\|\leq B,\forall x,x^{\prime}\in\mathcal{X}_{i}$. Without loss of generality, we further assume $c_{i}(x)\in[0,1]$.

In this work, We study a class of monotone continuous games, where the cost functions are monotone and continuous (Assumption 3.1). Games that satisfy this assumption include monotone-concave games, monotone potential games, extensive form games, Cournot competition, and splittable routing games. A discussion of these games is available in Section 3.1. Note that the class of monotone continuous games is commonly studied in the literature (Lin et al.,, ; Farina et al.,, ).

###### Assumption 3.1 .

For all player $i\in\mathcal{N}$, the cost function $c_{i}(x_{i},x_{-i})$ is continuous, differentiable, convex, and $\ell_{i}$-smooth in $x_{i}$. Further, $c_{i}$ has bounded gradient $|\nabla_{i}c_{i}(x)|\leq G$ and the gradient $F(x)=[\nabla_{i}c_{i}(x)]_{i\in\mathcal{N}}$ is a monotone operator, i.e., $(F(x)-F(y))^{\top}(x-y)\geq 0$, $\forall x,y$.

For notational convenience, we denote $L=\sum_{i\in\mathcal{N}}\ell_{i}$.

A common solution concept in the game is Nash equilibrium, which is a state of dynamic where no player can reduce its cost by unilaterally changing its action. Our aim is to learn a Nash equilibrium $x^{\ast}\in\prod_{i}\mathcal{X}_{i}$ of the game. Formally, the Nash equilibrium is defined as follows.

###### Definition 3.1 (Nash equilibrium) .

An action $x^{\ast}\in\prod_{i}\mathcal{X}_{i}$ is a Nash equilibrium if $c_{i}(x^{\ast})\leq c_{i}(x_{i},x_{-i}^{\ast})\,,\ \forall x_{i}\in\mathcal{X}
_{i},x_{i}\neq x_{i}^{\ast},i\in\mathcal{N}$.

When the game satisfies Assumption 3.1, and is with a compact action set, it is known that it must admit at least one Nash equilibrium (Debreu,, ).

###### Assumption 3.1 .

###### Definition 3.1 (Nash equilibrium) .

### 3.1 Examples of monotone Continuous Games

A wide range of monotone games are captured by Assumption 3.1, and we now present a few classic examples. We include more examples in the appendix.

###### Example 3.1 (monotone-concave game) .

Consider a two-player convex-concave game, where the objective function is $c_{1}(x_{1},x_{2})=f(x_{1},x_{2})$, $c_{2}(x_{1},x_{2})=-f(x_{1},x_{2})$. It is immediate that if $f$ is continuous, differentiable, smooth, convex in $x_{1}$, concave in $x_{2}$, then the game satisfies Assumption 3.1. Examples are rock paper scissors and chicken games.

###### Example 3.2 (Cournot competition) .

In the Cournot oligopoly model, there is a finite set of $N$ firms, where firm $i$ supplies the market with a quantity $x_{i}\in\left[0,C_{i}\right]$ of some good and $C_{i}$ is the firm’s production capacity. The good is priced as a decreasing function $P(x_{\mathrm{tot}})=a-bx_{\mathrm{tot}}$, where $x_{\mathrm{tot}}=\sum_{i=1}^{N}x_{i}$ is the total number of goods supplied to the market, and $a,b>0$ are positive constants. The cost of firm $i$ is then given by $c_{i}(x_{i},x_{-i})=d_{i}x_{i}-x_{i}P(x_{\mathrm{tot}})$, where $d_{i}$ is the cost of producing one unit of good. This is the associated production cost minus the total revenue from producing $x_{i}$ units of goods. It is clear that $c_{i}$ is continuous and differentiable, and Bravo et al., () showed $c_{i}$ has positive definite and bounded hessian (is convex and smooth).

###### Example 3.3 (Splittable routing game) .

In a splittable routing game, each player directs a flow, denoted as $f_{i}$, from a source to a destination within an undirected graph $G=(V,E)$. Each edge $e\in E$ is linked to a latency function, represented as $\ell_{e}(f)$, which denotes the latency cost of the flow passing through the edge. The strategies available to player $i$ are the various ways of dividing or ”splitting” the flow $f_{i}$ into distinct paths connecting the source and the destination. With some restrictions on the latency function, the game satisfies Assumption 3.1 (Roughgarden and Schoppmann,, ).

###### Example 3.1 (monotone-concave game) .

###### Example 3.2 (Cournot competition) .

###### Example 3.3 (Splittable routing game) .

### 3.2 Bandit Feedback and Strongly Uncoupled Dynamic

In this work, we focus on learning under bandit feedback and strongly uncoupled dynamics. The bandit feedback setting restricts each player to only observe the cost function $c_{i}(x_{i},x_{-i})$ with respect to the action taken $x_{i}$. The strongly uncoupled learning dynamic (Daskalakis et al.,, ) means players do not have prior knowledge of cost function or the action space of other players and can only keep track of a constant amount of historical information. As the bandit feedback and strongly uncoupled dynamic only require each player to access information of its own, this allows for modular development of the multi-player system, by reusing existing single-agent learning algorithms.

## 4 Algorithm

Our algorithm builds upon the renowned mirror-descent algorithm. The efficacy of online mirror-descent in solving Nash equilibrium has been demonstrated under full information, or either linear or strongly monotone cost functions, with extensive investigations into its last-iterate convergence investigated in Cen et al., (); Lin et al., (); Cai et al., (); Duvocelle et al., ().

Our algorithm differs from classic online mirror descent approaches by making use of two regularizers: A self-concordant barrier regularizer $h$ to build an efficient Ellipsoidal gradient estimator and contest the bandit feedback; and a regularizer $p$ to accommodate monotone (and not strongly monotone) games. Similar use of two regularizers has also been investigated (Lin et al.,, ). However, their method used the Euclidean norm regularize, which cannot be extended to our setting.

#### Regularizers

Let $h$ be a $\nu$-self-concordant barrier function (Definition 4.1), $p$ be a convex function with $\mu I\preceq\nabla^{2}p(x)\preceq\zeta I$, $\zeta>0,\mu\geq 0$. Let $D_{p}$ denote the Bregman divergence induced by $p$. We choose $p$ such that for any $x_{i},x_{i}^{\prime}\in\mathcal{X}_{i}$, $D_{p}(x_{i},x_{i}^{\prime})\leq C_{p}<\infty$, and for some $\kappa>0$, $c_{i}(x_{i},x_{-i})-\kappa p(x_{i})$ to be convex. Notice that when $c_{i}$ is convex but not linear, we can always find such $p$ when the action set is bounded. Intuitively, this is to interpolate a function $p$ that possesses less curvature than all $c_{i}$. We will discuss the modification to the algorithm needed when $c_{i}$ is linear in Section 5.3.

###### Definition 4.1 .

A function $h:\mathop{int}(\mathcal{X})\mapsto\mathbb{R}$ is a $\nu$-self concordant barrier for a closed convex set $\mathcal{X}\subseteq\mathbb{R}^{n}$, where $\mathop{int}(\mathcal{X})$ is an interior of $\mathcal{X}$, if 1) $h$ is three times continuously differentiable; 2) $h(x)\rightarrow\infty$ if $x\rightarrow\partial\mathcal{X}$, where $\partial\mathcal{X}$ is a boundary of $\mathcal{X}$; 3) for $\forall x\in\operatorname{int}(\mathcal{X})$ and $\forall\lambda\in\mathbb{R}^{n}$, we have $\left|\nabla^{3}h(x)[\lambda,\lambda,\lambda]\right|\leq 2\left(\lambda^{\top}
\nabla^{2}h(x)\lambda\right)^{3/2}$ and $\left|\nabla h(x)^{\top}\lambda\right|\leq\sqrt{\nu}\left(\lambda^{\top}\nabla
^{2}h(x)\lambda\right)^{1/2}$ where $\nabla^{3}h(x)\left[\lambda_{1},\lambda_{2},\lambda_{3}\right]=\left.\frac{
\partial^{3}}{\partial t_{1}\partial t_{2}\partial t_{3}}h\left(x+t_{1}\lambda
_{1}+t_{2}\lambda_{2}+t_{3}\lambda_{3}\right)\right|_{t_{1}=t_{2}=t_{3}=0}$ .

It is shown that any closed convex domain of $\mathbb{R}^{d}$ has a self-concordant barrier (Lee and Yue,, ).

###### Definition 4.1 .

#### Ellipsoidal gradient estimator

As our algorithm operates under bandit feedback and strongly uncoupled dynamics, we would need to design a gradient estimator while only using costs for the individual player.

Let $\mathbb{S}^{d}$, $\mathbb{B}^{d}$ be the $d$-dimensional unit sphere and the $d$-dimensional unit ball, respectively. Our algorithm estimates the gradient using the following ellipsoidal estimator:

$$ $\displaystyle\hat{g}_{i}^{t}=\frac{d}{\delta_{t}}c_{i}(\hat{x}^{t})(A_{i}^{t}) ^{-1}z_{i}^{t}\,,\quad A_{i}^{t}=(\nabla^{2}h(x_{i}^{t})+\eta_{t}(t+1)\nabla^{ 2}p(x_{i}^{t}))^{-1/2}\,,\quad\hat{x}_{i}^{t}=x_{i}^{t}+\delta_{t}A_{i}^{t}z_{ i}^{t}\,,$ $$

where $z_{i}^{t}$ is uniformly independently sampled from $\mathbb{S}^{d}$ and $\delta_{t},\eta_{t}\in[0,1]$ are tunable parameters.

One can show that $\hat{g}_{i}^{t}$ is an unbiased estimate of the gradient of a smoothed cost function $\hat{c}_{i}(x^{t})=\mathbb{E}_{w_{i}^{t}\sim\mathbb{B}^{d}}\mathbb{E}_{\mathbf
{z}_{-i}^{t}\sim\Pi_{j\neq i}\mathbb{S}^{d}}\left[c_{i}\left(x_{i}^{t}+A_{i}^{
t}w_{i}^{t},\hat{x}_{-i}^{t}\right)\right]$. When $p$ is strongly convex, one can upper bound $\left\|\nabla_{i}\hat{c}_{i}(x)-\nabla_{i}c_{i}(x)\right\|$ by the maximum eigenvalue of $A_{i}^{t}$ and it suffices to take $\delta_{t}=1$, which recovers the results in Lin et al., (). However, when $p$ is convex and not strongly convex, one would need to carefully tune $\delta_{t}$ to control the bias from estimating the smoothed cost function. This ellipsoidal gradient estimator was first introduced by Abernethy et al., () for the case of $c_{i}$ being linear, and was then extended by Hazan and Levy, () to the case of strongly convex costs. In learning for games, the ellipsoidal estimator was used in the case of strongly monotone games (Bravo et al.,, ; Lin et al.,, ).

Based on the ellipsoidal gradient estimator, we present our uncoupled and convergent algorithm for monotone games under bandit feedback.

Figure: Algorithm 1 Algorithm

#### Implementation

Notice that solving Equation (1) is equivalent to solving a convex but potentially non-smooth optimization problem. Certain sets $\mathcal{X}\subseteq\mathbb{R}^{d}$, including the cases when $\mathcal{X}$ is the strategy space of a normal-form game or an extensive-form game, can be solved by proximal Newton algorithm provably in $O(\log^{2}(1/\epsilon))$ iterations (Farina et al.,, ). When such guarantees are not required, one could accommodate other optimization methods in solving (1). Our experiment section provides more details.

The choice of $p$ and $h$ is game-dependent. For example, when $c_{i}(x)=x^{2}$ and the action set is on the positive half line, we can use the negative log function as our self-concordant barrier function $h$ and take $p=x$.

## 5 No-regret Convergence to Nash Equilibrium

In this section, we present our main results on the last-iterate convergence to the Nash equilibrium. We show that Algorithm 1 converges to the Nash equilibrium in monotone, strongly monotone, and linear games. Such convergence is no-regret, meaning that the individual regret of each player is sublinear.

For notational simplicity, we present the results in a perfect bandit feedback model, where player $i$ observes exactly $c_{i}(x^{t})$. The discussion of noisy bandit feedback, where player $i$ observes $c_{i}(x^{t})+\epsilon_{i}^{t}$, with $\epsilon_{i}^{t}$ be a zero-mean noise, is deferred to the appendix (Theorem D.1).

### 5.1 Perfect Bandit Feedback

The following theorem describes the last-iterate convergence rate (in expectation) for convex and strongly convex loss under perfect bandit feedback.

###### Theorem 5.1 .

Take $\eta_{t}=\begin{cases}\frac{1}{2dt^{3/4}}&\mu=0\\
\frac{1}{2dt^{1/2}}&\mu>0\,,\end{cases}$, $\delta_{t}=\begin{cases}\frac{1}{t^{1/4}}&\mu=0\\
1&\mu>0\,.\end{cases}$. With Algorithm 1, we have

$$ $\displaystyle\mathbb{E{}}\left[\sum_{i\in\mathcal{N}}D_{p}\left(x_{i}^{\ast},x _{i}^{T+1}\right)\right]\leq\$ $\displaystyle\begin{cases}O\left(\frac{nd\nu\log(T)}{\kappa T^{1/4}}+\frac{n \zeta dB}{T^{3/4}}+\frac{nBL}{\kappa\sqrt{T}}+\frac{ndC_{p}}{T^{1/4}}+\frac{nd \log(T)}{\kappa T^{1/4}}+\frac{\sqrt{n}B^{2}L\log(T)}{\kappa T^{1/4}}\right)& \mu=0\\ O\left(\frac{nd\nu\log(T)}{\kappa\sqrt{T}}+\frac{nd\zeta B}{T}+\frac{nBL}{ \kappa\sqrt{T}}+\frac{ndC_{p}}{\sqrt{T}}+\frac{nd\log(T)}{\kappa\sqrt{T}}+ \frac{BL\log(T)}{\mu\kappa\sqrt{T}}\right)&\mu>0\,,\end{cases}\,.$ $$

In the case of the monotone games, Bravo et al., () showed an asymptotic convergence to Nash equilibrium. To the best of our knowledge, Theorem 5.1 is the first result on the last-iterate convergence rate for monotone games. For strongly monotone games, Bravo et al., () first gave a $O(T^{-1/3})$ last-iterate convergence rate, which was later improved to $O(T^{-1/2})$ by Lin et al., ().

While we defer the proof to the appendix, we discuss the main ideas of deriving the results. By the update rule, we can obtain the inequality

$$ $\displaystyle\begin{split}&D_{h}\left(\omega_{i},x_{i}^{t+1}\right)+\eta_{t} \kappa(t+1)D_{p}\left(\omega_{i},x_{i}^{t+1}\right)\\ \leq\ &D_{h}\left(\omega_{i},x_{i}^{t}\right)+\eta_{t}\kappa(t+1)D_{p}\left( \omega_{i},x_{i}^{t}\right)+\eta_{t}\left\langle\nabla_{i}c_{i}\left(x^{t} \right),\omega_{i}-x_{i}^{t}\right\rangle+\eta_{t}\cdot\text{residual terms}\, ,\end{split}$ (2) $$

where $\omega_{i}$ is a fixed point given.
When the game is strongly monotone, we can directly use strongly monotoneity and take $p$ to be the Euclidean norm to obtain a recursive relation similar to $\left\|\omega_{i}-x_{i}^{t+1}\right\|_{2}^{2}\leq(1-\eta_{t}^{2})\left\|\omega
_{i}-x_{i}^{t+1}\right\|_{2}^{2}+\text{residual terms}$. This amounts to applying this recursion and upper-binding the residual terms individually to obtain a last-iterate convergence. However, when the game is monotone but not strongly monotone, we will need a different approach. Notice that $G=\nabla c_{i}-\nabla p$ is a monotone operator. Using the property of Bregman divergence, we have

$$ $\displaystyle\left\langle G(x)-G(x^{\prime}),x^{\prime}-x\right\rangle\leq\$ $\displaystyle-\sum_{i\in\mathcal{N}}\left(D_{p}\left(x_{i},x_{i}^{\prime} \right)+D_{p}\left(x_{i}^{\prime},x_{i}\right)\right)\,.$ $$

We then sum (2) and leverage the combination of two regularizations, which obtain

$$ $\displaystyle\eta_{T}\kappa(T+1)\sum_{i\in\mathcal{N}}D_{p}\left(\omega_{i},x_ {i}^{T+1}\right)$ $\displaystyle\leq\$ $\displaystyle\sum_{i\in\mathcal{N}}D_{h}\left(\omega_{i},x_{i}^{1}\right)+ \kappa\sum_{i\in\mathcal{N}}D_{p}\left(\omega_{i},x_{i}^{1}\right)+\sum^{T}_{t =1}\sum_{i\in\mathcal{N}}\eta_{t}\left\langle\nabla_{i}c_{i}(\omega),\omega_{i }-x_{i}^{t}\right\rangle$ $\displaystyle\ +\sum^{T}_{t=1}\sum_{i\in\mathcal{N}}\eta_{t}\left\langle\hat{g }_{i}^{t}-\nabla_{i}c_{i}\left(x^{t}\right),\omega_{i}-x_{i}^{t}\right\rangle+ \sum^{T}_{t=1}\sum_{i\in\mathcal{N}}\eta_{t}\left\langle\hat{g}_{i}^{t},x_{i}^ {t}-x_{i}^{t+1}\right\rangle\,.$ $$

Now it suffices to properly choose a fixed point $\omega_{i}$ such that both the first term $\sum_{i\in\mathcal{N}}D_{h}\left(\omega_{i},x_{i}^{1}\right)$ and the third term $\sum^{T}_{t=1}\sum_{i\in\mathcal{N}}\eta_{t}\left\langle\nabla_{i}c_{i}(\omega
),\omega_{i}-x_{i}^{t}\right\rangle$ are bounded. When $\omega_{i}$ is the Nash equilibrium $x_{i}^{\ast}$, the third term can be upper bounded trivially using the monotoneity of $c_{i}$, while it does not imply a bounded first term. Therefore, we set $\omega_{i}=x_{i}^{\ast}$ when the first term can be bounded. Otherwise, we set it to a close enough point to $x_{i}^{\ast}$, such that the first term can be bounded and the third term is bounded through a more careful calculation.

###### Theorem 5.1 .

#### High probability result

In the case of strongly monotone game, our results show that the $O(T^{-1/4})$ last-iterate convergence rate holds with high probability. This is the first high probability result for last-iterate convergence in strongly monotone games.

###### Theorem 5.2 .

With a probability of at least $1-\log(T)\delta$, $\delta\leq e^{-1}$, and with Algorithm 1, we have $\sum_{i\in\mathcal{N}}D_{p}\left(x_{i}^{\ast},x_{i}^{T+1}\right)\leq O\left(
\frac{nd\nu\log(T)}{\sqrt{T}}+\frac{nd\zeta B}{T}+\frac{nBL}{\sqrt{T}}+\frac{
ndC_{p}}{\sqrt{T}}+\frac{nd\log(T)}{\sqrt{T}}+\frac{dBL\log(T)}{\mu\sqrt{T}}+
\frac{nBd^{2}\log^{2}(1/\delta)\log(T)}{\min\{\sqrt{\mu},\mu\}\sqrt{T}}\right)$.

###### Theorem 5.2 .

### 5.2 Individual Low Regret

Beyond the fast convergence to Nash equilibrium, our algorithm also ensures each player with a sublinear regret when playing against other players. The sublinear regret convergence is a desirable property as the players could be self-interested in general, and want to ensure their return even when other players are not adhering to the protocol. The low regret property remains true for players that are potentially adversarial, despite the convergence to Nash equilibrium no longer holds in that case.

For player $i$, and a sequence of actions $\{\hat{x}_{i}^{t}\}_{t=1}^{T}$, define the individual regret as the cumulative expected difference between the costs received and the cost of playing the hindsight optimal action. That is, $\sum^{T}_{t=1}\mathbb{E{}}\left[c_{i}\left(\hat{x}_{i}^{t},x_{-i}^{t}\right)-c
_{i}\left(\omega_{i},x_{-i}^{t}\right)\right]$, where $\{x_{-i}^{t}\}_{t=1}^{T}$ is a fixed sequence of actions of other players. The following theorem shows a guarantee of the individual regret of each player.

###### Theorem 5.3 .

Take $\eta_{t}=\begin{cases}\frac{1}{2dt^{3/4}}&\mu=0\\
\frac{1}{2dt^{1/2}}&\mu>0\,,\end{cases}$, $\delta_{t}=\begin{cases}\frac{1}{t^{1/4}}&\mu=0\\
1&\mu>0\,,\end{cases}$. For a fixed $\omega_{i}\in\mathcal{X}_{i}$, a fixed sequence of $\{x_{-i}^{t}\}^{T}_{t=1}$, and with Algorithm 1, we have

$$ $\displaystyle\sum^{T}_{t=1}\mathbb{E{}}\left[c_{i}\left(\hat{x}_{i}^{t},x_{-i} ^{t}\right)-c_{i}\left(\omega_{i},x_{-i}^{t}\right)\right]=\ \begin{cases}O \left(\nu dT^{3/4}\log(T)+G\sqrt{T}+\ell_{i}\sqrt{n}BT^{3/4}\right)&\mu=0\\ O\left(\nu d\sqrt{T}\log(T)+G\sqrt{T}+\frac{nB\ell_{i}\sqrt{T}}{\mu}\right)& \mu>0\end{cases}\,.$ $$

Our result matches the $\sqrt{T}$ regret bound for strongly monotone games (Lin et al.,, ), but applies to monotone games as well.

###### Theorem 5.3 .

#### Implication on social welfare

By designing the algorithm to be no-regret, we can also show that the social welfare attained by the algorithm also converges to the optimal value.

The social welfare for a joint action $x$ is defined as $\mathrm{SW}(x)=\sum_{i\in\mathcal{N}}c_{i}(x)$. We let $\mathrm{OPT}=\min_{x}\mathrm{SW}(x)$ to denote the optimal social welfare.

###### Definition 5.1 ( Roughgarden, 2015 ; Syrgkanis et al., 2015 ) .

A game is $(C_{1},C_{2})$-smooth, $C_{1}>0$, $C_{2}<1$, if there exists a strategy $x^{\prime}$, such that for any $x\in\mathcal{N}$, $\sum_{i\in\mathcal{N}}c_{i}(x_{i}^{\prime},x_{-i})\leq C_{1}\mathrm{OPT}+C_{2}
\mathrm{SW}(x)$.

We have the following proposition which shows that the social welfare converges to optimal welfare on average.

###### Proposition 5.1 .

With $\eta_{t}=\frac{1}{2dt^{3/4}},\delta_{t}=\frac{1}{t^{1/4}}$, and suppose every player employ Algorithm 1, we have $\frac{1}{T}\sum^{T}_{t=1}\mathbb{E{}}\left[\mathrm{SW}(\hat{x})\right]=O\left(
\frac{C_{1}\mathrm{OPT}}{(1-C_{2})}+\frac{n\nu d\log(T)}{(1-C_{2})T^{1/4}}+
\frac{\sqrt{n}B\sum_{i\in\mathcal{N}}\ell_{i}}{(1-C_{2})T^{1/4}}\right)$.

###### Definition 5.1 ( Roughgarden, 2015 ; Syrgkanis et al., 2015 ) .

###### Proposition 5.1 .

### 5.3 Special Case: Linear Cost Function

When $c_{i}$ is linear, there does not exist a $p$ that is convex while making $c_{i}-\kappa p$ convex. Algorithm 1 therefore does not apply to the linear case.
This coincides with our intuition that the landscape $c_{i}$ does not provide enough curvature information for the algorithm to utilize.

To extend the algorithm to the linear case, we modify line 6 of Algorithm 1 as

$$ $x^{t+1}_{i}=\mathop{\rm argmin}_{x_{i}\in\mathcal{X}_{i}}\left\{\eta_{t}\left \langle x_{i},\hat{g}^{t}_{i}\right\rangle+\eta_{t}\tau(t+1)D_{p}(x_{i},x_{i}^ {t})+D_{h}(x_{i},x_{i}^{t})\right\}\,.$ $$

The idea is to first show the convergence of $x^{T}$ to a game with the cost $c_{i}(x)+\tau p(x)$. With this regularized game, we choose $p$ to be a strongly monotone function and measure the convergence in terms of the gap function $\langle c_{i}(x),x_{i}-x^{\ast}\rangle$. By carefully controlling $\tau$, we obtain the following result.

###### Theorem 5.4 .

With $\eta_{t}=\frac{1}{2d\sqrt{t}}$, $\tau=\frac{1}{T^{1/6}}$, $G_{p}=\sup_{x}\|\nabla p(x)\|$ and Algorithm 1, we have

$$ $\displaystyle\mathbb{E{}}\left[\sum_{i\in\mathcal{N}}\left\langle\nabla_{i}c_{ i}\left(x^{T}\right),x_{i}^{T}-x_{i}^{\ast}\right\rangle\right]$ $\displaystyle\leq\$ $\displaystyle\tilde{O}\left(\frac{BG_{p}+\sqrt{d(BL+G)(n\nu+nBL+nd^{2})}}{T^{1 /6}}+\frac{\sqrt{dBL(BL+G)}}{\sqrt{\mu}T^{1/6}}+\frac{\sqrt{dnC_{p}(BL+G)}}{ \sqrt{\mu}T^{1/4}}\right)\,,$ $$

Similar regularization techniques have been used in the analysis of the zero-sum game (Cen et al.,, ; Cai et al.,, ).
Our result matches the last-iterate convergence for zero-sum matrix game (Cai et al.,, ), which is a class of games with linear cost functions. However, our result is more general as it applies to multi-player linear games with monotone and compact action sets (while previous works only apply to a simplex action set). It remains open to how games with linear cost functions could be effectively learned and whether the convergence rate could be improved.

###### Theorem 5.4 .

## 6 Application to Time-varying Game

In this section, we further apply Algorithm 1 to games that evolve over time. A time-varying game $\mathcal{G}_{t}$ is a game where the cost function $c_{i}^{t}(\cdot)$, $i\in\mathcal{N}$ depends on $t$. The game $\mathcal{G}_{t}$ is not revealed to the players before choosing their actions $x_{t}$. We assume that $\mathcal{G}_{t}$ satisfies Assumption 3.1 for every $t$.

Such evolving games have applications in Kelly’s auction and power control, where the cost function may change as time-dependent values change, such as channel gains. While the changes of $\mathcal{G}_{t}$ can be random, we discuss two cases here, 1) when $\mathcal{G}_{t}$ converges to a static game $\mathcal{G}$ in $o(T)$ time, and 2) when the variation path of the Nash equilibrium, $\sum^{T}_{t=1}\|x_{i}^{t+1,\ast}-x_{i}^{t,\ast}\|$ is bounded in $o(T)$.

#### Converging monotone game

Let $\mathcal{G}_{t}$ denote the game formed by the costs $\{c_{i}^{t}(\cdot)\}_{i\in\mathcal{N}}$, and $\mathcal{G}$ be the game formed by the costs $\{c_{i}(\cdot)\}_{i\in\mathcal{N}}$. Suppose $\mathcal{G}_{t}$ converges to $\mathcal{G}$, and let $x^{\ast}$ be the set of Nash equilibrium of the game $\mathcal{G}$. The cost function $c_{i}^{t}$ converges to some cost function $c_{i}$ in $o(T)$ time. The following theorem shows the last iterate convergence to $x^{\ast}$.

###### Theorem 6.1 .

With $\sum^{T}_{t=1}\sum_{i\in\mathcal{N}}\max_{x}\|\nabla_{i}c_{i}(x)-\nabla_{i}c_{
i}^{t}(x)\|_{2}=T^{\alpha}$, take $\eta_{t}=\frac{1}{2dt^{3/4}}$, $\delta_{t}=\frac{1}{t^{1/4}}$, and under Algorithm 1, we have $\mathbb{E{}}\left[\sum_{i\in\mathcal{N}}D_{p}\left(x_{i}^{\ast},x_{i}^{T+1}
\right)\right]\leq O\left(\frac{nd\nu\log(T)}{\kappa T^{1/4}}+\frac{n\zeta dB}
{T^{3/4}}+\frac{nBL}{\kappa\sqrt{T}}+\frac{ndC_{p}}{T^{1/4}}\right.$ $\left.+\frac{nd\log(T)}{\kappa T^{1/4}}+\frac{\sqrt{n}B^{2}L\log(T)}{\kappa T^
{1/4}}+\frac{B}{T^{1/4-\alpha}}\right)$.

For monotone games, Duvocelle et al., () showed an asymptotic last-iterate convergence rate. To the best of our knowledge, Theorem 6.1 is the first last-iterate convergence rate for the class of converging monotone game.

###### Theorem 6.1 .

#### Evolving game and equilibrium tracking

We now discuss the case where $\mathcal{G}_{t}$ does not necessarily converge to a game $\mathcal{G}$, but the cumulative changes of the equilibrium are bounded. We use the variation path $V_{i}(T)=\sum_{t\in[T]}\left\|x_{i}^{t+1,\ast}-x_{i}^{t,\ast}\right\|$ to track the cumulative changes of equilibrium. In this case, the last-iterate convergence is meaningless, and the convergence is measured in terms of the average gap.
Because of this, the algorithm is slightly modified and updates with $x^{t+1}_{i}=\mathop{\rm argmin}_{x_{i}\in\mathcal{X}_{i}}\left\{\eta_{t}\left
\langle x_{i},\hat{g}^{t}_{i}\right\rangle+D_{h}(x_{i},x_{i}^{t})\right\}$.

###### Theorem 6.2 .

Assume $V_{i}(T)\leq T^{\varphi}$, $\varphi\in[0,1]$. Take $\eta_{t}=\frac{1}{2dt^{\frac{(1-\varphi)}{3}}}$, $\delta_{t}=\frac{1}{t^{1/2}}$, and under Algorithm 1, we have $\frac{1}{T}\sum^{T}_{t=1}\sum_{i\in\mathcal{N}}\left\langle\nabla_{i}c_{i}^{t}
\left(\hat{x}_{i}^{t},\hat{x}_{-i}^{t}\right),\hat{x}_{i}^{t}-x_{i}^{t,\ast}
\right\rangle=\ \tilde{O}\Big{(}\frac{n\nu d+Ln^{3/2}B^{2}+nG}{T^{\frac{2(1-
\varphi)}{3}}}+\frac{n}{T^{\frac{9}{8}-\frac{(4\varphi+5)^{2}}{72}}}\Big{)}$.

In the case of a strongly monotone game, Duvocelle et al., () gave a result of $T^{\varphi/5-1/5}$ and Yan et al., () gave a result of $T^{\varphi/3-2/3}$. In comparison, Theorem 6.2 extends the study to monotone games, and improves the result to $O\left(\max\{T^{2\varphi/3-2/3},T^{(4\varphi+5)^{2}/72-9/8}\}\right)$.

###### Theorem 6.2 .

## 7 Experiment

In this section, we provide a numerical evaluation of our proposed algorithm in three static games. We repeat each experiment with $5$ different random seeds. We ran all experiments with a 10-core CPU, with 32 GB memory. We set $\eta_{t}=\frac{1}{\sqrt{t+1}}$, and $\delta_{t}=0.001$.

We present the results of the following example games described below. More results with other parameters can be found in the Appendix K.

#### Cournot competition

In this Cournot duopoly model, $n$ players compete with constant marginal costs, each having individual constant price intercepts and slopes. We model the game with $5$ players, where the margin cost is $40$, price intercept is $[30,50,30,50,30]$, and the price slope is $[50,30,50,30,50]$.

#### Zero-sum matrix game

In this zero-sum matrix game, the two players aim to solve the bilinear problem $\min_{x}\max_{y}x^{\top}Ay$. We set this matrix $A$ to be $[1,2],[3,4]$.

#### monotone zero-sum matrix game

In this monotone version of the zero-sum matrix game, we regularize the game by the regularizer $x^{2}+y^{2}$.

Algorithm 1 is evaluated against two baseline methods: online mirror descent and gradient descent, with exact gradient, or estimated gradient (bandit feedback). We set the learning rate $\eta$ to be $0.01$ in both zero-sum matrix games and monotone zero-sum matrix games, and $0.09$ in Cournot competition.

Figure 1 summarizes our experimental findings, where our algorithm attains comparable performance to online mirror descent and gradient descent with full information. We also compare our algorithm to gradient descent with an estimated gradient, using the same ellipsoidal gradient estimator. However, apart from the zero-sum matrix game, we find the baseline algorithm performs too poorly to be compared.

Figure: Figure 1: Experiment on Cournot competition, zero-sum two-player minimax game, and monotone-concave game.
Refer to caption: extracted/5794487/figure/cournot2.png

## 8 Conclusion

In this work, we present a mirror-descent-based algorithm that converges in $O(T^{-1/4})$ in general monotone and smooth games under bandit feedback and strongly uncoupled dynamics. Our algorithm is no-regret, and the result can be improved to $O(T^{-1/2})$ in the case of strongly-monotone games. To our best knowledge, this is the first uncoupled and convergent algorithm in general monotone games under bandit feedback. We then extend our results to time-varying monotone games and present the first result of $O(T^{-1/4})$ for converging games and the improved result of $O\left(\max\{T^{2\varphi/3-2/3},T^{(4\varphi+5)^{2}/72-9/8}\}\right)$ for equilibrium tracking. We further verify the effectiveness of our algorithm with empirical evaluations.

## Appendix A More Example Games

###### Example A.1 (Extensive form game (EFG)) .

EFGs are games on a directed tree. At terminal nodes denoted as $z\in\mathcal{Z}$, each player $i\in\mathcal{N}$ incurs a cost $c_{i}(z)$ based on a function $c_{i}:\mathcal{Z}\rightarrow\mathbb{R}$. The action set of each player, $\mathcal{X}_{i}$, is represented through a sequence-form polytope known as $\mathcal{X}_{i}$ Koller et al., (). Considering the probability $p(z)$ of reaching a terminal node $z\in\mathcal{Z}$, the cost for player $i$ is expressed as $c_{i}(x):=\sum_{z\in\mathcal{Z}}p(z)c_{i}(z)\prod_{j\in\mathcal{N}}x_{j}\left[
\sigma_{j,z}\right]$. Here, $x=\left(x_{1},\ldots,x_{n}\right)\in\prod_{j\in\mathcal{N}}\mathcal{X}_{j}$ signifies the joint strategy profile, and $x_{j}\left[\sigma{j,z}\right]$ denotes the probability mass assigned to the last sequence $\sigma_{j,z}$ encountered by player $j$ before reaching $z$. The smoothness and concavity of utilities directly arise from multilinearity.

###### Example A.2 (monotone potential game) .

A game is called a potential game if there exists a potential function $\Phi:\mathcal{X}\rightarrow\mathbb{R}$, such that, $c_{i}(x_{i},x_{-i})-c_{i}(x_{i}^{\prime},x_{-i})=\Phi(x_{i},x_{-i})-\Phi(x_{i}
^{\prime},x_{-i})$, for all $i\in\mathcal{N}$. If $\Phi$ is continuous, differentiable, smooth, and monotone in $x_{i}$, then the game satisfies Assumption 3.1. For example, a non-atomic congestion game satisfies Assumption 3.1, as shown in Proposition 1 and 2 of Chen and Lu, ().

###### Example A.1 (Extensive form game (EFG)) .

###### Example A.2 (monotone potential game) .

## Appendix B Proof of Theorem 5.1

See 5.1

###### Proof.

We now upper bound the terms in Lemma J.1.

When $\mu=0$, taking expectation conditioned on $x^{t}$, we have $\mathbb{E{}}\left[\left\|A_{i}^{t}\hat{g}_{i}^{t}\right\|^{2}\mid x^{t}\right]
=\frac{d^{2}}{\delta_{t}^{2}}\mathbb{E{}}\left[c_{i}(\hat{x}^{t})^{2}\|z_{i}^{
t}\|^{2}\mid x^{t}\right]\leq\frac{d^{2}}{\delta_{t}^{2}}$. By Lemma J.2, and the choice $\eta_{t}=\frac{1}{2d\sqrt{t}}$, we have

$$ $\displaystyle\sum^{T}_{t=1}\eta_{t}\sum_{i\in\mathcal{N}}\mathbb{E{}}\left[ \left\langle\hat{g}_{i}^{t},x_{i}^{t}-x_{i}^{t+1}\right\rangle\right]\leq\$ $\displaystyle\sum^{T}_{t=1}\eta_{t}^{2}\sum_{i\in\mathcal{N}}\mathbb{E{}}\left [\left\|A_{i}^{t}\hat{g}_{i}^{t}\right\|^{2}\right]\leq nd^{2}\sum^{T}_{t=1} \frac{\eta_{t}^{2}}{\delta_{t}^{2}}\,.$ $$

By the definition of $\hat{c}_{i}$,

$$ $\displaystyle\sum_{i\in\mathcal{N}}\sum^{T}_{t=1}\eta_{t}\mathbb{E{}}\left[ \left\langle\hat{g}_{i}^{t}-\nabla_{i}c_{i}\left(x^{t}\right),\omega_{i}-x_{i} ^{t}\right\rangle\mid x^{t}\right]$ $\displaystyle=\$ $\displaystyle\sum_{i\in\mathcal{N}}\sum^{T}_{t=1}\eta_{t}\mathbb{E{}}\left[ \left\langle\nabla_{i}\hat{c}_{i}(x^{t})-\nabla_{i}c_{i}\left(x^{t}\right), \omega_{i}-x_{i}^{t}\right\rangle\mid x^{t}\right]$ $\displaystyle=\$ $\displaystyle\sum_{i\in\mathcal{N}}\sum^{T}_{t=1}\eta_{t}\mathbb{E{}}\left[ \mathbb{E{}}_{w_{i}\sim\mathbb{B}^{d}}\mathbb{E}_{\mathbf{z}_{-i}\sim\Pi_{j \neq i}\mathbb{S}^{d}}\left\langle\nabla_{i}c_{i}\left(x_{i}^{t}+\delta_{t}A_{ i}^{t}w_{i},\hat{x}_{-i}^{t}\right)-\nabla_{i}c_{i}\left(x^{t}\right),\omega_{ i}-x_{i}^{t}\right\rangle\mid x^{t}\right]$ $\displaystyle\leq\$ $\displaystyle B\sum_{i\in\mathcal{N}}\sum^{T}_{t=1}\eta_{t}\mathbb{E{}}\left[ \mathbb{E{}}_{w_{i}\sim\mathbb{B}^{d}}\mathbb{E}_{\mathbf{z}_{-i}\sim\Pi_{j \neq i}\mathbb{S}^{d}}\left\|\nabla_{i}c_{i}\left(x_{i}^{t}+\delta_{t}A_{i}^{t }w_{i},\hat{x}_{-i}^{t}\right)-\nabla_{i}c_{i}\left(x^{t}\right)\right\|\mid x ^{t}\right]$ $$

By the smoothness of $c_{i}$,

$$ $\displaystyle\mathbb{E}_{w_{i}\sim\mathbb{B}^{d}}\mathbb{E}_{\mathbf{z}_{-i} \sim\Pi_{j\neq i}\mathbb{S}^{d}}\left[\left\|\nabla_{i}c_{i}\left(x_{i}^{t}+ \delta_{t}A_{i}^{t}w_{i},\hat{x}_{-i}^{t}\right)-\nabla_{i}c_{i}\left(x^{t} \right)\right\|\right]$ $\displaystyle\leq\$ $\displaystyle\ell_{i}\mathbb{E{}}_{w_{i}\sim\mathbb{B}^{d}}\mathbb{E}_{\mathbf {z}_{-i}\sim\Pi_{j\neq i}\mathbb{S}^{d}}\left[\sqrt{\delta_{t}^{2}\left\|A_{i} w_{i}\right\|^{2}+\delta_{t}^{2}\sum_{j\neq i}\left\|A_{j}z_{j}\right\|^{2}} \right]\,.$ $$

Since $p$ is monotone, $\nabla^{2}p(x)$ is positive semi-definite, and $A_{i}^{t}\preceq(\nabla^{2}h(x_{i}))^{-1/2}$. For $\bar{x}_{i}^{t}=x_{i}^{t}+A_{i}^{t}w_{i}^{t}$. Define $\|v\|_{x}=\sqrt{v^{\top}\nabla^{2}h(x)v}$, we have $\|\bar{x}_{i}^{t}-x_{i}^{t}\|_{x_{i}}\leq\|\omega_{i}^{t}\|\leq 1$, and $\bar{x}_{i}^{t}\in W(x_{i}^{t})$, where $W(x_{i})=\{x^{\prime}_{i}\in\mathbb{R}^{d},\|x^{\prime}_{i}-x_{i}\|_{x_{i}}
\leq 1\}$ is the Dikin ellipsoid. Since $W(x_{i})\subseteq\mathcal{X}_{i},\forall x_{i}\in\mathop{int}(\mathcal{X}_{i})$, we can upper bound $\left\|A_{i}w_{i}\right\|^{2}$ by $B^{2}$, the diameter of the set $\mathcal{X}_{i}$. Hence $\|\nabla_{i}\hat{c}_{i}(x^{t})-\nabla_{i}c_{i}\left(x^{t}\right)\|\leq\ell_{i}
\delta_{t}\sqrt{n}B$. By Lemma J.5

$$ $\displaystyle\sum_{i\in\mathcal{N}}\sum^{T}_{t=1}\eta_{t}\mathbb{E{}}\left[ \left\langle\hat{g}_{i}^{t}-\nabla_{i}c_{i}\left(x^{t}\right),\omega_{i}-x_{i} ^{t}\right\rangle\mid x^{t}\right]=\$ $\displaystyle\sum_{i\in\mathcal{N}}\sum^{T}_{t=1}\eta_{t}\mathbb{E{}}\left[ \left\langle\nabla_{i}\hat{c}_{i}\left(x^{t}\right)-\nabla_{i}c_{i}\left(x^{t} \right),\omega_{i}-x_{i}^{t}\right\rangle\mid x^{t}\right]$ $\displaystyle\leq\$ $\displaystyle\sum_{i\in\mathcal{N}}\sum^{T}_{t=1}\eta_{t}\mathbb{E{}}\left[ \left\|\nabla_{i}\hat{c}_{i}\left(x^{t}\right)-\nabla_{i}c_{i}\left(x^{t} \right)\right\|\left\|\omega_{i}-x_{i}^{t}\right\|\mid x^{t}\right]$ $\displaystyle\leq\$ $\displaystyle\sqrt{n}B^{2}\sum_{i\in\mathcal{N}}\ell_{i}\sum^{T}_{t=1}\eta_{t} \delta_{t}\,.$ $$

When $\mu>0$, we set $\delta=1$. Then, taking expectation conditioned on $x^{t}$, we have $\mathbb{E{}}\left[\left\|A_{i}^{t}\hat{g}_{i}^{t}\right\|^{2}\mid x^{t}\right]
=d^{2}\mathbb{E{}}\left[c_{i}(\hat{x}^{t})^{2}\|z_{i}^{t}\|^{2}\mid x^{t}
\right]\leq d^{2}$. By Lemma J.2, and the choice $\eta_{t}=\frac{1}{2d\sqrt{t}}$, we have

$$ $\displaystyle\sum^{T}_{t=1}\eta_{t}\sum_{i\in\mathcal{N}}\mathbb{E{}}\left[ \left\langle\hat{g}_{i}^{t},x_{i}^{t}-x_{i}^{t+1}\right\rangle\right]\leq\$ $\displaystyle\sum^{T}_{t=1}\eta_{t}^{2}\sum_{i\in\mathcal{N}}\mathbb{E{}}\left [\left\|A_{i}^{t}\hat{g}_{i}^{t}\right\|^{2}\right]\leq nd^{2}\sum^{T}_{t=1} \eta_{t}^{2}\,.$ $$

By Lemma J.5, for any $\omega_{i}\in\mathcal{X}_{i}$, we have

$$ $\displaystyle\sum_{i\in\mathcal{N}}\sum^{T}_{t=1}\eta_{t}\mathbb{E{}}\left[ \left\langle\hat{g}_{i}^{t}-\nabla_{i}c_{i}\left(x^{t}\right),\omega_{i}-x_{i} ^{t}\right\rangle\mid x^{t}\right]=\$ $\displaystyle\sum_{i\in\mathcal{N}}\sum^{T}_{t=1}\eta_{t}\mathbb{E{}}\left[ \left\langle\nabla_{i}\hat{c}_{i}(x^{t})-\nabla_{i}c_{i}\left(x^{t}\right), \omega_{i}-x_{i}^{t}\right\rangle\mid x^{t}\right]$ $\displaystyle\leq\$ $\displaystyle\sum_{i\in\mathcal{N}}B\ell_{i}\sum^{T}_{t=1}\eta_{t}\mathbb{E{}} \left[\sum_{j\in\mathcal{N}}\left(\sigma_{\max}\left(A_{j}^{t}\right)^{2} \right)\mid x^{t}\right]$ $\displaystyle\leq\$ $\displaystyle\sum_{i\in\mathcal{N}}B\ell_{i}\sum^{T}_{t=1}\frac{1}{\mu(t+1)}$ $\displaystyle\leq\$ $\displaystyle\frac{B\sum_{i\in\mathcal{N}}\ell_{i}}{\mu}\sum^{T}_{t=1}\frac{1} {(t+1)}\,.$ $$

where the third inequality is by $\nabla^{2}h(x)$ being positive definite, and $\nabla^{2}p(x)\geq\mu I$.

Let $L=\sum_{i\in\mathcal{N}}\ell_{i}$. When $\mu=0$, combing and rearranging the terms, we have

$$ $\displaystyle\mathbb{E{}}\left[\sum_{i\in\mathcal{N}}D_{p}\left(x_{i}^{\ast},x _{i}^{T+1}\right)\right]$ $\displaystyle\leq\$ $\displaystyle O\left(\frac{n\nu\log(T)}{\kappa\eta_{T}T}+\frac{n\zeta B}{\eta_ {T}T^{3/2}}+\frac{nBL}{\kappa\sqrt{T}}+\frac{n}{\kappa\sqrt{T}}+\frac{nC_{p}}{ \eta_{T}T}+\frac{nd^{2}}{\kappa\eta_{T}T}\sum^{T}_{t=1}\frac{\eta_{t}^{2}}{ \delta_{t}^{2}}+\frac{\sqrt{n}B^{2}L\sum^{T}_{t=1}\eta_{t}\delta_{t}}{\kappa \eta_{T}T}\right)\,.$ $$

Take $\eta_{t}=\frac{1}{2dt^{3/4}}$, $\delta_{t}=\frac{1}{t^{1/4}}$, then $\sum^{T}_{t=1}\frac{\eta_{t}^{2}}{\delta_{t}^{2}}=O\left(\sum^{T}_{t=1}\frac{1
}{t}\right)=O(\log(T))$, and $\sum^{T}_{t=1}\eta_{t}\delta_{t}=O\left(\sum^{T}_{t=1}\frac{1}{t}\right)=O(
\log(T))$.
Hence, we have

$$ $\displaystyle\mathbb{E{}}\left[\sum_{i\in\mathcal{N}}D_{p}\left(x_{i}^{\ast},x _{i}^{T+1}\right)\right]\leq\$ $\displaystyle O\left(\frac{nd\nu\log(T)}{\kappa T^{1/4}}+\frac{n\zeta dB}{T^{3 /4}}+\frac{nBL}{\kappa\sqrt{T}}+\frac{ndC_{p}}{T^{1/4}}+\frac{nd\log(T)}{ \kappa T^{1/4}}+\frac{\sqrt{n}B^{2}L\log(T)}{\kappa T^{1/4}}\right)\,.$ $$

When $\mu>0$, combing and rearranging the terms, we have

$$ $\displaystyle\mathbb{E{}}\left[\sum_{i\in\mathcal{N}}D_{p}\left(x_{i}^{\ast},x _{i}^{T+1}\right)\right]$ $\displaystyle\leq\$ $\displaystyle O\left(\frac{n\nu\log(T)}{\kappa\eta_{T}T}+\frac{n\zeta B}{\eta_ {T}T^{3/2}}+\frac{nBL}{\kappa\sqrt{T}}+\frac{n}{\sqrt{T}}+\frac{nC_{p}}{\eta_{ T}T}+\frac{nd^{2}}{\kappa\eta_{T}T}\sum^{T}_{t=1}\eta_{t}^{2}+\frac{BL\log(T)} {\mu\kappa\eta_{T}T}\right)\,.$ $$

Take $\eta_{t}=\frac{1}{2dt^{1/2}}$, we have

$$ $\displaystyle\mathbb{E{}}\left[\sum_{i\in\mathcal{N}}D_{p}\left(x_{i}^{\ast},x _{i}^{T+1}\right)\right]\leq\$ $\displaystyle O\left(\frac{nd\nu\log(T)}{\kappa\sqrt{T}}+\frac{nd\zeta B}{T}+ \frac{nBL}{\kappa\sqrt{T}}+\frac{ndC_{p}}{\sqrt{T}}+\frac{nd\log(T)}{\kappa \sqrt{T}}+\frac{BL\log(T)}{\mu\kappa\sqrt{T}}\right)\,.$ $$

∎

###### Proof.

## Appendix C Proof of Theorem 5.3

See 5.3

###### Proof.

Define the smoothed version of $c_{i}$ as $\hat{c}_{i}(x)=\mathbb{E}_{w_{i}\sim\mathbb{B}^{d}}\left[c_{i}\left(x_{i}+
\delta A_{i}w_{i},x_{-i}\right)\right]$.
Then, we decompose as

$$ $\displaystyle\sum^{T}_{t=1}c_{i}\left(\hat{x}_{i}^{t},x_{-i}^{t}\right)-c_{i} \left(\omega_{i},x_{-i}^{t}\right)=\$ $\displaystyle\sum^{T}_{t=1}\left(\hat{c}_{i}\left(x_{i}^{t},x_{-i}^{t}\right)- \hat{c}_{i}\left(\omega_{i},x_{-i}^{t}\right)\right)+\sum^{T}_{t=1}\left(c_{i} \left(x_{i}^{t},x_{-i}^{t}\right)-\hat{c}_{i}\left(x_{i}^{t},x_{-i}^{t}\right)\right)$ $\displaystyle\ +\sum^{T}_{t=1}\left(\hat{c}_{i}\left(\omega_{i},x_{-i}^{t} \right)-c_{i}\left(\omega_{i},x_{-i}^{t}\right)\right)+\sum^{T}_{t=1}\left(c_{ i}\left(\hat{x}_{i}^{t},x_{-i}^{t}\right)-c_{i}\left(x_{i}^{t},x_{-i}^{t} \right)\right)\,.$ $$

For the first term, recall that by the update rule, we have,

$$ $\displaystyle D_{h}\left(\omega_{i},x_{i}^{t+1}\right)+\eta_{t}\kappa(t+1)D_{p }\left(\omega_{i},x_{i}^{t+1}\right)$ $\displaystyle=\$ $\displaystyle D_{h}\left(\omega_{i},x_{i}^{t}\right)+\eta_{t}\kappa(t+1)D_{p} \left(\omega_{i},x_{i}^{t}\right)+\eta_{t}\left\langle\nabla\hat{c}_{i}\left(x ^{t}\right),\omega_{i}-x_{i}^{t}\right\rangle+\eta_{t}\left\langle\hat{g}_{i}^ {t}-\nabla\hat{c}_{i}\left(x^{t}\right),\omega_{i}-x_{i}^{t}\right\rangle$ $\displaystyle\ +\eta_{t}\left\langle\hat{g}_{i}^{t},x_{i}^{t}-x_{i}^{t+1}\right\rangle$ $\displaystyle=\$ $\displaystyle D_{h}\left(\omega_{i},x_{i}^{t}\right)+\eta_{t}\kappa(t+1)D_{p} \left(\omega_{i},x_{i}^{t}\right)+\eta_{t}\left\langle\nabla\hat{c}_{i}\left(x ^{t}\right)-\kappa\nabla p(x_{i}^{t}),\omega_{i}-x_{i}^{t}\right\rangle+\eta_{ t}\left\langle\hat{g}_{i}^{t}-\nabla\hat{c}_{i}\left(x^{t}\right)+\kappa\nabla p (x_{i}^{t}),\omega_{i}-x_{i}^{t}\right\rangle$ $\displaystyle\ +\eta_{t}\left\langle\hat{g}_{i}^{t},x_{i}^{t}-x_{i}^{t+1} \right\rangle\,.$ $$

By Lemma J.5, for any $\omega_{i}\in\mathcal{X}_{i}$, we have

$$ $\displaystyle\mathbb{E{}}\left[\left\langle\hat{g}_{i}^{t}-\nabla\hat{c}_{i} \left(x^{t}\right)+\kappa\nabla p(x_{i}^{t}),\omega_{i}-x_{i}^{t}\right\rangle \mid x^{t}\right]=\$ $\displaystyle\mathbb{E{}}\left[\left\langle\nabla_{i}\hat{c}_{i}(x^{t})-\nabla _{i}\hat{c}_{i}\left(x^{t}\right)+\kappa\nabla p(x_{i}^{t}),\omega_{i}-x_{i}^{ t}\right\rangle\mid x^{t}\right]$ $\displaystyle=\$ $\displaystyle\mathbb{E{}}\left[\kappa\left\langle\nabla p(x_{i}^{t}),\omega_{i }-x_{i}^{t}\right\rangle\mid x^{t}\right]$ $\displaystyle=\$ $\displaystyle\mathbb{E{}}\left[\kappa p(\omega_{i})-\kappa p(x_{i}^{t})-\kappa D _{p}(\omega_{i},x_{i}^{t})\mid x^{t}\right]\,,$ $$

where the last equality follows from the definition of Bregman divergence.

Therefore,

$$ $\displaystyle\mathbb{E{}}\left[D_{h}\left(\omega_{i},x_{i}^{t+1}\right)+\eta_{ t}\kappa(t+1)D_{p}\left(\omega_{i},x_{i}^{t+1}\right)\right]$ $\displaystyle=\$ $\displaystyle\mathbb{E{}}\left[D_{h}\left(\omega_{i},x_{i}^{t}\right)+\eta_{t} \kappa tD_{p}\left(\omega_{i},x_{i}^{t}\right)+\eta_{t}\left\langle\nabla\hat{ c}_{i}\left(x^{t}\right)-\kappa\nabla p(x_{i}^{t}),\omega_{i}-x_{i}^{t}\right \rangle\right]+\eta_{t}\mathbb{E{}}\left[\kappa p(\omega_{i})-\kappa p(x_{i}^{ t})\right]$ $\displaystyle\ +\mathbb{E{}}\left[\eta_{t}\left\langle\hat{g}_{i}^{t},x_{i}^{t }-x_{i}^{t+1}\right\rangle\right]\,.$ $$

By the monotoneity of $\hat{c}_{i}\left(x^{t}\right)-\kappa p(x_{i}^{t})$, we have

$$ $\displaystyle\left\langle\nabla\hat{c}_{i}\left(x^{t}\right)-\kappa\nabla p(x_ {i}^{t}),\omega_{i}-x_{i}^{t}\right\rangle\leq\$ $\displaystyle\left(\hat{c}_{i}\left(\omega_{i},x_{-i}^{t}\right)-\kappa p( \omega_{i})\right)-\left(\hat{c}_{i}\left(x_{i}^{t},x_{-i}^{t}\right)-\kappa p (x_{i}^{t})\right)\,.$ $$

Hence

$$ $\displaystyle\mathbb{E{}}\left[\hat{c}_{i}\left(x_{i}^{t},x_{-i}^{t}\right)- \hat{c}_{i}\left(\omega_{i},x_{-i}^{t}\right)\right]$ $\displaystyle\leq\$ $\displaystyle\mathbb{E{}}\left[\frac{\left(D_{h}\left(\omega_{i},x_{i}^{t} \right)-D_{h}\left(\omega_{i},x_{i}^{t+1}\right)\right)}{\eta_{t}}+\kappa\left (tD_{p}\left(\omega_{i},x_{i}^{t}\right)-(t+1)D_{p}\left(\omega_{i},x_{i}^{t+1 }\right)\right)+\left\langle\hat{g}_{i}^{t},x_{i}^{t}-x_{i}^{t+1}\right\rangle \right]\,.$ $$

When $\mu=0$, by Lemma J.2, we have $\mathbb{E{}}\left[\left\langle\hat{g}_{i}^{t},x_{i}^{t}-x_{i}^{t+1}\right
\rangle\right]\leq\eta_{t}\mathbb{E{}}\left[\left\|A_{i}^{t}\hat{g}_{i}^{t}
\right\|^{2}\right]$.
Taking expectation conditioned on $x^{t}$, we have $\mathbb{E{}}\left[\left\|A_{i}^{t}\hat{g}_{i}^{t}\right\|^{2}\mid x^{t}\right]
=\frac{d^{2}}{\delta_{t}^{2}}\mathbb{E{}}\left[\tilde{c}_{i}(\hat{x}^{t})^{2}
\|z_{i}^{t}\|^{2}\mid x^{t}\right]\leq\frac{d^{2}}{\delta_{t}^{2}}$, and therefore $\mathbb{E{}}\left[\left\langle\hat{g}_{i}^{t},x_{i}^{t}-x_{i}^{t+1}\right
\rangle\right]\leq\frac{\eta_{t}d^{2}}{\delta_{t}^{2}}$.

Taking summation over $T$, and take $\eta_{t}=\frac{1}{2dt^{3/4}}$, $\delta_{t}=\frac{1}{t^{1/4}}$ we have

$$ $\displaystyle\sum^{T}_{t=1}\mathbb{E{}}\left[\hat{c}_{i}\left(x^{t}_{i},x_{-i} ^{t}\right)-\hat{c}_{i}\left(\omega_{i},x_{-i}^{t}\right)\right]\leq\$ $\displaystyle dT^{3/4}\mathbb{E{}}\left[D_{h}\left(\omega_{i},x_{i}^{1}\right) \right]+\kappa\mathbb{E{}}\left[D_{p}\left(\omega_{i},x_{i}^{1}\right)\right]+ \sum^{T}_{t=1}\frac{\eta_{t}d^{2}}{\delta^{2}}$ $\displaystyle\leq\$ $\displaystyle O\left(dT^{3/4}\mathbb{E{}}\left[D_{h}\left(\omega_{i},x_{i}^{1} \right)\right]+\kappa C_{p}+T^{3/4}\right)\,,$ $$

as we assumed $D_{p}(x_{i},x_{i}^{\prime})$ is bounded for any $x_{i},x_{i}^{\prime}$.

When $\mu>0$, taking expectation conditioned on $x^{t}$, we have $\mathbb{E{}}\left[\left\|A_{i}^{t}\hat{g}_{i}^{t}\right\|^{2}\mid x^{t}\right]
=d^{2}\mathbb{E{}}\left[c_{i}(\hat{x}^{t})^{2}\|z_{i}^{t}\|^{2}\mid x^{t}
\right]\leq d^{2}$. By Lemma J.2, and the choice $\eta_{t}=\frac{1}{2d\sqrt{t}}$, we have

$$ $\displaystyle\sum^{T}_{t=1}\sum_{i\in\mathcal{N}}\mathbb{E{}}\left[\left \langle\hat{g}_{i}^{t},x_{i}^{t}-x_{i}^{t+1}\right\rangle\right]\leq\$ $\displaystyle\sum^{T}_{t=1}\eta_{t}\sum_{i\in\mathcal{N}}\mathbb{E{}}\left[ \left\|A_{i}^{t}\hat{g}_{i}^{t}\right\|^{2}\right]\leq nd^{2}\sum^{T}_{t=1} \eta_{t}=nd^{2}\sqrt{T}\,.$ $$

Taking summation over $T$, and take $\eta_{t}=\frac{1}{2dt^{1/2}}$, we have

$$ $\displaystyle\sum^{T}_{t=1}\mathbb{E{}}\left[\hat{c}_{i}\left(x^{t}_{i},x_{-i} ^{t}\right)-\hat{c}_{i}\left(\omega_{i},x_{-i}^{t}\right)\right]\leq\$ $\displaystyle dT^{1/2}\mathbb{E{}}\left[D_{h}\left(\omega_{i},x_{i}^{1}\right) \right]+\kappa\mathbb{E{}}\left[D_{p}\left(\omega_{i},x_{i}^{1}\right)\right]+ nd^{2}\sqrt{T}\,,$ $$

as we assumed $D_{p}(x_{i},x_{i}^{\prime})$ is bounded for any $x_{i},x_{i}^{\prime}$.

Define $\pi_{x}(y)=\inf\left\{t\geq 0:x+\frac{1}{t}(y-x)\in\mathcal{X}_{i}\right\}$. Notice that $x_{i}^{1}(x)=\mathop{\rm argmin}_{x_{i}\in\mathcal{X}_{i}}h(x_{i})$, so $D_{h}(\omega_{i},x_{i}^{1})=h(\omega_{i})-h(x_{i}^{1})$.

- •
If $\pi_{x_{i}^{1}}(\omega_{i})\leq 1-\frac{1}{\sqrt{T}}$, then by Lemma J.6, $D_{h}(\omega_{i},x_{i}^{1})=\nu\log(T)$, and $\sum^{T}_{t=1}\mathbb{E{}}\left[\hat{c}_{i}\left(x^{t}_{i},x_{-i}^{t}\right)-
\hat{c}_{i}\left(\omega_{i},x_{-i}^{t}\right)\right]=O\left(\nu dT^{3/4}\log(T
)\right)$.
- •
Otherwise, we find a point $\omega_{i}^{\prime}$ such that $\|\omega_{i}^{\prime}-\omega_{i}\|=O(1/\sqrt{T})$ and $\pi_{x_{i}^{1}}(\omega_{i}^{\prime})\leq 1-\frac{1}{\sqrt{T}}$. Then $D_{h}(\omega_{i}^{\prime},x_{i}^{1})=\nu\log(T)$,
$\displaystyle\hat{c}_{i}\left(\omega_{i}^{\prime},x_{-i}^{t}\right)-\hat{c}_{i
}\left(\omega_{i},x_{-i}^{t}\right)\leq\left\langle\nabla_{i}\hat{c}_{i}\left(
\omega_{i}^{\prime},x_{-i}^{t}\right),\omega_{i}^{\prime}-\omega_{i}\right
\rangle\leq\|\nabla_{i}\hat{c}_{i}\left(\omega_{i}^{\prime},x_{-i}^{t}\right)
\|\|\omega_{i}^{\prime}-\omega_{i}\|\leq\frac{\max_{x}\|\nabla_{i}c_{i}\left(x
\right)\|}{\sqrt{T}}\,.$
Therefore, $\sum^{T}_{t=1}\mathbb{E{}}\left[\hat{c}_{i}\left(x^{t}_{i},x_{-i}^{t}\right)-
\hat{c}_{i}\left(\omega_{i},x_{-i}^{t}\right)\right]=O\left(\nu dT^{3/4}\log(T
)+\max_{x}\|\nabla_{i}c_{i}\left(x\right)\|\sqrt{T}\right)$.

For the second term, by Jensen’s inequality, we have

$$ $\displaystyle\hat{c}_{i}\left(x_{i}^{t},x_{-i}^{t}\right)\mathbb{E}_{w_{i}^{t} \sim\mathbb{B}^{d}}\left[c_{i}\left(x_{i}^{t}+\delta_{t}A_{i}^{t}w_{i}^{t},x_{ -i}^{t}\right)\right]\geq\$ $\displaystyle c_{i}\left(\mathbb{E}_{w_{i}^{t}\sim\mathbb{B}^{d}}x_{i}^{t}+ \delta_{t}A_{i}^{t}w_{i}^{t},x_{-i}^{t}\right)=\ c_{i}\left(x_{i}^{t},x_{-i}^{ t}\right)\,.$ $$

Therefore, we have $\sum^{T}_{t=1}\left(c_{i}\left(x_{i}^{t},x_{-i}^{t}\right)-\hat{c}_{i}\left(x_
{i}^{t},x_{-i}^{t}\right)\right)=0$.

When $\mu=0$, by the definition of $\hat{c}_{i}$ and the smoothness of $c_{i}$,

$$ $\displaystyle\|\nabla_{i}\hat{c}_{i}(x^{t})-\nabla_{i}c_{i}\left(x^{t}\right) \|=\$ $\displaystyle\left\|\mathbb{E}_{w_{i}\sim\mathbb{B}^{d}}\mathbb{E}_{\mathbf{z} _{-i}\sim\Pi_{j\neq i}\mathbb{S}^{d}}\left[\nabla_{i}c_{i}\left(x_{i}^{t}+ \delta_{t}A_{i}^{t}w_{i},\hat{x}_{-i}^{t}\right)-\nabla_{i}c_{i}\left(x^{t} \right)\right]\right\|$ $\displaystyle\leq\$ $\displaystyle\ell_{i}\sqrt{\mathbb{E{}}_{w_{i}\sim\mathbb{B}^{d}}\mathbb{E}_{ \mathbf{z}_{-i}\sim\Pi_{j\neq i}\mathbb{S}^{d}}\left[\delta_{t}^{2}\left\| \delta_{t}A_{i}w_{i}\right\|^{2}+\delta_{t}^{2}\sum_{j\neq i}\left\|A_{j}z_{j} \right\|^{2}\right]}\,.$ $$

Since $p$ is monotone, $\nabla^{2}p(x)$ is positive semi-definite, and $A_{i}^{t}\preceq(\nabla^{2}h(x_{i}))^{-1/2}$. For $\bar{x}_{i}^{t}=x_{i}^{t}+A_{i}^{t}w_{i}^{t}$. Define $\|v\|_{x}=\sqrt{v^{\top}\nabla^{2}h(x)v}$, we have $\|\bar{x}_{i}^{t}-x_{i}^{t}\|_{x_{i}}\leq\|\omega_{i}^{t}\|\leq 1$, and $\bar{x}_{i}^{t}\in W(x_{i}^{t})$, where $W(x)=\{x^{\prime}_{i}\in\mathbb{R}^{d},\|x^{\prime}_{i}-x_{i}\|_{x_{i}}\leq 1\}$ is the Dikin ellipsoid. Since $W(x_{i})\subseteq\mathcal{X}_{i},\forall x_{i}\in\mathop{int}(\mathcal{X}_{i})$, we can upper bound $\left\|A_{i}w_{i}\right\|^{2}$ by $B^{2}$, the diameter of the set $\mathcal{X}_{i}$. Hence $\|\nabla_{i}\hat{c}_{i}(x^{t})-\nabla_{i}c_{i}\left(x^{t}\right)\|\leq\ell_{i}
\delta_{t}\sqrt{n}B$.

Therefore, for the third term, we have

$$ $\displaystyle\sum^{T}_{t=1}\mathbb{E{}}\left[\hat{c}_{i}\left(\omega_{i},x_{-i }^{t}\right)-c_{i}\left(\omega_{i},x_{-i}^{t}\right)\right]\leq O\left(\sum^{T }_{t=1}\ell_{i}\delta_{t}\sqrt{n}B\right)\,.$ $$

Similarly, for the fourth term, we have $\sum^{T}_{t=1}\mathbb{E{}}\left[c_{i}\left(\hat{x}_{i}^{t},x_{-i}^{t}\right)-c
_{i}\left(x_{i}^{t},x_{-i}^{t}\right)\right]\leq O\left(\sum^{T}_{t=1}\ell_{i}
\delta_{t}\sqrt{n}B\right)$.

When $\mu>0$, by Lemma J.5, for any $\omega_{i}\in\mathcal{X}_{i}$, we have

$$ $\displaystyle\left\|\nabla_{i}\hat{c}_{i}(x^{t})-\nabla_{i}c_{i}\left(x^{t} \right)\right\|\leq\ \ell_{i}\sqrt{\sum_{j\in\mathcal{N}}\left(\sigma_{\max} \left(A_{j}^{t}\right)^{2}\right)}\leq\ \frac{n\ell_{i}}{\sqrt{\mu(t+1)}}\,.$ $$

where the second inequality is by $\nabla^{2}h(x)$ being positive definite, and $\nabla^{2}p(x)\geq\mu I$.

Therefore, for the third term, we have

$$ $\displaystyle\sum^{T}_{t=1}\mathbb{E{}}\left[\hat{c}_{i}\left(\omega_{i},x_{-i }^{t}\right)-c_{i}\left(\omega_{i},x_{-i}^{t}\right)\right]\leq O\left(\frac{ nB\ell_{i}\sqrt{T}}{\mu}\right)\,.$ $$

Similarly, for the fourth term, we have $\sum^{T}_{t=1}\mathbb{E{}}\left[c_{i}\left(\hat{x}_{i}^{t},x_{-i}^{t}\right)-c
_{i}\left(x_{i}^{t},x_{-i}^{t}\right)\right]\leq O\left(\frac{nB\ell_{i}\sqrt{
T}}{\mu}\right)$.

When $\mu=0$, with $\delta_{t}=\frac{1}{t^{1/4}}$, we have the regret as

$$ $\displaystyle\sum^{T}_{t=1}\mathbb{E{}}\left[c_{i}\left(\hat{x}_{i}^{t},x_{-i} ^{t}\right)-c_{i}\left(\omega_{i},x_{-i}^{t}\right)\right]=\ O\left(\nu dT^{3/ 4}\log(T)+\max_{x}\|\nabla_{i}c_{i}\left(x\right)\|\sqrt{T}+\ell_{i}\sqrt{n}BT ^{3/4}\right)\,.$ $$

When $\mu>0$, we have the regret as

$$ $\displaystyle\sum^{T}_{t=1}\mathbb{E{}}\left[c_{i}\left(\hat{x}_{i}^{t},x_{-i} ^{t}\right)-c_{i}\left(\omega_{i},x_{-i}^{t}\right)\right]=\ O\left(\nu dT^{1/ 2}\log(T)+\max_{x}\|\nabla_{i}c_{i}\left(x\right)\|\sqrt{T}+\frac{nB\ell_{i} \sqrt{T}}{\mu}\right)\,.$ $$

Combining the terms yields the final result.
∎

###### Proof.

## Appendix D Proof of Theorem D.1

We now consider the case where every player receive $\tilde{c}_{i}(x^{t})=c_{i}(x^{t})+\epsilon_{i}^{t}$, where $\mathbb{E{}}[\epsilon_{i}^{t}\mid\hat{x}^{t}]=0$, and $\|\epsilon_{i}^{t}\|^{2}\leq\sigma$. The following theorem describes the last-iterate convergence rate (in expectation) for monotone and strongly monotone loss under noisy bandit feedback.

###### Theorem D.1 .

With $\eta_{t}=\frac{1}{4d^{2}(1+\sigma)t^{3/4}}$, $\delta_{t}=\frac{1}{t^{1/4}}$

$$ $\displaystyle\sum_{i\in\mathcal{N}}D_{p}\left(x_{i}^{\ast},x_{i}^{T+1}\right)\leq\$ $\displaystyle O\left(\frac{n\nu d^{2}(1+\sigma)\log(T)}{\kappa T^{1/4}}+\frac{ n\zeta d^{2}(1+\sigma)B}{T^{3/4}}+\frac{nd^{2}(1+\sigma)C_{p}}{T^{1/4}}\right.$ $\displaystyle\ +\left.\frac{\sqrt{n}B^{2}L\log(T)}{\kappa T^{1/4}}+\frac{nd \log(T)}{\kappa(1+\sigma)^{2}T^{1/4}}\right)\,.$ $$

###### Proof.

Similar to Theorem 5.1, with Lemma J.1, we have

$$ $\displaystyle\sum_{i\in\mathcal{N}}D_{p}\left(x_{i}^{\ast},x_{i}^{T+1}\right)\leq\$ $\displaystyle O\left(\frac{n\nu\log(T)}{\kappa\eta_{T}T}+\frac{n\zeta B}{\eta_ {T}T^{3/2}}\right)+O\left(\frac{nB\sum_{i\in\mathcal{N}}\ell_{i}}{\kappa T^{3/ 2}}+\frac{n}{\kappa T^{3/2}}\right)\frac{\sum^{T}_{t=1}\eta_{t}}{\eta_{T}}+O \left(\frac{nC_{p}}{\eta_{T}T}\right)$ $\displaystyle+\frac{\sqrt{n}B^{2}L\sum^{T}_{t=1}\eta_{t}\delta_{t}}{\eta_{T} \kappa(T+1)}+\frac{1}{\eta_{T}\kappa(T+1)}\sum_{i\in\mathcal{N}}\sum^{T}_{t=1} \eta_{t}\left\langle\hat{g}_{i}^{t},x_{i}^{t}-x_{i}^{t+1}\right\rangle\,.$ $$

Taking expectation conditioned on $x^{t}$, we have $\mathbb{E{}}\left[\left\|A_{i}^{t}\hat{g}_{i}^{t}\right\|^{2}\mid x^{t}\right]
=\frac{d^{2}}{\delta_{t}^{2}}\mathbb{E{}}\left[\tilde{c}_{i}(\hat{x}^{t})^{2}
\|z_{i}^{t}\|^{2}\mid x^{t}\right]\leq\frac{d^{2}}{\delta_{t}^{2}}(2+2\sigma)$. By Lemma J.2, and the choice $\eta_{t}=\frac{1}{4d^{2}(1+\sigma)t^{3/4}}$, we have

$$ $\displaystyle\sum^{T}_{t=1}\eta_{t}\sum_{i\in\mathcal{N}}\mathbb{E{}}\left[ \left\langle\hat{g}_{i}^{t},x_{i}^{t}-x_{i}^{t+1}\right\rangle\right]\leq\$ $\displaystyle\sum^{T}_{t=1}\eta_{t}^{2}\sum_{i\in\mathcal{N}}\mathbb{E{}}\left [\left\|A_{i}^{t}\hat{g}_{i}^{t}\right\|^{2}\right]\leq nd^{2}\sum^{T}_{t=1} \frac{\eta_{t}^{2}}{\delta_{t}^{2}}=\frac{n\log(T)}{16(1+\sigma)^{2}}\,.$ $$

Combining everything, we have

$$ $\displaystyle\sum_{i\in\mathcal{N}}D_{p}\left(x_{i}^{\ast},x_{i}^{T+1}\right)$ $\displaystyle\leq\$ $\displaystyle O\left(\frac{n\nu d^{2}(1+\sigma)\log(T)}{\kappa T^{1/4}}+\frac{ n\zeta d^{2}(1+\sigma)B}{T^{3/4}}+\frac{nd^{2}(1+\sigma)C_{p}}{T^{1/4}}+\frac{ \sqrt{n}B^{2}L\log(T)}{\kappa T^{1/4}}+\frac{nd\log(T)}{\kappa(1+\sigma)^{2}T^ {1/4}}\right)\,.$ $$

∎

###### Theorem D.1 .

###### Proof.

## Appendix E Proof of Theorem 5.2

See 5.2

###### Proof.

Lemma J.1, we have

$$ $\displaystyle\sum_{i\in\mathcal{N}}D_{p}\left(x_{i}^{\ast},x_{i}^{T+1}\right)$ $\displaystyle\leq\$ $\displaystyle O\left(\frac{n\nu\log(T)}{\kappa\eta_{T}T}+\frac{n\zeta B}{\eta_ {T}T^{3/2}}\right)+O\left(\frac{nB\sum_{i\in\mathcal{N}}\ell_{i}}{\kappa T^{3/ 2}}+\frac{n}{\kappa T^{3/2}}\right)\frac{\sum^{T}_{t=1}\eta_{t}}{\eta_{T}}+O \left(\frac{nC_{p}}{\eta_{T}T}\right)$ $\displaystyle+\frac{1}{\kappa\eta_{T}(T+1)}\sum_{i\in\mathcal{N}}\sum^{T}_{t=1 }\eta_{t}\left\langle\hat{g}_{i}^{t},x_{i}^{t}-x_{i}^{t+1}\right\rangle+\frac{ 1}{\kappa\eta_{T}(T+1)}\sum^{T}_{t=1}\eta_{t}\sum_{i\in\mathcal{N}}\left \langle\hat{g}_{i}^{t}-\nabla_{i}c_{i}\left(x^{t}\right),\omega_{i}-x_{i}^{t} \right\rangle\,.$ $$

By Lemma J.2, we have

$$ $\displaystyle\sum^{T}_{t=1}\eta_{t}\sum_{i\in\mathcal{N}}\left\langle\hat{g}_{ i}^{t},x_{i}^{t}-x_{i}^{t+1}\right\rangle\leq\$ $\displaystyle\sum^{T}_{t=1}\eta_{t}^{2}\sum_{i\in\mathcal{N}}\left\|A_{i}^{t} \hat{g}_{i}^{t}\right\|^{2}\leq nd^{2}\sum^{T}_{t=1}\eta_{t}^{2}\,.$ $$

We then decompose the last term as

$$ $\displaystyle\sum^{T}_{t=1}\eta_{t}\sum_{i\in\mathcal{N}}\left\langle\hat{g}_{ i}^{t}-\nabla_{i}c_{i}\left(x^{t}\right),\omega_{i}-x_{i}^{t}\right\rangle=\$ $\displaystyle\sum^{T}_{t=1}\eta_{t}\sum_{i\in\mathcal{N}}\left\langle g_{i}^{t }-\hat{c}_{i}^{t}(x_{i}^{t}),\omega_{i}-x_{i}^{t}\right\rangle+\sum_{i\in \mathcal{N}}\sum^{T}_{t=1}\eta_{t}\left\langle\nabla_{i}\hat{c}_{i}(x^{t})- \nabla_{i}c_{i}\left(x^{t}\right),\omega_{i}-x_{i}^{t}\right\rangle\,.$ $$

By Lemma E.1, we have

$$ $\displaystyle\sum^{T}_{t=1}\eta_{t}\left\langle g_{i}^{t}-\hat{c}_{i}^{t}(x_{i }^{t}),\omega_{i}-x_{i}^{t}\right\rangle\leq O\left(\frac{Bd\log^{2}(1/\delta) \log(T)}{\min\{\sqrt{\mu},\mu\}}\right)\,,$ $$

with a probability of at least $1-\log(T)\delta$, $\delta\leq e^{-1}$.

By Lemma J.5, for any $\omega_{i}\in\mathcal{X}_{i}$, we have

$$ $\displaystyle\sum_{i\in\mathcal{N}}\sum^{T}_{t=1}\eta_{t}\left\langle\nabla_{i }\hat{c}_{i}(x^{t})-\nabla_{i}c_{i}\left(x^{t}\right),\omega_{i}-x_{i}^{t} \right\rangle\leq\$ $\displaystyle\sum_{i\in\mathcal{N}}B\ell_{i}\sum^{T}_{t=1}\eta_{t}\sum_{j\in \mathcal{N}}\left(\sigma_{\max}\left(A_{j}^{t}\right)^{2}\right)\mid x^{t}$ $\displaystyle\leq\$ $\displaystyle\sum_{i\in\mathcal{N}}B\ell_{i}\sum^{T}_{t=1}\frac{1}{\mu(t+1)}$ $\displaystyle\leq\$ $\displaystyle\frac{B\sum_{i\in\mathcal{N}}\ell_{i}}{\mu}\sum^{T}_{t=1}\frac{1} {(t+1)}$ $\displaystyle\leq\$ $\displaystyle\frac{BL\log(T)}{\mu}$ $$

where the third inequality is by $\nabla^{2}h(x)$ being positive definite, and $\nabla^{2}p(x)\geq\mu I$.

Therefore,

$$ $\displaystyle\sum^{T}_{t=1}\eta_{t}\sum_{i\in\mathcal{N}}\left\langle\hat{g}_{ i}^{t}-\nabla_{i}c_{i}\left(x^{t}\right),\omega_{i}-x_{i}^{t}\right\rangle\leq O \left(\frac{BL\log(T)}{\mu}+\frac{nBd\log^{2}(1/\delta)\log(T)}{\min\{\sqrt{ \mu},\mu\}}\right)\,.$ $$

Combining the terms, and with $\eta_{t}=\frac{1}{2d\sqrt{t}}$, we have

$$ $\displaystyle\sum_{i\in\mathcal{N}}D_{p}\left(x_{i}^{\ast},x_{i}^{T+1}\right)$ $\displaystyle\leq\$ $\displaystyle O\left(\frac{nd\nu\log(T)}{\kappa\sqrt{T}}+\frac{nd\zeta B}{T}+ \frac{nBL}{\kappa\sqrt{T}}+\frac{ndC_{p}}{\sqrt{T}}+\frac{nd\log(T)}{\kappa \sqrt{T}}+\frac{dBL\log(T)}{\kappa\mu\sqrt{T}}+\frac{nBd^{2}\log^{2}(1/\delta) \log(T)}{\kappa\min\{\sqrt{\mu},\mu\}\sqrt{T}}\right)\,.$ $$

∎

###### Lemma E.1 .

With a probability of at least $1-\log(T)\delta$, $\delta\leq e^{-1}$, we have

$$ $\displaystyle\sum^{T}_{t=1}\eta_{t}\left\langle g_{i}^{t}-\hat{c}_{i}^{t}(x_{i }^{t}),\omega_{i}-x_{i}^{t}\right\rangle\leq O\left(\frac{Bd\log^{2}(1/\delta) \log(T)}{\min\{\sqrt{\mu},\mu\}}\right)\,.$ $$

###### Proof.

Define $Z_{t}=\eta_{t}\left\langle g_{i}^{t}-\hat{c}_{i}^{t}(x_{i}^{t}),\omega_{i}-x_{
i}^{t}\right\rangle$. $\mathrm{Var}[Z_{t}]\leq\eta^{2}(\omega_{i}-x_{i}^{t})^{\top}\mathbb{E{}}[g_{i}
^{t}(g_{i}^{t})^{\top}](\omega_{i}-x_{i}^{t})$.
Then, with $\eta_{t}=\frac{1}{2d\sqrt{t}}$,

$$ $\displaystyle\max_{t}|Z_{t}|\leq\max_{t}\left\|\eta_{t}\left(g_{i}^{t}-\hat{c} _{i}^{t}(x_{i}^{t})\right)\right\|\left\|\omega_{i}-x_{i}^{t}\right\|\leq O \left(Bd\max_{t}\|\eta_{t}(A_{i}^{t})^{-1}z_{i}^{t}\|\right)\leq O\left(\max_{ t}\frac{Bd}{\mu(t+1)}\right)\leq O\left(\frac{Bd}{\mu}\right)\,,$ $$

where the third inequality is by the definition of $A_{i}^{t}$.

By the definition of gradient estimator, we have

$$ $\displaystyle(g_{i}^{t})^{\top}g_{i}^{t}\leq d^{2}\left((A_{i}^{t})^{-1}z_{i}^ {t}\right)^{\top}\left((A_{i}^{t})^{-1}z_{i}^{t}\right)\leq\frac{d^{2}}{\mu \eta_{t}(t+1)}\,.$ $$

Therefore, with $\eta_{t}=\frac{1}{2d\sqrt{t}}$

$$ $\displaystyle(\omega_{i}-x_{i}^{t})^{\top}\mathbb{E{}}[g_{i}^{t}(g_{i}^{t})^{ \top}](\omega_{i}-x_{i}^{t})\leq\$ $\displaystyle\frac{d^{2}\|\omega_{i}-x_{i}^{t}\|^{2}}{\mu\eta_{t}(t+1)}\leq \frac{d^{2}B^{2}}{\mu\eta_{t}(t+1)}\leq\ \frac{dB^{2}}{\mu\sqrt{t}}\,.$ $$

We have

$$ $\displaystyle\sqrt{\sum^{T}_{t=1}\eta_{t}^{2}(\omega_{i}-x_{i}^{t})^{\top} \mathbb{E{}}[g_{i}^{t}(g_{i}^{t})^{\top}](\omega_{i}-x_{i}^{t})}\leq\$ $\displaystyle\sqrt{\sum^{T}_{t=1}\frac{B^{2}}{d\mu t^{3/2}}}\leq\ O\left(\frac {B\sqrt{\log(T)}}{\sqrt{d\mu}}\right)\,.$ $$

Then, by Lemma 2 of Bartlett et al., (), with a probability of at least $1-\log(T)\delta$, $\delta\leq e^{-1}$,

$$ $\displaystyle\sum^{T}_{t=1}\eta_{t}\left\langle g_{i}^{t}-\hat{c}_{i}^{t}(x_{i }^{t}),\omega_{i}-x_{i}^{t}\right\rangle\leq\$ $\displaystyle 2\max\left\{2\sqrt{\sum^{T}_{t=1}\mathrm{Var}[Z_{t}]},\max_{t}|Z _{t}|\log(1/\delta)\right\}$ $\displaystyle\leq\$ $\displaystyle\max\left\{O\left(\frac{B\sqrt{\log(T)}}{\sqrt{d\mu}}\right),O \left(\frac{Bd\log(1/\delta)}{\mu}\right)\right\}\cdot\log(1/\delta)$ $\displaystyle\leq\$ $\displaystyle O\left(\frac{Bd\log^{2}(1/\delta)\log(T)}{\min\{\sqrt{\mu},\mu\} }\right)\,.$ $$

∎

###### Proof.

###### Lemma E.1 .

###### Proof.

## Appendix F Proof of Theorem 5.4

See 5.4

###### Proof.

We consider a regularized game with operator $\tilde{F}(x)=[\tilde{F}_{i}(x)]_{i\in\mathcal{N}}$, where $\tilde{F}_{i}(x)=\nabla c_{i}(x)+\tau\nabla p(x_{i})$, $\nabla p(x)=[\nabla_{i}p(x_{i})]_{i\in\mathcal{N}}$.

Similar to Lemma J.1, we have

$$ $\displaystyle\sum_{i\in\mathcal{N}}D_{p}\left(x_{i}^{\tau},x_{i}^{T+1}\right)$ $\displaystyle\leq\$ $\displaystyle O\left(\frac{n\nu\log(T)}{\eta_{T}\tau T}+\frac{n\mu B}{\eta_{T} \tau T^{3/2}}\right)+O\left(\frac{nB\sum_{i\in\mathcal{N}}\ell_{i}}{\tau T^{3/ 2}}+\frac{n}{\tau T^{3/2}}\right)\frac{\sum^{T}_{t=1}\eta_{t}}{\eta_{T}}+O \left(\frac{nC_{p}}{\eta_{T}T}\right)$ $\displaystyle+\frac{1}{\eta_{T}\tau(T+1)}\sum_{i\in\mathcal{N}}\sum^{T}_{t=1} \eta_{t}\left\langle\hat{g}_{i}^{t},x_{i}^{t}-x_{i}^{t+1}\right\rangle+\frac{1 }{\eta_{T}\tau(T+1)}\sum^{T}_{t=1}\eta_{t}\sum_{i\in\mathcal{M}}\left\langle \hat{g}_{i}^{t}-\tilde{F}_{i}\left(x^{t}\right),x_{i}^{\tau}-x_{i}^{t}\right\rangle$ $\displaystyle+\frac{1}{\eta_{T}\tau(T+1)}\sum^{T}_{t=1}\eta_{t}\sum_{i\in \mathcal{N}\setminus\mathcal{M}}\left\langle\hat{g}_{i}^{t}-\tilde{F}_{i}\left (x^{t}\right),\bar{x}_{i}-x_{i}^{t}\right\rangle\,.$ $$

Taking expectation conditioned on $x^{t}$, we have $\mathbb{E{}}\left[\left\|A_{i}^{t}\hat{g}_{i}^{t}\right\|^{2}\mid x^{t}\right]
=d^{2}\mathbb{E{}}\left[c_{i}(\hat{x}^{t})^{2}\|z_{i}^{t}\|^{2}\mid x^{t}
\right]\leq d^{2}$. By Lemma J.2, and the choice $\eta_{t}=\frac{1}{2d\sqrt{t}}$, we have

$$ $\displaystyle\sum^{T}_{t=1}\eta_{t}\sum_{i\in\mathcal{N}}\mathbb{E{}}\left[ \left\langle\hat{g}_{i}^{t},x_{i}^{t}-x_{i}^{t+1}\right\rangle\right]\leq\$ $\displaystyle\sum^{T}_{t=1}\eta_{t}^{2}\sum_{i\in\mathcal{N}}\mathbb{E{}}\left [\left\|A_{i}^{t}\hat{g}_{i}^{t}\right\|^{2}\right]\leq nd^{2}\sum^{T}_{t=1} \eta_{t}^{2}\,.$ $$

By Lemma J.5, for any $\omega_{i}\in\mathcal{X}_{i}$, we have

$$ $\displaystyle\sum_{i\in\mathcal{N}}\sum^{T}_{t=1}\eta_{t}\mathbb{E{}}\left[ \left\langle\hat{g}_{i}^{t}-\nabla_{i}c_{i}\left(x^{t}\right),\omega_{i}-x_{i} ^{t}\right\rangle\mid x^{t}\right]=\$ $\displaystyle\sum_{i\in\mathcal{N}}\sum^{T}_{t=1}\eta_{t}\mathbb{E{}}\left[ \left\langle\nabla_{i}\hat{c}_{i}(x^{t})-\nabla_{i}c_{i}\left(x^{t}\right), \omega_{i}-x_{i}^{t}\right\rangle\mid x^{t}\right]$ $\displaystyle\leq\$ $\displaystyle\sum_{i\in\mathcal{N}}\sum^{T}_{t=1}\eta_{t}\mathbb{E{}}\left[ \left\|\nabla_{i}\hat{c}_{i}(x^{t})-\nabla_{i}c_{i}\left(x^{t}\right)\right\| \left\|\omega_{i}-x_{i}^{t}\right\|\mid x^{t}\right]$ $\displaystyle\leq\$ $\displaystyle\sum_{i\in\mathcal{N}}B\ell_{i}\sum^{T}_{t=1}\eta_{t}\mathbb{E{}} \left[\sum_{j\in\mathcal{N}}\left(\sigma_{\max}\left(A_{j}^{t}\right)^{2} \right)\mid x^{t}\right]$ $\displaystyle\leq\$ $\displaystyle\sum_{i\in\mathcal{N}}B\ell_{i}\sum^{T}_{t=1}\frac{1}{\mu(t+1)}$ $\displaystyle\leq\$ $\displaystyle\frac{B\sum_{i\in\mathcal{N}}\ell_{i}}{\mu}\sum^{T}_{t=1}\frac{1} {(t+1)}\,.$ $$

where the third inequality is by $\nabla^{2}h(x)$ being positive definite, and $\nabla^{2}p(x)\geq\mu I$.

Combing and rearranging the terms, we have

$$ $\displaystyle\mathbb{E{}}\left[\sum_{i\in\mathcal{N}}D_{p}\left(x_{i}^{\tau},x _{i}^{T+1}\right)\right]$ $\displaystyle\leq\$ $\displaystyle O\left(\frac{n\nu\log(T)}{\eta_{T}\tau T}+\frac{n\zeta B}{\eta_{ T}\tau T^{3/2}}\right)+O\left(\frac{nB\sum_{i\in\mathcal{N}}\ell_{i}}{\tau \sqrt{T}}+\frac{n}{\tau\sqrt{T}}\right)+O\left(\frac{nC_{p}}{\eta_{T}T}\right) +O\left(\frac{nd^{2}}{\tau\eta_{T}T}\sum^{T}_{t=1}\eta_{t}^{2}+\frac{B\sum_{i \in\mathcal{N}}\ell_{i}}{\tau\mu\eta_{T}T}\sum^{T}_{t=1}\frac{1}{t}\right)\,.$ $$

Take $\eta_{t}=\frac{1}{2d\sqrt{t}}$, we have

$$ $\displaystyle\mathbb{E{}}\left[\sum_{i\in\mathcal{N}}D_{p}\left(x_{i}^{\tau},x _{i}^{T+1}\right)\right]$ $\displaystyle\leq\$ $\displaystyle O\left(\frac{nd\nu\log(T)}{\tau\sqrt{T}}+\frac{nd\zeta B}{\tau T }+\frac{nB\sum_{i\in\mathcal{N}}\ell_{i}}{\tau\sqrt{T}}+\frac{n}{\tau\sqrt{T}} +\frac{ndC_{p}}{\sqrt{T}}+\frac{nd\log(T)}{\tau\sqrt{T}}+\frac{dB\log(T)\sum_{ i\in\mathcal{N}}\ell_{i}}{\tau\mu\sqrt{T}}\right)\,.$ $$

We can decompose as

$$ $\displaystyle\left\langle F\left(x^{T}\right),x^{T}-x^{\ast}\right\rangle$ $\displaystyle=\$ $\displaystyle\left\langle F\left(x^{T}\right),x^{T}-x^{\tau}\right\rangle+ \left\langle F\left(x^{T}\right),x^{\tau}-x^{\ast}\right\rangle$ $\displaystyle\leq\$ $\displaystyle G\left\|x^{T}-x^{\tau}\right\|+\left\langle F\left(x^{\tau} \right)+\tau\nabla p(x^{\tau}),x^{\tau}-x^{\ast}\right\rangle+\left\langle F \left(x^{T}\right)-F\left(x^{\tau}\right),x^{\tau}-x^{\ast}\right\rangle+\tau B \left\|\nabla p(x^{\tau})\right\|$ $\displaystyle\leq\$ $\displaystyle\sum_{i\in\mathcal{N}}(B\ell_{i}+G)\left\|x^{T}_{i}-x^{\tau} \right\|+\tau B\left\|\nabla p(x^{\tau})\right\|\,.$ $$

Since $\nabla^{2}p(x)\succeq\mu I$, we have $\|x_{i}^{\tau}-x_{i}^{T}\|\leq\sqrt{D_{p}(x_{i}^{\tau},x_{i}^{T})}$. Let $G_{p}=\sup_{x}\|\nabla p(x)\|$, $L=\sum_{i\in\mathcal{N}}\ell_{i}$, we have

$$ $\displaystyle\mathbb{E{}}\left[\sum_{i\in\mathcal{N}}\left\langle\nabla_{i}c_{ i}\left(x^{T}\right),x_{i}^{T}-x_{i}^{\ast}\right\rangle\right]$ $\displaystyle\leq\$ $\displaystyle O\left(\tau BG_{p}\right)+\tilde{O}\left(\frac{\sqrt{d(BL+G)(n \nu+nBL+nd^{2})}}{\sqrt{\tau}T^{1/4}}\right)+\tilde{O}\left(\frac{\sqrt{dBL(BL +G)}}{\sqrt{\tau\mu}T^{1/4}}\right)+O\left(\frac{\sqrt{dnC_{p}(BL+G)}}{\sqrt{ \mu}T^{1/4}}\right)$ $\displaystyle\leq\$ $\displaystyle\tilde{O}\left(\frac{BG_{p}+\sqrt{d(BL+G)(n\nu+nBL+nd^{2})}}{T^{1 /6}}\right)+\tilde{O}\left(\frac{\sqrt{dBL(BL+G)}}{\sqrt{\mu}T^{1/6}}\right)+O \left(\frac{\sqrt{dnC_{p}(BL+G)}}{\sqrt{\mu}T^{1/4}}\right)\,,$ $$

where the last inequality is by taking $\tau=\frac{1}{T^{1/6}}$.
∎

###### Proof.

## Appendix G Proof of Proposition 5.1

See 5.1

###### Proof.

By Theorem 5.3, we have

$$ $\displaystyle\sum^{T}_{t=1}\sum_{i\in\mathcal{N}}\mathbb{E{}}\left[c_{i}\left( \hat{x}_{i}^{t},\hat{x}_{-i}^{t}\right)\right]\leq\$ $\displaystyle\sum^{T}_{t=1}\sum_{i\in\mathcal{N}}\mathbb{E{}}\left[c_{i}\left( \omega_{i},\hat{x}_{-i}^{t}\right)\right]+O\left(n\nu dT^{3/4}\log(T)+\sqrt{n} BT^{3/4}\sum_{i\in\mathcal{N}}\ell_{i}\right)$ $\displaystyle\leq\$ $\displaystyle C_{1}\mathrm{OPT}\cdot T+C_{2}\sum^{T}_{t=1}\mathbb{E{}}\left[ \mathrm{SW}(\hat{x})\right]+O\left(n\nu dT^{3/4}\log(T)+\sqrt{n}BT^{3/4}\sum_{ i\in\mathcal{N}}\ell_{i}\right)\,.$ $$

As $\sum^{T}_{t=1}\sum_{i\in\mathcal{N}}\mathbb{E{}}\left[c_{i}\left(\hat{x}_{i}^{
t},\hat{x}_{-i}^{t}\right)\right]=\mathbb{E{}}\left[\mathrm{SW}(\hat{x})\right]$, we solve for $\mathbb{E{}}\left[\mathrm{SW}(\hat{x})\right]$ and obtain

$$ $\displaystyle\frac{1}{T}\sum^{T}_{t=1}\mathbb{E{}}\left[\mathrm{SW}(\hat{x}) \right]=O\left(\frac{C_{1}\mathrm{OPT}}{(1-C_{2})}+\frac{n\nu d\log(T)}{(1-C_{ 2})T^{1/4}}+\frac{\sqrt{n}B\sum_{i\in\mathcal{N}}\ell_{i}}{(1-C_{2})T^{1/4}} \right)\,.$ $$

∎

###### Proof.

## Appendix H Proof of Theorem 6.1

See 6.1

###### Proof.

Similar to Theorem 5.1, we have

$$ $\displaystyle\sum_{i\in\mathcal{N}}D_{p}\left(x_{i}^{\ast},x_{i}^{T+1}\right)$ $\displaystyle\leq\$ $\displaystyle O\left(\frac{n\nu\log(T)}{\eta_{T}\kappa T}+\frac{n\zeta B}{\eta _{T}T^{3/2}}\right)+O\left(\frac{nB\sum_{i\in\mathcal{N}}\ell_{i}}{\kappa T^{3 /2}}+\frac{n}{\kappa T^{3/2}}\right)\frac{\sum^{T}_{t=1}\eta_{t}}{\eta_{T}}+O \left(\frac{nC_{p}}{\eta_{T}T}\right)$ $\displaystyle+\frac{1}{\kappa\eta_{T}(T+1)}\sum_{i\in\mathcal{N}}\sum^{T}_{t=1 }\eta_{t}\left\langle\hat{g}_{i}^{t},x_{i}^{t}-x_{i}^{t+1}\right\rangle+\frac{ 1}{\kappa\eta_{T}(T+1)}\sum^{T}_{t=1}\eta_{t}\sum_{i\in\mathcal{M}}\left \langle\hat{g}_{i}^{t}-\nabla_{i}c_{i}^{t}\left(x^{t}\right),x_{i}^{\ast}-x_{i }^{t}\right\rangle$ $\displaystyle+\frac{1}{\kappa\eta_{T}(T+1)}\sum^{T}_{t=1}\eta_{t}\sum_{i\in \mathcal{N}\setminus\mathcal{M}}\left\langle\hat{g}_{i}^{t}-\nabla_{i}c_{i}^{t }\left(x^{t}\right),\bar{x}_{i}-x_{i}^{t}\right\rangle+B\sum^{T}_{t=1}\Delta^{ t}\,,$ $$

where $\Delta^{t}=\sum_{i\in\mathcal{N}}\max_{x}\|\nabla_{i}c_{i}(x)-\nabla_{i}c_{i}^
{t}(x)\|_{2}$.

We now upper bound the remaining terms by discussing them by cases.

When $\mu=0$, taking expectation conditioned on $x^{t}$, we have $\mathbb{E{}}\left[\left\|A_{i}^{t}\hat{g}_{i}^{t}\right\|^{2}\mid x^{t}\right]
=\frac{d^{2}}{\delta_{t}^{2}}\mathbb{E{}}\left[c_{i}^{t}(\hat{x}^{t})^{2}\|z_{
i}^{t}\|^{2}\mid x^{t}\right]\leq\frac{d^{2}}{\delta_{t}^{2}}$. By Lemma J.2, and the choice $\eta_{t}=\frac{1}{2d\sqrt{t}}$, we have

$$ $\displaystyle\sum^{T}_{t=1}\eta_{t}\sum_{i\in\mathcal{N}}\mathbb{E{}}\left[ \left\langle\hat{g}_{i}^{t},x_{i}^{t}-x_{i}^{t+1}\right\rangle\right]\leq\$ $\displaystyle\sum^{T}_{t=1}\eta_{t}^{2}\sum_{i\in\mathcal{N}}\mathbb{E{}}\left [\left\|A_{i}^{t}\hat{g}_{i}^{t}\right\|^{2}\right]\leq nd^{2}\sum^{T}_{t=1} \frac{\eta_{t}^{2}}{\delta_{t}^{2}}\,.$ $$

By the definition of $\hat{c}_{i}$,

$$ $\displaystyle\sum_{i\in\mathcal{N}}\sum^{T}_{t=1}\eta_{t}\mathbb{E{}}\left[ \left\langle\hat{g}_{i}^{t}-\nabla_{i}c_{i}^{t}\left(x^{t}\right),\omega_{i}-x _{i}^{t}\right\rangle\mid x^{t}\right]$ $\displaystyle=\$ $\displaystyle\sum_{i\in\mathcal{N}}\sum^{T}_{t=1}\eta_{t}\mathbb{E{}}\left[ \left\langle\nabla_{i}\hat{c}_{i}^{t}(x^{t})-\nabla_{i}c_{i}^{t}\left(x^{t} \right),\omega_{i}-x_{i}^{t}\right\rangle\mid x^{t}\right]$ $\displaystyle=\$ $\displaystyle\sum_{i\in\mathcal{N}}\sum^{T}_{t=1}\eta_{t}\mathbb{E{}}\left[ \mathbb{E{}}_{w_{i}\sim\mathbb{B}^{d}}\mathbb{E}_{\mathbf{z}_{-i}\sim\Pi_{j \neq i}\mathbb{S}^{d}}\left\langle\nabla_{i}c_{i}^{t}\left(x_{i}^{t}+\delta_{t }A_{i}^{t}w_{i},\hat{x}_{-i}^{t}\right)-\nabla_{i}c_{i}^{t}\left(x^{t}\right), \omega_{i}-x_{i}^{t}\right\rangle\mid x^{t}\right]$ $\displaystyle\leq\$ $\displaystyle B\sum_{i\in\mathcal{N}}\sum^{T}_{t=1}\eta_{t}\mathbb{E{}}\left[ \mathbb{E{}}_{w_{i}\sim\mathbb{B}^{d}}\mathbb{E}_{\mathbf{z}_{-i}\sim\Pi_{j \neq i}\mathbb{S}^{d}}\left\|\nabla_{i}c_{i}^{t}\left(x_{i}^{t}+\delta_{t}A_{i }^{t}w_{i},\hat{x}_{-i}^{t}\right)-\nabla_{i}c_{i}^{t}\left(x^{t}\right)\right \|\mid x^{t}\right]$ $$

By the smoothness of $c_{i}^{t}$,

$$ $\displaystyle\mathbb{E}_{w_{i}\sim\mathbb{B}^{d}}\mathbb{E}_{\mathbf{z}_{-i} \sim\Pi_{j\neq i}\mathbb{S}^{d}}\left[\left\|\nabla_{i}c_{i}^{t}\left(x_{i}^{t }+\delta_{t}A_{i}^{t}w_{i},\hat{x}_{-i}^{t}\right)-\nabla_{i}c_{i}^{t}\left(x^ {t}\right)\right\|\right]$ $\displaystyle\leq\$ $\displaystyle\ell_{i}\mathbb{E{}}_{w_{i}\sim\mathbb{B}^{d}}\mathbb{E}_{\mathbf {z}_{-i}\sim\Pi_{j\neq i}\mathbb{S}^{d}}\left[\sqrt{\delta_{t}^{2}\left\|A_{i} w_{i}\right\|^{2}+\delta_{t}^{2}\sum_{j\neq i}\left\|A_{j}z_{j}\right\|^{2}} \right]\,.$ $$

Since $p$ is monotone, $\nabla^{2}p(x)$ is positive semi-definite, and $A_{i}^{t}\preceq(\nabla^{2}h(x_{i}))^{-1/2}$. For $\bar{x}_{i}^{t}=x_{i}^{t}+A_{i}^{t}w_{i}^{t}$. Define $\|v\|_{x}=\sqrt{v^{\top}\nabla^{2}h(x)v}$, we have $\|\bar{x}_{i}^{t}-x_{i}^{t}\|_{x_{i}}\leq\|\omega_{i}^{t}\|\leq 1$, and $\bar{x}_{i}^{t}\in W(x_{i}^{t})$, where $W(x_{i})=\{x^{\prime}_{i}\in\mathbb{R}^{d},\|x^{\prime}_{i}-x_{i}\|_{x_{i}}
\leq 1\}$ is the Dikin ellipsoid. Since $W(x_{i})\subseteq\mathcal{X}_{i},\forall x_{i}\in\mathop{int}(\mathcal{X}_{i})$, we can upper bound $\left\|A_{i}w_{i}\right\|^{2}$ by $B^{2}$, the diameter of the set $\mathcal{X}_{i}$. Hence $\|\nabla_{i}\hat{c}_{i}(x^{t})-\nabla_{i}c_{i}\left(x^{t}\right)\|\leq\ell_{i}
\delta_{t}\sqrt{n}B$. By Lemma J.5

$$ $\displaystyle\sum_{i\in\mathcal{N}}\sum^{T}_{t=1}\eta_{t}\mathbb{E{}}\left[ \left\langle\hat{g}_{i}^{t}-\nabla_{i}c_{i}^{t}\left(x^{t}\right),\omega_{i}-x _{i}^{t}\right\rangle\mid x^{t}\right]=\$ $\displaystyle\sum_{i\in\mathcal{N}}\sum^{T}_{t=1}\eta_{t}\mathbb{E{}}\left[ \left\langle\nabla_{i}\hat{c}_{i}^{t}\left(x^{t}\right)-\nabla_{i}c_{i}^{t} \left(x^{t}\right),\omega_{i}-x_{i}^{t}\right\rangle\mid x^{t}\right]$ $\displaystyle\leq\$ $\displaystyle\sum_{i\in\mathcal{N}}\sum^{T}_{t=1}\eta_{t}\mathbb{E{}}\left[ \left\|\nabla_{i}\hat{c}_{i}^{t}\left(x^{t}\right)-\nabla_{i}c_{i}^{t}\left(x^ {t}\right)\right\|\left\|\omega_{i}-x_{i}^{t}\right\|\mid x^{t}\right]$ $\displaystyle\leq\$ $\displaystyle\sqrt{n}B^{2}\sum_{i\in\mathcal{N}}\ell_{i}\sum^{T}_{t=1}\eta_{t} \delta_{t}\,.$ $$

Let $L=\sum_{i\in\mathcal{N}}\ell_{i}$. When $\mu=0$, combing and rearranging the terms, we have

$$ $\displaystyle\mathbb{E{}}\left[\sum_{i\in\mathcal{N}}D_{p}\left(x_{i}^{\ast},x _{i}^{T+1}\right)\right]$ $\displaystyle\leq\$ $\displaystyle O\left(\frac{n\nu\log(T)}{\kappa\eta_{T}T}+\frac{n\zeta B}{\eta_ {T}T^{3/2}}+\frac{nBL}{\kappa\sqrt{T}}+\frac{n}{\kappa\sqrt{T}}+\frac{nC_{p}}{ \eta_{T}T}+\frac{nd^{2}}{\kappa\eta_{T}T}\sum^{T}_{t=1}\frac{\eta_{t}^{2}}{ \delta_{t}^{2}}+\frac{\sqrt{n}B^{2}L\sum^{T}_{t=1}\eta_{t}\delta_{t}}{\kappa \eta_{T}T}+\frac{B\sum^{T}_{t=1}\Delta^{t}}{\eta_{T}T}\right)\,.$ $$

Take $\eta_{t}=\frac{1}{2dt^{3/4}}$, $\delta_{t}=\frac{1}{t^{1/4}}$, then $\sum^{T}_{t=1}\frac{\eta_{t}^{2}}{\delta_{t}^{2}}=O\left(\sum^{T}_{t=1}\frac{1
}{t}\right)=O(\log(T))$, and $\sum^{T}_{t=1}\eta_{t}\delta_{t}=O\left(\sum^{T}_{t=1}\frac{1}{t}\right)=O(
\log(T))$.
Hence, we have

$$ $\displaystyle\mathbb{E{}}\left[\sum_{i\in\mathcal{N}}D_{p}\left(x_{i}^{\ast},x _{i}^{T+1}\right)\right]\leq\$ $\displaystyle O\left(\frac{nd\nu\log(T)}{\kappa T^{1/4}}+\frac{n\zeta dB}{T^{3 /4}}+\frac{nBL}{\kappa\sqrt{T}}+\frac{ndC_{p}}{T^{1/4}}+\frac{nd\log(T)}{ \kappa T^{1/4}}+\frac{\sqrt{n}B^{2}L\log(T)}{\kappa T^{1/4}}+\frac{B\Delta}{T^ {1/4}}\right)\,,$ $$

where $\Delta=\sum^{T}_{t=1}\sum_{i\in\mathcal{N}}\max_{x}\|\nabla_{i}c_{i}(x)-\nabla
_{i}c_{i}^{t}(x)\|_{2}$.
∎

###### Proof.

## Appendix I Proof of Theorem 6.2

See 6.2

###### Proof.

We first fix a player $i$ decomposes

$$ $\displaystyle\sum^{T}_{t=1}\left\langle\nabla_{i}c_{i}^{t}\left(\hat{x}_{i}^{t },\hat{x}_{-i}^{t}\right),\hat{x}_{i}^{t}-x_{i}^{t,\ast}\right\rangle=\$ $\displaystyle\sum^{T}_{t=1}\left\langle\nabla_{i}c_{i}^{t}\left(\hat{x}_{i}^{t },\hat{x}_{-i}^{t}\right),\hat{x}_{i}^{t}-\omega_{i}\right\rangle+\sum^{T}_{t= 1}\left\langle\nabla_{i}c_{i}^{t}\left(\hat{x}_{i}^{t},\hat{x}_{-i}^{t}\right) ,\omega_{i}-x_{i}^{t,\ast}\right\rangle\,.$ $$

For the second term, we partition the horizon of play $T$ into $m$ batches $T_{k}$, $k\in[m]$, each of length $|T_{k}|=T^{q}$, $q\in[0,1]$. We will determine $q$ later. Note that the number of batches is thus $m=T^{1-q}$. For the batch $T_{k}$, we pick $\omega_{i}$ to be the Nash equilibrium of the first game. Then

$$ $\displaystyle\sum_{t\in[T_{k}]}\left\langle\nabla_{i}c_{i}^{t}\left(\hat{x}_{i }^{t},\hat{x}_{-i}^{t}\right),\omega_{i}-x_{i}^{t,\ast}\right\rangle\leq\$ $\displaystyle\sum_{t\in[T_{k}]}\left\|\nabla_{i}c_{i}^{t}\left(\hat{x}_{i}^{t} ,\hat{x}_{-i}^{t}\right)\right\|\left\|\omega_{i}-x_{i}^{t,\ast}\right\|$ $\displaystyle\leq\$ $\displaystyle GT^{q}\max_{t\in[T_{k}]}\left\|\omega_{i}-x_{i}^{t,\ast}\right\|$ $\displaystyle\leq\$ $\displaystyle GT^{q}\sum_{t\in[T_{k}]}\left\|x_{i}^{t+1,\ast}-x_{i}^{t,\ast}\right\|$ $\displaystyle\leq\$ $\displaystyle GT^{q}V_{i}(T_{k})\,,$ $$

where the third inequality is by the definition of $\omega_{i}$.

Therefore, we have

$$ $\displaystyle\sum^{T}_{t=1}\left\langle\nabla_{i}c_{i}^{t}\left(\hat{x}_{i}^{t },\hat{x}_{-i}^{t}\right),\hat{x}_{i}^{t}-x_{i}^{t,\ast}\right\rangle=\$ $\displaystyle\sum^{m}_{k=1}\sum_{t\in[T_{k}]}\left\langle\nabla_{i}c_{i}^{t} \left(\hat{x}_{i}^{t},\hat{x}_{-i}^{t}\right),\hat{x}_{i}^{t}-\omega_{i}\right \rangle+GT^{q}V_{i}(T)\,.$ $$

Define the smoothed version of $c_{i}$ as $\hat{c}_{i}^{t}(x)=\mathbb{E}_{w_{i}\sim\mathbb{B}^{d}}\left[c_{i}^{t}\left(x_
{i}+\delta A_{i}w_{i},x_{-i}\right)\right]$.
Then, for batch $T_{k}$, we decompose $\sum^{T}_{t=1}\left\langle\nabla_{i}c_{i}\left(\hat{x}_{i}^{t},\hat{x}_{-i}^{t
}\right),\hat{x}_{i}^{t}-\omega_{i}\right\rangle$ as

$$ $\displaystyle\sum_{t\in[T_{k}]}\left\langle\nabla_{i}c_{i}\left(\hat{x}_{i}^{t },\hat{x}_{-i}^{t}\right),\hat{x}_{i}^{t}-\omega_{i}\right\rangle$ $\displaystyle=\$ $\displaystyle\sum_{t\in[T_{k}]}\left\langle\nabla_{i}\hat{c}_{i}\left(\hat{x}_ {i}^{t},\hat{x}_{-i}^{t}\right),\hat{x}_{i}^{t}-\omega_{i}\right\rangle+\sum_{ t\in[T_{k}]}\left\langle\nabla_{i}c_{i}\left(\hat{x}_{i}^{t},\hat{x}_{-i}^{t} \right)-\nabla_{i}\hat{c}_{i}\left(\hat{x}_{i}^{t},\hat{x}_{-i}^{t}\right), \hat{x}_{i}^{t}-\omega_{i}\right\rangle$ $\displaystyle\leq\$ $\displaystyle\sum_{t\in[T_{k}]}\left\langle\nabla_{i}\hat{c}_{i}\left(\hat{x}_ {i}^{t},\hat{x}_{-i}^{t}\right),\hat{x}_{i}^{t}-\omega_{i}\right\rangle+B\sum_ {t\in[T_{k}]}\left\|\nabla_{i}c_{i}\left(\hat{x}_{i}^{t},\hat{x}_{-i}^{t} \right)-\nabla_{i}\hat{c}_{i}\left(\hat{x}_{i}^{t},\hat{x}_{-i}^{t}\right) \right\|_{2}\,.$ $$

For the first term, recall that by the update rule, we have,

$$ $\displaystyle D_{h}\left(\omega_{i},\hat{x}_{i}^{t+1}\right)=\$ $\displaystyle D_{h}\left(\omega_{i},\hat{x}_{i}^{t}\right)+\eta_{t}\left \langle\nabla\hat{c}_{i}^{t}\left(\hat{x}^{t}\right),\omega_{i}-\hat{x}_{i}^{t }\right\rangle+\eta_{t}\left\langle\hat{g}_{i}^{t}-\nabla\hat{c}^{t}_{i}\left( \hat{x}^{t}\right),\omega_{i}-\hat{x}_{i}^{t}\right\rangle$ $\displaystyle\ +\eta_{t}\left\langle\hat{g}_{i}^{t},\hat{x}_{i}^{t}-\hat{x}_{i }^{t+1}\right\rangle\,.$ $$

By Lemma J.5, for any $\omega_{i}\in\mathcal{X}_{i}$, we have

$$ $\displaystyle\mathbb{E{}}\left[\left\langle\hat{g}_{i}^{t}-\nabla\hat{c}^{t}_{ i}\left(\hat{x}^{t}\right),\omega_{i}-\hat{x}_{i}^{t}\right\rangle\mid\hat{x}^ {t}\right]=\$ $\displaystyle\mathbb{E{}}\left[\left\langle\nabla_{i}\hat{c}^{t}_{i}(\hat{x}^{ t})-\nabla_{i}\hat{c}^{t}_{i}\left(\hat{x}^{t}\right),\omega_{i}-\hat{x}_{i}^{ t}\right\rangle\mid\hat{x}^{t}\right]=0\,.$ $$

Therefore,

$$ $\displaystyle\mathbb{E{}}\left[D_{h}\left(\omega_{i},\hat{x}_{i}^{t+1}\right) \right]=\$ $\displaystyle\mathbb{E{}}\left[D_{h}\left(\omega_{i},\hat{x}_{i}^{t}\right)+ \eta_{t}\left\langle\nabla\hat{c}^{t}_{i}\left(\hat{x}^{t}\right),\omega_{i}- \hat{x}_{i}^{t}\right\rangle\right]+\eta_{t}\mathbb{E{}}\left[\left\langle\hat {g}_{i}^{t},\hat{x}_{i}^{t}-\hat{x}_{i}^{t+1}\right\rangle\right]\,.$ $$

Rearranging the terms yields

$$ $\displaystyle\mathbb{E{}}\left[\left\langle\nabla\hat{c}^{t}_{i}\left(\hat{x}^ {t}\right),\hat{x}_{i}^{t}-\omega_{i}\right\rangle\right]\leq\$ $\displaystyle\mathbb{E{}}\left[\frac{\left(D_{h}\left(\omega_{i},\hat{x}_{i}^{ t}\right)-D_{h}\left(\omega_{i},\hat{x}_{i}^{t+1}\right)\right)}{\eta_{t}}+ \eta_{t}\left\langle\hat{g}_{i}^{t},\hat{x}_{i}^{t}-\hat{x}_{i}^{t+1}\right \rangle\right]\,.$ $$

By Lemma J.2, we have $\mathbb{E{}}\left[\left\langle\hat{g}_{i}^{t},\hat{x}_{i}^{t}-\hat{x}_{i}^{t+1
}\right\rangle\right]\leq\eta_{t}\mathbb{E{}}\left[\left\|A_{i}^{t}\hat{g}_{i}
^{t}\right\|^{2}\right]$.
Taking expectation conditioned on $\hat{x}^{t}$, we have $\mathbb{E{}}\left[\left\|A_{i}^{t}\hat{g}_{i}^{t}\right\|^{2}\mid\hat{x}^{t}
\right]=\frac{d^{2}}{\delta_{t}^{2}}\mathbb{E{}}\left[\tilde{c}_{i}^{t}(\hat{x
}^{t})^{2}\|z_{i}^{t}\|^{2}\mid\hat{x}^{t}\right]\leq\frac{d^{2}}{\delta_{t}^{
2}}$, and therefore $\mathbb{E{}}\left[\left\langle\hat{g}_{i}^{t},\hat{x}_{i}^{t}-\hat{x}_{i}^{t+1
}\right\rangle\right]\leq\frac{\eta_{t}d^{2}}{\delta_{t}^{2}}$.

Taking summation over $T$, and take $\eta_{t}=\frac{1}{2dt^{p}}$, $\delta_{t}=\frac{1}{t^{r}}$ we have

$$ $\displaystyle\sum_{t\in[T_{k}]}\mathbb{E{}}\left[\left\langle\nabla\hat{c}^{t} _{i}\left(\hat{x}^{t}\right),\hat{x}_{i}^{t}-\omega_{i}\right\rangle\right]\leq\$ $\displaystyle dT^{p}\mathbb{E{}}\left[D_{h}\left(\omega_{i},x_{i}^{1}\right) \right]+\sum_{t\in[T_{k}]}\frac{\eta_{t}d^{2}}{\delta^{2}}$ $\displaystyle\leq\$ $\displaystyle O\left(dT^{p}\mathbb{E{}}\left[D_{h}\left(\omega_{i},x_{i}^{1} \right)\right]+T^{q(p-2r)}\right)\,,$ $$

as we assumed $D_{p}(x_{i},x_{i}^{\prime})$ is bounded for any $x_{i},x_{i}^{\prime}$.

Define $\pi_{x}(y)=\inf\left\{t\geq 0:x+\frac{1}{t}(y-x)\in\mathcal{X}_{i}\right\}$. Notice that $x_{i}^{1}(x)=\mathop{\rm argmin}_{x_{i}\in\mathcal{X}_{i}}h(x_{i})$, so $D_{h}(\omega_{i},x_{i}^{1})=h(\omega_{i})-h(x_{i}^{1})$.

- •
If $\pi_{x_{i}^{1}}(\omega_{i})\leq 1-\frac{1}{\sqrt{T^{q}}}$, then by Lemma J.6, $D_{h}(\omega_{i},x_{i}^{1})=\nu\log(T^{q})$, and $\sum^{T}_{t=1}\mathbb{E{}}\left[\hat{c}_{i}\left(\hat{x}^{t}_{i},x_{-i}^{t}
\right)-\hat{c}_{i}\left(\omega_{i},x_{-i}^{t}\right)\right]=O\left(\nu dT^{1-
p}\log(T^{q})\right)$.
- •
Otherwise, we find a point $\omega_{i}^{\prime}$ such that $\|\omega_{i}^{\prime}-\omega_{i}\|=O(1/\sqrt{T^{q}})$ and $\pi_{x_{i}^{1}}(\omega_{i}^{\prime})\leq 1-\frac{1}{\sqrt{T^{q}}}$. Then $D_{h}(\omega_{i}^{\prime},x_{i}^{1})=\nu\log(T^{q})$,
$\displaystyle\left\langle\nabla_{i}\hat{c}_{i}^{t}\left(\omega_{i}^{\prime},x_
{-i}^{t}\right),\omega_{i}^{\prime}-\omega_{i}\right\rangle\leq\|\nabla_{i}
\hat{c}_{i}^{t}\left(\omega_{i}^{\prime},x_{-i}^{t}\right)\|\|\omega_{i}^{
\prime}-\omega_{i}\|\leq\frac{G}{\sqrt{T^{q}}}\,.$
Therefore, $\sum_{t\in[T_{k}]}\mathbb{E{}}\left[\hat{c}_{i}\left(\hat{x}^{t}_{i},x_{-i}^{t
}\right)-\hat{c}_{i}\left(\omega_{i},x_{-i}^{t}\right)\right]=O\left(\nu dT^{p
}\log(T^{q})+GT^{q/2}+T^{q(p-2r)}\right)$.

By the definition of $\hat{c}_{i}$ and the smoothness of $c_{i}$,

$$ $\displaystyle\|\nabla_{i}\hat{c}_{i}(\hat{x}^{t})-\nabla_{i}c_{i}\left(\hat{x} ^{t}\right)\|=\$ $\displaystyle\left\|\mathbb{E}_{w_{i}\sim\mathbb{B}^{d}}\mathbb{E}_{\mathbf{z} _{-i}\sim\Pi_{j\neq i}\mathbb{S}^{d}}\left[\nabla_{i}c_{i}\left(\hat{x}_{i}^{t }+\delta_{t}A_{i}^{t}w_{i},\hat{x}_{-i}^{t}\right)-\nabla_{i}c_{i}\left(\hat{x }^{t}\right)\right]\right\|$ $\displaystyle\leq\$ $\displaystyle\ell_{i}\sqrt{\mathbb{E{}}_{w_{i}\sim\mathbb{B}^{d}}\mathbb{E}_{ \mathbf{z}_{-i}\sim\Pi_{j\neq i}\mathbb{S}^{d}}\left[\delta_{t}^{2}\left\| \delta_{t}A_{i}w_{i}\right\|^{2}+\delta_{t}^{2}\sum_{j\neq i}\left\|A_{j}z_{j} \right\|^{2}\right]}\,.$ $$

Since $p$ is monotone, $\nabla^{2}p(x)$ is positive semi-definite, and $A_{i}^{t}\preceq(\nabla^{2}h(x_{i}))^{-1/2}$. For $\bar{x}_{i}^{t}=\hat{x}_{i}^{t}+A_{i}^{t}w_{i}^{t}$. Define $\|v\|_{x}=\sqrt{v^{\top}\nabla^{2}h(x)v}$, we have $\|\bar{x}_{i}^{t}-\hat{x}_{i}^{t}\|_{x_{i}}\leq\|\omega_{i}^{t}\|\leq 1$, and $\bar{x}_{i}^{t}\in W(\hat{x}_{i}^{t})$, where $W(x)=\{x^{\prime}_{i}\in\mathbb{R}^{d},\|x^{\prime}_{i}-x_{i}\|_{x_{i}}\leq 1\}$ is the Dikin ellipsoid. Since $W(x_{i})\subseteq\mathcal{X}_{i},\forall x_{i}\in\mathop{int}(\mathcal{X}_{i})$, we can upper bound $\left\|A_{i}w_{i}\right\|^{2}$ by $B^{2}$, the diameter of the set $\mathcal{X}_{i}$. Hence $\|\nabla_{i}\hat{c}_{i}(\hat{x}^{t})-\nabla_{i}c_{i}\left(\hat{x}^{t}\right)\|
\leq\ell_{i}\delta_{t}\sqrt{n}B$.

With $\delta_{t}=\frac{1}{t^{r}}$, we have

$$ $\displaystyle\sum_{t\in[T_{k}]}\mathbb{E{}}\left[\left\langle\nabla_{i}c_{i} \left(\hat{x}_{i}^{t},\hat{x}_{-i}^{t}\right),\hat{x}_{i}^{t}-\omega_{i}\right \rangle\right]=\ O\left(\nu dT^{p}\log(T^{q})+GT^{q/2}+T^{q(p-2r)}+\ell_{i} \sqrt{n}B^{2}T^{q(1-r)}\right)\,.$ $$

Combining, as $m=T^{1-q}$ we have

$$ $\displaystyle\sum^{T}_{t=1}\mathbb{E{}}\left[\left\langle\nabla_{i}c_{i}^{t} \left(\hat{x}_{i}^{t},\hat{x}_{-i}^{t}\right),\hat{x}_{i}^{t}-x_{i}^{t,\ast} \right\rangle\right]$ $\displaystyle=\$ $\displaystyle O\left(GT^{q}V_{i}(T)\right)+\sum_{j\in[m]}\tilde{O}\left(\nu dT ^{1-p}+GT^{q/2}+T^{q(p-2r)}+\ell_{i}\sqrt{n}B^{2}T^{q(1-r)}\right)$ $\displaystyle=\$ $\displaystyle\tilde{O}\left(\nu dT^{(1-q)+p}+GT^{(1-q)+q/2}+T^{(1-q)+q(p-2r)}+ \ell_{i}\sqrt{n}B^{2}T^{(1-q)+q(1-r)}+GT^{q}V_{i}(T)\right)\,.$ $$

When $V_{i}(T)=T^{\varphi}$, $\varphi\in[0,1]$, we set $q=\frac{2(1-\varphi)}{3}$, $p=\frac{(1-\varphi)}{3}$, $r=\frac{1}{2}$, we have

$$ $\displaystyle\sum^{T}_{t=1}\mathbb{E{}}\left[\left\langle\nabla_{i}c_{i}^{t} \left(\hat{x}_{i}^{t},\hat{x}_{-i}^{t}\right),\hat{x}_{i}^{t}-x_{i}^{t,\ast} \right\rangle\right]=\$ $\displaystyle\tilde{O}\left(\left(\nu d+G+\ell_{i}\sqrt{n}B^{2}\right)T^{\frac {1+2\varphi}{3}}+T^{\frac{(2\varphi+1)(\varphi+2)}{9}}\right)\,.$ $$

Divided by $T$, we have

$$ $\displaystyle\frac{1}{T}\sum^{T}_{t=1}\mathbb{E{}}\left[\left\langle\nabla_{i} c_{i}^{t}\left(\hat{x}_{i}^{t},\hat{x}_{-i}^{t}\right),\hat{x}_{i}^{t}-x_{i}^{ t,\ast}\right\rangle\right]=\$ $\displaystyle\tilde{O}\left(\frac{\nu d+G+\ell_{i}\sqrt{n}B^{2}}{T^{\frac{2(1- \varphi)}{3}}}+\frac{1}{T^{\frac{9}{8}-\frac{(4\varphi+5)^{2}}{72}}}\right)\,.$ $$

Sum over $i\in\mathcal{N}$ and we have the claimed result.
∎

###### Proof.

## Appendix J Auxiliary Lemmas

###### Lemma J.1 .

With the update rule equation 1,

$$ $\displaystyle\sum_{i\in\mathcal{N}}D_{p}\left(x_{i}^{\ast},x_{i}^{T+1}\right)$ $\displaystyle\leq\$ $\displaystyle O\left(\frac{n\nu\log(T)}{\eta_{T}\kappa T}+\frac{n\zeta B}{\eta _{T}T^{3/2}}\right)+O\left(\frac{nB\sum_{i\in\mathcal{N}}\ell_{i}}{\kappa T^{3 /2}}+\frac{n}{\kappa T^{3/2}}\right)\frac{\sum^{T}_{t=1}\eta_{t}}{\eta_{T}}+O \left(\frac{nC_{p}}{\eta_{T}T}\right)$ $\displaystyle+\frac{1}{\kappa\eta_{T}(T+1)}\sum_{i\in\mathcal{N}}\sum^{T}_{t=1 }\eta_{t}\left\langle\hat{g}_{i}^{t},x_{i}^{t}-x_{i}^{t+1}\right\rangle+\frac{ 1}{\kappa\eta_{T}(T+1)}\sum^{T}_{t=1}\eta_{t}\sum_{i\in\mathcal{M}}\left \langle\hat{g}_{i}^{t}-\nabla_{i}c_{i}\left(x^{t}\right),x_{i}^{\ast}-x_{i}^{t }\right\rangle$ $\displaystyle+\frac{1}{\kappa\eta_{T}(T+1)}\sum^{T}_{t=1}\eta_{t}\sum_{i\in \mathcal{N}\setminus\mathcal{M}}\left\langle\hat{g}_{i}^{t}-\nabla_{i}c_{i} \left(x^{t}\right),\bar{x}_{i}-x_{i}^{t}\right\rangle\,,$ $$

where $\bar{x}_{i}$ is a point such that $\|\bar{x}_{i}-x_{i}^{\ast}\|=O(1/\sqrt{T})$ and $\inf\left\{t\geq 0:x_{i}^{1}+\frac{1}{t}(\bar{x}_{i}-x_{i}^{1})\in\mathcal{X}_
{i}\right\}\leq 1-1/\sqrt{T}$.

###### Proof.

By the update rule equation 1, we have

$$ $\displaystyle\eta_{t}\hat{g}_{i}^{t}+\eta_{t}\kappa(t+1)\left(\nabla p\left(x_ {i}^{t+1}\right)-\nabla p\left(x_{i}^{t}\right)\right)+\left(\nabla h\left(x_{ i}^{t+1}\right)-\nabla h\left(x_{i}^{t}\right)\right)=0\,.$ $$

For a fixed point $\omega_{i}$, by the three-point equality of Bregman divergence, we have

$$ $\displaystyle D_{h}\left(\omega_{i},x_{i}^{t+1}\right)$ $\displaystyle=\$ $\displaystyle D_{h}\left(\omega_{i},x_{i}^{t}\right)-D_{h}\left(x_{i}^{t+1},x_ {i}^{t}\right)+\left\langle\nabla h\left(x_{i}^{t}\right)-\nabla h\left(x_{i}^ {t+1}\right),\omega_{i}-x_{i}^{t+1}\right\rangle$ $\displaystyle=\$ $\displaystyle D_{h}\left(\omega_{i},x_{i}^{t}\right)-D_{h}\left(x_{i}^{t+1},x_ {i}^{t}\right)+\eta_{t}\left\langle\hat{g}_{i}^{t},\omega_{i}-x_{i}^{t+1} \right\rangle+\eta_{t}\kappa(t+1)\left\langle\nabla p\left(x_{i}^{t+1}\right)- \nabla p\left(x_{i}^{t}\right),\omega_{i}-x_{i}^{t+1}\right\rangle$ $\displaystyle=\$ $\displaystyle D_{h}\left(\omega_{i},x_{i}^{t}\right)-D_{h}\left(x_{i}^{t+1},x_ {i}^{t}\right)+\eta_{t}\left\langle\hat{g}_{i}^{t},\omega_{i}-x_{i}^{t+1} \right\rangle+\eta_{t}\kappa(t+1)\left(D_{p}\left(\omega_{i},x_{i}^{t}\right)- D_{p}\left(\omega_{i},x_{i}^{t+1}\right)-D_{p}\left(x_{i}^{t+1},x_{i}^{t} \right)\right)\,.$ $$

Rearranging and by the non-negativity of Bregman divergence, we have,

$$ $\displaystyle D_{h}\left(\omega_{i},x_{i}^{t+1}\right)+\eta_{t}\kappa(t+1)D_{p }\left(\omega_{i},x_{i}^{t+1}\right)$ $\displaystyle\leq\$ $\displaystyle D_{h}\left(\omega_{i},x_{i}^{t}\right)+\eta_{t}\kappa(t+1)D_{p} \left(\omega_{i},x_{i}^{t}\right)+\eta_{t}\left\langle\hat{g}_{i}^{t},\omega_{ i}-x_{i}^{t}\right\rangle+\eta_{t}\left\langle\hat{g}_{i}^{t},x_{i}^{t}-x_{i}^ {t+1}\right\rangle$ $\displaystyle=\$ $\displaystyle D_{h}\left(\omega_{i},x_{i}^{t}\right)+\eta_{t}\kappa(t+1)D_{p} \left(\omega_{i},x_{i}^{t}\right)+\eta_{t}\left\langle\nabla_{i}c_{i}\left(x^{ t}\right),\omega_{i}-x_{i}^{t}\right\rangle+\eta_{t}\left\langle\hat{g}_{i}^{t }-\nabla_{i}c_{i}\left(x^{t}\right),\omega_{i}-x_{i}^{t}\right\rangle+\eta_{t} \left\langle\hat{g}_{i}^{t},x_{i}^{t}-x_{i}^{t+1}\right\rangle\,.$ $$

By Lemma J.3 and the assumption that $c_{i}(x)-\kappa p(x_{i})$ is monotone, we have

$$ $\displaystyle\eta_{t}\sum_{i\in\mathcal{N}}\left\langle\nabla_{i}c_{i}\left(x^ {t}\right),\omega_{i}-x_{i}^{t}\right\rangle\leq\$ $\displaystyle-\eta_{t}\kappa\sum_{i\in\mathcal{N}}\left(D_{p}\left(x_{i}^{t}, \omega_{i}\right)+D_{p}\left(\omega_{i},x_{i}^{t}\right)\right)+\eta_{t}\sum_{ i\in\mathcal{N}}\left\langle\nabla_{i}c_{i}\left(\omega\right),\omega_{i}-x_{i }^{t}\right\rangle\,.$ $$

Therefore,

$$ $\displaystyle\sum_{i\in\mathcal{N}}D_{h}\left(\omega_{i},x_{i}^{t+1}\right)+ \eta_{t}\kappa(t+1)\sum_{i\in\mathcal{N}}D_{p}\left(\omega_{i},x_{i}^{t+1}\right)$ $\displaystyle\leq\$ $\displaystyle\sum_{i\in\mathcal{N}}D_{h}\left(\omega_{i},x_{i}^{t}\right)+\eta _{t}\kappa t\sum_{i\in\mathcal{N}}D_{p}\left(\omega_{i},x_{i}^{t}\right)+\eta_ {t}\sum_{i\in\mathcal{N}}\left\langle\nabla_{i}c_{i}(\omega),\omega_{i}-x_{i}^ {t}\right\rangle+\eta_{t}\sum_{i\in\mathcal{N}}\left\langle\hat{g}_{i}^{t}- \nabla_{i}c_{i}\left(x^{t}\right),\omega_{i}-x_{i}^{t}\right\rangle$ $\displaystyle\ +\eta_{t}\sum_{i\in\mathcal{N}}\left\langle\hat{g}_{i}^{t},x_{i }^{t}-x_{i}^{t+1}\right\rangle\,.$ $$

Summing over $T$, by the non-negativity of Bregman divergence, we have

$$ $\displaystyle\eta_{T}\kappa(T+1)\sum_{i\in\mathcal{N}}D_{p}\left(\omega_{i},x_ {i}^{T+1}\right)$ $\displaystyle\leq\$ $\displaystyle\sum_{i\in\mathcal{N}}D_{h}\left(\omega_{i},x_{i}^{1}\right)+ \kappa\sum_{i\in\mathcal{N}}D_{p}\left(\omega_{i},x_{i}^{1}\right)+\sum^{T}_{t =1}\sum_{i\in\mathcal{N}}\eta_{t}\left\langle\nabla_{i}c_{i}(\omega),\omega_{i }-x_{i}^{t}\right\rangle+\sum^{T}_{t=1}\sum_{i\in\mathcal{N}}\eta_{t}\left \langle\hat{g}_{i}^{t}-\nabla_{i}c_{i}\left(x^{t}\right),\omega_{i}-x_{i}^{t}\right\rangle$ $\displaystyle\ +\sum^{T}_{t=1}\sum_{i\in\mathcal{N}}\eta_{t}\left\langle\hat{g }_{i}^{t},x_{i}^{t}-x_{i}^{t+1}\right\rangle\,.$ $$

Define $\pi_{x}(y)=\inf\left\{t\geq 0:x+\frac{1}{t}(y-x)\in\mathcal{X}_{i}\right\}$, let us consider $x_{i}^{\ast}$, the equilibrium of the game.

- •
If $\pi_{x_{i}^{1}}(x_{i}^{\ast})\leq 1-1/\sqrt{T}$, we set $\omega_{i}=x_{i}^{\ast}$. Let this set of player be $\mathcal{M}$
- •
Otherwise, we find $\bar{x}_{i}\in\mathcal{X}_{i}$ such that $\|\bar{x}_{i}-x_{i}^{\ast}\|=O(1/\sqrt{T})$ and $\pi_{x_{i}^{1}}(\bar{x}_{i})\leq 1-1/\sqrt{T}$. We set $\omega_{i}=\bar{x}_{i}$.

By Lemma J.6, and initializing $x_{i}^{1}$ to minimize $h$, thus $D_{h}(\omega_{i},x_{i}^{1})=h(\omega_{i})-h(x_{i}^{1})\leq\nu\log(T)$.

Therefore, we have

$$ $\displaystyle\eta_{T}\kappa(T+1)\left(\sum_{i\in\mathcal{M}}D_{p}\left(x_{i}^{ \ast},x_{i}^{T+1}\right)+\sum_{i\in\mathcal{N}\setminus\mathcal{M}}D_{p}\left( \bar{x}_{i},x_{i}^{T+1}\right)\right)$ $\displaystyle\leq\$ $\displaystyle n\nu\log(T)+\kappa\sum_{i\in\mathcal{M}}D_{p}\left(x_{i}^{\ast}, x_{i}^{1}\right)+\kappa\sum_{i\in\mathcal{N}\setminus\mathcal{M}}D_{p}\left( \bar{x}_{i},x_{i}^{1}\right)+\sum^{T}_{t=1}\eta_{t}\sum_{i\in\mathcal{M}}\left \langle\nabla_{i}c_{i}(x^{\ast}_{\mathcal{M}},\bar{x}_{\mathcal{N}\setminus \mathcal{M}}),x_{i}^{\ast}-x_{i}^{t}\right\rangle$ $\displaystyle+\sum^{T}_{t=1}\eta_{t}\sum_{i\in\mathcal{N}\setminus\mathcal{M}} \left\langle\nabla_{i}c_{i}(x^{\ast}_{\mathcal{M}},\bar{x}_{\mathcal{N} \setminus\mathcal{M}}),\bar{x}_{i}-x_{i}^{t}\right\rangle+\eta_{t}\sum^{T}_{t= 1}\sum_{i\in\mathcal{M}}\left\langle\hat{g}_{i}^{t}-\nabla_{i}c_{i}\left(x^{t} \right),x_{i}^{\ast}-x_{i}^{t}\right\rangle$ $\displaystyle\ +\eta_{t}\sum^{T}_{t=1}\sum_{i\in\mathcal{N}\setminus\mathcal{M }}\left\langle\hat{g}_{i}^{t}-\nabla_{i}c_{i}\left(x^{t}\right),\bar{x}_{i}-x_ {i}^{t}\right\rangle+\sum_{i\in\mathcal{N}}\sum^{T}_{t=1}\eta_{t}\left\langle \hat{g}_{i}^{t},x_{i}^{t}-x_{i}^{t+1}\right\rangle\,.$ $$

By the three-point inequality and the non-negativity of Bregman divergence, we have

$$ $\displaystyle\sum_{i\in\mathcal{N}\setminus\mathcal{M}}D_{p}\left(\bar{x}_{i}, x_{i}^{T+1}\right)=\$ $\displaystyle\sum_{i\in\mathcal{N}\setminus\mathcal{M}}D_{p}\left(\bar{x}_{i}, x_{i}^{\ast}\right)+\sum_{i\in\mathcal{N}\setminus\mathcal{M}}D_{p}\left(x_{i} ^{\ast},x_{i}^{T+1}\right)-\sum_{i\in\mathcal{N}\setminus\mathcal{M}}\left \langle\bar{x}_{i}-x_{i}^{\ast},\nabla p\left(x_{i}^{T+1}\right)-\nabla p\left (\bar{x}_{i}\right)\right\rangle$ $\displaystyle\geq\$ $\displaystyle\sum_{i\in\mathcal{N}\setminus\mathcal{M}}D_{p}\left(x_{i}^{\ast} ,x_{i}^{T+1}\right)-\sum_{i\in\mathcal{N}\setminus\mathcal{M}}\left\langle\bar {x}_{i}-x_{i}^{\ast},\nabla p\left(x_{i}^{T+1}\right)-\nabla p\left(\bar{x}_{i }\right)\right\rangle\,.$ $$

By Cauchy-Schwarz and the smoothness of $p$, we have

$$ $\displaystyle\sum_{i\in\mathcal{N}\setminus\mathcal{M}}\left\langle\bar{x}_{i} -x_{i}^{\ast},\nabla p\left(x_{i}^{T+1}\right)-\nabla p\left(\bar{x}_{i}\right )\right\rangle\leq\$ $\displaystyle\sum_{i\in\mathcal{N}\setminus\mathcal{M}}\left\|\bar{x}_{i}-x_{i }^{\ast}\right\|\left\|\nabla p\left(x_{i}^{T+1}\right)-\nabla p\left(\bar{x}_ {i}\right)\right\|$ $\displaystyle\leq\$ $\displaystyle\zeta\sum_{i\in\mathcal{N}\setminus\mathcal{M}}\left\|\bar{x}_{i} -x_{i}^{\ast}\right\|\left\|x_{i}^{T+1}-\bar{x}_{i}\right\|$ $\displaystyle\leq\$ $\displaystyle O\left(\frac{n\zeta B}{\sqrt{T}}\right)$ $$

As $x_{i}^{\ast}$ is a Nash equilibrium, we have $\sum_{i\in\mathcal{N}}\left\langle\nabla_{i}c_{i}(x^{\ast}),x_{i}^{\ast}-x_{i}
^{t}\right\rangle=0$, therefore,

$$ $\displaystyle\eta_{t}\sum_{i\in\mathcal{M}}\left\langle\nabla_{i}c_{i}(x^{\ast }_{\mathcal{M}},\bar{x}_{\mathcal{N}\setminus\mathcal{M}}),x_{i}^{\ast}-x_{i}^ {t}\right\rangle+\eta_{t}\sum_{i\in\mathcal{N}\setminus\mathcal{M}}\left \langle\nabla_{i}c_{i}(x^{\ast}_{\mathcal{M}},\bar{x}_{\mathcal{N}\setminus \mathcal{M}}),\bar{x}_{i}-x_{i}^{t}\right\rangle$ $\displaystyle=\$ $\displaystyle\eta_{t}\sum_{i\in\mathcal{N}}\left\langle\nabla_{i}c_{i}(x^{\ast }),x_{i}^{\ast}-x_{i}^{t}\right\rangle+\eta_{t}\sum_{i\in\mathcal{N}}\left \langle\nabla_{i}c_{i}(x^{\ast}_{\mathcal{M}},\bar{x}_{\mathcal{N}\setminus \mathcal{M}})-\nabla_{i}c_{i}(x^{\ast}),x_{i}^{\ast}-x_{i}^{t}\right\rangle$ $\displaystyle\ +\eta_{t}\sum_{i\in\mathcal{N}\setminus\mathcal{M}}\left\langle \nabla_{i}c_{i}(x^{\ast}_{\mathcal{M}},\bar{x}_{\mathcal{N}\setminus\mathcal{M }}),\bar{x}_{i}-x_{i}^{\ast}\right\rangle$ $\displaystyle\leq\$ $\displaystyle\eta_{t}\sum_{i\in\mathcal{N}}\ell_{i}\left\|x_{i}^{\ast}-x_{i}^{ t}\right\|\left(\sum_{i\in\mathcal{N}\setminus\mathcal{M}}\left\|x^{\ast}_{i}- \bar{x}_{i}\right\|\right)+\eta_{t}\sum_{i\in\mathcal{N}\setminus\mathcal{M}} \left\|\nabla_{i}c_{i}(x^{\ast}_{\mathcal{M}},\bar{x}_{\mathcal{N}\setminus \mathcal{M}})\right\|\left\|\bar{x}_{i}-x_{i}^{\ast}\right\|$ $\displaystyle\leq\$ $\displaystyle O\left(\frac{\eta_{t}nB\sum_{i\in\mathcal{N}}\ell_{i}}{\sqrt{T}} +\frac{\eta_{t}n}{\sqrt{T}}\right)\,.$ $$

Hence, as $D_{p}(x_{i},x_{i}^{\prime})\leq C_{p},\forall x_{i},x_{i}^{\prime}$,

$$ $\displaystyle\sum_{i\in\mathcal{N}}D_{p}\left(x_{i}^{\ast},x_{i}^{T+1}\right)$ $\displaystyle\leq\$ $\displaystyle O\left(\frac{n\nu\log(T)}{\eta_{T}\kappa T}+\frac{n\zeta B}{\eta _{T}T^{3/2}}\right)+O\left(\frac{nB\sum_{i\in\mathcal{N}}\ell_{i}}{\kappa T^{3 /2}}+\frac{n}{\kappa T^{3/2}}\right)\frac{\sum^{T}_{t=1}\eta_{t}}{\eta_{T}}+O \left(\frac{nC_{p}}{\eta_{T}T}\right)$ $\displaystyle+\frac{1}{\kappa\eta_{T}(T+1)}\sum_{i\in\mathcal{N}}\sum^{T}_{t=1 }\eta_{t}\left\langle\hat{g}_{i}^{t},x_{i}^{t}-x_{i}^{t+1}\right\rangle+\frac{ 1}{\kappa\eta_{T}(T+1)}\sum^{T}_{t=1}\eta_{t}\sum_{i\in\mathcal{M}}\left \langle\hat{g}_{i}^{t}-\nabla_{i}c_{i}\left(x^{t}\right),x_{i}^{\ast}-x_{i}^{t }\right\rangle$ $\displaystyle+\frac{1}{\kappa\eta_{T}(T+1)}\sum^{T}_{t=1}\eta_{t}\sum_{i\in \mathcal{N}\setminus\mathcal{M}}\left\langle\hat{g}_{i}^{t}-\nabla_{i}c_{i} \left(x^{t}\right),\bar{x}_{i}-x_{i}^{t}\right\rangle\,.$ $$

∎

###### Lemma J.2 .

Take $\eta_{t}\leq\frac{1}{2d}$, we have

$$ $\displaystyle\left\langle\hat{g}_{i}^{t},x_{i}^{t}-x_{i}^{t+1}\right\rangle=\$ $\displaystyle\eta_{t}\left\|A_{i}^{t}\hat{g}_{i}^{t}\right\|^{2}\,.$ $$

###### Proof.

Define

$$ $\displaystyle f(x_{i})=\eta_{t}\left\langle x_{i},\hat{g}^{t}_{i}\right\rangle +\eta_{t}(t+1)D_{p}(x_{i},x_{i}^{t})+D_{h}(x_{i},x_{i}^{t})\,.$ $$

As adding the linear term $\langle x_{i},\hat{g}_{i}^{t}\rangle$ does not affect the self-concordant barrier property, and $p$ is strongly monotone, $f(x)$ is a self-concordant barrier.

Define the local norm $\|h\|_{x}:=\sqrt{h^{\top}\nabla^{2}f(x)h}$, by Holder’s inequality, we have

$$ $\displaystyle\left\langle\hat{g}_{i}^{t},x_{i}^{t}-x_{i}^{t+1}\right\rangle=\$ $\displaystyle\left\|\hat{g}_{i}^{t}\right\|_{x^{t}_{i},\ast}\left\|x_{i}^{t}-x _{i}^{t+1}\right\|_{x_{i}^{t}}\,.$ $$

Notice that

$$ $\displaystyle\nabla f(x_{i}^{t})=\eta_{t}\hat{g}_{i}^{t}\,,\nabla^{2}f(x_{i}^{ t})=\eta_{t}(t+1)\nabla^{2}p(x_{i}^{t})+\nabla^{2}h(x_{i}^{t})\,.$ $$

Therefore, by our assumption that $c_{i}(x)\in[0,1]$,

$$ $\displaystyle\left\|\left(\nabla^{2}f(x_{i}^{t})\right)^{-1}\nabla f(x_{i}^{t} )\right\|_{x^{t}_{i}}=\$ $\displaystyle\eta_{t}\left\|A_{i}^{t}\hat{g}_{i}^{t}\right\|$ $\displaystyle\leq\$ $\displaystyle\eta_{t}d|c_{i}(\hat{x}^{t})|\leq\eta_{t}d\,.$ $$

By Lemma J.4, take $\eta_{t}\leq\frac{1}{2d}$, we have

$$ $\displaystyle\left\|x_{i}^{t}-x_{i}^{t+1}\right\|_{x_{i}^{t}}=\$ $\displaystyle\left\|x_{i}^{t}-\arg\min_{x}f(x_{i}^{t})\right\|_{x_{i}^{t}}\leq \ 2\left\|\left(\nabla^{2}f(x_{i}^{t})\right)^{-1}\nabla f(x_{i}^{t})\right\|_ {x^{t}_{i}}\leq\eta_{t}\left\|A_{i}^{t}\hat{g}_{i}^{t}\right\|\,.$ $$

Therefore, we have

$$ $\displaystyle\left\langle\hat{g}_{i}^{t},x_{i}^{t}-x_{i}^{t+1}\right\rangle=\$ $\displaystyle\eta_{t}\left\|A_{i}^{t}\hat{g}_{i}^{t}\right\|^{2}\,.$ $$

∎

###### Lemma J.3 .

[Proposition 1 Bauschke et al., ()]
For an operator $G$ that $G-\nabla p(x)$ is monotone,

$$ $\displaystyle\left\langle G(x)-G(x^{\prime}),x^{\prime}-x\right\rangle\leq\$ $\displaystyle-\sum_{i\in\mathcal{N}}\left(D_{p}\left(x_{i},x_{i}^{\prime} \right)+D_{p}\left(x_{i}^{\prime},x_{i}\right)\right)\,.$ $$

###### Proof.

By the monotonicity of $G-\nabla p(x)$, we have

$$ $\displaystyle\left\langle G(x)-G(x^{\prime}),x^{\prime}-x\right\rangle\leq\$ $\displaystyle\left\langle\nabla p(x)-\nabla p(x^{\prime}),x^{\prime}-x\right\rangle$ $\displaystyle\leq\$ $\displaystyle-\sum_{i\in\mathcal{N}}\left(D_{p}\left(x_{i},x_{i}^{\prime} \right)+D_{p}\left(x_{i}^{\prime},x_{i}\right)\right)\,,$ $$

where the second inequality is due to the definition of Bregman divergence.
∎

###### Lemma J.4 (Lemma 3 Lin et al., ( 2021 ) ) .

For any self-concordant function $g$ and let $\lambda(x,g)\leq\frac{1}{2}$, $\lambda(x,g):=$ $\|\nabla g(x)\|_{x,\star}=\left\|\left(\nabla^{2}g(x)\right)^{-1}\nabla g(x)
\right\|_{x}$, we have $\|x-$ $\arg\min_{x^{\prime}\in\mathcal{X}}g\left(x^{\prime}\right)\|_{x}\leq 2\lambda
(x,g)$, where $\|\cdot\|_{x}$ is the local norm given by $\|h\|_{x}:=\sqrt{h^{\top}\nabla^{2}g(x)h}$.

###### Lemma J.5 (Lemma 7 of Lin et al., ( 2021 ) ) .

Suppose that $c_{i}$ is a monotone function and $A_{i}\in\mathbb{R}^{d\times d}$ is an invertible matrix for each $i\in\mathcal{N}$, we define the smoothed version of $c_{i}$ with respect to $A_{i}$ by $\hat{c}_{i}(x)=\mathbb{E}_{w_{i}\sim\mathbb{B}^{d}}\mathbb{E}_{\mathbf{z}_{-i}
\sim\Pi_{j\neq i}\mathbb{S}^{d}}\left[c_{i}\left(x_{i}+A_{i}w_{i},\hat{x}_{-i}
\right)\right]$ where $\mathbb{S}^{d}$ is a $d$-dimensional unit sphere, $\mathbb{B}^{d}$ is a $d$-dimensional unit ball and $\hat{x}_{i}=$ $x_{i}+A_{i}z_{i}$ for all $i\in\mathcal{N}$. Then, the following statements hold true:

- •
$\nabla_{i}\hat{c}_{i}(x)=\mathbb{E}\left[d\cdot c_{i}\left(\hat{x}_{i},\hat{x}
_{-i}\right)\left(A_{i}\right)^{-1}z_{i}\mid x_{1},x_{2},\ldots,x_{N}\right]$.
- •
If $\nabla c_{i}$ is $\ell_{i}$-Lipschitz continuous and we let $\sigma_{\max}(A)$ be the largest eigenvalue of $A$, we have $\left\|\nabla_{i}\hat{c}_{i}(x)-\nabla_{i}c_{i}(x)\right\|\leq\ell_{i}\sqrt{
\sum_{j\in\mathcal{N}}\left(\sigma_{\max}\left(A_{j}\right)\right)^{2}}$.

###### Lemma J.6 (Lemma 2 Lin et al., ( 2021 ) ) .

Suppose that $\mathcal{X}$ is a closed, monotone and compact set, $R$ is a $\nu$-self-concordant barrier function for $\mathcal{X}$ and $\bar{x}=\arg\min_{x\in\mathcal{X}}R(x)$ is a center. Then, we have $R(x)-R(\bar{x})\leq\nu\log\left(\frac{1}{1-\pi_{\bar{x}}(x)}\right)$. For any $\epsilon\in(0,1]$ and $x\in\mathcal{X}_{\epsilon}$, we have $\pi_{\bar{x}}(x)\leq\frac{1}{1+\epsilon}$ and $R(x)-R(\bar{x})\leq\nu\log\left(1+\frac{1}{\epsilon}\right)$.

###### Lemma J.1 .

###### Proof.

###### Lemma J.2 .

###### Proof.

###### Lemma J.3 .

###### Proof.

###### Lemma J.4 (Lemma 3 Lin et al., ( 2021 ) ) .

###### Lemma J.5 (Lemma 7 of Lin et al., ( 2021 ) ) .

###### Lemma J.6 (Lemma 2 Lin et al., ( 2021 ) ) .

## Appendix K More Experimental Results

In Figure 2 and 3 we supplement more experiment results for zero-sum matrix games and Cournot competition. Note that in Figure 3, the curve of OMD with gradient coincides exactly with the curve GD with gradient. We found similar observations that our algorithm attains comparable performance to OMD and GD with full information gradient.

Figure: Figure 2: More examples on the zero-sum matrix game, with $A$ being $[2,1],[1,3]$, $[3,0],[0,1]$, and $[1,2],[2,0]$.
Refer to caption: extracted/5794487/figure/minimax3.png

Figure: Figure 3: More examples on the Cournot competition, with the marginal cost being $50,60,70$.
Refer to caption: extracted/5794487/figure/cournot3.png

## Peer Reviews

confidence: 3
contribution: 1
initial_rating: 3
presentation: 2
questions: Please see the weakness section.
soundness: 1
strengths: - The authors attempted to improve the state-of-the-art last-iterate convergence rate for general monotone game and their time-varying variants --- the existing best bounds are $T^{-1/2}$ for strongly monotone games by Lin et al. (2021), and $T^{-1/6}$ for linear games by Cai et al. (2023).
summary: This paper design an algorithm for monotone games with bandit feedback that has last-iterate convergence guarantee.  The convergence rate is $T^{-1/4}$ for monotone games, and $T^{-1/6}$ for linear games.
weaknesses: - I have concern about the soundness of the results. At the first sight, there is a strange gap between the results for general monotone game and the linear game in Table 1:  for general monotone game the bound is $T^{-1/4}$, and for linear game the bound is $T^{-1/6}$.  However, linear game is a special case of monotone game. The author claimed that for linear games, one cannot find a convex function $p$ that satisfies the definitions in Line 217.  However, for any linear game, one can always artificially add a perturbation function $\epsilon ||x||^2$ to make it strictly monotone.  Applying the $T^{-1/4}$ bound for general monotone game, and bounding the error due to perturbation, one should be able to get a bound of $T^{-1/4}+\epsilon$ for linear games.  Then taking $\epsilon\to 0$, it seems we should also get a $T^{-1/4}$ bound also for linear games. 

- It seems the main gap lies in Theorem 5.1.  In the theorem, although the right-hand side of the bound is $T^{-1/4}$, the left-hand side is not the usual Euclidean distance to the equilibrium, but the distance induced by the $p$ function defined in Line 217. This distance could be arbitrarily smaller than the Euclidean distance if $p$ is close to linear. Translating this distance back to Euclidean distance will just make this bound vacuous.  Therefore, I think the claim of the paper is flawed and it does not seem to make improvement over prior work.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: A couple of questions/issues for the authors:

1. In the third example, it is claimed that splittable routing games are monotone. Can the authors justify this claim? It is not obvious to me.
2. Before Proposition 5.1, the authors write that "We have the following proposition which shows that the social welfare converges to optimal welfare on average". This is not correct, the dynamics only approximate the optimal welfare (depending on the smoothness parameters).
soundness: 3
strengths: The paper studies an important and well-studied problem in the intersection of optimization and game theory, and makes a number of concrete contributions that improve over the prior state-of-the-art. As described above, the paper obtains the best-known rates for monotone games and time-varying games under bandit feedback, which is certainly an important contribution. Further, the techniques employed in the paper are also quite non-trivial, and rely on using two different regularizers in an interesting way. While most prior results examine last-iterate convergence in the full-feedback model, the more realistic bandit model introduces several technical challenges. I believe that the results of the paper are well within the scope of ICLR, and will be well-received from the community on learning in games. The most related papers have been adequately discussed. All claims appear to be sound; I did not find any notable issue in the approach. The writing overall is of high quality.
summary: The paper studies the last-iterate convergence of no-regret dynamics in monotone games under bandit feedback. In particular, they provide a new algorithm that attains the best-known rate of convergence of $T^{-1/4}$ and $T^{-1/2}$ under strong monotonicity, while guaranteeing at the same time the no-regret property. This is the first convergence rate for uncoupled dynamics in monotone games under bandit feedback. Further, for time-varying games, the convergence rate improves over the prior state-of-the-art.
weaknesses: In terms of weaknesses, it appears that the proof mostly relies on existing techniques, although the way those techniques are used seems to have new aspects. I would encourage the authors to highlight more the technical challenges and the technical contributions compared to prior work. There is also one issue that really confuses me: Section 5.3 is about the special case of linear cost functions; how is possible that the rate is worse in that special case? For example, matrix games are clearly monotone, so why doesn't the rate of $T^{-1/4}$ apply in that case?

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: - A big concern is the potential issue induced by the non-uniqueness of the Nash equilibrium for monotone games. In Theorem 5.1, convergence is measured by the distance of the actions to x_i^*. Does this statement hold for each x_i^*? Should the convergence be measured using the distance of the actions to the set of Nash equilibria? 

- The concept of 'uncoupled' is quite confused. In games, each player's payoff depends on the actions of other agents, which suggests that their dynamics should be inherently coupled. However, a clear description of strongly uncoupled dynamics is not given.

- The assumptions required for each theorem are not explicitly stated, making it difficult for readers to follow directly from the theorem statements.

- The presentation of Algorithm 1 should be improved. For example, agents should first sample z and then play the perturbed action. Besides, each agent should receive feedback after all agents play their actions. Please see Algorithm 2 in [Lin 2021].
soundness: 2
strengths: The paper provides a theoretical analysis on several cases, including the convergence rate for monotone games (both in expectation and with high probability), social welfare, linear cost, and the time-varying case.
summary: This paper studies the convergence of mirror-descent algorithm in general monotone games and strongly monotone games. Several theoretical results are given. The time-varying monotone games are also considered. Overall I find the analyzed problem not new and the convergence rate is not surprised.
weaknesses: - Many convergence rates in this paper fail to improve the existing result. The advantage of the proposed algorithm is unclear. The simulation results are also weak to demonstrate the advantage of the proposed algorithm. 

- There is a large room for the simulation section to be improved. Please add comparison of Algorithm 1 to, at least, the method in [Lin 2021]. Besides, the examples used in simulation are simple.

- The technical contributions are unclear. The techniques used, including the ellipsoidal gradient estimator, are similar to those found in existing literature.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: 1. Can the $O(T^{-1/4})$ last-iterate convergence rate be considered as the $O(T^{3/4})$ regret for bandit convex optimization?

2. For bandit optimization with convex and smooth functions, the state-of-the-art regret is $O(T^{2/3})$ by [1], which seems to correspond to a last-iterate rate of $O(T^{-1/3})$ in the setup of smooth monotone games. Is it possible to improve the current $O(T^{-1/4})$ to $O(T^{-1/3})$?

3. For BCO problems with smooth or strongly convex functions, FTRL seems to be more popular than OMD [1,2]. Is it possible to represent Algorithm 1 using an FTRL-based update rule? Besides, are FTRL and OMD equivalent in the setup of BCO or bandit smooth monotone games?

4. The rates in Table 2 are not last-iterate results. First, the guarantees in Duvocelle et al. (2023) and Yan et al. (2023) are represented in a regret-type rate. Second, the rate in Theorem 6.2 is actually not last-iterate since the performance measure is $\frac{1}{T} \sum_t \cdots$. I suggest that the authors could correct this issue in the next version.

5. It seems that the rates authors mentioned in Duvocelle et al. (2023) and Yan et al. (2023) do not need smoothness? I did not check their results very carefully, and I suggest that the authors could conduct a careful double check about whether the above two works need smoothness. If not, these works seem to be not comparable since Duvocelle et al. (2023) and Yan et al. (2023) focused on strongly monotone games without smoothness while this paper considers monotone smooth games.

6. It should also be made clear that Duvocelle et al. (2023) and Yan et al. (2023) used tracking error $\\|x_t - x^*\\|^2$ as the performance measure, which is different from the measure used in this paper. Thus again I think these works are actually not comparable. Besides, if I am wrong about some statements, it is welcome that the authors could correct me.

6. In Line 287, the authors said that "We show that Algorithm 1 converges to the Nash equilibrium in monotone, strongly monotone, and linear games."  It should be made clear that the results for different kinds of games require different parameter configurations. 

7. Could the authors provide some explanations about the validness of the permanence measure $\sum_i D_p(x_i^*, x_i^{T+1})$? Why this measure is a valid measure of the distance of the algorithm's output to the Nash equilibrium? The gap using Bregman divergence heavily relies on how convex the function $p(\cdot)$ is. If $p(\cdot)$ is nearly a linear function, this measure seems not to be a good enough performance measure, from my point of view, intuitively. I guess that the authors use this quantity as the performance measure mainly due to technical reasons, as I said in the 'Weaknesses' part?



References:

[1] Improved Regret Guarantees for Online Smooth Convex Optimization with Bandit Feedback, AISTATS 2011

[2] Bandit Convex Optimization: Towards Tight Bounds, NIPS. 2014
soundness: 2
strengths: Extending the studies from strongly monotone games to generally monotone ones is meaningful. The proposed algorithm where a new regularizer is used is novel. The authors have also proved a high-probability result for the global convergence rate. And they have also applied their results to the social welfare to validate the importance of their results.
summary: This paper studies the problem of learning in a general monotone game with bandit feedback, with strongly uncoupled dynamics. For smooth cost functions, the authors achieved an $O(T^{-1/4})$ last-iterate convergence rate. For strongly monotone games, the obtained last-iterate convergence matches the state-of-the-art rate $O(T^{-1/2})$. The proposed algorithm uses the standard gradient estimator for BCO, but updates with a slightly different OMD-based algorithm with a different regularizer.  When each player runs the same algorithm, the individual regret can also be guaranteed with $O(T^{3/4})$ regret for generally monotone games and $O(T^{1/2})$ for strongly monotone games. Finally, the authors further extended the results to time-varying games, considering two cases: (1) the time-varying game sequence gradually converges to a static game, and (2) the game sequence does not converge, and the performance measure relies on some non-stationarity measures depicting how the game sequence changes.
weaknesses: The core of achieving the last-iterate convergence is inserting a regularizer $p(\cdot)$ into the OMD update. Concretely, in the OMD update,  the authors imported an additional additive $\eta (t+1) D_p(x_i, x_i^t)$ into the OMD update. And the core analysis is shown in Lemma J.1 in the appendix. Specifically, by using $\sum_i D_p(x_i^*, x_i^{T+1})$ as the performance measure, the $\eta (t+1) D_p(x_i, x_i^t)$ in the OMD update can be extracted and moved to the left-hand side of the three-point equality of Bregman divergence, dividing both sides by $O(T)$ yields the performance measure on the left-hand side and a term like $(Regret)/T$ on the right-hand side. Consequently, it remains to analyze the regret guarantee of the proposed method and dividing it by $T$ yields the final last-iterate convergence rate. 

This idea is novel. However, the key question is how we can access such function $p(\cdot)$. As stated by the authors on Page 5, the function $p(\cdot)$ has to satisfy the condition that $c_i(x_i, x_{-i}) - \kappa p(x_i)$ is convex. To compute such a valid $p(\cdot)$, the algorithm must have the complete information of the original cost function $c_i$, which is not permitted by the learning protocol since $c_i$ is unknown. Otherwise, if $p(\cdot)$ is given by the learning problem, the condition of $c_i(x_i, x_{-i}) - \kappa p(x_i)$ being convex should be an assumption that should be put in Section 3 along with Assumption 3.1. However, I am more inclined to believe that this should not be an assumption since $p(\cdot)$ is something that appears in the algorithm, while assumptions are actually statements about the problem-dependent and algorithm-independent quantities. Can the authors provide some further explanations on this issue?