Uncoupled and Convergent Learning in Monotone Games under Bandit Feedback
Authors: Jing Dong
Baoxiang Wang
Yaoliang Yu
Venue: NeurIPS 2025 poster ()
Keywords: Game theory
online learning
Primary area: optimization

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})$ 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})$ 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.

Uncoupled and Convergent Learning in Monotone Games under Bandit Feedback
Jing Dong"
The Chinese University of Hong Kong, Shenzhen j jingdong@link cuhk, edu. cn
Baoxiang Wang"
The Chinese University of Hong Kong, Shenzhen bxiangrang@cuhk. edu.cn cn
Yaoliang Yu*
University of Waterloo and Vector Institute yaoliang. yu@uwaterloo.cc
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 wide range real applications. We propose a mirrror-descent-basee algorithm, which converges ((7-1/4) under Bregman divergence and is also no-regret, where the choice of Bregman divergence is determined by the convexity of the game. The result is achieved by the dedicated use of two regularizations and the analysis of the fixed point thereof. The convergence rate is further improved to OTT-1/2) 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.
Introduction
We consider multi-player online learning in games. In this problem, the cost function for each player unknown to the player, and they need to learn to play the game through repeated interaction with other players. We focus class of monotone and smooth games, which was first introduced by Rosen (1965). This encapsulates a wide array common games, such as two-player zero-sum games, convex-concave games, and zero-sum polymatrix games (Bregman and Fokin, 1987). Our goal is to find algorithms that solve the problem under bandit feedback and strongly uncoupled dynamics. Within this context, each player 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 the time- average convergence Nash equilibrium learning in monotone games (Even-Dar et al., 2009; Syrgkanis et al., 2015; Farina et al., 2022). However, these works only guarantee the convergence of the time average of the joint action profile. Such
Authors are ordered alphabetically.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

convergence properties are less appealing because while the trajectories of the players converge in the time-average sense, they may still exhibit cycling (Mertikopoulos al., 2018). This jeopardizes the practical use of such algorithms.
Popular no-regret algorithms such mirror descent have demonstrated convergence in the last iterate within specific scenarios, such as two-player zero-sum games (Cai et al., 2023) and strongly monotone games (Bravo al., 2018; Drusvyatskiy al., 2022: Lin al., 2021). Yet convergence to a Nash equilibrium in monotone and smooth games is not available unless one assumes exact gradient feedback and coordination of players (Cai al., 2022; Cai and Zheng, 2023). remains open as to whether a no-regret algorithm can efficiently converge to 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 Nash equilibrium in general monotone and smooth games with bandil feedback and strongly uncoupled dynamics?
In this work, we present a seirror-deceent-baae algorithm designed to converge Nash equilibrium in monotone and smooth games. Our algorithm uncoupled, convergent and 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 justifies that our algorithm could be deployed in both stationary and staniinttionryy tasks.
We achieve state-of-the-art results in both monotone games and time-varying monotone games.
In monotone and smooth games:
Under bandit feedback and strongly uncoupled dynamics, show our algorithm achieves last-iterate convergence rate of O(T-1/4).
In cases where the game exhibits strong monotonicity, our result improves to O(T 1/2), matching the current best available convergence rates for strongly monotone games (Drusvy- atskiy et al., 2022; Lin et al., 2021).
-Our algorithm is no regret, albeit players may be self-interested. The individual regret is at most ( in monotone games and at most ((72/2) in strongly monotone games.
time-varying monotone and smooth games:
If the game eventually converges to a static state within a time frame of O(T*), our algorithm achieves convergence in O(T
If the game does not converge but experiences gradual changes in a Nash equilibrium that evolves in O(T+), our algorithm exhibits convergence rates of O (max (T20/3-2/3, T(Ap-5)) (0000-5)77/799//) /72-9/8) }) The algorithm outperforms best available results of T0/5-1/5 by Duvocelle et al. (2023) and 2 by Yan et (2023).
Table and Table 2 summarize results and the results of previous works. We remark that, compared to previous results, which are typically obtained with the & norm or gap function being the convergence metric, measure the convergence. A suitable regularizer is chosen based on the curvature of the game, and the choice of our algorithm's 's regularizer will affect the meaning of convergence. We remark that the different convergence notions do not imply each other in general. It is only in the special case of a strongly monotone game that results be obtained with convergence in la norm, and convergence in the gap function implies convergence in & norm if the equilibrium is unique.
the Bregman divergence induced by the algorithm'' 's regularizer to
2 Related Works
Monotone games. The convergence monotone games has been studied in a significant line of research. For strongly monotone game under exact gradient feedback, the linear last-iterate convergence rate is known (Tseng, 1995; Liang and Stokes, 2019; Zhou et al., 2020). Under noisy gradient feedback, Jordan al. (2023) showed a last- convergence rate of O(T-1). Under bandit feedback, Bervoets et al. (2020) proposed an algorithm that asymptotically converges to the equilibrium if is unique. Bravo et al. (2018) subsequently introduced algorithm with last-iterate convergence rate of O13-)/3) while also ensuring the no-regret property. Later works (Lin et al.,

---

Table 1: Summary of results for monotone games. "E" stands for the result in expectation, and "P" stands for the result held 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 refer to noisy gradient, "E" for exact gradient. We use "(N)" to remark that the results also be obtained with noisy feedback. We also remark that prior works have used mostly two different convergence metrics, the distance between gap function (denoted as "G")) Our results are ohtained with the Bregman divergence between iterates and the Nash equilibrium set (denoted as "B"), and we use the gap function for the linear cost function special case. For other asymptotic convergence guarantees, we use "A" to denote it.
iterates and the Nash equilibrium (denoted as "L"), and
Class of games
Convergence Metric
Feedback
Results
0(T-1/3)
Bravo et al. (2018)
StroM
bandit
(E)
((T-1/2)
Drusvyatskiy et al. (2022)
StroM
bandit
(E)
L
O(T-1/2)
Lin et al. (2021)
StroM
bandit (N)
(E)
Jordan al. (2023)
StroM
N
O(T
L
O(T-1/2)
Ours
StroM
bandit (N)
(E & P)
B
Mertikopoulos and Zhou (2019)
M
N
asymptotic
A
Cai and Zheng (2023)
M
E
O(T-1)
G
Tatarenko and Kamgarpour (2019)
M
bandit
asymptotic
O(T-1/4)
Ours
M
bandit (N)
(E)
B
O(T-1/6)
Cai al. (2023)
linear*
bandit
(E)
((T-1/6)
Ours
linear
bandit
(E)
G
2021) further improved the last-iterate convergence rate to O(T-1/2) under bandit feedback using the self-concordant barrier function. Jordan al. (2023) gave 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 zero-mean noise), Lin et al. (2021) showed that the convergence rate is still OT-11/2).
For monotone but not strongly monotone games, Mertikopoulos and Zhou (2019) leveraged the dual averaging algorithm to demonstrate asymptotic convergence rate under noisy gradient feedback. With access to the exact gradient information, Cai and Zheng (2023) gave last-iterate convergence rate of O(T-1). In the context of bandit feedback, Tatarenko and Kamgarpour (2019) proposed an algorithm that asymptotically converges to a Nash equilibrium.
Time-varying monotone games. Motivated by world applications such as Cournot competi- tion, where multiple firms supply goods to the market, and pricing is subject to fluctuations due to factors like weather, holidays, and politics. Duvocelle et (2023) studied the strongly monotone game under 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 ((T*) across horizon T. Duvocelle et al. (2023) provided an algorithm that attains con- vergence rate of OTT9/5-1/5) under bandit feedback. Subsequent work of Yan et al. (2023) further improved this rate to (1T9/3-2/3 under exact gradient feedback.

---

Table 2: Summary of last-iterate convergence results for time-narying games. All results here in expectation results. Strongly monotone games are abbreviated to "StroM", and monotone games are abbreviated to "M". We also remark that prior works have used mostly two different convergence metrics, the & distance between the iterates and the Nash equilibrium, and the gap function (see Theorem 5,4 for example), Our results are obtained with the Bregman divergence between the iterates and the Nash equilibrium set, and use the gap function the linear cost function special case.
Class of games
Time-varying property
Feedback
Results
Duvocelle al. (2023)
StroM M
converging O(1T)
bandit
asymptotic
Ours
converging in O(Ta)
bandit
O(T-1/4+a)
Duvocelle et al. (2023)
StroM
( variation path
bandit
0(T9/5-1/5)
Yan al. (2023)
StroM
( variation path
exact
O(T9/3-2/3)
gradient
O (max (max(
Ours
M
((T*) variation path
bandit
T(4p+5)
3 Preliminaries
We consider multi-player game with players, with the set of players denoted N. Each player takes action on compact and convex set X; S IR of d dimensions, and has cost function c z-1). where 2; E X; is the action of the i-th player and x-; E I J J X3 the action of all other players. We assume the radius of X, is bounded, i.e., || - a'll I B, Vx, of E X. Without loss of generality, further assume (x) E [).
In this work, we study a class of monotone continuous games, where the gradient of the cost functions is monotone, and the cost functions are continuous (Assumption 3.1). Games that satisfy this assumption include convex-concave games, convex 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., 2021: Farina et al., 2022).
Assumption 3.1. For all player i E N, the cost function cg(M,,, x--)) is continuous, disferentiable, convex, and s-sshooth in x,, Further, o has bounded gradient [v)c(()) I G and the gradient F(x: [V.r(=))eeN is monotone operator, i.e., (F(x) FVy)) (x: v) 2 0, Vx, y-
For notational convenience, we denote L = EiENN
A common solution concept in the game is the Nash equilibrium, which is a state of dynamics where no player can reduce its cost by unilaterally changing its action. Our aim to learn a Nash equilibrium x" E II, X; of the game. Formally, the Nash equilibrium is defined as follows.
Definition 3.1 (Nash equilibrium). An action x² E II; Xx is a Nash equilibrium if cc(x") S xx,,, Vr; E X E N.
When the game satisfies Assumption 3.1, and is with a compact action set, is known that must admit at least one Nash equilibrium (Debreu, 1952).
3.1 Examples of Monotone Continuous Games
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 (convex-coneave game). Consider a two-player convex-concave game, where the objective function is eı (x)) ((11,22), (2( - -(xx1 22). It is immediate that if s is continuous, differentiable, smooth, convex in Fı, concave in 12, 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 finite set of N firms, where firm supplies the market with a quantity x; E [0, Cx) of some good and C2 is the firm's 's production capacity. The good is priced as decreasing function P(xrot) burots where

---

Fiot = EE= Tj is the total number of goods supplied to the market, and a, > O are positive x; x;P( where di is the cost
constants. The cost of firm is then given by (-)) of producing one unit of good. This is the associated production cost minus the total revenue from producing T; units of goods. It is clear that 6; continuous and differentiable, and Bravo et al. (2018) showed that e has a positive definite and bounded Hessian (i.e., convex and smooth).
Example 3.3 (Splittable routing game). In a splittable routing game, each player directs a flow, denoted as from source to a destination in an undirected graph G (V, E). Each edge E E is linked to a latency function, represented as (e(f), which denotes the latency cost of the flow passing through the edge. The strategies available player i are the various ways of dividing or "splitting" the flow fü 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, 2015).
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 (2,,, x x=x)) with respect to the action taken F;. The strongly uncoupled learning dynamic (Daskalakis et al., 201 1) means players do not have prior knowledge of the 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-playe system, by reusing existing single-agent learning algorithms.
Algorithm
Our algorithm builds upon the renowned mirror-descent algorithm. The mirror descent algorithm generalizes the gradient descent by extending first-order optimization to constrained decision spaces by leveraging Bregman divergences for updates. For an agent with decision set X' C Rd, mirror map h : X + I (a strictly convex, differentiable function), and step size Th > 0 at iteration the mirror descent update takes the form It41 arg min { (V x)
(1, x+)]. where ft X' - R denotes the agent's loss (or negative payoff) at iteration 6, and Dp, 2xx) = p(z) p(z))= (Vp(zt),
zτ) is the Bregman divergence induced by p. We also remark that each player may choose their own pt. instead of agreeing on the same p. and thus the overall dynamic still uncoupled. The efficacy of online mirror-descent in finding a Nash equilibrium has been demonstrated under full information, and in both linear and strongly monotone games, with extensive investigations into its last-iterate convergence investigated in Cen al. (2021); Lin et al. (2021); Cai et al. (2023); Duvocelle et al. (2023).
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 regularizer p accommodate monotone (and not strongly monotone) games. Similar use of two regularizers has also been investigated (Lin et al., 2021). However, their method used the Euclidean norm regularization, which cannot be extended our setting.
Regularizers. Let h be a u-self- barrier function (Definition 4.1), p be a convex function with μ < v²p(z) 3 ÇI, Ç > 0, 2 O. Let D, denote the Bregman divergence induced by p. We choose such that for any Ii, x/ E X, (,, x4) S Cp < oc, and for some k >> 0, es ( xy((x)) is convex. Note that when G; 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.. We will discuss the necessary modification to the algorithm when e, is linear in Section 5.3.
Definition 4.1. A function h. iin((X) + R is v-self concordant barrier for a closed convex set X C R", where in)( is an interior of X. if 1) h is three times continuously differentiable; 2) h(x) xc i + 0X, where 0X is boundary of X; 3) for Vx int(X') and VX I..,
we have ( < 2 (A (²h())>) 3/2 and [h(a)) X1 S (ATT))()))) 1/2 where
(2)(2)) [dI, X2, Aa] 0t, (I + tIii + f2 + tada)
(1=13=1==0
5

---

It is shown that any closed convex domain of R has a self cofforannord barrier (Lee and Yue, 2021). We also remark that adding linear function does change the self-concordant property, as the third derivative of any linear function is zero; therefore, the addition of the linear term does not affect the third derivative of sum the functions.
Ellipsoidal gradient estimator. As our algorithm operates under bandit feedback and strongly uncoupled dynamies, would need to design gradient estimator while only using costs for the individual player.
Let 84, Bá be the d-dimensional unit sphere and the d-dimensional unit ball, respectively. Our algorithm estimates the gradient using the following ellipsoidal estimator:
d of - 5,
= (A)) A (V²h(a,)) - ne(t p(V)) 1/2 = + &,
where zf is uniformly independently sampled from S (before receiving the feedback) and 8,, Th [0, 1] are tunable parameters.
One can show that of is an unbiased estimate of the gradient of a smoothed cost function (xx)) = B..-BBBBB. -0, [c (x) Auw #[:]] When is strongly convex, one can upper bound (+)(()) (v)((r)] by the maximum eigenvalue A and it suffices take 6, 1, which recovers the results in Lin et al. (. However, when is convex and not strongly convex, one would need to carefully tune ó, to control the bias from estimating the smoothed cost function. This ellipsoidal gradient estimator was first introduced by Abernethy et al. (2008) for the case of c, being linear, and was then extended by Hazan and Levy (2014) 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., 2018; Lin et al., 2021).
Based on the ellipsoidal gradient estimator, we present our uncoupled and convergent algorithm for monotone games under bandit feedback.
Algorithm 1: Doubly regularized online Mirror Descent with bandit feedback
Input: Learning rate Me, parameter o,, regularizer b(.).p(). constant i. 1 x. = argmin,,ea Exx; h(z;)
2 for t = 1...., T do
Set A! = (VPh(x)) + (t 1)V*p(=;))
Sample 2f gd uniformly at random
5
Play at = of + 6,4f24 receive bandit feedback (ā,, --4)
Update gradient estimator of = (c)
Update the strategy
argmin (n (xr, Di) m 1)Dp(a,, + (n(,),a))) 2,EX
(1)
Implementation. Note that solving Equation (1) is equivalent to solving convex but potentially non-smooth optimization problem. Certain sets X' C gd, including the cases when X' is the strategy space of a normal-fome game or an extensive-form game, can be solved by the proximal Newton algorithm provably Olog" (1/e)) iterations (Farina et al., 2022). When such guarantees are not required, one could use other optimization methods to solve (1), Our experiment section provides more details.
The choice of and h is game-dependen, For example, when (x) x² 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) = log(1 + z) with k <
No-regret Convergence to a Nash equilibrium
In this section, we present our main results on the last-iterate convergence to a Nash equilibrium. We show that Algorithm converges to Nash equilibrium 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 e; (z"). The discussion of noisy bandit feedback, where player observes cx t with ef be zero-mean noise, is deferred to the appendix (Theorem 1.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 T
20074
p=
== Define EiEN Dy (Ki, 24.) as
1 p>0.
#>0.
20072
infsex. EieN Dp Ii), where X is the set of Nash equilibrium. With Algorithm and under Assumption 3.1, we have
E
Σ iEN
Dp (2t a2
new (T)
xT1/
+
T3/1
+
KVT
nBL
+
ndC₂
Tyf +
(dlog(
xT
+
P = 0 xT
ndv log(T)
RVT
ndCB
RVT
nBL
ndC, VT
+
nd (og()) BLlog(T)
RVT
NRVT
p 0
We remark that if each player chooses different ps, we can obtain the same convergence guarantee under the metric E [EieN Dp. xx; +)], as the analysis hold through decomposing into
In the case of monotone games, Bravo et al. (2018) showed an asymptotic convergence to a Nash equilibrium. To the best of our knowledge, Theorem 5.1 is the first result on the last-iterate con- vergence rate for monotone games. For strongly monotone games, Bravo al. (2018) first gave O(T-1/3) last-iterate convergence rate, which was later improved to O(T-1/2) by Lin et al. (2021).
We note that the choice of the regularizer p determines the convergence metrics D-(-.) and therefore affects the meaning of convergence. In the most extreme case, where p is linear, such metrics can be vacuous. Therefore, it important to choose an appropriate p recover Nash equilibrium. Under Assumption 3.1, this metric may imply an c-Nash equilibrium. While these measures are meaningful for comparison, we remark that they may not directly comparable the (total) gap function used in some prior works. Specifically, neither of the two measures upper bounds the other.
While we defer the proof to the appendix, we discuss the main ideas for deriving the results. By the update rule, we can obtain the inequality for an arbitrary wi:
Dp (wi, + + m) + D) (w);x 111
(2)
$ Dr (wi,, x/) + m + 1) (w,, x;) + n (v.c, (z') we 2t) + me residual terms.
When the game is strongly monotone, we can directly use strongly monotonicity and take p to be the Euclidean norm to obtain a recursive relation similar to
||w| - 112 < - ni ||: o + residual terms.
This amounts applying this recursion and upper-bounding the residual terms individually obtain a last-iterate convergence. However, when the game is monotone but not strongly monotone, we will need a different approach. Notice that G = Vc; Vp a monotone operator. Using the property of Bregman divergence, we have (G(z) - G(x'), x' - x) < - -EEN (D, (I,, x!) + Dp (e(.
We then the recursive inequality and leverage the combination of two regularizations, which gives upper bound qrx(T 1) EiEN Dr (wi, 2, +.) Now it suffices properly choose suitable wi such that both the first term ΣiEN Dn (W,, and the the cumulative sum of Et EREN Ne (V,c(ww), w; - .r) are bounded. When Wi is a Nash equilibrium x;, the later term can be upper bounded trivially using the monotonicity c,, while does not imply a bounded first
term. Therefore, we set w; = xf when the first term can be bounded. Otherwise, we set it to close enough point to 2/, such that the first term can be bounded and the later term is bounded through more careful calculation.
7

---

High probability result. In the case of a 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. Define ΣiEN Dp (Xf zi) as inf ΣvEN Dp (2t, where X is the set of Nash equilibrium. With a probability of at least and with Algorithm
log(T)ō, S e_
and under Assumption 3.1, we have EieN Dp (X Fy + S
O Ind log(T) nd B nBL adCp RVT VT + ndloogT)
aVT + dBLlog(T) BPVT + wBd (1/6)
RVT
is smin(ya.py
5.2 Individual Low Regret
Beyond the fast convergence Nash equilibrium, our algorithm also ensures each player has sublinear regret when playing against other players. The sublinear regret 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 { define the individual regret as the cumulative expected difference between the costs received and the cost of playing the hindsight optimal action.
That is, Σ E [c (ft, x c; (wi, ]. where {--; ;)== is a fixed sequence of actions of other players. The following theorem shows a guarantee of the individual regret of each player.
2d0374 #=
# = 0
Theorem 5.3. Take T/- =
& = E:7x
For a fixed Wi E X2 a fixed P 0,
1>0,"
[1
72
sequence of
(x (x- and with Algorithm have
+ GVT L + KO,)) fo ( (udTT3/Alo(() log(T))
11
Σ E (2), ca (W,, xid)=
pd pdVT + GVT
BBIYT + xxC,))
#> 0
where max Dp(a, S Cp-
Our result matches the VT regret bound for strongly monotone games (Lin et al., 2021), but applies to monotone games well.
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 joint action is defined SW(x) CiEN We let OPT min, (W: to denote the optimal social welfare.
Definition 5.1 (Roughgarden 2015; Syrgkanis et al. 2015). Fix Ci > 0, C2 L. game is (Ci, C2 -smoohh if there exists a strategy x', such that for any x E Iliex Xr Ci (I( G OPT + C2 (2(
The following proposition confirms that the social welfare converges to optimum on average.
Proposition 5.1. With тi: 2 8; 717., and suppose every player employ Algorithm 1, we have audlng(T)
+ IT [(S(())) O OGT (1-CA)TI + JaB Inn for a (C1, C2)-smooth game.
(I-C.JTV
5.3 Special Case: Linear Cost Function
When c; is linear, there does not exist a p that is convex while making c; - kp strictly convex. Algorithm I therefore does not apply the linear case. This coincides with our intuition that the landscape e; 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 as 2
argmin {T7 (Z., Øt) + T (t + 1) (z,, x!) + Du(
(4)
2,EX,
The idea is to first show the convergence of I. to a game with the cost (x(x) + Tp(x). With this regularized game, we choose p to be a strongly convex function and measure convergence in terms of the gap function (c. (z), 24 x²). By carefully controlling T, we obtain the following result.

---

Theorem 5.4. With linear C₁, Vi [m], T
1 T
Gp
2dve'
sup,
/Vp(t)l and Algorithm I, BG G
we
have
E
(iic (x")
T - m;
S
δ
ABLABL+G)
(dnC,(BL+G)
T176
VETV
VuI
Similar regularization techniques have been used in the analysis the zero-sum game (Cen et al., 2021; Cai al., 2023). Our result matches the last-iterate convergence for zero-sum matrix game (Cai et al., 2023), 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 convex and compact action sets (while previous works only apply to simplex action set). remains open how games with linear cost functions could be effectively learned and whether the convergence could be improved.
6 Application to Time-varying Game
In this section, we further apply Algorithm to games that evolve over time. A time- game G. is a game where the cost function (-). i N depends on t. The game G. is not revealed to the players before choosing their actions We assume that G. 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 dime-dependent values change, such as channel gains. While the changes of G can be random, we discuss two cases here, 1) when Go converges to static game G in (TT) time, and 2) when the variation path of some Nash equilibrium, Ei= || ++ I f.* is bounded in oTT).
Converging monotone game. Let G. denote the game formed by the costs {c) and G be the game formed by the costs {es (-)) Suppose Go converges G, and let X" be the set of Nash equilibrium of the game G. The cost function ej converges to some cost function e in o(T)) time, The following theorem shows the last iterate convergence to x².
Theorem 6.1. With Et= EieN max, (1) vic((z)l22 = T", take 2d1374 6, 2:7 Define EIEN Dp (27, 3i) as inx ΣIEN (ī,, vi), where X is the set of Nash equilibrium of game G. Under Algorithm and under Assumption 3.1, we have E 1EEEN D, (X) xt
ndv log(T)
MCAB T374
RAL
ndC, T474
(Tg V log(T)
RT174
WVT
KT774
KT
7174
For monotone games, Duvocelle al. (2023) showed asymptotic last-iterate convergence rate. To the best of our knowledge, Theorem 6. is the first last-iterate convergence rate for the class of converging monotone game.
Evolving game and equilibrium tracking. We now discuss the case where G, does not necessarily converge to game G, but the cumulative changes of some equilibrium are bounded. We use the variation path Vi(T)) Eieny |x) | x. to track the cumulative changes of equilibrium. In this setting, the last-iterate convergence is not applicable, and the convergence is measured in terms of the average gap. Because of this, the algorithm is slightly modified and updates with 1--1 argmin {me (f,,9)) + (a),
Theorem 6.2. Assume Vi(T) S TP, E [0, Take = zd . 8,
137. Under
Algorithm and under Assumption 3.1, we have + ET EieN (Vict (5t,
-x
ò and+ 3 4
20--)
In the case of a strongly monotone game, Duvocelle et al. (2023) gave result of T and Yan et al. (2023) gave result of Tw/3-2// In comparison, Theorem 6.2 extends the study to monotone games, and improves the result to O (max (T20/3-2/2 2/3 (/) //2--3) }).

---

Cource competition
7wm--um mariss game
contar minima game
30
satrattc gred
60 with estenated gradect
Oun
with posket
4.50
4.25
Dax
00 wit coimitegrreon
with grader.
4.00
3.75
30-
2.00
1.75
1.50
300
22
50
150
175
43
00
382
Teantrys
Figure 1: Experiment on Cournot competition, zero-sum two-player minimax game, and convex-concave game. In Cournot competition, the curves of OMD and GD overlap with each other.
7 Experiment
In this section, we provide a numerical evaluation of our proposed algorithm in three static games. We repeat each experiment with 50 different random seeds. We ran all experiments with a 10-core CPU, with GB memory. We set 1)t V and 6, = 0.001 for our algorithm.
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, players compete with constant marginal costs, each having individual constant price intercepts and slopes. We model the game with 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]. We have included results of other choices of intercepts and slopes in the appendix.
Zero-sum matrix game. In this zero-sum matrix game, the two players aim to solve the bilinear problem min, max, T Ay. We set this matrix A to be [[1,2], [3, 4J]. We have included results of other choices of A in the appendix.
Monotone zero-sum matrix game. In this monotone version of the zero-sum matrix game, we regularize the game by the regularizer x² y²
Algorithm 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 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. This demonstrates the fast convergence of our algorithm as suggested by the theoretical results. We also compare our algorithm to gradient descent with an estimated gradient, using the same ellipsoidal gradient estimator, for fairer comparison. Our algorithms are shown to be more robust to partial information (bandit feedback), which again validates our theoretically fast convergence results. All the codes can be found at https :// /gggtttt.../.. com/ htw.tu/.ooo//iggogoo//ooooooenoo wraploongg//moooottengggaoaa
Conclusion
In this work, we present a mirror-descent-baased algorithm that converges in O(T41/4) in general monotone and smooth games under bandit feedback and strongly uncoupled dynamics. Our algo- rithm is no-regret, and the result can be improved to (T21 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 ((T4//4) for converging games and the improved result of O (max (T24/332/3 T(4++5) /722-/98)))))))))))))))))))))))) 998) for equilibrium tracking. We further verify the effective- ness of our algorithm with empirical evaluations.
10

---

Acknowledgement
Baoxiang Wang and Jing Dong are partially supported by the National Natural Science Foundation of China (72394361) and the Vector Institute (Visiting Researcher program and Internships Program). YY gratefully acknowledges NSERC and CIFAR for funding support.
References
Abernethy, J., Hazan, E., and Rakhlin, A. (2008). Competing in the dark: An efficient algorithm for bandit linear optimization. In Conference Learning Theory.
Bartlett, P., Dani, V., Hayes, T., Kakade, S., Rakhlin, A., and Tewari, A. (2008). High-probability regret bounds for bandit online linear optimization. In Conference on Learning Theory.
Bauschke, H. H., Bolte, J., and Teboulle, M. (2017). A descent lemma beyond Lipschitz gradient contimuity: First-order methods revisited and applications. Mathematics of Operations Research, 42(2):330-348.
Bervoets, S., Bravo, M., and Faure, M. (2020). Learning with minimal information in continuous games. Theoretical Economics, 15(44:1471-1508
Bravo, M., Leslie, D., and Mertikopoulos, P. (2018). Bandit learning in concave n-person games. Advances in Neural Information Processing Systems.
Bregman, L. and Fokin, I. (1987). Methods of determining equilibrium situations in zero-sum polymatrix games. Optimizatsia, 40(57):70-82.
Cai, Y., Luo, H., Wei, C.-Y., and Zheng, W. (2023). Uncoupled and convergent learning in two-player zero-sum markov games. arXiv preprint ar3.v:2303.027.8.
Cai, Y., Oikonomou, A., and Zheng, W. (2022). Finite-time last-iterate convergence for learning in multi-played games. Advances in Neural Information Processing Systems.
Cai, Y. and Zheng, W. (2023). Doubly optimal no-regret learning in monotone games. In International Conference on Machine Learning.
Cen, S., Wei, Y., and Chi, Y. (2021), Fast policy extragradient methods for competitive games with entropy regularization. Advances Neural Information Processing Systems.
Chen, P.-A. and Lu, C.-J. (2016). Generalized mirror descents in congestion games. Artificial Intelligence, 241:217-243.
Daskalakis, C., Deckelbaum, A., and Kim, A. (2011). Near-optimal no-regret algorithms for zero-sum games. In Symposium on Discrete Algorithms.
Debreu, G. (1952). A social equilibrium existence theorem. Proceedings of the National Academy of Sciences, 38(10):886-8)) 893.
Drusvyatskiy, D., Fazel, M., and Ratliff, J. (2022). Improved rates for derivative free gradient play in strongly monotone games. Conference on Decision and Control. IEEE.
Duvocelle, B., Mertikopoulos, P., Staudigl, M., and Vermeulen, D. (2023). Multiagent online learning in time- varying games. Mathematics of Operations Research, 48(2):914-94)
Even-Dar, E., Mansour, Y., and Nadav, U. (2009). the convergence of regret minimization dynamics in concave games. In Symposium on Theory of computing.
Farina, G., Anagnostides, I., Luo, H., Lee, C.-W., Kroer, C., and Sandholm, T. (2022). Near-optimal no-regret learning dynamics for general convex games. Advances in Neural Information Processing Systems.
Hazan, E. and Levy, (2014). Bandit convex optimization: Towards tight bounds. Advances in
Neural Information Processing Systems.

---

Jordan, M. I., Lin, T., and Zhou, Z. (2023). Adaptive, doubly optimal no-regret learning in strongly monotone and exp-concave games with gradient feedback. arXiv:2310.14085.
Koller, D., Megiddo, N., and Von Stengel, B. (1996). Efficient computation equilibria for extensive two-person games. Games and Economic Behavior, 14(2)247-259.
Lee, Y. T. and Yue, M.-C. (2021). Universal barrier is n-self-concordant, Mathematics of Operations Research, 46(3): 129-1148.
Liang, T. and Stokes, J. (2019). Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks. In International Conference on Artificial Intelligence and Statistics, pages 907-915.
Lin, T., Zhou, Z., Ba, W., and Zhang, J. (2021). Doubly optimal no-regret online learning in strongly monotone games with bandit feedback. arXiv preprint arXiv:21 12.02856.
Mertikopoulos, P., Papadimitriou, C., and Piliouras, G. (2018). Cycles in adversarial regularized learning. In Proceedings of the twenty-ninth annual ACM-SIAM symposium discrete algorithms.
Mertikopoulos, P. and Zhou, Z. (2019). Learning in games with continuous action sets and unknown payoff functions. Mathematical Programming. 173:465-507.
Rosen, J. B. (1965). Existence and uniqueness of equilibrium points for concave n-person games. Econometrica: Journal of the Econometric Society, pages 520-534.
Roughgarden, T. (2015). Intrinsic robustness of the price of anarchy. Journal of the ACM (JACM). 1-45):1-42.
Roughgarden, T. and Schoppmann, F. (2015). Local smoothness and the price of anarchy in splittable congestion games. Journal of Economic Theory, 156:317-342.
Syrgkanis, V., Agarwal, A., Luo, H., and Schapire, R. E. (2015). Fast convergence regularized learning in games. Advances in Neural Information Processing Systems.
Tatarenko, T. and Kamgarpour, M. (2019). Learning nash equilibria in monotone games. In IEEE 58th Conference on Decision and Control (CDC). IEEE.
Tseng, P. (1995). On linear convergence of iterative methods for the variational inequality problem. Journal of Computational and Applied Mathematics, 60(1-2):337-25..
Yan, Y.-H., Zhao, P., and Zhou, Z.-H. (2023). Fast rates in time-narying strongly monotone games. In International Conference on Machine Learning. PMLR.
Zhou, Z.,, Mertikopoulos, P., Bambos, N., Boyd, S. P., and Glynn, P. W. (2020). On the convergence of mirror descent beyond stochastic convex programming. SIAM Journal on Optimization, 30( 1):687 716.
12

---

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

---

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

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [No]
Justification: We will provide open access the code and data upon acceptance of this paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co
conolicyy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / /ttpss.ccpppliiiiim wwtppccppcc////ccccccccccccccclt htppllc/ggiieee http//uudeeee/eeee https//ooSSSuuiiseeeeeeee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The experimental settings are described in the experiment settings in detail to reproduce the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Yes, all figures for the experiments are shown with shading the one standard deviation error.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
15

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
All computational resources used have been stated in the experiment section.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: hww.rpsu....///. cc. http/p/bbi//tticcccuiellllll
Answer: [Yes]
Justification:
have reviewed the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- cration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper is foundational and theoretical research without particular applica- tion or deployment.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
16

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper is theoretical with no such risk.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The experimental environment used in this paper is synthetic.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
17

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
The experiment environments have been described in detail in this paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
18

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
19


Reviews:
[{"review_id": "mSgeo6haNs", "reviewer": "Reviewer_X31B", "summary": "The paper considers monotone games in a setting where the players\noperate independently (uncoupled), and observe their costs/payoffs but\nnot the gradient of the cost function (bandit feedback). The class of\nmonotone games include convex-concave games, Cournot competition, and\nsplittable routing games.\n\nIn particular, they analyse the last-iterate distance to the Nash\nequilibrium of an algorithm based on mirror descent. Given that only\nbandit feedback is available, the algorithm uses an ellipsoidal\ngradient estimator.\n\nIn overall, they prove convergence O(1/T^1/2) for strongly monotone\ngames, O(1/T^1/4) for monotone games, and O(1/T^1/6) for linear games\n(results are also available for time-varying games). According to the\nauthors, this is the first last-iterate convergence results available\nfor monotone games. Previous results have either been asymptotic, or\nhave made stronger assumptions about the games.\n\nThere is also an experimental comparison between their algorithm and\nOMD and GD.", "questions": "To follow the analysis, it would be helpful if the paper provides a\nvery brief introduction to mirror descent.\n\nAlgorithm 1, line 4. You could state that z_i^t is sampled u.a.r. from\nthe d-Sphere, and before receiving the bandit feedback.\n\nAlgorithm 1, line 6. It would be useful with a comment about the\nhardness of solving the optimisation problem in Eq (1).\n\nAs far as I can see, there is a typo in the statement of Lemma\nJ.2. Instead of an identity, the result should be an upper bound. In\nparticular, the Holder inequality is stated as an equality. This\nchange would not have any impact on the overall result since Lemma J.2\nis always applied as an upper bound.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "In overall, this is a highly significant contribution that deserves to\nbe published.\n\nI must admit that the paper is outside my core area of expertise. I\nhave therefore not had the opportunity to read every proof in detail.\nHowever, I have some minor remarks below.\n\nThe experimental study is rather light touch, and only uses 5\ndifferent random seeds. The authors should consider more independent\nruns to take into account variance. It would also be interesting to\nsee how the behaviour of the algorithm scales with increasing\ndimension d (currently only very low dimensions are explored). The\nexperimental results should be discussed more in-depth and contrasted\nwith the theoretical results.", "was_revised": true, "final_justification": "Based on the discussions after the rebuttal and taking into my own comments regarding some weaknesses in the experimental evaluation, I felt that a score of 6 (flawless) was too high. I have therefore reduced the score to 5.", "rebuttal": "We thank the reviewer for the encouraging feedback. We're glad the contribution is viewed as significant. \nWe will revise the manuscript accordingly. Specifically, we will:\n\n1. Increase the number of random seeds and include experiments in higher dimensions to better assess variance and scalability.\n\n\n2. Expand the discussion of experimental results and relate them more clearly to the theoretical findings.\n\n\n3. Add a brief introduction to mirror descent for clarity.\n\n\n4. Clarify in Algorithm 1 that zitz_i^tzit​ is sampled uniformly at random from the ddd-sphere, before receiving feedback.\n\n\n5. Add a remark on the hardness of solving Eq. (1).\n\n\n6. Fix the typo in Lemma J.2 and restate it as an upper bound."}, {"review_id": "nk5KdaxKO6", "reviewer": "Reviewer_G5Qr", "summary": "The paper studies the problem of no-regret learning in general monotone problems under bandit feedback. The main result is a mirror descent-based algorithm that attains faster rates in strongly monotone and monotone problems. The results are also extended to time-varying problems, improving again over the existing rates. Experiments are also provided to support some of the theoretical findings.", "questions": "I have two main questions:\n\n- Can the authors explain the incongruity highlighted above related to monotone problems and zero-sum games? Is it the case that the result for monotone problems requires stronger assumptions? \n- Can the authors provide the precise statements for the theorems? The key assumptions were not clear even after reading the appendix.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "On the positive side, the paper studies a well-motivated and important problem. While there has been much work studying last-iterate convergence in games, most existing results apply under full feedback. This paper is part of a recent line of work that tries to extend those results to the bandit feedback setting. There are many challenges in extending those results to the bandit feedback setting. To my knowledge, the results reported by the paper provide significant improvements over the current state of the art. Given the significance of this problem, I believe this is a valuable contribution. The technical approach is also non-trivial and contains some interesting ideas. Although the main ideas appear to be known from prior work, I believe that the way those prior techniques are used in combination in this setting is new. Moreover, the writing overall is reasonable and the paper goes a good job at motivating the key ideas.\n\nOn the other hand, I have some concerns about the paper. First, there is a claim that I find very confusing. Table 1 claims that the rate obtained for zero-sum games is worse than general monotone problems. This doesn't make sense since (two-player) zero-sum games are monotone. The only way to reconcile this is that the main result for the monotone case requires further assumptions that are hidden. It is essential that the authors can address this confusion. Also, the statements of the theorems are not rigorous enough. They do not clearly state the main assumptions and most of the parameters that appear in the statements are not defined or specified in that context. I expect to see formal, self-contained statements.", "was_revised": true, "final_justification": "In my original review I was confused about a certain inconsistency in one of the main results of the paper. The authors were able to address that point in the rebuttal; even though Table 1 contained a really confusing claim, that issue can be easily corrected for the final version. Overall, I believe the result is significant enough for publication.", "rebuttal": "We thank the reviewer for the detailed and constructive comments. We hope the following clarify the reviewer's concern. \n\n### Regarding the confusion in Table 1\n\nWe agree that zero-sum games are a subclass of monotone problems, and we apologize for the lack of clarity. The linear zero-sum case does not require stronger assumptions. However, due to the flatness of the cost functions in this setting, our analysis framework requires special treatment. In particular, the Bregman divergence induced by the regularizer ppp becomes ill-defined, which prevents a direct comparison using that measure.\nInstead, our results for the linear zero-sum case are stated in terms of the standard gap function, $\\sum_i <\\nabla_i c(x_i), x_i - x_i^\\ast >$, which remains meaningful in this context. While this differs in form from the result in the general monotone setting, it is not weaker.\nWe will revise the presentation of Table 1 and the accompanying discussion to clarify this distinction. We will also provide formal, self-contained theorem statements in the main text, including all assumptions and parameter definitions.\n\n### Can the authors provide the precise statements for the theorems? The key assumptions were not clear even after reading the appendix.\n\nThe only parameters required in our main theorem are $\\eta_t$ and $\\delta_t$, both of which are stated explicitly in the theorem. We do not rely on any additional hidden assumptions; everything is captured by Assumption 3.1. To improve clarity, we will revise the theorem statement to directly reference Assumption 3.1 and ensure that all relevant parameters and conditions are clearly defined and self-contained."}, {"review_id": "hVxwxxg2xX", "reviewer": "Reviewer_KCuo", "summary": "This paper studies the problem of no-regret learning in smooth monotone games with bandit feedback, focusing on developing uncoupled algorithms with non-asymptotic last-iterate convergence rates. The main contribution of the paper is that they proposed a mirror descent-based no-regret online learning algorithm that achieves $O(T^{-1/4})$ last-iterate convergence rate with respect to a problem-dependent Bregman divergence between the iterate and the Nash equilibria. When the loss function is linear (i.e., in two-player zero-sum games), they propose another algorithm with a $O(T^{-1/6})$ last-iterate convergence rate. They also extend the results for time-varying monotone games and present convergence rate results under several bounded variation assumptions.", "questions": "1. Does the $O(T^{-1/4})$ convergence rates hold for the gap function or the total gap function? Or in other words, is the $T$-th iterate an  $O(T^{-1/4})$-approximate Nash equilibrium of the game?\n2. What is the requirement of choosing $p$ in Algorithm 1? In the current presentation, it seems that one can choose $p$ to be linear (as discussed in the weakness above), but then the guarantee on $D_p(x, x^*)$ becomes vacuous?", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strength: This paper tackles an important question on uncoupled learning in smooth monotone games with bandit feedback, for which existing results are limited to either strongly monotone games, zero-sum games, or only asymptotic convergence rates. \n\nWeakness: Although this paper studies an interesting and important question, several of its claims do not seem correct to me, which significantly undermines its contribution. In short, the main result of $O(T^{-1/4})$ last-iterate convergence rates does not hold for the gap function/other standard convergence measures, and the given guarantee could be vacuous. I think a major revision is need to address these issues. Detailed comments below.\n1. The claimed $O(T^{-1/4})$ last-iterate convergence rates for general smooth monotone games is not for standard convergence measures such as the gap function, the total gap function, the KL-divergence (or Euclidean distance) between the iterate and a Nash equilibrium. Instead, the proximity to a Nash equilibrium $x*$ is measured by $D_p(x^t, x^{*})$, where $p$ is a **game-dependent** convex function. Specifically, in lines 154-155, the function $p$ is chosen so that $c - \\kappa p$ is convex. This is problematic since if we choose $p$ to be a linear function (which is convex and bounded over a compact set), then the corresponding Bregman divergence $D_p(x, x')$ is zero for any two points, making the convergence rate vacuous. Line 193-195 says *\"when $c_i(x) = x^2$, $\\dots$, we can $\\dots$ take $p = x$\"*. For this choice of $p$, $D_p(x, x') = 0$ for any two points, and the guarantees in Theorems 5.1, 5.2, 6.1 are vacuous.\n2. Continuing on the last point, where the authors give an example where they choose $p = x$ to be a linear function. The sentence on Line 263 *\"when $c_i$ is linear, there does exist a $p$ that is convex while making $c_i - \\kappa p$ convex.\"* makes no sense since we can choose $p$ to be a linear function and the resulting function $c_i - \\kappa p$ is linear, thus convex. \n3. The choice of $p$ also gives rise to a minor concern on the uncoupledness of the algorithm. Typically, when the players are playing an unknown game, it is common to assume they know some (upper bounds of) game parameters, such as the smoothness. For example, as long as the agents know they are playing a $L$-smooth monotone game (the specific game instance remains unknown), they can choose their step size and achieve convergence in any $L$-smooth monotone game. But to implement Algorithm 1 in the paper, the agents must also agree on a function $p$ which depends on the unknown game instance, and the choice of $p$ must be different even in the class of $L$-smooth monotone games (and even if they know $L$). This issue affects the uncoupledness of the algorithm.", "was_revised": true, "final_justification": "I updated my rating to borderline accept, provided that the authors promise to update the current misleading claims (Table 1, abstract, and introduction) on the $T^{-1/4}$ convergence rate on monotone games. It should be made clear that it is a problem-dependent rate that holds for the problem-dependent Bregman divergence and does not imply bounds on the gap functions.", "rebuttal": "We thank the reviewer for their detailed and thoughtful comments. We appreciate the recognition of the importance of the problem we study and would like to clarify a few key points.\n\n### On the concern regarding the use of Bregman divergence and the possibility of vacuous bounds \n\nWe agree that if $p$ is chosen to be a linear function, the corresponding Bregman divergence becomes zero, and the bound would indeed be vacuous. However, this does not affect the validity of our result, $p$ is a design choice, and our framework allows for choosing $p$ to be sufficiently curved (i.e., not flat), ensuring the Bregman divergence is meaningful. We will clarify this point in the revision to avoid any misunderstanding.\n\n### On the issue of uncoupledness and agreement on $p$\nIt is not necessary for all players to agree on the same function $p$. Our result holds even when each player selects their own $p_i$, as long as the key assumption, namely, that $c_i−\\kappa pi$ is convex, is satisfied. In the case where all players use the same $p$, we can express convergence using the total Bregman divergence $\\sum_i D_p(x_i, x_i^\\ast)$. If players use different pip_ipi​, the result generalizes naturally to $\\sum_i D_{p_i} (x_i, x_i^\\ast)$. We assume that players take the same $p$ for a simpler presentation. \nWe will revise the manuscript to make these points more explicit and to address the valid concerns raised. Thank you again for the valuable feedback."}, {"review_id": "obLRqBeJKU", "reviewer": "Reviewer_8yuX", "summary": "The article presents a set of mirror descent algorithms for oblivious learners in continuous action monotone games. These learners only take actions and receive rewards - they do not receive gradient information or any information about actions or rewards of other players. The authors consider each of static games, converging games, and drifting games, giving state of the art convergence guarantees in each case, in terms of the last iterate convergence. A customary cursory experimental demonstration is provided.", "questions": "Lines 152-158, and Lines 193-195. Please provide some discussion at least flagging up the issue of how to choose p when learners are supposed to be quite oblivious. Ideally some realistice examples would be given where the reader could see how p could be chosen (I don't count c(x)=x^2).\n\nLine 155: “convex but not linear”. Do we just mean “strictly convex”? I’m concerned that a function c_i that is linear in part of the function space but strictly convex elsewhere might not admit a kappa and admissible p while staying convex.\n\nLines 160-168 repeat the conditions on h twice over.\n\nLine 174. Previous works have had to work to ensure the actually-played \\hat{x}_i^t are in the feasible set. I suspect that the ellipsoidal estimator, combined with the barrier function, does this automatically? Please can you just note this fact - it is not clear from what is presented in the article.\n\nAlgorithm 1, Inputs line. Have I missed something? There a constant kappa that has appeared out of nowhere. What is this and what effect does it have on anything?\n\nAlgorithm 1, line 4. This would read much more nicely if it started with \"sample z\", before then defining \\hat{x}, then receiving the feedback (ie the order in which it happens in the code).\n\nLine 207, and other similar theorem statements. The convergence is given in terms of the sum of the Bregman divergences with respect to the game-dependent, user-chosen p regularizer. In contrast, most results in the literature that are given with respect to Bregman divergences are with respect to a non-game-dependent regularizer such as the h in this article. Some discussion of this would be valuable.\n\nLine 214, the term \"a fixed point given\" is confusing - it could be interpreted that omega is a fixed point of the dynamic (which it is not). I think \"omega_i is any strategy\" would suffice?\n\nSection 5 generally. If mu = 0 it is far from clear to me that there is a unique Nash equilibrium. Yet your results implicitly assume there is. Please can you clarify or fix this.\n\nLine 228. “While it does not imply a bounded first term”. The first term in question is a Bregman divergence with respect to barrier regulariser h. The only way the first term could be “unbounded” for fixed \\omega is if \\omega was on the boundary. Since you want \\omega to be a Nash equilibrium, you ought to say when a Nash equilibrium is on the boundary, \\omega has to be carefully chosen. Boundary Nash are often distinguished in the literature but you make no mention of this.\n\nTheorems 5.2 and 5.3. kappa does not appear in these results as stated. It vanishes some way through the proofs. You need to decide if it should be dropped from Theorem 5.1, or included in these two theorems.\n\nLine 271. I think the only change to algorithm 1 is to replace kappa with tau. And now we specify tau. If I am correct, then this feels like a peculiar way to present it. Why not just specify that now you take kappa=1/T^{1/6} and carry on. Also, within this theorem, you do not specify what delta_t should be. And your results are in terms of G, whereas you have defined G_p in the first line of the statement.\n\nLines 295-297. These appear to claim both that Duvocelle provided a result and that you are the first to provide the same result. Please clarify.\n\nLine 300. By writing down x_i^{t,*} you once again assume a unique equilibrium at each time point. I don't believe conditions have been specified which ensure the uniques of the equilibrium. Please clarify.\n\nLine 303. The key innovation of the paper, the inclusion of the D_p regularizer, is now not included in the the mirror map. Is that deliberate? Please explain why omitting this is now the right thing to do.\n\np9, some better discussion of the results would be extremely helpful. In particular, are the plots showing what we would expect to see (i.e. what is the expected outcome of each of the competitor algorithms, and is this what we see). Is the higher initial variance from your algorithm to be expected? Is the non-convergence of GD with estimate expected? Being consistent with your color scheme across the plots would be really helpful too - green is GD with gradient on the outside plots, but GD with estimated gradient on the middle plot...\n\nLines 324 and 325 seem to contradict line 312?\n\nI have not read all of the proofs in great detail. They look to be about right, but there is a lot of algebra and a lot of repetition. They are not particularly nicely presented - the reader has to do a lot of their own work to follow from one line to the next. I did notice the following problems:\n\nLine 552: \"Similar to Theorem 5.1\" is a little too much of a leap for me. Theorem 5.1 starts by referring directly to Lemma J.1. Lemma J.1 is entirely based on fixed cost functions. I expect that if I were to replace the c's in Lemma J.1 with c_t's then the difference would be the B\\sum\\Delta^t term. But a reader should not have to work through the proof of Lemma J.1 to be confident that all the other terms (except the last 2) in Lemma J.1 are not dependent on c being fixed. I would have thought a Lemma J.1 in terms of possibly evolving cost functions, that could then be specialized by fixing them, would be more useful.\n\nLine 614. Lemma J.3 is for G-\\nabla p being monotone. But here you state (essentially) that G-p is monotone. I believe that, since p is strictly convex, the result may hold anyway. But as written the logic is incorrect I think. Note also that Lemma J.3 is not quite what is needed - it has a single term on the LHS whereas this result has a sum on the LHS (see also comments on Lemma J.3).\n\nLine 615. You should really offer some more help to the reader than “Therefore”. Perhaps “Summing  [Eqn no for line 613] and using [eqn no for line 614] to replace the third term on the right hand side, we can then drop the non-negative D_p(x,omega) term to get” or something. Of course, dropping out the D_p from the inequality in Line 614 (while explaining that you do so) would mean less going on here.\n\nLine 616. Technically, you are summing over t, not over T. There’s a lot going on here too – these three lines took me half an hour to work out! Some more help to the reader would be very valuable. Perhaps “Summing over T, cancelling both sum_{t,i} D_h and sum_{t,i} tD_p terms, and discarding the non-negative D_h(omega,x^{T+1}, we have”. You’re also missing an eta_1 multiplier on the second term of the RHS.\n\nLine 621, and Lemma J.6, need to be significantly clearer. In the lemma, pi is undefined, as is {\\cal X}_\\epsilon. Both need to be defined. Then Line 621 needs to justify why the claimed result is a consequence of the lemma. Using the same words as the lemma would help (i.e. I think that x_i^1 is a center and I think it is implicitly claiming that omega\\in {\\cal X}_{1-1/\\sqrt{T}}, but it is not clear how this fits together or why we have a bound of nu\\log(T).\n\nLine 622, last two sub-lines, you have sum eta_t terms outside of the sum over t, which I think should be inside.\n\nLine 629. I think, since f changes with both x_i^t and t you should probably include these as arguments?\n\nLines 630-631. This needs a lot more explanation. I don’t believe it has been stated that D_p or D_h are self-concordant barriers, so why does adding the linear term make f a self-concordant barrier?\n\nLine 632. This should be an inequality, not an equality.\n\nLine 634 there is a mistake. A_i^t is defined on p5 to be (\\nabla^2 f(x_i^t))^{-1/2}, but here it is taken to be (\\nabla^2 f(x_i^t))^{-1}. Additionally, the second line of the equations is, I think, never used?\n\nLine 635. You take x_i^{t+1} to be argmin f(x_i^t). But it should be argmin_{x_i} f_{x_i^t,t}(x_i) (i.e. the x_i^t and t are fixed arguments, whereas it’s the argument x_i of f that you maximise over). Also, there is a mistake here – the kappa term from algorithm 1 is not part of f, so this armin is not correct.\n\nLine 639. Is p a function from the combined action space X, or from individual action spaces X_i? The first line here implies the former, but the second the latter. There’s also, within the lemma, no obvious reason why the nabla_p (x) – nabla_p(x’) relates to a sum over i of different D_p(x_i,x_i’) terms. I would advise simply making the lemma more specific to the use case in the article.", "limitations": "The article should definitely discuss the limitations from needing to know the cost functions well enough to be able to select an appropriate p. Other than that, I think any limitations are well specified in the results.", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The article achieves better results than have yet been published, with a O(1/T^0.25) results in monotone games, improving to O(1/T^0.5) for strictly monotone games, with the obvious modifications for converging and drifting games. These are strong results, showing a high quality paper.\nThere is a lot squeezed in to one paper here. This is both a strength and a weakness. It means there is a lot of progress, but is quite difficult to follow all that is attempted to be presented, even for a somewhat expert reader (I have published closely related papers and currently supervise PhD students on this topic). Clarity is somewhat weak as a result.\nWhile the algorithm is somewhat standard, the key innovation which allows these new results is the introduction of the assumption in lines 152-158. Two different regularizers allows better control of the learning rates. However this also brings a weakness - it is far from clear how an oblivious learning could choose there p regularizer, since it depends quite strongly on the particular form of the game's cost functions.", "was_revised": true, "final_justification": "I think the work is nice. There is a weakness in that choosing p_i for an oblivious player is hard, and it's not obvious how to do it. There's also a weakness that the convergence result depends on the choice of p. The authors have committed to being explicit about this in the final article. So I think the article is good enough to publish, but the weaknesses ensure it is only a weak accept.", "rebuttal": "We thank the reviewer for the detailed and constructive comments. \n\n### General Acknowledgment on Proof Comments:\n\nWe sincerely thank the reviewer for their careful and detailed reading of the proofs. Their understanding is correct, and we very much value their comments and suggestions for improving the clarity and accessibility of the arguments. We will revise the manuscript to address all of the issues raised, including improving transitions between lines, clarifying technical assumptions (e.g., monotonicity and the structure of evolving cost functions), fixing notation inconsistencies, and expanding explanations where necessary to assist the reader in following the derivations.\n\n### On the uniqueness of the Nash equilibrium:\n\nWe appreciate the reviewer’s careful attention to this point. We do not assume the Nash equilibrium is unique. Our results, including Theorem 5.1, are stated to guarantee convergence to some Nash equilibrium, but not necessarily a specific one. When multiple equilibria exist, the algorithm may converge to any of them, and our current analysis does not control which one is selected. We will revise the manuscript to clarify this point explicitly and avoid any impression that uniqueness is assumed.\n\n### On the boundedness of the Bregman divergence and boundary Nash equilibria:\n\nWe thank the reviewer for the insightful comment. The reviewer is indeed correct; boundary equilibria are indeed often treated separately in the literature. However, we did not make any assumption that the equilibrium does not live on the boundary; we have to consider the unbounded cases. We will add a discussion of this in the revised manuscript.\n\n### Choosing p when learners are (partially) oblivious\n\nWe want to remark that our framework does not require full knowledge of the game or of other players’ objectives. The regularizer $p_i$ can be chosen individually (and differently) by each player based solely on their own cost structure. Our theorem and analysis are presented with the same $p$ only for a simpler presentation.  \n\n### Regarding realistic choices for $p_i$, a few examples include:\n\nFor objectives with known curvature, entropic or Mahalanobis-type regularizers (or quadratic forms adapted to the geometry of $c_i$) may also be suitable.\n\nEven if $c_i$ is not uniformly curved, one can often choose a $p_i$ such that $p_i$ has stronger curvature than $c_i$, ensuring $c_i - \\kappa p_i$ is convex for some $\\kappa$.\n\n\n### On the feasibility of $\\hat{x}_i^t$​:\n\nWe thank the reviewer for pointing this out. The reviewer is correct​, our construction ensures feasibility by design, and we will make this explicit in the updated manuscript.\n\n### On the relationship with Duvocelle’s results:\n\nWe thank the reviewer for pointing this out. We will revise the text to clarify the distinction. Duvocelle’s results apply to strongly monotone games, whereas our results hold for general monotone games. Our results therefore, do not overlap.\n\n### On the notation $x_i^{t,*}$ and uniqueness (line 300):\n\nWe thank the reviewer for the observation. To clarify, $x _i^{t,\\ast}​$ refers to one equilibrium point at time, and we do not assume uniqueness of the equilibrium. The analysis holds as long as $x_i^{t,\\ast}$​ is any Nash equilibrium, and our results do not require it to be unique. We will revise the notation and clarify this in the text.\n\n### On the omission of $D_p$​ from the mirror map in Line 303:\n\nYes, this is deliberate. The result in this section concerns the convergence of the average iterate result for equilibrium tracking, for which we do not need the additional regularization from $D_p$. The inclusion of $D_p$ is crucial for our last-iterate convergence results, but not necessary for average-iterate convergence. We will clarify this distinction in the revision.\n\n### Line 630-631 on self-concordant barrier with linear term:\n\nWe will revise the manuscript and note that $h(x)$ is a self-concordant barrier function. Therefore, we consider a function $f(x) = h(x) + \\langle a, x \\rangle$, it is still a self-concordant barrier function. This is because the third derivative of any linear function is zero, the addition of the linear term does not affect the third derivative of $f$. Since self-concordance is defined in terms of bounds on the third derivative relative to the second derivative, $f$ inherits the self-concordance of $h$.\n\n### Line 639, is $p$ defined on $\\mathcal{X}_i$ or $\\mathcal{X}$. \n\nIn our setup, $p$ is defined as a separable function over the combined action space $\\mathcal{X} = \\prod_{i \\in \\mathcal{N}} \\mathcal{X}i$, meaning $p(x) = \\sum{i \\in \\mathcal{N}} p_i(x_i)$, where each $p_i$ is defined on the individual player’s action space $\\mathcal{X}_i$.\n\nBecause of this separability, the gradient of $p$ decomposes as, $\\nabla p(x) = (\\nabla p_1(x_1), \\nabla p_2(x_2), \\ldots, \\nabla p_N(x_N))$, and the Bregman divergence with respect to $p$ satisfies  $D_p(x, x') = \\sum _{i \\in \\mathcal{N}} D _p (x_i, x'_i)$ . \n\nThus, the inner product difference involving $\\nabla p(x) - \\nabla p(x')$ naturally decomposes into a sum over the players’ individual spaces, which explains why the inequality $\\langle \\nabla p(x) - \\nabla p(x'), x' - x \\rangle \\leq - \\sum_{i \\in \\mathcal{N}} ( D_{p_i}(x_i, x'i) + D{p_i}(x'_i, x_i) )$ holds.\n\nWe hope that this addresses the reviewer's concerns and we welcome any further questions."}]

Author rebuttal:

Meta-review: This paper studies last-iterate convergence in monotone games with bandit feedback via mirror descent, achieving improved rates in several settings. Reviewers agree that the problem is important and interesting, though concerns arose about clarity of convergence measures and the algorithm's strong dependence on the knowledge of parameter $p$ of other players, and these are never clarified in the Introduction section and the comparison table. The authors promised to clarifying things in the revised version. After discussion, reviewers converged to borderline/weak accept, with no strong objections. Overall, the work is technically solid and merits acceptance pending the promised revisions.
Decision: Accept (poster)