The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
Authors: Côme Fiegel
Pierre Menard
Tadashi Kozuno
Michal Valko
Vianney Perchet
Venue: ICML 2025 poster (2025)
Keywords: Game theory
Bandit
Last-iterate convergence
Online learning
Primary area: general_machine_learning->online_learning_active_learning_and_bandits
TL;DR: We show that learning how to play a game is sometimes harder when using uncoupled algorithms.

Abstract: We study the problem of learning in zero-sum matrix games with repeated play and bandit feedback. 
Specifically, we focus on developing uncoupled algorithms that guarantee, without communication between players, convergence of the last-iterate to a Nash equilibrium. Although the non-bandit case has been studied extensively, this setting has only been explored recently, with a bound of $\mathcal{O}(T^{-1/8})$ on the exploitability gap. We show that, for uncoupled algorithms, guaranteeing convergence of the policy profiles to a Nash equilibrium is detrimental to the performances, with the best attainable rate being $\mathcal{O}(T^{-1/4})$ in contrast to the usual $\mathcal{O}(T^{-1/2})$ rate for convergence of the average iterates. We then propose two algorithms that achieve this optimal rate. The first algorithm leverages a straightforward tradeoff between exploration and exploitation, while the second employs a regularization technique based on a two-step mirror descent approach.

The Harder Path: Zero-Sum Games with Bandit Feedback
Last Iterate Convergence for Uncoupled Learning in
Côme Fiegel Pierre Menard Tadashi Kozuno Michal Valko
Vianney Perchet 126
Abstract
edly playing the game. Specifically, consider the bandit feedback setting, where the payoff matrix is unknown and players only observe their losses or rewards.
We study the problem of learning in zero-sum matrix games with repeated play and bandit feed- back. Specifically, we focus on developing uncou- pled algorithms that guarantee, without commu- nication between players, the convergence the last-iterate to a Nash equilibrium. Although the non-bandit case has been studied extensively, this setting has only been explored recently, with a bound of (T/)) on the exploitability gap. We show that, for uncoupled algorithms, guarantecing convergence of the policy profiles to a Nash equi- librium is detrimental to the performance, with the best attainable rate being (2T-1/44) in contrast to the usual 1/221//2) rate for convergence of the average iterates. We then propose two algorithms that achieve this optimal rate up to constant and logarithmic factors. The first algorithm leverages a straightforward trade-off between exploration and exploitation, while the second employs a reg- ularization technique based on a two-step mirror descent approach.
Within the context of uncoupled learning, each player learns the minimax policy independently, without communication or knowledge of their opponent's actions. This setup mo- tivates the use of methods similar to those employed in classical single-player online learning (Cesa-Bianchi & Lu- gosi, 2006), where player adapts to play optimally in an adversarially changing environment.
These methods usually bound the player's regret, defined as the difference between the best possible cumulative loss under fixed policy and the actual cumulative loss incurred by the player. They are known to be applicable in the con- text of games compute minimax policies (Cesa-Bianchi Bianchi & Lugosi, 2006). They however have two well-known weak- nesses:
The policies played over the iterations generally do not converge or even approach an equilibrium.
Instead, the average policy computed and outputted as proxy for convergence. While averaging tabular policies is simple and inexpensive, this step is not as simple for practical applications. For instance, it is not clear how to compute the average of policies rep- resented by a neural network (Heinrich et al., 2015; McAleer et al., 2022).
1. Introduction
In zero sum matrix games, two players each take a single action and accordingly receive for the first player a loss and the second player gain the same magnitude. Such games always admit for each player at least one minimax policy (a specific case of Nash equilibrium), assuming stochastic choice of action (v. Neumann, 1928). Computing these policies, however, is non-trivial and requires knowledge of the underlying game matrix of payoffs.
In part for this reason, significant portion of the recent literature studies methods with last-iterate convergence for which the actual policies played over time converge toward Nash equilibrium. Some algorithms, such as Optimistic Mirror Descent (OMD, Popov 1980; Rakhlin & Sridha- ran 2013), exhibit this convergence despite being initially proposed for their regret-bounding properties, but with a vastly different analysis. For the OMD algorithm, in the deterministic
We are interested in lcarning minimax policies by repeat-
'Equal contribution 'ENSAE Paris CREST, Palaiseau, France Innia FairPlay 'ENS Lyon, Lyon, France "OMRON SINIC X. Tokyo, Japan Steallhh AI Startup / Inria ENS "Criteo AI Lab, Paris, France. Correspondence to: Côme Fiegel <come.fiegel Coome.iceellnoomeeee normalesup.org>.
citimmiiitttifllll-fffoommee full-information feedback setting, the rate of convergence of the exploitabilty gap toward zero is even improved, transitioning from O(1/T) for the average to linear rate for the last iterate (Wei et al., 2021).
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
However, the literature on last-iterate convergence with stochastic feedback is limited, and even more so when con-

---

The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
sidering bandit feedback. While properties of the last-iterate convergence have been studied in the broader context of stochastic variational inequalities, these works often rely assumptions that are not applicable to matrix games, such as second-order sufficiency (Azizian et al., 2021), in addition to not accounting for the bandit feedback aspect.
the output of the underlying algorithm, which is here regret-based.
We also propose more practical algorithm, based on a strong regularization of the problem, which does not require the computation of average policy. It enjoys ((T-1/4) rate, thanks to the use of an un- biased estimate of the losses in contrast to previous approaches. However, even if the last iterate converges, the algorithm is not completely anytime as the regu- larization must be chosen with the knowledge of the horizon T. To address this limitation, a doubling trick approach is stated, which features the same exploration- exploitation trade-off.
Recently, some methods (Cai et al., 2023; Dong et al., 2024) were proposed for this specific problem. They however only obtained an upper bound of (T88 on the exploitability gap with high probability 1 Considering the best known lower bound was S2(T from a reduction to the K -arms bandit problem, Cai et al. (2023) raised the question of whether a better lower bound was achievable.
In this work, we address the following question: What
is the best attainable rate for last-iterate convergence of uncoupled learning with bandit feedback in matrix games?
The different rates are summarized in Table 1.
2. Contributions
3. Related works
We focus in the above settings on zero-sum matrix games.
Variational inequalities The problem of finding a Nash equilibrium for a matrix game can be formulated as find- ing the solution of a specific Lipschitz variational incqual- ity (Mancino & Stampacchia, 1972), which is furthermore monotone when the game is zero-sum.
We provide a better lower bound for the problem of learning a minimax profile with uncoupled convergent algorithms and bandit feedback. This lower bound, of Q(T=1/44 for the L convergence given p E [2, oo], shows that guaranteeing last-iterate convergence is harder than just guaranteeing convergence for the aver- age iterates, which can be done at a rate 1/22)
Finding algorithms for solving monotone variational in- equalities is a major part of the optimization literature, starting with the proximal point algorithm (Martinet, 1970; Tyreell, 1976). In particular, using two samples at each iteration, the Extra-Gradicnt method (Korpelevich, 1976; Nemirovski, 2004) has (1/TT) convergence for the aver- age iterate. With a strongly monotone operator, the rate is even linear (Facchinei & Pang, 2004) for the last iterate.
Intuitively, this relies on the fact that, at least for some simple 2 x 2 games, there exists a minimax policy for one player that renders all actions of the other player equivalent, thereby preventing any learning on their part. Meanwhile, policy converging to this minimax policy may not entirely prevent learning but will sig- nificantly slow it down, the difference between the two action rewards converges to zero
For stochastic variational inequality, in which only an unbi- ased estimate of the operator is observed, a rate (1/v/T) is obtained by Juditsky et al. (2011) for the average iterates. For strongly monotone operators, this rate can be improved to OL/TT) (Nemirovski et al., 2009).
This lower bound is also stated for p E (0,2), for which it improves to Q(T ((T-1)(++))
We propose general simple framework for transform- ing an algorithm with classical anytime guarantees into one with last-iterate guarantees, based on a simple exploration-exploitatio trade-off. We use this frame- work to show that the above lower bound is tight: with the EXP3-IX of Kocák et al. (2014), a ((T-1/(2+p) rate can be attained for the L convergence, given any p in (0, 2]. However, the computation of some aver- age policies is still needed, the framework relies
An important way generalize some of the aforementioned methods is through the mirror descent approach, which ex- tends Euclidean methods to other geometries, as discussed by Nemirovskif & IUdin (1983). This generalization is par- ticularly crucial when dealing with bandit feedback, with the EXP3 algorithm, introduced by Auer et al. (2002), serving as key example of this approach under the Kullback-Leibler geometry.
Instead of relying on two samples at each iteration as in the Extra-gradien method, the Optimistic Mirror Descent re- uses the previous one as an estimate. While it can be traced back to Popov (1980), it has regained interest relatively recently (Chiang et al., 2012; Rakhlin Sridharan, 2013).
'Dong et al. (2024) obtained a rate 1/44) on the Kullback- Leibler divergence between the profile and the Nash equilibrium, which only translates in general into a rate (T-1/88 for the exploitability gap
2

---

The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
Algorithm
Convergence
Rate
Cai et al. 2023 (Algoritmm 1)
High probability
Ö 1/8)
I?
O(T-116)
Dong et 2024 (Algorithm 1)
High probubility
((T-1/8)
Simultaneous Explore Exploit (this puper)
L', L. (0,2)
O(T-1/(247)
Uncoupled Regularized EXP3 (this paper)
L2
0(4-1/44
Lower bound (this paper)
L LP. p E (0, 2]
O(T-1/(2+p)
Table 1. Rate of convergence of the exploitability gap of algorithms with last-iterate guarantees under bandit feedback. The notation δ hides logarithmic dependences in T, and in ō for algorithms that converges with probability least 1 6.
Learning in games In the case of a deterministic feed- back, classical regret-bounding algorithms can be shown to enjoy ((1/VT) rate for the average iterates. Optimistic mirror descent in particular improves this rate to (1/TT) (Rakhlin & Sridharan, 2013; Kangarshahi et al., 2018). Us- constant, the rate can even be shown to be linear (Tseng, 1995; Wei et al., 2021) for the last iterate. However, Cai et al. (2024) recently proved that for some algorithms, including OMD, obtaining a (1/TT) rate for the last iterate without this problem-dependent con- stant is impossible.
max- max-player wants to maximize it.
The two players allowed play stochas- tically: they choose two mixed policies Aa == {er ((a=)((a== = and v E AB ==
ing a problem-dependent
{ Ehn u(b) = 1] and optimize their choice according
to the expected loss L(p, v) defined by:
L( v) = Eargato [L b)]
A tuple (u, E Aa x An of policies will be called a profile
This work focuses on learning a minimax strategy with ban- dit feedback using uncoupled algorithms. In the context of smooth monotone games, several recent studies, build- ing on the foundational work of Bravo al. (2018), have explored a setting where only the value associated with the chosen policy profile is observed (Hsieh al., 2019; Drusvyatskiy al., 2022; Tatarenko & Kamgarpour, 2022; Huang& & Hu, 2024; Ba et al., 2025). However, this approach does not account for the inherent stochasticity present in the K-arms bandit problem: particularly in matrix games, this observed value represents the average of the rewards un- der the policies, rather than the reward of single sampled action profile.
We look to obtain minimax profile (a special case of the later Nash-equilibrium, Nash Jr 1950), defined as profile (μ² v²) that satisfies
14 E arrg min L(u .²) and V" E arg max L(x"; vt), ulEAr
v'EAg
whose existence is guaranteed (v. Neumann, 1928).
The proximity of profile (μ, v) to the set of Nash equilibria can be characterized using the exploitability gap:
EG v) = min L(ye, u)
max L(u, vt)
wIEDA
vtEAB
Note that the exploitability gap is zero if and only if (μ, v) is Nash equilibrium.
Meanwhile, Abe et al. (2023) considered a stochastic feed- back, but without the specific bandit aspect. Muthukumar et al. (2020) showed an impossibility result that some of the algorithms with no-regret guarantees cannot converge almost surely to Nash equilibrium.
Sequential learning with bandit feedback We assume that at each iteration I, both players select some policies j²' and v², sample two actions a' ~ nu and b' ~ v', and get stochastic loss l E [0, 1] associated to these two moves. Formally, we assume the existence, for each a E A and b B, of probability distribution p(a, b) on [0, 1] such that
In our setting, Cai al. (2023) recently showed that O(T- 1/5) rate can be attained, result later extended by Dong et al. (2024) to smooth monotone games.
MEN, , p(a', ,1)) and Ee-p(a,t [6] = L(a,
4. Setting
Zero-sum matrix game Two players, called the min- and
where F= =FF)) is a filtration recursively defined by the observations,
the max-player, respectively play actions A and 6 B, in sets of cardinality A and B, to receive a loss L(a, b) E
[0, 1]: the min- min-player wants to minimize this loss, while the
F'= a (w.a be, e.,,e...',,, a.....'''''
3

---

The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
with w the internal randomness (extra to the sampling of actions) of both players.
5. Lower bound
In this section, we establish that these assumptions com- bined are quite restrictive. Especially, we show it is impos- sible to guarantee a better rate than @(T-1/(2tP) for the L last-iterate convergence with p E (0,
This filtration summarizes all information available to both players up to the beginning of round + 1. A sequence of profile (j²,, YeN will especially be called a learning sequence if it predictable with respect to F.
For this purpose, we will consider the following 2 games, for any E E [- 1-1/12, 1/12|:
Last-iterate convergence We define, for all >> O the F-norm| II-Ilp (Banach, 1932) for some real random variable
BB22/3 - E)
BB133 + e)
M =
X by
B(133)
B(2/3)
| 1p = [I
where B denotes a Bernoulli distribution.
For these games, regardless of the choice of in the domain, it is easily shown that
Now, let f= (fN) be a positive sequence decreasing to 0. A learning sequence (j²', v²) will satisfy Lt last-iterate convergence of rate f' if
1/2 1/2
vt E N. |[ ,'I,, S
is the only min- max max player policy, with an associated value of 1/2. Furthermore, the exploitability gap of any profile (u*, u²) is least proportional to the distance |8*] between 2' and v², with 8 = =1 1/2.
It is asymptotic if there simply exists some To N such that
N To, |E,G(( S S
On the contrary, the min-max min-player policy depends on the choice of s, as there exists no policy for the min-player policy that is good regardless of this choice. Especially, the exploitability gap of any profile (H, can be shown to be at least proportional to |e| for one of the two games M-5 and M...
This requires both players to play policies they deem near- optimal during each iteration, instead of simply outputting one good policy each at the end of the procedure.
We therefore assume that the game matrix is either M or M but that the exact choice is unknown. At each iteration L, conditioning on F(-1, the law of the reward vector (i.e. the law of the rewards for each action) for the min- min-player is given by:
Output convergence On the other end, an algorithm has an L" output convergence of rate g. with = (g" )eN a sequence decreasing to 0, if it can output learning sequence (fi i²) such that:
Vt E N. |EG(i, DI),, 06
B 81/2+ 28'=)
with M
(1/2 (
This restriction is weaker than the previous last-iterate con- vergence, it does not put any constraint the actual policies played at each round. It however still forces the algorithm to have anytime guarantees.
1 (1/2+
with M
B B1/2-
where we re-used the value 5 characterizing the difference between of and the min-max policy v*.
Uncoupled algorithm We say an algorithm is uncoupled if it independently controls the two players, without active communication between the two instances. In particular, we assume that observation of the opponent's ss action is not possible.
Guaranteeing an exploitability gap in o(E) at any horizon T implies the min-player can discriminate between these two options. Using some additive properties of the Kullback- Leibler divergence, we know that, without the observation of the max-player actions (b')eN, this discrimination is only possible with an arbitrarily high probability when:
This definition a bit informal as completely characterizing the impossibility of communication is hard mathematically. Indeed, even if direct communication is forbidden, the two instances are not isolated as the loss of one player still depends on the actions of the other. Nothing technically prevents one player from passing bits of information to the other through artificial choices of policies.
Σ (1) 2(1).
Given full control of 8 over the iterations, the ideal choice would be 8 = +1/2, which gives the usual lower bound

---

The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
Je| 2 (/T-1/2). However, the last-iterate convergence assumption implies that 5c must also converge to O. De- pending on how strong this convergence of 8 must be, the minimum value of |=| that allows the discrimination greatly
Algorithm 1 Simultaneous Explore or Exploit
1: Input: Algorithm A with L output convergence
Sequence (p') E [0,,1]
2: Initialize: ko <-
increases.
Draw u ~~ [[) 1]) common to both players
3: Algorithm: For ( = 1 to +00:
This idea is formalized in the following theorem, proven in Appendix A.
k²
p' + u
If k2
Theorem 5.1. Assume that the sampled action b' ~ v of the max-player at each iteration I. is never observed. Then, for any p E (0, 2]. no learning sequence can achieve simultaneously for all 2 x matrix games described above an LP last iterate convergence of
Play current profile (u u²') and update algo-
rithm A
Otherwise:
Play the output (i 84
4: Output: Learning sequence of policies with L last- iterate convergence
118
even asymptotically.
Remark 5.2. As mentioned in Section 4, the uncoupling of the two instances is hard to formalize mathematically. In the above theorem, this formalization is done through the assumption that the max player's sampled action is never observed. As the max-player already knows its optimal policy v* and consequently does not need this knowledge for learning, we consider this assumption to be reasonable.
vergence. Indeed, the anytime version of EXP3-IX (Kocák et al., 2014; Neu, 2015) achieves rate of ((111/2) for the average profile with high probability, which can be trans- lated into the same rate for the L output convergence for any p > O.
While these two ways of converging are not equivalent, there is a procedure that transforms any algorithm A with L output convergence guarantees into one with L last- iterate convergence, at price of worse rate. The idea is simple: at each iteration, either both players "explore" by playing one iteration of A and updating accordingly, or "exploit" by both playing the current estimate.
Furthermore, this assumption of not observing the oppo- nent's moves is important for the rate. Indeed, the obser- vation of these moves would allow the estimation of each entry of the game matrix at rate Ö (t-1/2), assuming that each action is played for non- non-negligible proportion of the iterations. With this estimated game matrix, asymptotically playing the associated minimax profile would lead to the same O (1-1/2) rate for the exploitability gap.
If the probabilities (p') (eT) of exploring at each iterations satisfy:
+o0
The p > 2 case: Theorem 5.1 only deals with p E (0,2). 2). For E (2, 2o], using 1- < 11-112 for any random variable (Rudin, 2006), we immediately get the following corollary. Corollary 5.3. Under the same assumption as Theorem 5.1, for any p E (2, oo), no learning sequence can achieve si- multaneously for all 2 2 matrix games described above an L last iterate convergence of
lim p' = and 7
Σ p' = t=1
the resulting learning sequence has last-iterate convergence. Indeed, the first condition makes the exploration contri- bution to the exploitability gap negligible asymptotically, while the second ensures that the outputs of A converge to some minimax policies.
1
t
The players need be synchronized in their choices of exploration and exploitation steps. This can be done by sharing a single seed u ~ 2([0, 11) as shown in Lemma B.1 of the appendix.
236
even asymptotically.
The next section shows that the lower bound cannot be improved in rate for p E (0, 2). as it is tight up to some constant and logarithmic factors. We conjecture that, despite the above loose bounding, it also cannot be improved for p E (2, oo).
The procedure is summarized in Algorithm 1. The follow- ing lemma, proven in Appendix B. formalizes the above intuition, given some rate for the output of algorithm A.
Lemma 6.1. Assume that A satisfies an ousput convergence of rate g. Then Algorithm 1 satisfies an LP last iterate convergence of rate f defined by
6. Exploration-Exppoitttoo trade-off
The above theorem shows that for uncoupled algorithms, LP Past-iterate convergence is strictly harder than output con-
r²= 2: [(0)}} 1/2 + [
5

---

A higher r allows for faster convergence but at the price of slightly different Nash-equilibrium (u*T, .**)). This im- plies trade-off, as the exploitability gap of this regularized The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
where r² = EE p*]
theoretically prevents the convergence the minimax pol- icy, even in average (Kozuno et al., 2021). A simple way to counteract this issue is to use IX estimation (Neu, 2015) and add an additive term 7 to the denominator, but this biases the estimation and potentially worsens the rate. The- orem 7.2 shows that this bias is not necessary, at least for the L convergence.
We obtain the following theorem with the anytime version of EXP3-IX and the appropriate parameters.
Theorem 6.2. Using Algorithm with probabilities p' t-p/(2+0), and as A. the algorithm EXP3-IX with param- eters V'min 2 min / //og((A) (At) for the min-player and vimax mmxx = /ogg( B) (Bt) for the max-player, we obtain an L last-iterate convergence rate of
Regularization Given T > O, we define the regularized zero-sum game L over A X Ag with
/ 1 ste log + ()++1))/))
I. (), = E, [T,a, b)] + 7 (KLL(u, - DDKL 20)
This approach thus reaches the optimal rate (((TT)) men- tioned above for the L convergence, up to some logarithmic and constant factors. However, it has several drawbacks that make it not applicable in real settings:
where DKL is the Kullback-Leibler divergence between two distributions and (m", an arbitrary profile. This game admits a unique Nash equilibrium, which will be denoted by (n*T, vT)).
No communication is required, but the players are not truly uncoupled in the usual sense as they still need to share a common seed (a sample from a uniform law at the beginning of the game). Note that this does not go against the hypothesis of Theorem 5.1, as this seed can be the random variable w of the filtration F.
Similarly to the regularization of a convex function in or- der to make it strongly convex, the point of this transfor- mation is to transform the monotone pseudo-gradien op- erator F : A x AB + RA-B defined by F(2, v) := (V v), - VoLlu,, vi) into a strongly monotone opera- tor FT (v,
(T,LT v), V (u, which satis- fies, for all (1, (4',1/) E A x AB:
The exploitation steps are only performed to respect the anytime guarantees and have no practical use.
(F (p. F (4', w/), (p 1 v))
One of the main points of the last-iterate convergence is to avoid the computation of the average necessary in the regret-based algorithm. Not only is this com- putation still required here (the output of EXP3-IX is average), but also needs to be done at almost every iteration.
2T T
(IR =
r M'lli + || 11)
Nash equilibrium for the base game can be shown to be at most proportional to r.
7. Regularized mirror descent
Regularized updates Given T > 0, a common way of up- dating is to do a mirror-descent with the regularized pseudo- gradient FT, which for example used by in this setting Cai al. (2023). We instead use the following updates:
Because of these drawbacks, we propose another algorithm instead based on some regularized dynamics for the conver- gence.
Loss estimation As explained in the settings, at each iter- ation f, the mean loss vectors L(- v²) and I(n(.-) -) for respectively the min and max players are not observed, only one sample e is observed by both players. It can however be estimated through the importance sampling estimators:
D¹ arg min(1 - TT/ DDx (u, (() + TT/ (H, Mc AcAs
3A = arg min(1 - Tiy')DKL (v. (t + Tn D (v.
MEAB
Ee [(==o')
T144 arg arg min (emin: 11) + DKI
ge
min
(aaa))
HEAA
1- Ee
T,411 arg arg min (( +DLLUUV')
je
(10)) [(b=b))
HEAB
While these estimators are unbiased, their variance is not bounded as the probabilities associated to any action can become arbitrarily small. For this reason, their use alone
This method is similar to the one proposed by Munos et al. (2023), but is here able to deal with non non- -ommmemetiic games and bandit feedback. works two steps. First, the two
6

---

The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
Algorithm 2 Uncoupled Regularized EXP3
The following theorem, proven in Appendix C, formalizes this idea and provides guarantees for the final output of Algorithm 2.
1: Input: Learning rates n/' > 0
Regularization parameter r > 0
2: Algorithm: Initialize 1²11 and y*11 to the uniform poli- cies 1r and vº.
Theorem 7.2. Ler T be a fixed horizon. Then, using regular- ization T ((A + B) /T) / (log( A) log( log(B)) and the learning rates n/ = 2/(((t + 1)) for all t, Algorithm 2 guarantees
Fort = 1 to +00:
1e' - arg Ne (1 Tnn" Yon''DRI (p, 12:))
Tnj PKu(H,,p))
u² ( arg ves DKk (K, (2.) Tn' DKL ())
A + B T
1/4
| ,l)2 S 3v2
/log(AB)
Sample and play at ~ ut, B ue
Observe ft
With the conrect choice of regularization, Algorithm 2 there- fore benefits from an optimal I,2 rate of ((T-1/4) for the final output. However, as explained above, this choice of regularization depends on the horizon T, and the above rate is thus only guaranteed near the final output. The actual last-iterate guarantee of the whole sequence up to T is given by
1r t arg MEA, n (Pmm::)) H4
+ (KL 12)
DTTHl t arg min of ( (maxxs)
(
where ft w²(at) [at) and l
ex
v*(bt) ((0e)
1-2²
3: Output: Learning sequence (u', ,v²).
1, T1/
TT/ 11/2
fx min
policies are regularized proportionally the learning rate. This gives the two policies uí and v' that are used to sample E. Then regular mirror step update (with the Kullback- Leibler divergence) is applied with the unbiased estimate of the loss. The whole procedure is summarized in Algo- rithm 2.
which technically does not match the lower bound of Theo- rem 5.1. Remark 7.3. An intuitive way of fixing this issue would be to use an adaptive regularization parameter 7² x /-1/1 that decreases over time. Unfortunately, we failed to show the convergence of this method. The main reason is that, while the regularized solution can be shown to converge to the minimax profile minimizing the entropy as r goes to 0, the convergence is sometimes too slow when one of the two minimax policies is on the border of the simplex. This can be interpreted through the perspectives of Azizian et al. (2021): the Legendre exponent of the entropy is different on the border.
These updates allow a relatively simple bound on the Kullback-Leiblrr divergence between the intermediate pro- files (A77 (Tie) and the regularized Nash equilibrium, proven in Appendix C.
Lemma 7.1. Let T E 10. Taking of = 2/ (T(t + 1)) along with p= = nh and vT.1 = vd the uniform policies gives with the above updates
2(A+ B) E [DKe(m ((ttt + " s 721
8. Doubling trick and regularization
for all t E.
In order to get the anytime guarantees required for Algo- rithm 2, the usual solution in the online learning literature is the doubling trick. It consists in starting the algorithm with a small horizon Ti, and recursively restarting it every time the horizon is reached with new horizon T; 27;-1- However, its use is not straightforward for this problem, as a complete restart of the algorithm would go directly against the last-iterate convergence assumption.
To our knowledge, this is the first result of a ((1((rTT) rate for the Billback-Leibler divergence between the regu- larized solution of game and the iterates under the bandit setting for matrix game. This improves the rate (1/rv/t obtained by Dong et al. (2024), although this latter result was obtained with high probability (and not only in expec- tation), in addition of holding for any r-strongly monotone operator.
For this reason, we propose to use the doubling trick with slight adjustment. Instead of directly restarting with a weaker regularization and discarding the current iterate after every subloop i, the meta meta-procedee procedure will perform a trade-off between playing the old instance i - 1, which has already been played over many iterations, and the new instance i, which has better asymptotical guarantees. Specifically, it will play the new instance with a certain probability p/. close to O at the beginning and increasing to over the iteration
Using Pinsker inequality (Pinsker, 1964), this results in (T/(TVT)) bound for the 1-norm between (nT wiit) and (H***, n ). Considering that the gap between L", for which (1**, ,T***) is optimal, and that L is at most propor- tional to 7, the best value of T for the trade-off seems to be obtained when 7 x 1/(rVT) where x denotes asymp- totic equivalence up to a constant. This corresponds to T-111
7

---

The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
j of subloop i as the new instance gets played more and obtains better guarantees.
Algorithm 3 Doubling trick approach
Input:
Algorithmss Au: A2, ...
This meta meta-procedure is summarized in Algorithm 3. As in Algorithm 1, the two players need to be synchronized in their choice between the old and the new instances, hence the same seed is sampled for both at the initialization.
Horizons Ti, T2..... E N
Parameters S1, S2 ... E R>
2: Initialize: Draw N ~ [ 1J) common to both players
3: Algorithm: For i = to +oo:
The following theorem gives the rate of this meta- proceerree Theorem 8.1. Using Algorithm 3 with, for each A., the algorithms and parameterization of Theorem 7.2, along with Ti = 32(12)) and S; = =8(2",, we obtain the bound
For j = 1 to T;:
p. - min (1. e
7:
+ m
If k
(A+B) B 1/1
Play one iteration of A,
|EG 12)1 S 30
Vlo((AB) log(t)
Otherwise:
Play one iteration of A;-1
for any total number of iterations t T1 +
... + Ti-1 + j.
4: Output: Learning sequence of policies with L last-
The proof is given in Appendix C, and relies on a careful choice of the probabilities yl at each loop i to compensate for the imperfect anytime guarantees of Algorithm 2. More precisely, this probability pi must be inversely proportional to the squared exploitability gap of the new iterates. This squared exploitability gap is roughly given by the Kullback- Leibler divergence between the iterates and the new regular- ized solution, whose inverse is proportional to the number of iterations from Lemma 7.1. This justifies an exponential increase up to I, after which the procedure can be safely restarted.
iterate convergence
This article opens the following research directions:
Extensive-form games: These results could be extended to the more general setting of extensive-form games (Kuhn, 1953), in which the players take multiple successive actions without complete knowledge of the current game state. The two approaches proposed in this article could be adapted in a relatively straight-forward way (using IXOMD (Kozuno et al., 2021) as algorithm AA for the first, and the dilated Shannon entropy (Kroer al., 2015) as the regularizer for the second) and obtain the same rate with respect to the horizon T. However, an interesting question arises: what is the optimal dependence on the total size of the action sets? This becomes particularly important in the context of extensive-form games where the number of actions is very large.
Synchronisation Algorithm 3 therefore reaches the opti- mal rate ((T-1/4) for the L last-iterate convergence, up to logarithmic and constant factors. However, it shares some of the weaknesses of Algorithm 1, as it still requires the two players to synchronize their choices of either instance A; or A;-1, with the latter being only played for the anytime guarantees.
More natural methods: Is it possible to obtain anytime last- iterate guarantees without relying on some synchronicity between the two players?
9. Conclusion
We studied the convergence of uncoupled algorithms for learning zero-sum games with bandit feedback. We showed that imposing anytime last-iterate convergence worsens the rate compared to just requiring convergence of the average policies, with a lower bound of ((T for the LP F- norm of the exploitability gap given p E (0, 2). in contrast of the usual rate (T2222)
Stronger convergence: for the uncoupled L convergence given > 2, and for the uncoupled convergence with high probability?
Is the Q(T-1/4) lower bound tight
We especially wonder if these last two questions could be solved using modified version of the optimistic mirror descent algorithm, for example by tweaking the estimated losses or the learning rates.
We then proposed two algorithms that match this rate. The first relies on some synchronization of the two players to bal- ance between efficient exploration of the game and exploita- tion of near-optimal policy. A second algorithm relies instead on a regularization of the game and also matches the rate for the L norm. However, the latter does not have the required anytime guarantees. A doubling trick effectively solves this issue, using a synchronization similar to the first algorithm.
Impact statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be
'hhe number of state-action pairs to be precise.
8

---

The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
specifically highlighted here.
Press, 84108-5. URL
Cambridge,
2006.
ISBN 978-0-521-
doi: 101007/C8097805111546999
References
https://wwet orgbbriddeeegg/ooooooooo http:///drrtttoo-oaaaaaiinnaarda ABCSFGAC0152AA1944C05006655
Abe. K., Ariu, K., Sakamoto, M., Toyoshima, K., and Iwasaki, A. Last-iterate convergence with full and noisy feedback in two-player zero-sum games, 2023.
Chiang, C.-K., Yang, T., Lee, C.-J.. Mahdavi, M., Lu, C.-J,, Jin, R., and Zhu, S. Online Optimization with Gradual Variations. In Proceedings of the 25th An- nual Conference on Learning Theory, pp. 6.1-6.20. JMLR Workshop and Conference Proceedings, June 2012. URL https: / /ppppceeeing......// mlr press/v23/ chiang12 html. ISSN: 1938-7228.
Auer, P. Cesa-Bianchi, N., Freund, Y. and Schapire, R. E. The Nonstochastic Multiarmed Bandit Prob- lem. SIAM Journal on Computing, (2(1)778-77, January 2002. ISSN 0097-5397. doi: 10.1137/ 50097539701398375
URL pettss:/epuuie siam.
org/doi/10. 10..0..137/00000 11111//0077733771133377777777777 Publisher: Society for Industrial and Applied Mathematics.
Dong, J., Wang, B., and Yu, Y. Uncoupled and convergent learning in monotone games under bandit feedhack. arXiv 2024.
Azizian, W., Jutzeler, F., Malick, J., and Mertikopoulos, P. The last-iterate convergence rate of optimistic mirror descent in stochastic variational inequalities, 2021.
preprint arXiv:2408.08::
Drusvyatskiy, D., Fazel, M., and Ratliff, L. J. Improved Rates for Derivative Free Gradient Play in Strongly Mono- tone Games. In 2022 IEEE 61st Conference on Decision and Control (CDC), pp. 3403-3408, December 2022. doi: 10. (DW.:CCDDS10999222229999999 ieeexplore. www.loorreeee.ee.ee org/ www..r////cmmmee999955555 ISSN:
Ba, W. Lin, T., Zhang, J., and Zhou, Z. Doubly Opti- mal No- No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback. Operations Research, Jan- doi: 10. 00.127/opre.2221. 0445. URL https: htttss://puuoonninoe informs org/ doi/abs/100 http:/1..11///ppp// 2021 0445. Publisher: IN-
URL https:
uary 2025. ISSN 0030-364X.
2576-2370.
FORMS.
Facchinei, F. and Pang, J.-S. (eds.). Finite-Dimensional
Variational Inequalities and Complementarity Problems. Springer Series in Operations Research and Financial Engineering. Springer, New York, NY, 2004. ISBN 978- 0-387-95580-3. doi: 10.1007/b97543. link. mankksprrgger.. wwwpiinee.co/............... 1007 10t.//001.777//775444
Banach, S. Théorie des opérations linéaires. 1932. URL pettps:/euddll
URL http://
Bravo, M., Leslie, D., and Mertikopoulos, Bandit Learning in Concave N-Person Games. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL https:// papers .ncers..iip..om cc/paper /atp hash/ hcpperseippp.ccppppee.e...
Heinrich, J., Lanctot, M., and Silver, D. Fictitious self-play in extensive-form games. In International conference on machine learning, 2015.
4TTCB0T70055442234444448888--888 html.
Hiriart-Urrugy J.-B. and Lemaréchal, C. Fundamentals of Convex Analysis, pp. 163-208. 01 2001. ISBN 978-3- 540-42205-1. doi: 10. 00.10077978-33 3-1---3----555500 022-66442-6666
Cai, Y. Luo, H., Wei, C.-Y., and Zheng, W. Uncoupled and convergent learning in two-player zero-sum markov games with bandit feedback. In Proceedings of the 37th International Conference on Neural Information Process- ing Systems, NIPS '23, Red Hook, NY, USA, 2023. Cur- ran Associates Inc.
Hsieh, Y.G.,, lutzeler, F., Malick, J., and Mertikopoulos, P. On the Convergence of Single-Call Stochastic Extra- Gradient Methods. Advances in Neural Information Processing Systems, Vancouver, Canada, December 2019, URL https: //te:r////iaa////eeeeeeeeeeeaaae htt.eiiiiaaaaaa..aa...aaaaaaaaaa hwt.:aecccccccaaa2200555555
Cai, Y., Farina, G., Grand-Clément, J., Kroer, C., Lee, C.-W,, Luo. H., and Zheng, W. Fast Last- Iterate Convergence of Learning in Games Re- quires Forgetful Algorithms. November 2024. URL.
Huang, Y. and Hu. J. Zeroth-Order Learning in Con- tinuous Games Via Residual Pseudogradient Estimates. IEEE Transactions on Automatic Control, pp. 1-16, 2024. ISSN 1558-2523. doi: 10.1109/TAC2002..
http:://ppenreeieeeeeee///e 200abriele//20Farina///
3479874. URL https:// http:://eeeeeeeeeeeeeeeee ieee org/ docmment/107115447ddneeee
htrpraaeeeoaaaannnsssoaoaaaaaaad (1Pr (aabbriel__Fainna]]
Conference Name: IEEE Transactions on Automatic Control.
Cesa-Bianchi, N. and Lugosi, G. Prediction, University
Juditsky, A. B., Nemirovski. A. S., and Tauvel, C. Solv- ing variational inequalities with Stochastic Mirror-Prox
Learning, and Games.
Cambridge

---

The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
algorithm. Stochastic Systems, 1(1):17, 2011. doi: 10.1214/10-SSY01. URL https://hall sccinncceseeee/////eccce ha1-00318043.
McAleer, S., Farina, G., Lanctot, M., and Sandholm, T. ESCHER: Eschewing importance sampling in games by computing a history value function to estimate regret. CoRR, foss/200.004122, 2022. doi: 10.48550/rxXi.22266 04122. URL
Kangarshahi, E. A., Hsieh, Y.-P., Sahin, M. F., and Cevher, V. Let's be Honest: An Optimal No-Regret Framework for Zero-Sum Games. In Proceedings of the 35th Interna- tional Conference on Machine Learning, pp. 2488-2496. PMLR, July 2018. URL
40..1/..85///// arxvv..
04122.
Munos, R., Valko, M., Calandriello, D., Azar, M. G., Row- land, M., Guo, Z. D., Tang, Y., Geist, M., Mesnard, T. Michi, A., Selvi, M., Girgin, S., Momchev, N., Bachem, O., Mankowitz, D. J., Precup, D., and Piot, B. Nash learning from human feedback, 2023.
mml.. mlr. press/v80/ /aao//aaaaaraaaaaaa shahi 18a.html. 3498.
ISSN: 2640-
Kocák, T., Neu, G., Valko, M., and Munos, R. Efficient learning by implicit exploration in bandit problems with side observations. In Advances in Neural Information Processing Systems 27, 2014.
Muthukumar, V., Phade, S., and Sahai, A. On the Impos- sibility of Convergence of Mixed Strategies with Opti- mal No-Regret Learning. Mathematics of Operations Research, November 2020. ISSN 0364-765X. doi: 10. 00..128/moo.2002.000000 URL hnttps:/ppubsonliii
Korpelevich, G. M. The extragradient method for finding saddle points and other problems. 1976.
inf orms orge httg///oo/1...0 httpd///..............e/ /moor. 2022. Pub-
lisher: INFORMS.
Kozuno, T., Ménard, P., Munos, R., and Valko, M. Model- free learning for two-player zero-sum partially observable Markov games with perfect recall. In Proceedings of the 35th International Conference on Neural Information Processing Systems, NIPS 211, pp. 11987-11998, Red Hook, NY, USA, December 2021. Curran Associates Inc.
Nash Jr, J. F. Equilibrium points in N-person games. Pro- ceedings of the National Academy of Sciences of the United States of America, 36(1):48-49 49, 1950.
Nemirovski, A. Prox-Method with Rate of Convergence (11/t) for Variational Inequalities with Lipschitz Contin- uous Monotone Operators and Smooth Convex- Concave Saddle Point Problems. SIAM Journal on Optimization, 15(1):229-22) 151, 2004.
ISBN 978- 778-1-71384-539-3
Kroer, C., Waugh, K., Kiline-Karzan, F., and Sandholm, T. Faster First-Order Methods for Extensive-Fone Game Solving. In Proceedings of the Sixteenth ACM Confer- ence on Economics and Computation, EC 15, pp. 817- 834, New York, NY, USA, June 2015. Association for Computing Machinery. ISBN 978-1-4503-3410-5. doi: 10. 70.1144522764448.776477766 URL. 276447
Nemirovski, A., Juditsky, A., Lan, G., and Shapiro, A. Robust Stochastic Approximation Approach to Stochas- tic Programming. SIAM Journal on Optimization, 19 (4):1574-1609, January 2009. ISSN 1052-6234. doi: 10.11377777704277. htthtt:ss///pppe ssaaubs.siam...... org/ doi/10. 1117/0707044 dustrial and Applied Mathematics.
Publisher: Society for In-
Kuhn, H. W. Extensive Games and the Problem of Infor- mation. Annals of Mathematics Studies, 28:193-216, 1953.
Nemirovskiï, A. S. and IUdin, D. B. Problem Com- plexity and Method Efficiency in Optimization. Wiley, 1983, ISBN 978-0-477 978-0-471-10345555 Google-Books 6UL- VAAAAMAAJ.
Maneino, O. G. and Stampacchia, G. Convex program- ming and variational inequalities. Journal of Optimiza- tion Theory and Applications, 9(1::3-23, January 1972
Neu, G. Explore no more: improved high- probbbbbbbbiltty regret bounds for non-stochastic bandits. In Proceedings of the 29th International Conference Neural Information Processing Systems Volume 2, volume 2 of NIPS' 15, pp. 3168-3176, Cambridge, MA, USA, December 2015. MIT Press.
ISSN 1573-2878. doi: 10. 1007/8/0009332.0.. URL https: / /ttii ott//o////////............. 1111111111000000000000
Martinet, B.
Brêve communication. Régularisation d' d'inéquations variationnelles par approximations successives. Revue française d'informatique et de recherche opérationnelle. Série rouge, 4(R3):
Pinsker, M. Information and information stability of random
variables and processes. 1964.
154-158, 1970. ISSN 0373-8000, 2777-3515. doi:
URL https://www.
Popov, D. A modification of the Arrow-Hurwicz
asaim-m2and http:///www....aaeee//eeeeeeeeee absa 19900/3// html. Number: R3 Publisher: EDP Sciences.
method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, 28(5):845- 848, November 1980. ISSN 1573-8876. doi: 10.
10

---

The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
1007/BF01141092, URL.ntpp::/bbi..or//....0 BF01141092.
Rakhlin, A. and Sridharan, K. Optimization, learning, and games with predictable sequences. Proceedings of the 27th International Conference on Neural Information Processing Systems Volume 2, volume 2 of NIPS' 13, pp. 3066-3074, Red Hook. NY, USA, December 2013. Curran Associates Inc.
Rudin, W. Real and Complex Analysis. Tata McGraw- Hill, 2006. ISBN 978-0-07-061987-6. Google-Books-ID: 3d8umJoRdOSC.
Tatarenko, T. and Kamgarpour, gence of Payoff-based Algorithms Nash Equilibrium in Strongly Monotone Games, February 2022. URL http:
the Rate of Conver-
//arxiv. org/ abs/ aasa//200 2202 11147. arXiv:2202.11 1147 [math].
Tseng, P. On linear convergence of iterative methods for the variational inequality problem. Journal of Computational and Applied Mathematies, 60(1):237-22) 1995. ISSN http://org//.111110777-------090
0377-0427. doi:
00094-H. Proceedings of the International Meeting on Linear/Nonlinear Iterative Methods and Verification of Solution.
Tyrrell, R. R. Monotone Operators and the Proximal Point Algorithm SIAM Journal on Control and Optimiza- tion, 1976. URL https://epubs. siam. sta......../.................... org/do1/10. 1137/0814056.
Neumann, J. Zur Theorie der Gesellschaftsspiele. Math- ematische Annalen. 100(1):295-322 December 1928. doi: 10. 148777//011448 URL
ISSN 1432-1807.
https: http://doooooro.../.// 10010007/BBBB 1448847.
Wei, C., Lee, C., Zhang, M., and Luo, H. Last-iterate conver- gence of decentralized optimistic gradient descent/ascent in infinite-horizon competitive markov games. In Belkin, M. and Kpotufe, S. (eds.), Conference on Learning The- ory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pp. 4259 4299. PMLR, 2021. URL http: // //proceedings mlr, press/v134/wele html.

---

The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
A. Lower bound
Theorem 5.1. Assume that the sampled action v of the max-player at each iteration is never observed. Then, for
any p E (0, 2), no learning sequence can achieve simultaneousty for all 2 matrix games described above an L last iterate convergence of
4 t
118
even asymptotically.
Proof. We will use the games mentioned the main body, defined with:
M = 2/3 -
1/3 + 1/3+s
with E E 1-1/12,
1/3
2/3
where the entries of the matrix indicate the parameters of some i.id Bernoulli for the actual game.
We will assume that the learning sequence satisfies an asymptotic L" last iterate convergence with f of the form
f Cp t2tp with Cp (0,
and show that this is impossible for all games given Cp low enough.
Notations Let z denote the knowledge of both players up to round included with =²:= (w, at, e....., a', f¹), such that the sequences (f²") and (v²) of policies are predictable with respect to the filtration (o(2"))<EN rather than F from the assumption.
We will consider the games M M and - with a fixed choice of Er that we will specify later. Let Fg. Pr and P-r respectively be the probabilities associated to playing these games, with Il- pr Il-llzr, and ||- I1-II-T,, the associated p (pseudo)-norms norms, For any random variable X and 0 E Z, we will denote by P the probability distribution on X given Fg.
Now, given an horizon T, let ET and E-T respectively be the two events ET == {xT(1) < 1/2} and E-T = {nT (1) 2 1/2]. ET denotes suboptimal choice for the game M and E E suboptimal choice for the game M-ér as we will show in the next section. Under Po. one of these two events happens with a probability of at least 1/2, we will denote with 0² [-T,T]
112 8* 1/2 8¹ with 8' E 1-1/2,1/2]
For clarity, we will take the strategy of the max max-player v' to be in the form
Link between the policies and exploitability gaps The exploitability gap will be lower bounded twice in this section: for the max-player under the game M and for the min-player under the games M and M- We will use the fact that the value all of these games 1/2.
Given a max mla-pr policy vA, we have
1/2++
M
1/2 - /3/3
which implies (for M"), EG(μ vt) 2 1/2 min, (H, M MM.'") = 8¹/3
(1) ] and any E 1-1/12, 1/12).
On the other hand, given a min-player policy y²² = 1 1 1r (1)
11/3 + 1/3,3 en¹ (1)
(M 4T"
2/3 - 113 ty [2 (1)
1
[0]
(with the R notation for the transpose). Then, using the vectors el
:
and e²
12

---

The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
With M under event ET {u" S 11/2] (2.(M) ,T)) +T) 2 1/2 + ex/2. hence: EG(μ', v/) 2 max (Mer)" ,4t) 1/2 2 ET/2
With M or under event F F-T =1x 2 1/2]: (c.(MM))) "nr")""")))))
.xt) 2 21/2 + eT/2.
hence: EG(n', ,') 2 max (v, (M-rr) .ut) 1/2 2 ST/2
In both cases, the exploitability gap is at least e2/2.
Asymptotic KL divergence From the definition of the sequence (z*) and the additive properties of the KL divergence, we obtain the following inequalities
DKL (P6" .b/)) DKL PpT)
-
Eo
DKL
6T
T
= DxL (Po. Pūj) + Eo Σ DKL [pa"ls""
- 0r
+ Eo
Σ
DEL (p= -
= Eo
p² (I)DRa //..12 23--20 20 sign (0 (0T))T)
< Bo
1012
< Eo
10910
< Eo
Σ (3EG 12))
T
< 216s
Σ
LEG(, v lll_p
where we especially used the reversed Pinsker inequality with 1/6 < 1/2 8'/3 - -25 20'ssin signninn" (0 )er S 5/6, and the previous lower bound of the exploitability gap under Po. For the third equality:
DxL (PP poy, is 0 as the internal randomness do not depend on the model.
DxL. (1g* (+= 11) is also 0, for all i, as the choice of the action (conditionally on the previous move) also does not depend on the model.
From the computations above, DKL [pf (==1==--1
_pf(==-1 corresponds to the KL divergence between a Bernoulli
B(1/2 + 8²/3) and Bernoulli B(1/2 + 8¹ 3- 25' signsgn( ((T the first move is played by the first player, otherwise.
Now assume that the restriction holds for all f To. then for any T To
13

---

The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
DKI.
Po P S 21667
To + Σ
(M9pp)
1=
21667
To +
t .+
1=1
T ,
S 21667
To
1 dt
2 +
216
To + 2
T 240
2166
To + 2T
Which implies the asymptotic bound:
lim sup DKL. (Po" .P T S 432s7. T
Probability of a suboptimal choice
Defining ||llr the total variation between two probabilities P and Q:
P Q Qlivv
sup PP(E) Q(E)
E event
and using the measurability of E with respect to a (=²"), the fact that Po (oEE²)) 2 1/2 by definition and Pinsker inequality, we get
lim inf Por (F.5²)
> lim inf +00
(oo(F0")
|2""
0z
T++00
TV.
2
lim
lupsup sup
1 DKL (PO", ,P:T)
2
T +
6v6 limsupey
T
This implies that fixing ET
21v6 T forces the probability of this suboptimal choice to be at least 1/ asymptotically.
Final bound
Combining the previous choice of e with the suboptimality of μ² under E
lim inf [G( ,,,T (lrr, Tzto 2 lim (Por (E**) Egr ( (EG(H", (CCG(""NT7"" />))=>))))))))>)))))))) Tst 7-400
7
in Por (80")
$ ET Tsto
(P85)) 1/4
lim inf Pør
48
T
4 4
48v6
As 1 1 this implies that the guarantees cannot be attained asymptotically for all games assuming f is defined with
1876" 118
118 t
14

---

The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
B. Proofs for the Simultaneous Explore or Exploit approach
Lemma B.l. Let (p*) E [0, 1]a. The sequence of Bernoulli random variables (EN defined by
= 1s' + 1s" + +ul
where
and ~ u~,((111))
satisfies:
V e N, B|B" p
and Σ B' s
Let x, y E R such that S y S Let {.} denote the fractional part. We distinguish two cases with the same result:
Proof.
If {ar S (v) (and consequently [a] = [y]). then
[L + ul +1= Ly + w = (u E (1- 100,1-160 -0],)-(x))) = (4) - {x} = y
If [x} > {y} (which necessarily implies [x]] = Lyl -),
PP ([ + ul + 1 = Ly + u)) = P (u [0, - (1) (v), = 1- (x) + {v)
Using, for each E N, s--1 and y s¹ yields the first equality. The inequality is obtained by telescoping the term:
Σ B = | +
[u]
Lemma B.2. Assume that A satisfies output convergence of rate 9- Then Algorithm satisfies L last iterate convergence of rate defined by
fr 2² (10) + +
where r' Ek- p*
Proof. Using the previous lemma where B is the action of exploring, we obtain is non-increasing,
|EG II,,, E [EG("",
- (p'' [EG(UL, +²)]+(( + D')EE EG(a" 122)) 1
(p' + (or"))))
2 (1
where we used the notation 1 1E r + ul and the inequalities, for all xr y E Ryo:
(x + 9) < 20-1 (x9 + y9) for q 2 from the convexity of
(x + 8) < (x y9) for q 1 as y (x + 8) x y is decreasing on E>o-
15

---

The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
Theorem B.3. (Neu, 2015) Given A arms and 8 E (0, setting nf = 2/
log A for all the bound of EXP3-IX is At
AT log A
n² S 4v AT Al)oog(()+ +
2
log(2/6)
with probability -
Applying this theorem to both Riin and R with 8' = = gives the bound, with probability at least - 8:
At
Bt log +1 log(4/0)
Ry Rm S 4v At log(())
2/ log +1 log(4/0) + 4v Btlog(B)+
(
SA BY log A + B) + (2V/L++ AVAL++2BBB)) log(4/0)
<8 log (AA + B)/
where we used very loose upper bounds for simplicity.
Theorem 6.2. Using Algorithm/ I with probabilities p' = P/(2tt)) and as A, the algorithu EXP3-IX with parameters Amin 2 Vlog( (A)) (At) for the min-player and vimax 2mmxxx Vlog(B) (B)) for the max-player, we obtain an D last-iterate convergence rale of
f = 17 aोω log (1))+))))p)
Proof. LP bound
We first show that the average policy played by EXP3-IX converges for the norm. Let p E (0, 2] and / N, we consider 6 p/t in the above inequality. Then, the sum of the two regrets is bounded by T,
|EEG(R rd) E [EG(," styoe
$ t [[Rtiin )
1
< Stt +
(11- -1) (8 BB)/))
t
$ t p (8V(A+ B)tlog B){² /p)
1
As for all 2 from the concavity of the log function,
( + x²) e log(p-x") < + 10gg((=))+1 =
we obtain
A+ B t
|| LEG(""DD") S 56
log ()(A+B)&/1)
Lemma application We apply Lemma 6.1 with p¹ =t As in this case,
1+1
22 ((++)) -1) 11] 2 -2)
I+ du
We obtain (loosely) a rate
8r 2 2 (x') + gdd]
zir 11V2214+++ B log (4(A+ BY8 /p) t +i
22217V Blog (4 B)t² /p) t +.
16

---

The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
C. Proofs for the Regularized EXP3 algorithm
Notations: In this section, the computations will be done directly the space W = A x AB using w = (14, v) and the operators, for 0,
F(w) = Fr ( mins maxx
L(M,-))
B
h(w)= - Σ u(a) (log(u(a)) 11) Σ v(b) (log(u(b)) 1) a=l
b=1
FT (w) (L(, L(u,-)) + (Vh(w)- vh(w"))
D(w, w') = (KL( + (K)(
With these notations, have the following properties:
F is a monotone operator over W, and the solutions w* E W of the variational inequalities
Vw (F(F(w"),, w w) 50
are the Nash equilibrium of the game associated to L.
Fr is strongly monotone operator. It has only one solution w for which the above inequality is always an equality and satisfies for all w, w' E W:
(F" F (w'), w w') (D(w, w'),,,,)+++ D(w', w))
B( = F(w))
D the Bregman divergence associated to h, and especially satisfies the law of cosines, for all x, y, E W:
D(2, 2) = D(x.y) D(y, 2) + (Vh(2) Vh(y). x))
Before proving the lemma, we notice that the updates of Algorithm 2 can be rewritten in the W space (if TT) $ 1):
wf = arg maamm-innnnnni - r/'r)D(w, =. + 7 D(w, w
wEW
(+1 arg min o/ (k+.w) D(w, w²)
W
weW
which are equivalent to the updates, taking the gradient of the above expressions,
Vh(w") = (1 - (h(w)) + Ty Vl((9) (l( Vh(w²) n/² fr
where we used the notations
I x= + Vw E W, (a - w) = 0
Lemma C.I. Let (0, 1). Taking r/' 2/ along with nx 1100 and vT,1 100 the uniform policies gives with the above updates
2(A + B)
[DKa(n"** ,,,)' DKI.lUti ,utd)]]
72
for all N.
17

---

The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
Proof. Updates:
From the law of cosines applied to the two updates, have:
(1) (1 (1-r1) (1-n"))((w"** w= (1 7/'r)''('" (wc w') (1 - n/T) w0=+) + (L T/T)) (Vh(wT-)) Vh(w"), w w²tt) 2 (1 - ---'''''D[''' w + n (Vh(w²) - Vh(w)), w² w7)+)
and
(2) D w = -( w²) + D(w", w + (Vh(w - Vh(w"),, ( wt with
w' - - = D(w"it, w0) + D(w", w w - n ( [
(2) - (1) yields when conditioned on Ft11;
E [D(w w F 11
- (1 1/'r)D( (w Tx w + E. [D] (wo,, w w. (
+ ('''D( w') - n ( (w' w FT (Tw"))
= (1 - 1/'rDD(u 2 " + E |D(w", w gittll }|5(11]
+ "1'TD("" w²) n¹ (w' w FF (w0) F² (w"())
(1 ''')D((w** TM ( + EE DDw'' w r.+ }|
'1'TD(w' w w²²
< (1 - v'r)D((x*** w + EE [Dww,, w w
Second order bound: We now want to show
E D(w', t }| s (171)² A A B
We start by showing
E [Kk n (((+))))== S (77) 2 A
2
and the rest will follow by symmetry. This inequality is classic in the bandit literature, but we provide quick proof below for completeness.
If we define p as the unprojected update defined by:
Vha = Vha(m²) - v/ Pr.
we know, because of the generalized Pythagorean theorem (Hiriart-Urruty & Lemaréchal, 2001), that
E [DKi(p' p 1 1 < [Dxi, (
Then, using the convex conjugate ht (Hiriart- Urruty & Lemaréchal, 2001), the following holds, using classical properties of the Bregman divergence:
E DRL(H' 1( = E [DN; (Vha V
E Duu (Vha(H') - P (
(
Pr (mmn) [55-
EE
2
(
((a)2
Σ
(a)))
2
A
< (n²)
18

---

The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
where we used Taylor inequality along with the fact that the hessian
(Vha(())) (a)a())= Diag(u(a))
increasing all components with respect μ., which implies the negativity of the third-order term. Indeed, each component of the unprojected policy decreases along the update.
Recursion We then have the recursive property, taking the global expectation:
w s < nTT)E [D(W wtth)]] + (17)) B
E (Dw"",
2
With vy' 7(447. this is everything we need for the desired property
A +
E (i( w())) < 2 721
Indeed, for & = 1, the property immediately follows from, as w. is the uniform profile,
A+ + B
D(w w h(w"**) S log(A) (Bg s
72
and < 1 by assumption.
Then, assuming the property holds for f, we notice that for ł +
2
A+
A+B
[" w w
2
+ 2
1+1 1
72.1
(t + 1)2
B
2
+ 1)
72
i
+(t+1)
t(t
B
B
2 72
1
I((+1)
2 A+ B
72(++1)*
Lemma C.2. For a zero-sum game with rewards in (0, 1), the exploitability gap is 1-Lipchitz with respect to the 1-norm.
Proof. Let (M, v) and w' (4', v') be two profiles in A AB, then
LEG(w) EG(w))] = sup L(x .V) - sup L(ui, 1/)
sup L(u, ut) + sup L(k', ,21) it
1¹
< sup L(11 ,b) - sup L(ue, )²) +
sup Li,, ut) - sup Lid .t))
vt
< | 1'11, + 11111/11
I w ll1
following the fact that, for any (pt, vt), + L(ut, v) and + L(H, are both 1-Lipschitz as the coefficients of the matrix are in [0, 1].
Theorem 7.2. Let T be a fixed horizon. Then, using regularization ((A (A 1/ /2/ (log(A) + (B) and the learning rates of 2/(((t + for all Algorithm guarantees
A+ B
1/4
|E D²) <
332
Vlg(AA (AB).
T
19

---

The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
Proof. We can safely assume T A B 4 as the bound is immediate otherwise. We first notice, iteration T:
From the optimality of w up to the regularization.
EG(w"**) S TDrI (w"", ("",""",,,")
(log(A) + log(B))
From Pinsker inequality and Lemma 7.1,
4(A + B) || - w11 ( I
72 T
By definition of w arg min.
(1 n1- DKL : + Tr) "r1i"z0 DKL (w ) S 1)² DKi ,00))
Hence, re-using Pinsker inequality,
n-T r s n/²² DeL Pu , S 4nj" (log(A) + log(B)) = T + (log(A) + log( (B)
||lT -w--- 1T S 2wx w T.
where used n² 1iT+ and in particular o7
T 2 3 by assumption.
With all these inequalities together, along with Lemma C.2 for the 1-Lipschitzness of the exploitability gap,
E [FFG(W")]
< E (FTG(W + "mll -== 11
(EG(wTit) + 11 - ||| + "mw wT 11 )
IE
E
EG(wT++)2 +
- 112 1
-
lww - w 1P
3
7 (log(A) + log( 4(A B)
8
(log(A) + log logo())))) B))
T2T
T ++1
In particular, with 7 log()) V
A+B T
we obtain,
+ B
$) T
8
E [EG(W")) [EG
<3 4
+
(log(A) + log( ())
T
hence, as T' 2224 4 A+ B 4,
A B T
E [EG(w"))] S 188
(log(A) log B))
and by taking the square root,
[A+B B) 1/4
IEG(w < 332
Vlog(A) - log(B).
T
Theorem 8.1. Using Algorithm 3 with, for each A,, the algorithms and parameterization of Theorem 7.2, along with T, =2((22)) and S; = 8(2)), we obtain the bound
A + B 1/4
||EG 222 < 30
Vlog( (AB) log(t)
t
for any total number of iterations Tj +... T +
20

---

The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
Proof. Let EG(i, 8) be the exploitability gap of sub-algorithm M, after iterations. With the notations
CA,B 1 B (log(A) + log(B))
2 we have from the proof of Theorem 7.2, taking T = s and T² log( 1o
A+B
VT.
E [EG((,,)) S CA.B
assuming 8 S T.
We will also use the notation, for any i T,, TT i. Note that, because of the sampling method, the actual number of calls 8 will be at least s/ - 1.
= Pk. the expected sum of calls of sub-algorithm Mj during the loop
We notice, for any 5,, log(T.) S S S, log(Ti),
$
TB 3 - 1
and in particular,
111 21
1
48,
-2)
57.
4(1
2e 2)
S 511
T.
S e 3T (+)
21,
where we used _ < 1 +
1 +
< 1
5
111
Txx 2
2 62
5. 37
15.
Now, for any j S T, and = Ti + ... + T + j. We have
E|G ,1/91 = xd E EG(i,
E
+ (1 (1- p\) E EG(i 1,
a(i))
B(1.))
where 8 2 s - and s' 2 T: 1-11 1.
First term (a(i,))):
Either j < 2
S: log(T)), then ali,)) S s vI; using EG(i, s) S
Either log(T) < j < St log(T)), in this case, using
we obtain
S 2T.
S 2
o 12
e 2
p
This yields
VT:
ali,) < A
SBCA,B VT,
S,
Either S; logg(T)) < j. in this case, using (*) again with [S; log(T:)) instead of j. we obtain:
S
1+1
S
5 12
-12
2T;
21

---

The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
1 which again yields:
VT.
ali,5) S ACA. S;
SiC A,B VT,
as p & 1.
Second term (3(i,))
For the second term, which depends on the total number of call of algorithm M, we will lower-bound this number using only the calls during the loop i As T 2 [ log(L;-1)), we have, using inequality (x) on the loop - 1, with the previous quantity, above,
T- - 12 8-1 -12 Si-1 82 8
2
and we obtain:
V
1
B(i.)) S A
8(i 1)CA,B
S
VT:-1
Final bound
To conclude, we will also need the simple inequalities:
2 E Ti (and thus S 27, if / is loop i).
4T;-1 2 Ti
& Log((T-1)/ 12g(2)
Using these, we obtain, for any j. and = Ti + + Ti-1 +j:
E EG(H", v²)3] =(i,,) + ((i,j)
1
1
S A
+ +8(1-117)
- 1)CA,B VT--1
VT,
8
(v2+2V2)
CA,B log(Ti)
log(2)
Vt
(V2+ 2V2
log(1)
CA,B
log(2)
Vi
Finally, taking the square root and using the definition of CA.B,
A + B 1/4 (4+
LEG('",'\\2 V log(2)
144
(V2+2V2)
V(log(A) log log(t)
A+1 B
1/4
30
V(log(A) A) + log log(!)
22


Reviews:
[{"review_id": "2aUZziNhyj", "reviewer": "Reviewer_bHVB", "summary": "This paper studies a zero-sum matrix game in which two players repeatedly select stochastic policies, sample actions, and receive stochastic losses—without access to the underlying payoff matrix—that depend on their joint actions. The authors aim to develop an uncoupled algorithm that independently controls each player without explicitly observing the other player’s actions, while ensuring last-iterate convergence of the players' policies to a Nash equilibrium. \nThe paper establishes a convergence rate lower bound of $\\Omega(T^{-1/4})$ for this problem. To address the challenge, the authors propose two algorithms (Algorithm 2 and Algorithm 3). They show that Algorithm 2 achieves an $\\ell^2$ convergence rate of $O(T^{-1/4})$, while Algorithm 3 achieves an $\\ell^2$ convergence rate of $\\tilde{O}(T^{-1/4})$.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer bHVB for taking the time to review our submission and especially for pointing out the issues in the notations. We address the concerns below.\n\n>It is concerning that the abstract claims both proposed algorithms achieve the optimal convergence rate. Could the authors kindly clarify whether the algorithms match the lower bound up to constant factors, only in terms of the order of $T$ or if the rates differ by logarithmic factors (e.g., $\\log (T)$)?\n\nThe rate is indeed only matched up to logarithmic factors, and we do not try to hide it in the paper. In the abstract, this comes from an oversight due to the change of the $\\tilde{\\mathcal{O}}$ notation to $\\mathcal{O}$ as the lower bound does not include any log factor. We will change the abstract to address this confusion.\n\n>The consistent use of Big-$\\mathcal{O}$ notation to express lower bounds throughout the paper is somewhat confusing, as Big-$\\Omega$ notation is typically used for lower bounds. For instance, this appears in Section 1 when referencing the lower bound from [Cai et al., 2023], as well as in Table 1 and Section 2. Could the authors kindly clarify whether this usage is intentional?\n\n This is an oversight, and we will change the relevant Big-$\\mathcal{O}$ notations into Big-$\\Omega$ (including in the abstract).\n\n>Could the authors kindly provide appropriate citations for the transformation procedure described in Section 6?\n\nWhile the idea behind the transformation procedure is natural, we are not aware of an article using this trick to transform an average profile convergence into a last-iterate convergence. If you have any precise references in mind that we did not stumble upon, please do not hesitate to give them so that we can add them to the paper\n\n>The notation $\\ell^p$ ($\\ell^t$) appears to be used with different meanings in various parts of the paper, which may lead to confusion. It would be helpful if the authors could clarify or standardize the notation to improve readability.\n\nIndeed, we use the notation $\\ell^p$ for the convergence of the sequence and $\\ell^t$ for the loss, and we assumed changing one of the two would bring more confusion. As the two refer to two completely different objects, we considered this overlap of notation acceptable. However, we propose to instead talk of the convergence of the sequence of the random variables $EG(\\mu^t,\\nu^t)$ in the $L^p$ space toward $0$, which we also believe to be better in addition of avoiding this overlap.\n\n>Could the authors confirm whether, to the best of their knowledge, the convergence rate upper and lower bounds presented in this work are the tightest currently known?\n\nThe rates presented in Table 1 are the tightest currently known for high probability convergence. There also exists a $\\mathcal{O}(t^{-1/6})$ rate for the $\\ell^2$ convergence that was pointed to us that we will add to the table (and which we directly improve).\n\n>If so, could the authors kindly elaborate on the analytical tools or techniques they employed to derive a tighter lower bound on the convergence rate compared to prior works?\n\nThe idea of the tighter lower bound is the focus of section 5 and is based on improving the classical lower bound on best arm identification (see e.g. [1]) for our context. This lower bound is based, from the point of view of one player, on the difficulty between distinguishing a sequence of $T$ Bernoulli $\\mathcal{B}(1/2)$ and a sequence of $T$ Bernoulli $\\mathcal{B}(1/2-\\varepsilon)$, which is required to guarantee $\\epsilon$-optimality. We show that $\\epsilon$-optimality in the context of last-iterate convergence for games can require distinguishing between a sequence of $T$ Bernoulli $\\mathcal{B}(1/2)$ and a sequence of $T$ Bernoulli $\\mathcal{B}(1/2-\\varepsilon_t)$ for $t$ varying between $1$ and $T$, with $\\varepsilon_t=\\mathcal{O} (EG(\\mu^t,\\nu^t))$. This implies a trade-off at each iteration between getting more information on the $\\varepsilon$-optimal strategy and playing near-optimal profiles $(\\mu^t,\\nu^t)$, which explains the worse rate.\n\n[1] Jean-Yves Audibert, Sébastien Bubeck. Best Arm Identification in Multi-Armed Bandits, COLT 2010", "claims_and_evidence": "It is concerning that the abstract claims both proposed algorithms achieve the optimal convergence rate. Could the authors kindly clarify whether the algorithms match the lower bound up to constant factors, only in terms of the order of $T$, or if the rates differ by logarithmic factors (e.g., $\\log(T)$)?", "methods_and_evaluation_criteria": "The evaluation criteria (convergence rates) make sense.", "theoretical_claims": "The consistent use of Big-$O$ notation to express lower bounds throughout the paper is somewhat confusing, as Big-$\\Omega$ notation is typically used for lower bounds. For instance, this appears in Section 1 when referencing the lower bound from [Cai et al., 2023], as well as in Table 1 and Section 2. Could the authors kindly clarify whether this usage is intentional?", "experimental_designs_or_analyses": "This paper does not provide any numerical study.", "relation_to_broader_scientific_literature": "This paper contributes to the broader online learning research community by providing a tighter (compared to prior works, e.g., [Cai et al., 2023]) convergence lower bound for a specific setting of zero-sum matrix game.", "essential_references_not_discussed": "Could the authors kindly provide appropriate citations for the transformation procedure described in Section 6?", "other_strengths_and_weaknesses": "Strengths:\n- The paper addresses a complex setting of zero-sum games by incorporating bandit feedback, uncoupled learning, and last-iterate convergence.\n- It provides a convergence rate lower bound for the considered problem, contributing to the theoretical understanding of this setting.\n\nWeakness:\n- The presentation of the theoretical results is unclear.\n- This paper does not include any numerical validation to support the effectiveness of the proposed algorithms.", "other_comments_or_suggestions": "The notation $\\ell^p$ ($\\ell^t$) appears to be used with different meanings in various parts of the paper, which may lead to confusion. It would be helpful if the authors could clarify or standardize the notation to improve readability.", "questions_for_authors": "- Could the authors confirm whether, to the best of their knowledge, the convergence rate upper and lower bounds presented in this work are the tightest currently known?\n- If so, could the authors kindly elaborate on the analytical tools or techniques they employed to derive a tighter lower bound on the convergence rate compared to prior works?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BwZwGSP5Eg", "reviewer": "Reviewer_U4sa", "summary": "The paper aims to improve the upper and lower bounds in  Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to express our sincere gratitude to Reviewer U4sa for their very comprehensive and constructive feedback. We appreciate the encouragement, particularly the acknowledgement of our \"honest and transparent presentation of results\". \n\nWe prepared a response for all of the questions, but we were greatly limited by the 5000 characters limit. We will only be able to submit (once) the response to the rest of the questions (especially some of the longest replies) after the reviewer's response.\n\n>Q1\n\nFor our analysis to hold, the regularization term currently needs to be the same for both players for Algorithm 2. As it is a hyper-parameter, we consider this requirement to be substantially weaker than actual communication.\n\n>Q2\n\nThe reason we use this shared seed that allows the sampling of a shared Bernoulli with parameter $p^i$ at each iteration, and not a Bernoulli directly is to make sure the two players have exactly the same sample $B^i$. The two players indeed need to explore and exploit simultaneously, as the exploitation (i.e. playing the output of $\\mathcal{A}$) of one would otherwise bias the exploration of the other: the guarantees of $\\mathcal{A}$ only holds if both players play the algorithm over the relevant iterations.\n\n>Q3\n\nIf at each iteration $i$, the actions $a^i$ and $b^i$ are observed by the two players, then, for any entry $(a,b)$ of the matrix, the expected value of this entry can be estimated by averaging all of the observations for which $(a^i,b^i)=(a,b)$. Assuming that each action profile is played on average $\\Omega(t)$ times over $t$ iterations as $t$ scales to $+\\infty$, then each entry of the matrix can be estimated with a precision of $\\tilde{\\mathcal{O}}(t^{-1/2})$ using Hoeffding inequality. Suppose each player computes its minimax strategy associated with the resulting estimated matrix (which can be done \"offline\", without observations) and plays it at each iteration. It can then be shown that the exploitability gap scales with the precision of $\\tilde{\\mathcal{O}}(t^{-1/2})$.\n\n>Q4\n\nAs explained in line 620, the proof also uses random matrices with Bernoulli entries, the entries of the matrix $M^\\epsilon$ being the parameter of these Bernoulli. The confusion might come from lines 647-669, where we do the computation directly using this matrix, as the exploitability gap is defined for the expected loss matrix. We will add a sentence to clarify.\n\n> Markov games question\n\nWe are not sure we fully understand the question. We assume that \"learning rate\" refers to our guarantees. While their second algorithm reduced to a single stage seems to be similar to their first algorithm on matrix games, the opposite transformation (transforming an algorithm that works on matrices into an algorithm that works on Markov games) is not trivial. In particular, their approach relies on estimating the value associated with each state.\n\n>gradient descent question\n\nAny mirror descent algorithm (including gradient descent) would not converge in general. In particular, if a fully mixed equilibrium exists, then the divergence between this equilibrium and the iterates is non-decreasing on expectation at each iteration. \nWe think optimistic gradient descent would not work, but we think optimistic multiplicative weights update (which relies on the Shannon entropy instead) could if we use two different rates for the intermediate iterates and the actual iterates. We are not sure whether the optimal rate of $\\mathcal{O}(t^{-1/4})$ is attainable with this method and if an additional problem-dependent constant would be necessary.\n\n>page 19\n\nTypo\n\n>page 18\n\nIndeed, this property does not hold for any regularizer, although it works for the most common ones, such as Shannon, Tsallis or the log-barrier (we only get $\\nabla h^3 \\leq 0$ for the $\\ell_2$ regularizer).\n\n>page 17\n\nIt follows the fact that the gradient of the minimizer of a convex function belongs to the opposite of the (here constant) normal cone associated with this point and the constraints.\n\n>page 16\n\n(a) This choice was made as Lemma C.1 relies on the estimated loss being non-negative.\n(b) typo\n\n>page 13\n\nEach term $t$ is the expectation of the same KL divergence with $\\theta^{t-1}$ taken under $P_0^{z^{t-1}}$. As $z^{t-1}$ is the only random variable in each term of the sum, this is the same as taking the expectation under $P_0$ directly.\n\n>line 689\n\nSee reviewer 3.\n\n> Questions for authors\n\nWhile a learning sequence is predictable using the internal randomess and the past actions and reward, a non-learning sequence could be based on the unknown entries of the matrix $L$, for example, which would go against the lower bound.\n\nThe next intuition is correct\n\nIn this setting, it is easier to consider that we announce our mixed strategy to an authority, which then returns both the sampled action and the associated reward. Otherwise, the convergence would indeed fail with the pure strategies.", "claims_and_evidence": "The evidence is fairly clear, but I will provide a detailed explanation of my questions in the following sections.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "As I mention later in my review, I would like to congratulate the authors on their honest and transparent presentation of results. With that in mind, I have a few questions to ensure we are on the same page:\n\t1.\tWhy are we attempting to minimize communication if we allow the loss function to be designed with a common regularization term (with a shared regularizer weight)? Could these two characteristics be relaxed simultaneously?\n\t2.\tWhile I conducted a careful proof-reading, I did not have time to fully grasp the necessity of the shared random variable seed in communication. Why can’t the incoming p^i play the role of u? I am trying to understand why we cannot instead leverage arbitrary information from strategies in the sequence.\n\t3.\tIn lines 236–243, there is a reference to an information-theoretic old-fashioned result. Could you elaborate on this? Specifically, why does allowing observation enable us to estimate each matrix entry? I assume the matrix size is at least O(t^{-1/2})—could you provide a more detailed explanation? I found this particularly interesting.\n\t4.\tOne aspect that initially confused me was the lower bound. In the proof in the Appendix, you exclusively examine three different games, rather than a random matrix with Bernoulli entries. What exactly is meant by “Bernoulli” in the main text? Was this an earlier idea, or am I missing something in the problem formulation?", "experimental_designs_or_analyses": "It is an excellent paper that does not require experiments.\n\nHowever, what I would like to see clarified is whether the paper models the behavior of a game-learning process between two independent agents or if it simply describes a collaborative uncoupled dynamics algorithm that will be employed in one server.", "relation_to_broader_scientific_literature": "The paper achieves better learning rates than those found in the literature.\n\nWithout having reviewed the results of Cai and Dong on zero-sum Markov games, could you explain how their baseline translates to the stage-game setting? The reason I ask is that Markovian noise introduces additional stochasticity, and I would like to determine whether this improved learning rate can be obtained “for free” in this setting. Finally, I would also like to know whether the authors believe a similar result could be achieved using standard gradient descent or optimistic gradient descent under bandit feedback, rather than requiring full feedback.", "essential_references_not_discussed": "I would like to request a comment and a more detailed explanation regarding lines 195–207.\n\nSpecifically:\n\t1.\tIs there any existing literature on the concept of passing bits to others through artificial choices? If so, I would appreciate references or further discussion on this point.\n\t2.\tI would also like to better understand an aspect related to the notion of uncoupled dynamics. Based on the authors’ description, it is unclear whether the step size is a common constant step size, a varying common step size, or if different step sizes have been collaboratively chosen to shape the dynamics—or if they truly remain “uncoupled.”\n\t3.\tWhy exactly do we want an uncoupled algorithm rather than the even more general notion of independent play? Does this choice primarily aid parallelization, or does it serve as a better model of real-world scenarios?", "other_strengths_and_weaknesses": "For me, the most interesting aspects of this paper are:\n\n(a) The honesty in the statements. I truly commend one or more of the authors for their transparency in presenting the results.\n\n(b) The structured distinction between different iterate types. While it may not necessarily be the most accurate modeling approach, I appreciate the authors’ effort to clearly differentiate between last-iterate, average-iterate, output-iterate, and how these relate to asymptotic vs. general results.\n\nAs a faculty member, if all the papers I reviewed were of this level of quality, I would genuinely enjoy reviewing even more.", "other_comments_or_suggestions": "Clarification Requests & Suggested Revisions\n\nPage 19, Line 1038\n\t•\tWhy is there a norm applied to the KL-divergence? Could you clarify the reasoning behind this?\n\nPage 18\n\t•\tIn the secondary order bound, please clarify whether the negative third-order term pertains specifically to exponential gradient descent (for the case of the entropy regularizer).\n\t•\tInitially, I attempted to prove this for any regularizer, but I do not believe it holds for \\ell_2 regularization. Am I mistaken?\n\t•\tAre there other regularizers (e.g., Tsallis) that satisfy the property \\nabla h^3 < 0?\n\t•\tIf the claim is indeed correct for all regularizers, please explain why.\n\nPage 17\n\t•\tI would appreciate a more detailed explanation of why the property \\equiv holds in this context.\n\t•\tPersonally, I prefer to express mirror descent using the constrained optimality condition inequality. While this does not change the correctness of the algorithm, I would appreciate it if you could state a lemma indicating whether this applies only to entropy regularization or to all regularizers.\n\nPage 16\n\t•\tThis part was quite confusing to me. In Page 16, it is evident that the authors follow a constant-sum formulation rather than zero-sum. While this does not impact the dynamics, I would like to understand:\n\t•\t(a) Why was this choice made?\n\t•\t(b) Why does F_\\tau have 1-L for the y-player, whereas the F operator has -L? These two seem inconsistent—could you clarify?\n\nPage 15\n\t•\tIn the last three inequalities, I believe that we should have B_t \\log B in the pre-last summand (first line).\n\t•\tI would recommend multiplying all summands by 2, and for the first one, multiplying by \\sqrt{t} (I believe this might be a typo).\n\nProofreading Issues & Formatting Corrections\n\t•\tLine 797: Missing closing parenthesis.\n\t•\tLine 650: Should be |\\delta^t/3| instead of the current notation.\n\t•\tLine 640: There are two colons instead of one.\n\nPage 13\n\t•\tThe paper uses the additive KL divergence property. Could you please rewrite this section?\n\t•\tThe issue is that \\mathbb{E}_0 does not refer to P_0, but rather to P_0^{z^T}.\n\t•\tAs a result, when summing over the history, there are redundant elements.\n\t•\tI am not suggesting that it is incorrect, but I would appreciate a detailed response in your replies to verify that there are no proofreading issues here.\n\nLine 689\n\t•\tPlease include one explanatory sentence for the reader, clarifying which terms are zero and why in this line.\n\n⸻\n\nFinal Notes\n\nI appreciate the effort that has gone into this paper. The above points focus on improving clarity, correctness, and presentation to ensure that all arguments are fully transparent and well-supported.\n\nWould you be able to address these concerns in your response?", "questions_for_authors": "Questions and Clarifications for Discussion\n\nI would greatly appreciate it if you could provide responses to the questions I have posed in the previous sections.\n\nOne of the most critical aspects of the paper is the discussion surrounding learning-output-last-iterate iteration. Having served on multiple review committees, I have often encountered disputes between different models and interpretations of these notions.\n\nLet’s see if I have understood correctly:\n\n\t•\tA sequence is called learning if its past completely determines its predictability.\n\n\t•\tConsider Rock-Paper-Scissors as an example. We say that a sequence is learning if its behavior depends on observations from previous rounds.\n\n\t•\tIf the distribution is stationary, then it is also a learning sequence, correct?\n\n\t•\tIn other words, any sequence that can be computed based on past information qualifies as a \nlearning sequence.\n\nThus, the natural question arises:\n\n##What constitutes a non-learning sequence?##\n\nLet’s now examine a classic question that often arises in the algorithms community:\n\n\t•\tSuppose I compute a last-iterate sequence of extra-gradient updates inside a subroutine.\n\n\t•\tHowever, in the main function, I output the time-averaged sequence as my “actual” \nsequence.\n\nIf I understood correctly, the paper attempts to reconcile this distinction using the output and last-iterate sequence framework.\n\t•\tThat is, \\hat{\\mu}_t represents the averaged sequence, while \\mu_t represents the last-iterate sequence.\n\n\t•\tIs this the correct intuition?\n\nDefining the $played$ Distribution in a Bandit Setting (lines 192)\n\nWhat exactly determines the distribution being $played$?\n\t•\tIn a bandit setting, how do we rigorously define this distribution?\n\n\t•\tUnlike in a centralized version of bandit game, we do not submit our mixed strategy to an authority that then returns a bandit feedback element, right .\n\n\t•\tInstead, in a bandit setting, we simply announce pure strategies.\n\nCould you clarify these details? I appreciate the effort you have made to formalize these distinctions—even if we later find issues with the model during the rebuttal discussion, your approach to structuring these ideas is commendable.\n\n⸻\n\nFinal Request: Intuition Behind the Doubling Modified Trick\n\nWhile I was able to follow and learn a lot from this paper, I found the method for the doubling modified trick highly unintuitive.\n\nCould you provide a more detailed intuition behind:\n\t1.\tHow this method was chosen (designed)?\n\n\t2.\tWhy it works?\n\nThis was the part of the analysis that had the least intuition regarding the computations, and I would greatly appreciate further clarification.\n\n\nP.S. A satisfactory response to the questions I’ve raised—especially regarding the distinctions from prior work, the modeling clarity around bandit feedback and iterate definitions, and the theoretical subtleties—could lead me to raise my score to “Strong Accept”.\n\nP.S.2 I may have asked this already, but I was genuinely surprised that the authors do not require any form of \\epsilon-greedy exploration.\nOne possible explanation is the clever anchoring step involving the term\n$(\\tau\\cdot \\eta_t) D_{\\mathrm{KL}}(m, m_0)$,\nbut I’d really like to understand how the analysis successfully avoids the need for exploration noise.\n\t•\tIs this avoidance enabled by the negative third derivative of the regularizer (e.g., $\\nabla^3 h < 0$)?\n\t•\tOr is there another mechanism or structural property of the setup that removes the need for explicit exploration? When is the assumption of the extrapolation necessary and when not?\n\nA short clarification on this point would be greatly appreciated, as it’s quite non-standard and technically impressive—if valid.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QOw7Yjy1ml", "reviewer": "Reviewer_eajt", "summary": "This paper studies the last-iterate convergence rates of uncoupled learning dynamics in two-player zero-sum games with bandit feedback. One of the main contributions of the paper are lower bounds for uncoupled learning dynamics: (1) $\\Omega(t^{-1/(2+p)})$ lower bound for any-time $\\ell_p$ last-iterate convergence rates when $p \\in (0,2]$; and (2) $\\Omega(t^{-1/4})$ lower bound for $p \\ge 2$. Then the authors propose two algorithms for the problem. The first one is a general framework that could transform the guarantee of output sequence to last-iterate convergence by simultaneously exploring or exploiting. By appling EXP3-IX, this framework gives $\\tilde{O}(t^{-1/(2+p})$ last-iterate convergence rates. The drawback of this approach is (1) it is not fully uncoupled as it requires shared randomness; (2) it still requires iterate-averaging in execution. The second algorithm uses regularization and achieves $O(t^{-1/4})$ $\\ell_2$ last-iterate convergence. However, the convergence is not any-time as the time horizon is required to choose the step size. A doubling trick fixes this issue but introduces synchronization again just like the first algorithm.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer eajt for the review and for pointing out a result that we missed in one of our references.\n\n>I think related works have been substantially discussed. The only comment I have is regarding the results in [1]. For uncoupled learning in zero-sum games, there are two results in [1] for last-iterate convergence rates measured by the duality gap: (1) $\\mathcal{O}(T^{-1/8})$ high-probability bound and (2) $\\mathcal{O}(T^{-1/6})$ bound in expectation. This paper discusses the first one but not the second one. Since the current paper focuses on last-iterate convergence in expectation, comparing the second bound in [1] would make the discussion more complete.\n\n Indeed, this $\\mathcal{O}(t^{-1/6})$ result in expectation is an unhighlighted result of [1] that we missed and that should appear in Table 1. Their result is stated for the $\\ell^1$ norm in Theorem 4 of Appendix $C$, but a slight change to the proof seems to make it hold for the $\\ell^2$ norm.\n\n>Could you explain how to derive line 682 from line 679-680? Maybe it is trivial, but I think some explanation would be helpful for the readers.\n\nThe link between the two lines is relatively direct computation-wise, but it is far from obvious and deserves more explanation. The internal randomness $\\omega$ of the two players is independent of the game by construction, which implies that $\\mathcal{D}(P_0^{\\omega},P_{\\theta^T}^{\\omega})$ is $0$. The same can be said of $a^t|z^{t-1}$ for any $t$: the policy $\\mu^t$ of the min-player is predictable with respect to $(\\sigma(z^t))$, and the action $a^t$ is sampled from $\\mu^t$ independently from the past. This implies that $\\mathcal{D}((P_0^{a^t|z^{t-1}},P_{\\theta^T}^{a^t|z^{t-1}})$ is also $0$ for all $t$.\n\nFinally, the terms of the sum come from developing the observation of the min-player given the predictable policy $(1/2+\\delta^t,1/2-\\delta^t)$ of the opponent, as explained in line 189-right of the main paper.\nThese explanations will be added to the proof.", "claims_and_evidence": "Yes. The claims are supported by proofs.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "I checked the proofs for the lower bounds and the other proofs also look fine to me.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "This paper studies the last-iterate convergence rates of uncoupled learning dynamics in two-player zero-sum games with bandit feedback. The paper's results contribute to the broad line of research in learning in games, which has recently been applied in machine learning. More specifically, uncoupled learning dynamics in games have been studied recently: [1] gives the first algorithm with $O(t^{1/8})$ high-probability last-iterate convergence and $O(t^{-1/6})$ expected last-iterate convergence; [2] generalizes this result to monotone games. The current paper provides the first lower bounds for the problem. The paper also offers new algorithms with improved convergence rates. Although strictly speaking, they are not fully uncoupled,\n\n[1] Cai, Yang, Haipeng Luo, Chen-Yu Wei, and Weiqiang Zheng. \"Uncoupled and convergent learning in two-player zero-sum markov games with bandit feedback.\" NeurIPS 2023\n\n[2] Dong, Jing, Baoxiang Wang, and Yaoliang Yu. \"Uncoupled and Convergent Learning in Monotone Games under Bandit Feedback.\" arxiv preprint, 2024", "essential_references_not_discussed": "I think related works have been substantially discussed. The only comment I have is regarding the results in [1]. For uncoupled learning in zero-sum games, there are two results in [1] for last-iterate convergence rates measured by the duality gap: (1) $O(t^{-1/8})$ high-probability bound and (2) $O(t^{-1/6})$ bound in expectation. This paper discusses the first one but not the second one. Since the current paper focuses on last-iterate convergence in expectation, comparing the second bound in [1] would make the discussion more complete.", "other_strengths_and_weaknesses": "This is a good paper. The presentation is clear and easy to follow, and the authors thoroughly explain the high-level ideas. \n\nThis paper provides the first lower bounds for uncoupled learning under bandit feedback and separate bandit feedback with full gradient feedback. These results are very interesting. \n\nThe algorithms proposed in the paper are also interesting. In particular, I appreciate that the authors distinguish \"any-time\" last-iterate convergence from convergence when the time horizon $T$ is known. Clearly, the former is stronger and the \"real\" guarantee one seeks for last-iterate convergence. The authors do a good job of clearly stating the weaknesses of both of their algorithms, which I appreciate. As the authors admit, both algorithms fail to achieve the any-time last-iterate convergence in a fully uncoupled way, yet they could yield $O(t^{-1/4})$ convergence if we allow some shared randomness.", "other_comments_or_suggestions": "Some equations may be explained in more detail. See my question.", "questions_for_authors": "1. Could you explain how to derive line 682 from line 679-680? Maybe it is trivial, but I think some explanation would be helpful for the readers.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "T9ZacpUkEP", "reviewer": "Reviewer_TkNJ", "summary": "This paper improves the lower bound for learning matrix games with bandit feedback and last-iterate convergence in the uncoupled setting from $O(T^{-1/2})$ to $O(T^{-1/4})$. The authors then propose a black-box reduction from an algorithm with the so-called “output convergence” to the last-iterate convergence, though still requiring the computation of average policies. The authors then try to fix this drawback by proposing the regularized mirror descent algorithm and a variant of it by using the doubling trick.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer TkNJ for taking the time to review our article and for the clarity suggestion. We address the concerns below.\n\n>Nevertheless, I think there is no fundamental difference between the definitions of “output convergence” and the average-iterate convergence.\n\nWe preferred to state the results and Lemma 6.1 under the assumption that $\\mathcal{A}$ has a convergence of its output, whether it comes from averaging (as in the EXP3-IX algorithm that we use) or other means. We preferred to state it this way, as the output could also come from a reweighted average for example, or by sampling uniformly at random a policy among the ones played.\n\n>Therefore, I have to say I do not think that the authors really establish an algorithm that has anytime last-iterate convergence and operates in a truly uncoupled manner, like the algorithm in [1].\n\nWhile the anytime algorithms require a common seed and are not uncoupled in the same sense as in [1], they match the definition of uncoupledness that is required for the lower bound stated in Theorem 5.1 to hold. This lower bound relies on the absence of communication \\textit{between} the iterations and does not exclude an agreement before the start of the iterations. One of the main points of the two anytime algorithms was especially to characterize the minimax rate.\n\nFurthermore, we would argue that the main weakness of Algorithm 2, the lack of anytime guarantees, is not problematic in practice. One of the main applications of last-iterate is to avoid the averaging of complex representation as explained in line 32-right, and the anytime convergence is not important for this matter.\n\n>Lemma 6.1 is a key lemma in this work and I would suggest the authors give more discussions and the proof sketch (if possible) in the paper.\n\nThe paragraphs above Lemma 6.1 provide the key point behind the lemma and can be seen as a proof sketch, we will add more quantitative arguments and re-organize the section to make it more apparent.\n\n>Besides, on the RHS of Line 302-329, the authors just introduce the design of the “regularized mirror descent” but without giving any discussions or explanations about this. Why can this kind of design enable a convergence rate of $\\mathcal{O}(1/T)$ for the Bregman divergence?\n\nWe could add that the “regularized mirror descent” algorithm can roughly be seen as applying a regular mirror descent with the regularized operator $F_\\tau$, hence the name, the two-steps update making the computation and the proof easier. This regularization makes the operator strongly monotone. Similarly to how strong convexity accelerates the convergence to the minimum, strong monotonicity makes the mirror descent convergent at a rate $\\mathcal{O}(1/T)$. We propose to add a proof sketch of Lemma 7.1 to explain how we obtain this result.\n\n>Further, what is the intuition behind the LHS of Line 336 and 338? Since \n $\\mu^0$ is a uniform distribution, I think the operation on Line 336 is equivalent to the following FTRL-style update?\n\n Indeed, the two updates are equivalent. However, the intuition between Line 336\n $$\\mu^{t} \\gets argmin_{\\mu_\\in\\Delta_A} (1-\\tau\\eta^t)KL(\\mu,\\mu^{\\tau,t}) + \\tau\\eta^t KL(\\mu,\\mu^0)$$\n is to regularize the iterates toward the uniform, to \"stabilize\" the algorithm and allow the convergence. This specific regularization is not normally present in FTRL and only appears in the above equation because of the $(1-\\eta^t\\tau)$ factor.", "claims_and_evidence": "I think some claims in this work might not be technically rigorous. Please see the weakness part below for details.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I did not check the correctness of the proof details.", "experimental_designs_or_analyses": "Not applicable.", "relation_to_broader_scientific_literature": "The theoretical findings are new. But I am still concerned about its technical values. Please see the weakness part below for details.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "**Weakness**\n1. **Theoretical Results**: In the abstract, the authors claim that they propose two algorithms to achieve the optimal rate of $O(T^{-1/4})$. However, I think this is a bit misleading and even a bit overclaimed. \n   * In Algorithm 1, if I understand correctly, the key insight is that an algorithm with “output convergence” can be translated into an algorithm with last-iterate convergence. Nevertheless, I think there is no fundamental difference between the definitions of “output convergence” and the average-iterate convergence. If an algorithm has the average-iterate convergence, then the output sequence $(\\hat{\\mu}^t, \\hat{\\nu}^t)$ can be chosen as $(\\hat{\\mu}^t, \\hat{\\nu}^t)=(\\sum_{1\\le i\\le t} \\mu_i, \\sum_{1\\le i\\le t} \\nu_i,)$, which is guaranteed to converge. This leads to at least two downsides of Algorithm 1 in this work: the two players are not fully uncoupled and it is still required to compute the average policy profile, which are also noted by the authors at the end of Section 6. \n   * To tackle the above issues, the authors propose Algorithm 2, which is indeed fully uncoupled and does not require computing the average policy profile. However, its convergence guarantee is not anytime. To further fix this issue, the authors consider equipping their Algorithm 2 with the common doubling trick, at the cost of making the algorithm coupled again.\n\n   Therefore, I have to say I do not think that the authors really establish an algorithm that has anytime last-iterate convergence and operates in a truly uncoupled manner, like the algorithm in [1]. Besides, [1] establish a high-probability convergence guarantee while the definition of the $\\ell^p$ convergence in this work only permits the convergence in expectation.\n2. **Presentation**: Some parts of this work seem to lack sufficient explanations. Lemma 6.1 is a key lemma in this work and I would suggest the authors give more discussions and the proof sketch (if possible) in the paper. Besides, on the RHS of Line 302-329, the authors just introduce the design of the “regularized mirror descent” but without giving any discussions or explanations about this. Why can this kind of design enable a convergence rate of $O(1/t)$ for the Bregman divergence? Further, what is the intuition behind the LHS of Line 336 and 338? Since $\\mu^0$ is a uniform distribution, I think the operation on Line 336 is equivalent to the following FTRL-style update?\n$$\n\\mu^t\\in \\arg\\min_{\\mu} –(1-\\tau\\eta^t)\\langle \\nabla \\psi(\\mu^{\\tau,t}), \\mu \\rangle+ \\psi(\\mu)\n$$\n\n[1] Cai et al. Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback. NeurIPS, 2023.", "other_comments_or_suggestions": "Please see the weakness part above.", "questions_for_authors": "Please see the weakness part above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper establishes a T^{-1/4} lower bound for the last-iterate convergence rate in decoupled two-player zero-sum games, improving upon the previously known T^{-1/2} bound. The lower bound construction is simple and interesting. The authors also present two algorithms that achieve matching upper bounds. As Reviewer TkNJ and eajt pointed out and mentioned in the paper, these algorithms require strong coordination between the players such as shared randomness or synchronization, so it's not as natural as previous algorithms. Nevertheless, they still satisfy the definition of decoupling. Overall, the lower bound offers a meaningful contribution to our understanding of this problem, and I think the paper could be accepted.
Decision: Accept (poster)