From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications
Authors: Yang Cai
Haipeng Luo
Chen-Yu Wei
Weiqiang Zheng
Venue: NeurIPS 2025 poster ()
Keywords: Last-Iterate Convergence
Learning in Games
Zero-Sum Games
Bandit Feedback
Online Learning
Primary area: theory

Abstract: The convergence of online learning algorithms in games under self-play is a fundamental question in game theory and machine learning. Among various notions of convergence, last-iterate convergence is particularly desirable, as it reflects the actual decisions made by the learners and captures the day-to-day behavior of the learning dynamics. While many algorithms are known to converge in the average-iterate, achieving last-iterate convergence typically requires considerably more effort in both the design and the analysis of the algorithm. Somewhat surprisingly, we show in this paper that for a large family of games, there exists a simple black-box reduction that transforms the average iterates of an uncoupled learning dynamics into the last iterates of a new uncoupled learning dynamics, thus also providing a reduction from last-iterate convergence to average-iterate convergence. Our reduction applies to games where each player’s utility is linear in both their own strategy and the joint strategy of all opponents. This family includes two-player bimatrix games and generalizations such as multi-player polymatrix games. By applying our reduction to the Optimistic Multiplicative Weights Update algorithm, we obtain new state-of-the-art last-iterate convergence rates for uncoupled learning dynamics in multi-player zero-sum polymatrix games: (1) an $O(\frac{\log d}{T})$ last-iterate convergence rate under gradient feedback, representing an exponential improvement in the dependence on the dimension $d$ (i.e., the maximum number of actions available to either player); and (2) an $\tilde{O}(d^{\frac{1}{5}}T^{-\frac{1}{5}})$ last-iterate convergence rate under bandit feedback, improving upon the previous best rates of $\tilde{O}(\sqrt{d}T^{-\frac{1}{8}})$ and $\tilde{O}(\sqrt{d}T^{-\frac{1}{6}})$.

From Average-lterate to Last-Iterate Convergence in Games: A Reduction and Its Applications
Yang Cai Yale University yang. wwweyaalleeeeeeee edu
Haipeng Luo University of Southern California haipengl @uscc edu
Chen-Yo Yu Wei University of Virginia chenyu. wornuu.weivvirginn.. edu
Weiqiang Zheng
Yale University weiqiang .aeaaag...heeeeee zhenge edu
Abstract
The convergence of online learning algorithms in games under self-play is fun- damental question in game theory and machine learning. Among various notions convergence, last-iterate convergence is particularly desirable, as reflects the actual decisions made by the learners and captures the day-to-day behavior the learning dynamics. While many algorithms are known to converge in the average-iterate, achieving last-iterate convergence typically requires considerably more effort in both the design and the analysis of the algorithm. Somewhat sur- prisingly, show in this paper that for large family of games, there exists simple black-box reduction that transforms the average iterates of an uncoupled learning dynamics into the last iterates of thus also providing a reduction from last-iterate convergence to average-iterate convergence. Our reduction applies games where each player's utility linear in both their own strategy and the joint strategy of all opponents. This family includes two-player bimatrix games and generalizations such as multi-player polymatrix games. By applying our reduction to the Optimistic Multiplicative Weights Up- date algorithm, we obtain new state-of-the-as the-art last-iterate convergence rates for uncoupled learning dynamics in multi-player zero-sum polymatrix games: (1) an O logdd last-iterate convergence rate under gradient feedback, representing an exponential improvement in the dependence on the dimension (i.e., the maximum number actions available to either player); and (2) an Ó(d last-iterate convergence rate under bandit feedback, improving upon the previous best rates of Ó(Vir-b {) and Ó(vdT- à).
uncoupled learning dynamics,
Introduction
The convergence of online learning algorithms in games under self-play is fundamental question in both game theory and machine learning. Self-play methods for computing Nash equilibria have enabled the development of superhuman Al agents in competitive games such as Go [Sil+17], Poker [Bow+15; BS18; BS19], Stratego [Per+22], and Diplomacy [FAI+22]] More recently, self-play learning algorithms have also been applied to large language model (LLM) alignment with human feedback, which can modeled as two-player zero-sum game [Mun+23; Swa+24; Ye+24; Wu+24; Liu+24; Liu+25]. From game-theoretic perspective, understanding the convergence behavior of self-play dynamics provides predictive insights into strategic multi-agent interactions and informs the design of more effective mechanisms.
Authors are ordered alphabetically.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Among various notions of convergence, last-iterate convergence is particularly desirable, as it reflects the actual decisions made by the learners and captures the day-to-day behavior of the learning dynamics. Formally, we say an algorithm has a last-iterate convergence rate of S(T) to Nash equílibria (where f(T) a decreasing function with -im S(T) = 0) if the generated sequence of strategy profiles (x*) satisfies that, for any T 2 1, the iterate x:' is an (apprrooooi Nash equilibrium. This notion of anytime last-iterate convergence is stronger than those considered in some prior works, which do not provide the same guarantee for every T,, but instead require knowing the time horizon in advance. See Section 1.1 for a detailed discussion.
Despite its importance, classical results on the convergence of self dynamics primarily concern average-iterate convergence. It is well known that when both players in a two-player zero-sum game employ no-regret online learning algorithms, the time-average of their strategies converges to a Nash equilibrium [FS99]. In contrast, a large class of online learning algorithms inclluiin Mirror Descent (MD) and Follow-the- Regllaialrr settings. Worse yet, the sequence of actual decisions made by the learners can diverge, exhibiting cyclic or even chaotic behavior IMPP18; BP18; DP18].
(FTRI.)faill to achieve last-iterate convergence in such
Aside from last-iterate convergence, another desirable property of self-play learning dynamics with multiple self-interested agents is uncoupledness [DDK11]. In uncoupled learning dynamics, each player refines their strategies with minimal information about the game, while avoiding extensive inter- player coordination (e.g., shared randomness) and communication. Uncoupled learning dynamics are also studied under the names of independent or decentralized learning dynamics [OSZ21]. They are particularly appealing in large-scale games, where either the game is high-dimensional and full information hard to obtain, or there are many players and coordination is difficult to enforce.
Due to their importance in large-scale games, designing and analyzing uncoupled learning dynamics with last-iterate convergence rates has received extensive attention recently due its importance both in theory and practice. We will review this long line of work in Section 1.1, and only point out here that achieving last-iterate convergence typically requires considerably more effort in both the design and analysis of algorithms. On the design side, techniques such as optimism and regularization are often applied to ensure convergence of algorithms like OMD and FTRL. On the analysis side, establishing last-iterate convergence rates often demands problem- problem-spccific Lyapunov functions combined with tailored arguments. This stands in stark contrast to average-iterat convergence in two-player zero-sum games, which follows directly from the no-regret property of the algorithms.
Our contribution Somewhat surprisingly, we show in this paper that for a large family of games, there exists a simple black-box reduction, A2L (Algorithm 1), that transforms the average iterates of an uncoupled learning dynamic into the last iterates of another uncoupled learning dynamic, thereby providing a reduction from last-iterate convergence to average-iterate convergence. Our reduction applies to games where each player's 's utility is linear in both their own strategy and the joint strategy of all opponents. This family includes two-player bimatrix games and generalizations such as multi-plat multi-player polymatrix games. Our reduction also works for games with nonlinear utilities but special structures such as the proportional response dynamics in Fisher markets ( (Appendix B).
Aside from its conceptual contribution, our reduction also yields concrete improvements for uncoupled learning in multi-player zero-sum polymatrix games (which include two-player zero-sum games as special cases) and leads to new state-of-the-art last-iterate convergence rates. Let d be the maximum number of actions available to each player. We apply our reduction to the Optimistic Multiplicative Weights Update (OMWU) algorithm [RS13; Syr+15], which is known achieve an Oloo d/T) weeaae--teratee convergence rate in multi-playen zero-sum polymatrix games under gradient feedback. As a result, our reduction yields uncoupled learning dynamics, A2 L-MWUU that enjoys an (log d/ d/T) last-iterate convergence rate under gradient feedback. This represents an exponential improvement in the dependence on compared to the best previously known (poly(d))T) rate [CZ23b]. As an additional consequence, each player using L- incurs only Ollog dllog T) dynamic regret.
We further extend reduction to the more challenging setting where only bandit feedback, rather than full gradient feedback, is available. To this end, we design a new algorithm, A2L-OMWU-Bandit (Algorithm 2), which augments the reduction with utility estimation procedure. We show that A2 A2L-OMMU--Band t achieves a O(T-1/5) last-iterate convergence rate with high probability. This result improves upon the previously best known rates of Ö 1/8) (high probability) and Ö(T-1/6) (in expectation) established in [Cai+23] for the special case of two-player zero-sum games.
2

---

1.1 Related Works
There is a vast literature on the regret guarantee and last-iterate convergence of learning algorithms in games, Here, we mainly review results applicable to two-player zero-sum games. For convergence under other conditions, such as strict equilibria and strong monotonicity, we refer readers to [GVM21; JLZ24; Ba+25] and the references therein.
Individual Regret Guarantee for Learning in Games While @(vT) regret is fundamental for online learning against adversarial loss sequences, improved regret is possible for multi-agent learning in games. Starting from the pioneer work of [DDK11], a long line of works propose uncoupled learning dynamics with O(1) regret in zero-sum games [RS13] and more generally variationally stable games [HAM21], and ((poly(log TT) (swap) regret even in general-sum normal- form games [DFG21; Ana+22a; Ana+22b; SPF25] and Markov games [Cai+24b; Mao+24). However, guarantees for the stronger (worst-case) dynamic regret remain underexplored. It is worth noting that in the adversarial setting, achieving even sublinear dynamic regret impossible. As corollary of our (log d I last-iterate convergence rate, A2L-OMWU guarantees that each player suffers only Ologg d log I') dynamic regret, an exponential improvement on the dependence on d [CZ23b].
Last-Iterate Convergence with Gradient Feedback Two classic methods that exhibit last-iterate convergence are the Extra Gradient (EG) algorithm [Kor76] and the Optimistic Gradient (OG) algorithm [Pop80], which are optimistic variants of vanilla gradient descent. Both algorithms are known to converge asymptotically in the last iterate, but their convergence rates remained open until recently, highlighting the challenge of analyzing last-iterate convergence rates. [Wei+21] established problem-dependent linear convergence rates for OG. Tight O(I/VT) last-iterate convergence rates for both EG and OG were subsequently established by [COZ22; GTG22], matching the lower bounds from [Gol+20; GPD20].
Although the O(1/VT) rate is tight for EG and OG, these algorithms not optimal among first-order methods. By leveraging anchoring- bbased acceleration techniques from the optimization literature [Hal67], accelerated versions of EG and OG have been proposed to achieve an (11/T) last-iterate convergence rate [Di220; YR21; C723b; C723a; CO724]. This matches the lower bounds for all first-order methods [OX21; YR21J. We note that all these results incur poly(d) dependence. In contrast, our algorithm achieves exponentially better dependence on d.
In addition to optimism, regularization is another effective technique for achieving last-iterate convergence. By adding a regularization term, the original game becomes strongly monotone, enabling standard gradient-based algorithms to achieve linear last-iterate convergence-alleet on the modified game. Setting the regularization strength to O(e) yields an iteration complexity of (log(1/e))/ for computing an e-approximate Nash equilibrium (CWC21: CWC24], corresponding to an (logT/TT convergence rate. However, this approach has key limitations: it requires calibrating the regularization strength based on the total number of iterations T, and the resulting convergence guarantee applies only to the final iteration. It does not satisfy the stronger criterion of anytime last- iterate convergence. This distinction is crucial: without the anytime guarantee, a trivial workaround exists-one can run any no-regret algorithm for T 1 steps and output the average iterate at step T. Moreover, only anytime guarantees give individual dynamic regret guarantees.
While a diminishing regularization schedule does yield anytime last-iterate convergence, it leads to a slower convergence rate O(T-1/4) rate [PZO23]. With an additional assumption on the regularized Nash equilibrium, [ZDR22] obtained a (T/3 last-iterate convergence rate. One might wonder whether more aggressive schedules, such as the doubling trick, could improve this. However, it remains unclear whether such methods guarantee true anytime convergence." In contrast, our algorithm achieves anytime last-iterate convergence without requiring prior knowledge of the time horizon, and it attains the optimal O(1/T) rate, eliminating the extra logarithmic factor.
We also remark that there is a line of work on last-iterate convergence under noisy gradient feed- back [Hsi+22]. [ASI22; Abe+23; Wu+25] design algorithms based on perturbation and show last-iterate convergence to a stationary point near Nash equilibrium in both gradient and noisy
'[Liu+23] uses the doubling trick to establish Ö(T-1) last-iterate convergence rate for the output policy of the algorithm (which generally differs from the day-to-day policy the players use to interact with each other). This is a weaker notion of last-iterate convergence than the one considered in this paper. which concerns the convergence of the day-to-day policy.
3

---

gradient feedback. [Abe+23] also show asymptotic convergence to an exact Nash equilibrium by adaptively adjusting the perturbation. For non-asymptotic convergence rates, [Abe+24] establish Ó(T-1/10) last-iterate convergence rate, which improved O(T-1/7) by [Abe+25] recently.
Last-Iterate Convergence with Bandit Feedback Compared to gradient feedback, achieving last-iterate convergence under bandit feedback (i.e.. payoff-based feedback) significantly more challenging and remains less understood. [Cai+23] provides the first set of last-iterate convergence results for uncoupled learning dynamics in two-player zero-sum (Markov) games. They propose mirror-dexccnt-basse algorithms that achieve a higb-probabilityy convergence rate of (TT-1/8) and rate of ((T-1/6) in expectation. Concurrently, [Che+23; Che+24] introduce best-response-basee algorithms with an expected ((T-1/8) last-iterate convergence rate. A follow-up work [DWY24] presents extensions to general monotone games. Our work improves upon these results by achieving a probbbibbyyyllity 1/5) rate, and our guarantees extend to the more general setting of multi player zero-sum polymatrix games.
Last-Iterate Convergence of OMWU The Optimistic Multiplicative Weights Update (OMWU) algo- rithm [RS13; Syr+15] is fundamental algorithm for learning in games. It achieves an O(1 average-iterate convergence rate in two-player zero-sum games and guarantees (log individ- ual regret even in general-sum games [DFG21; Ana+22a; SPF25]. For last-iterate convergence in two-player zero-sum games, [DP19; HAM21] establish asymptotic convergence of OMNU, and [Wei+21] proves problem-dependen linear convergence rate under the assumption of unique Nash equilibrium. However, for worst-case uniform last-iterate convergence convergence-withour -without relying on problem-dependent constants [CCai+44a] recently proved an (1(1) lower bound, showing that OMWU's last-iterate convergence can be arbitrarily slow.
2 Preliminaries
Notations We denote the d-dimensional probability simplex as A = fo R : 0 S S
Dd 24 1).
The uniform distribution in A is denoted as Uniform(d).
2.1
Games
An n-player game G ([n), (23), {ui}) consists of n players indexed by [ni] == {1, 2, .n.....,.... Each player selects strategy I; from closed convex set X; Rdd We refer to == max d; as the dimensionality of the game. Given strategy profile
(I,, I-;), player i receives utility (x(x) E [0, 1]. A game is in normal-form if each player has a finite number of d; actions and given an action profile
(a,, a-), the utility for player i is u; (a). In normal-form games, the strategy set for each player u is the probability simplex 2; = Ad; and given a strategy profile the expected utility for player i is Eviejn) av (ai,...., ).
We focus on games with linear utilities.
Assumption 1. A game G has linear utilities for each player i,
the utility function un (2., -i) is linear in x; X,
* the function in (Z4, is linear in x= E XjtiKz.
For such games, we define u4(-, 211 E Id be the unique vector such that u((x) (z,, x=)) We remark that Assumption is weaker than assuming us (z) is linear in the whole strategy profile I E X,X, As an example, the bilinear function u(x1, = II Axz satisfies Assumption since it linear in 3 and also linear in x2, but it is not linear (21, This structure includes several important game classes:
Example (Two-Player Bimatrix Games). There are two players: the x- æ-player chooses mixed strategy x E Ad, and the y-player chooses y E dd Let A, B E Rd xd2 be the payoff matrices. The x-player's utility is (xr(x,))) v) x=1 Ay, and the y-player's utility is uy uy(x,, y) x= By. Two-player bimatrix games satisfy Assumption I due to the bilinear structure of the utilities. A two-player zero-sum game is special case where A + B B=
Example 2 (Multi-Player Polymatrix Games). Polymatrix games [Jan68; How72) generalize himatrix games to multiple players by introducing networked interactions. The players form the vertices of

---

graph G = ([n),), E), where each edge (i.5) E E represents two-player bimatrix game between players and j with payoff matrices A1, and A, Each player selects a strategy from A and plays the same strategy against all neighbors. Given a strategy profile I E x; Ad player i's utility is defined as Ljs(ss)er." x. Jz A zero-sum polymatrix game [CD11; Cai+ 16] a special case where the total utility sums to zero, Le., Dis (x(x) = for any strategy profile x.
Nash Equilibrium and Total Gap An E-approximate Nash equilibrium of G is strategy profile I E X such that no player i can deviate from Iy and improve her utility by more than & > 0,
u (, 2 u,(2), E, E [m], Val E X₁
When = 0, the strategy profile is Nash equilibrium. We note that games with linear utilities have at least one Nash equilibrium [Nas50]. Given strategy profile I, we use the total gap to evaluate its proximity to Nash equilibria. Specifically, we define TGAP(z) == En=1 (max;;ex; u, u,(z), - ux(x)). We note that by definition, if TGAP(z) S s, then æ is an e-approximate Nash equilibrium. In two-player zero-sum games, the total gap is also known as the duality gap.
2.2 Online Learning
Online Learning and Regret In an online learning problem, a learner repeatedly interacts with the environment. At each time f 2 1, the learner chooses an action x' from closed convex set X' while the environment simultaneously selects a linear utility function. The learner then receives a reward w'(x') == (u', x²) and observes some feedback. We focus on the gradient feedback setting, where the learner observes u²; the more restricted bandit feedback setting is studied in Section 5.
The goal of the learner is minimize the (external) regret, the difference between the cu- mulative utility and the utility of the best fixed action in hindsight, defined as Reg(T) == maxxex Et= (x) El= n' (x"). An online learning algorithm is no-regret if its regret is sub- linear in T. that is, Reg(T) = o()). ). We note that classic results show that Reg(T)) = O(VT) can be achieved and cannot be improved when utilities are chosen adversarially.
A stronger notion of regret is the (worst-case) dynamic regret [Zin03], which competes with the utility achieved by the best actions in each iteration, defined as DReg(T) (T) := Σ max (x(x) Eis u'(x"). We remark that when utilities are chosen adversarially, it is impossible to achieve sublinear dynamic regret, that is, DReg(T) (TT)).
Convergence of Learning Dynamics For multi-agent learning dynamics in games, each player uses an online learning algorithm to repeatedly interact with other players. At each time t, player chooses strategy æd; gets utility u; (*f, ,' and receives the utility vector vf == us( wa(,,x")) as feedback. For any T 2 1, we denote the average iterate as . = (क .......... I,,) where ..- = 4 E wt, and each player i's individual regret as Reg, (T). We show that the average iterate n"' T -t=1 x² has total gap bounded by + > (T)) for zero-sum polymatrix games (a generalization of the classic result of [FS99] for zero-sum bimatrix games). Thus, as long as each player has sublinear regret, average-iterate convergence Nash equilibria is guaranteed. The proof is in Appendix A.
-Average-Iterate Iterate Convergence by Bounding Regret). Let {x'} be the iterates of an online learning dynamics in zero-sum polymatrix game. Define :" + Σ x' to be the average iterate for all T 2 1. Then the total gap of the average iterate ह" for any 2 1
Lemma (Average-
(GAP(*")
max TEXA4
Σ uel - -
1 T Σ
(T).
However, the convergence of the average-iterate sequence (=') does not imply the convergence of the last-iterate (x*), which is the real strategy played by the agents. Even worse, many online learning algorithms diverge and exhibit cycling or chaotic behavior even in simple two-player zero-sum games [MPP18; BP18; DP18].
Optimistic Multiplicative Weights Update (OMWU) The OMWU algorithm [RS13; Syr+15] is an optimistic variant of the classic Multiplicative Weights Update (MWU) algorithm [AHK12] with
5

---

the only modification that the most recent utility observation is counted twice. In each time 2 OMWU with steps size r7 > 0 chooses the strategy x' A be
1 b(())
x' argmax
u 1
where we define v² := 0 and Φ is the negative entropy regularizer. The OMWU updates also admits closed-form expression:
exp Ence u" + ut (t])) Σj=1 exp (n(Er ut [i] + ut (D)
Vi E [d]
OMWU has been extensively studied in the online learning and game theory literature [RS13; Syr+ Das+18 18; CP20; Wei+21; DFG21; Cai+24a; SPF25], with state-of-the-ar individual regret guarantees in zero-sum games and general-sum games. We will use the regret bounded by variation in utility (RVU) property of OMWU throughout the paper.
Theorem (Proposition [Syr+15]). The regret of OMWU for sequence of utilities {u²} satisfies
Reg (7) = max
Σ (u x²) t=1
logd
T + Σ | - 11
T
1st I1?
AE
An
[=1
Lemma (Adapted from Theorem of [Syr+15]). In a n-player normal-form game, let x and x' be s (n 1)2 Σi= || - 2!ll
two strategy profiles. Then Ei=1 (u((;==s)) -
Reduction From Last-Iterate to Average-Iterate
In this section, introduce black-box reduction that transforms any online learning algorithm into a new one such that, when employed in a game with linear utilities (Assumption 1), the produced iterates exactly match the averaged iterates produced by the original algorithm.
Specifically, consider an n--paaer game 9, where each player employs an online learning algorithm R, and generate iterates {ě*), J. We propose reduction, A2L (Algorithm 1), and let each player i employs A2 (R.) generating new sequence (F'). We show that for any 2 1. D' 1==1 =;: that is, the last iterate of (x*) equals the running average of (
The intuition of the reduction is as follows. Given any algorithm R, A2L(R) runs R subroutine and gets strategy x' in every iteration t. We note that the sequence {x*) is produced internally in the reduction and not played by the players. A2L(R) plays the averaged strategy 3' Ei= x* and gets the gradient feedback पº. To show that the last iterate of (I') equals the running average of (ā'), it suffices to prove that ge = x². The next step is the key observation: when all players employ this reduction and play the running average, they can recover/extract the unseen utility vector u' w (+,x²) x²) under strategy æ! (which is not played) by the identity w' Lt (I 1)za" which holds due to the linearity of the utility (Assumption 1). Then A2I(R) forwards this recovered utility R. Since R receives the same utilities when played alone or as subroutine in A2L(R). we can conclude
that the iterates { equal the internal iterates of {z*}. Thus F' "i_ x² = E & A formal proof using induction is provided later in this section. We also provide an illustration of the A2 L reduction for two-player zero-sum game max, min, Ay (Example 1) below, where we use the subscripts æ and y to denote the corresponding quantities for the two players.
Ag
+++
Rx
Average
Extract
Rx
11
A
yf+1
Ry
Average
Extract
Ry
A2L: Black Box
A key feature of this reduction is that it preserves uncoupledness: each player only observes their own utility, without access to other players' strategies, or any form of communication shared randomness.

---

Algorithm 1: A2L: Black-Boy Reduction from Average to Last-Iterate
Input: An online learning algorithm R.
for 1 = 1.2,.... ..2...., do
Get x from R
Play x² = Ek= x² and receive o' b Play the running average iterates
3
Compute u' 1 t.u' - - w Recover the unseen utility
Forward utility u' R
Theorem 2. Consider any n-player game 9 that satisfies Assumption 1). Let { : E [n], (T]} be the iterates generated by each player running R, and let { [m], t [T] be the iterates generated by running A2L (R.). Then for all i E [n] and E [T]. we have क. = Σi= at.
Proof of Theorem 2. Note that A2L (R:) uses R; subroutine. Let {a{) denote the strategies produced by R, during the execution of A2L (R,). By Line 3, we have o Ei= at Vi
[n], [T]] Hence, it suffices to show that 2 = o for all i [n], e [T].
We prove this by induction on t. Let the induction hypothesis be: for all & < t and all E [n]] we have x. = t and u = ua(,,=;;)
Base Case:
1. Initialization ensures x i! for all e [n]. By Lines and 4, we also have u = पH uu(, _ u,(, x-,) = (.(,,1,))
Induction Step: Suppose the hypothesis holds for t. Then for all & S t and i E [n]]. we have uf = x=,,,==,))) = (. a-+) Since R,'s output at time I + 1 depends only on the sequence (u/)igka get x; x af+1 for all i.
At time / + each player i in A2L (Rt) plays 2/+1 the utility vector
Et k= s..
Then each player receives
74I
1
u Us
u x
(by linearity of u, (Assumption 1)).
t +
t
t+1
Then, ui (+ 1) w. 1= the induction hypothesis holds for +1
ut
E Uz( uz(,,
Ei u4(, x1)) Thus,
By induction, x o for all i and f, and so .. = 1 Σl
Ek_ #/.
Discussion on Limitations We discuss some limitations of our reduction compared to existing algorithms with last-iterate convergence guarantees, such as Extra Gradient (EG), Optimistic Gradient (OG), and their variants. Our reduction relies on the linear utility assumption (Assumption 1), which includes important classes of games such as multi-player polymatrix games, but does not extend to settings with concave utilities- such as convex-concave min-max optimization whhere EG and OG are known achieve last-iterate convergence [COZ22]. Moreover, since our approach reduces last-iterate convergence to average-iterate convergence, it inherently requires computing the running average of iterates. contrast, algorithms like EG and OG do not involve such averaging procedures. Nonetheless, our reduction offers a simple and broadly applicable method for achieving last-iterate convergence in games with linear utilities, and it yields tfatc-of-the-an convergence rates under both gradient and bandit feedback settings (see Sections 4 and 5).
Extension Games with Nonlinear Utilities The core idea of A2L reduction lies in extracting the unseen feedback of u from the observed feedback n', for which Assumption 1 is sufficient but not necessary. For example, in Appendix B, we show that A2L is also applicable to Proportional Response Dynamics (PRD) in Fisher markets where Assumption 1 does not hold. We obtain ((1/T) last-iterate convergence rate for PRD markets with Gross Substitutes utilities, improving [CCT25] which only shows an average-iterate convergence. We defer detailed background on Fisher market and discussion on why A2L works to Appendix B. We believe that there are other similar examples where A2L applies even without Assumption 1.
7

---

Comparision with [Cut19] Our work is related to [Cut19], which proposes reduction called anytime milin-ttobbttll (AO2B) and achieves last-iterate convergence in offline convex optimization. While our A2I reduction and the AO2B reduction share the idea of playing the average of previous iterates, they differ significantly in several key aspects:
AO2B is designed for static optimization, where the loss function remains fixed across rounds. A2T, on the other hand, applies dynamic multi-agent game setting, where each player's loss function changes over time due to the changing actions of other players.
Problem setting:
A02B aims to solve single offline optimization problem with improved convergence rates and does not guarantee equivalence between the last iterate of the new learning algorithm and the average iterate of the original algorithm (since the gradient feedbacks are different). In contrast, A2L L aims to establish the equivalence between the last iterate of the new dynamics and the averaged iterate of the original dynamics.
Objective:
Use of gradient: In AO2B, the learner updates directly using the gradient at the average iterate r' = - x. In contrast, A2L requires post-pree proccesccsssing the gradient feedback to recover the true gradient at the original iterate x², as shown in Line 4 of Algorithm
Weighted Version of A2L The A2L reduction naturally extends to the weighted averaging setting, provided all players agree on the weights {as} in advance and incorporate them into the reduction. More specifically, in each iteration i, each player plays the weighted average of their past iterates
o Σi= 0g Ek=1 agaa Due the linearity of utilities, the gradient feedback can still be used to
recover the gradient corresponding to the original iterate æ² and the A2L reduction in Algorithm 1 is the special case of {a, = 1}. As result, the last iterate of the new dynamics corresponds to the weighted average in the original dynamics. The correctness follows the same steps as in Theorem 2. This weighted version of A2L provides additional flexibility and can be beneficial in practice. For example, for regret matching [Tam14], an algorithm widely used for solving large-scale games like poker [BS18; BS19], linear averaging (i.e., 0z = t) often empirically outperforms uniform averaging. despite having the same theoretical rate.
4 Learning in Zero-Sum Games with Gradient Feedback
In this section, we show that our reduction gives uncoupled learning dynamics with improved last-iterate convergence rates in two-player zero-sum games and zero-sum polymatrix games.
We apply our reduction to the Optimistic Multiplicative Weights Update (OMWU) algorithm, which has been extensively studied in the literature [RS13; Syr+15; Das+ CP20; Wei+21; DFG21; Cai+24a; SPF25]. For d-dimensional two- two-player zero-sum games, while recent result [Cai+24a] shows that OMWU's last-iterate convergence can be arbitrarily slow, it is well-known that OMWU achieves an O lo average- iterate convergence rate [RS13]. Now let us denote the algorithm after A2L reduction as A2L-OMNU. By Theorem 2 and Lemma 1, we get O(log d. T-1) last-iterate convergence rate result of A-LOOMWU (Theorem 3). As corollary of our fast last-iterate convergence rates, A2L-OMWU also guarantees that each player's individual dynamic regret is only O(log d log T). Missing proofs in this section are in Appendix C.
Theorem 3. Let (H²) } be the iterates of A2I-OMWU learning dynamics in an n-player zero-sum polymatrix game with step size 1) S 1[= Then any T 1, Jf an E log d, of
aapproximate
Nash equilibrium.
Corollary 1. In the same setup as Theorem for any player i E [m]. DReg." 0 Ei log d. log T').
To our knowledge, results give the fastest last-iterate convergence rates for learning in zero- sum games. Compared to the accelerated optimistic gradient (AOG) algorithm [CZ23b] which has ((P)) T last-iterate convergence rates, our results achieves the same optimal 7 dependence while improve exponentially on the dependence on the dimension d. Compared the entropy regularized extragradient algorithm [CWC21; CWC24), which achieves O ((oRd]o8TT) last-iterate convergence rate, our results do not require regularization and shave the log T factor. Moreover, our results and those of [C7.23b] are stronger anytime convergence results that holds for every iterate 2 1, while results in [CWC21; CWC24] hold only for the final iterations and require knowing the total number
8

---

of iterations T in advance for tuning the regularization parameter (as mentioned in Section 1.1, trivial solution exists for such weaker guarantees), thus with no dynamic regret guarantee.
Robustness against Adversaries In the case where other players are adversarial and may not ensure sublinear regret for the player.
follow the A2I-OMWU algorithm, simple modification Specifically, the player can track their cumulative utilities and regret to time T', and if the regret exceeds (loog I') - whhic cannot happen if all players follow A2I-OMWU -hey can switch standard no-regret algorithm that guarantees O O(VT) regret the worst case.
Learning in Zero-Sum Games with Bandit Feedback
In this section, we show the application of our reduction for uncoupled learning dynamics in zero-sum games with bandit feedback. Unlike the gradient feedback setting, where each player observes the utility of every action, the bandit feedback setting is more realistic and much harder. Specifically, consider the following uncoupled interaction protocol: in each iteration
Each player maintains mixed strategy st A de and plays action of ~ aaf;
Each player i then receives number u; (aa") as feedback.
Importantly, a player only observes the utility one action but not the whole utility vector. Also, player does not observe the actions/strategies of other players.
Algorithm Design Ideally, we would like have bandit learning dynamics whose last iterates are the average iterates of another bandit learning dynamics. This would give a OT b) last-iterate convergence rate since bandit algorithms have ((VT) regret. However, the lack of utility vector feedback prevents from directly applying A2L reduction since
no longer use the linearity to recover the original utility when other players use the averaged strategies. To overcome this challenge, design A2 L-OMWU-Bandl (Algorithm 2), where in addition A2 L,, add for estimating the utility vector from bandit feedback. With sufficiently accurate estimation of the utility vector, then use A2L in the gradient feedback setting.
component
Algorithm 2: A21--MMUU--addit OMWU with bandit feedback and A2L reduction (for player
Parameters: Step size 1) 0, (B, --== [1}
2 Initialization: zi < Uniform(d:)) 0 =
for t 1.2..... do
x + + The - (1 e.) + Uniform(()
Sample actions from æf_e for B, rounds and compute 0 as an estimate of ui,e based on (1)
Computed estimated utility it + t - - (t-1) 01-1
7
Update using OMWU: x + argmax { (xr, Exse o + ( -
Estimation To estimate the utility vector when each player only observes the reward after taking an action, we let the each player their current strategy to interact with each other for sequence of B, rounds and then use the bandit feedback to calculate an estimated utility (Line 6). Let us denote the sampled actions
the B, rounds {a+ {at,.... fat,....,_* a..,, and the corresponding bandit feedback as BB .B). We use the following simple estimator for the utility vector:
(r_,...,, r....,,Brrrr
Σk= Iaa a)
O [a] [
Va.
D I[a = a]
To encourage exploration, we also mix the strategy with e, amount of uniform distribution (Line 5) to ensure that every action receives sufficient samples in each epoch.
Last-Iterate Convergence Rate In Algorithm 2, each iterate { J is repeated B, times within epoch
t. We will show that this sequence { enjoys Ö(t-1) last-iterate convergence rate. Let {5*}

---

denote the actual iterates executed by the players in every round k, which remains the same in each epoch. When B, = d t², we get the following Odt k- last-iterate rate of {v*). If the maximal number of actions is unknown to the players in a fully uncoupled setting, we can choose B, = t* and get an (dk -) convergence rate.
Theorem 4. Consider an n-player zero-sum polymatrix game and denote d == max d, Ler {y²} be the iterates generated by all players running A2I-OMWU-Rande t with n S a then for any & E (0, 1), with probability least ( 8), ) for any k 2 1, y² is an 3y-approximate Nash equilibrium with
log 2 (
dk dbk when Br = d. or By =0 o n nnlog
3x =
dk when Br = tt.
7
"
To our knowledge, Ö b) is the fastest last-iterate convergence rate of uncoupled learning dynamics in zero-sum polymatrix games, improving the previous Ö(T 3) (high--robability) and Ö(T=)) b)
(expectation) rates for two-player zero-sum games [Cai+23].
Technical highlight The main challenge in analyzing the last-iterate convergence rate of Algorithm 2 lies in handling the estimation error. Let A = Ü Th,s denote the estimation error from Line 6. A naive analysis leads to summation of first-order error terms, o [| which results in suboptimal ((T7)/7) rate. To improve this, we introduce a refined analysis that carefully balances the error terms with the negative terms in the RVU inequality (Theorem 1), resulting in a summation of second-order error terms, O ||! (see Lemma 3). This sharper analysis ultimately yields an improved O(T51/5) convergence rate. The full proof provided in Appendix D.
Discussion Our results also reveal an intriguing distinction between the gradient and bandit feedback settings. In the gradient feedback case, while our reduction improves the dependence the dimension d, it achieves the same O convergence rate as existing algorithms such as the accelerated optimistic gradient (AOG) algorithm [CZ23b]. This might suggest that applying a similar utility estimation procedure to AOG would also yield O(75) rate under bandit feedback. However, the analyses of these two types of algorithms diverge significantly in the presence of estimation error:
For AOG, establishing last-iterate convergence requires proving the (approximate) monotonicity of a carefully designed potential function at every iteration. This sensitivity to estimation error leads to error propagation and ultimately slower rate: we did not manage to get rate faster than ((T-1/8) [Cai+23]. In contrast, our reduction-by transforming last-iterate convergence into average-iterate convergence onnlerrence-onlyyeeee requires analysis on the regret, which simpler, less sensitive, and gives the improved O(7-1/5) rate. This suggests an advantage of our A2L reduction over existing algorithms in the bandit feedback setting. Nevertheless, it remains interesting open question whether one can design uncoupled learning dynamics with fast convergence rates in the bandit feedback setting using existing algorithms like AOG without relying on the A2L reduction.
Robustness against Adversaries When facing possibly adversarial opponents who may not follow Algorithm 2, the player could still guarantec sublinear regret by running Algorithm 2 with an additional regret estimation procedure. Whenever the player detects that her regret is --icch can not happen when all the players employ Algorithm 2-she can switch to a standard bandit algorithm with optimal regret. This modification guarantees Ö(Tš) regret in the worst-case. We present the regret estimation procedure and the proof in Appendix E.
Conclusion
In this paper, we give a simple black-box reduction, A2L, that transforms the average iterates of an uncoupled learning dynamics the last iterates of a new uncoupled learning dynamics. By A2L reduction, we present improved last-iterate convergence rates of uncoupled learning dynamics in zero-sum polymatrix games: (1) O(log d T- rate under gradient feedback, and (2) Ö b) rate under bandit feedback. It is an interesting future direction to explore further applications of the A reduction for learning in games. Other directions include designing uncoupled learning dynamics for more general games like Markov games and time-varying games with faster last-iterate convergence rates under bandit feedback.
10

---

Acknowledgement
We thank the anonymous NeurIPS reviewers for constructive comments. We also thank Arnab Maiti and Nathan Monette for comments on typos and minor errors in the previous version of the paper, which helped us improve the paper. YC supported by the NSF Awards CCF-1942583 (CAREER) and CCF-2342642. HI. is supported by NSF award I19-1943607. WZ. is supported by the NSF Awards CCF- 1942583 (CAREER), CCF-2342642, and Research Fellowship from the Center for Algorithms, Data, and Market Design at Yale (CADMY).
References
[Abe+23]
Kenshi Abe, Kaito Ariu, Mitsuki Sakamoto, Kentaro Toyoshima. and Atsushi Iwasaki. "Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Games". In: International Conference Artificial Intelligence and Statistics. PMLR.
2023, pp.
[Abe+24] Kenshi Abe, Kaito Ariu, Mitsuki Sakamoto, and Atsushi Iwasaki. "Adaptively Perturbed Mirror Descent for Learning in Games". In: International Conference Machine Learning. PMLR. 2024, pp. 31-80.
[Abe+25] Kenshi Abe, Mitsuki Sakamoto, Kaito Ariu, and Atsushi Iwasaki. "Boosting Perturbed Gradient Ascent for Last-Iterate Convergence in Games". In: The Thirteenth Interna- tional Conference on Learning Representations 2025.
[AHK12] Sanjeev Arora, Elad Hazan, and Satyen Kale. "The multiplicative weights update method: meta-algorithm and applications". In: Theory of computing 8.1 (2012), pp. 121-164.
[Ana+22a] Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Noah Golowich, and Tuomas Sandholm. "Near-optimal no-regret learning for correlated equilibria in multi- mullti-paayrr general-sum games". In: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC). 2022.
[Ana+22b] Ioannis Anagnostides, Gabriele Farina, Christian Kroer, Chung- Wei Lee, Haipeng Luo, and Tuomas Sandholm. "Uncoupled Learning Dynamics with O T) Swap Regret in Multiplayer Games". In: Advances in Neural Information Processing Systems (NeurIPS). 2022.
[AS122] Kenshi Abe, Mitsuki Sakamoto, and Atsushi Iwasaki. "Mutation-driven follow the regularized leader for last-iterate convergence in zero-sum games". In: Uncertainty in Artificial Intelligence. PMLR. 2022, pp. 1-10.
[Ba+25]
Wenjia Ba, Tianyi Lin, Jiawei Zhang, and Zhengyuan Zhou. "Doubly optimal no-regret online learning in strongly monotone games with bandit feedback". In: Operations Research (2025).
[BDX11]
Benjamin Birnbaum, Nikhil R Devanur, and Lin Xiao. "Distributed algorithms via gradient descent for Fisher markets"' In: Proceedings of the 12th ACM conference on Electronic commerce. 2011, pp. 127-136.
[Bow+15]
Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. "Heads-up limit hold em poker is solved".. In: Science 347.6218 (2015), pp. 145-149.
[BP18]
James P Bailey and Georgios Piliouras. "Multiplicative weights update in zero-sum games". In: Proceedings of the 2018 ACM Conference on Economics and Computation. 2018, pp. 321-338.
[BS18]
Noam Brown and Tuomas Sandholm. "Superhuman AI for heads-up no-limit poker: Libratus beats top professionals.. In: Science 359.6374 (2018), pp. 418-424.
[BS19]
Noam Brown and Tuomas Sandholm. "Superhuman AI for multiplayer poker"". In: Science 365.6456 (2019), pp. 885-890.
[6ai+16]
Yang Cai, Ozan Candogan, Constantinos Daskalakis, and Christos Papadimitriou. "Zero- sum polymatrix games: A generalization of minmax". In: Mathematics of Operations Research 41.2 (2016), pp. 648-655.
[Cai+23] Yang Cai, Haipeng Luo, Chen-Ya Yu Wei, and Weiqiang Zheng. "Uncoupled and con- vergent learning in two-player zero-sum markov games with bandit feedback". In: Advances in Neural Information Processing Systems 36 (2023), pp. 36364-36406.

---

[Cai+24a]
Yang Cai, Gabriele Farina, Julien Grand Clément, Christian Kroer, Chung- Wei Lee, Haipeng Luo, and Weiqiang Zheng. "Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms". In: The Thirly-eighth Annual Conference on Neural Information Processing Systems. 2024.
[Cai+24b] Yang Cai, Haipeng Luo, Chen- Yu Wei, and Weiqiang Zheng. "Near-optimal policy optimization for correlated equilibrium in general-sum markov games" In: International Conference on A Artificial Intelligence and Statistics. PMLR. 2024, pp. 3889-3897.
[CCT25]
Yun Kuen Cheung, Richard Cole, and Yixin Tao. "Proportional Response Dynamics in Gross Substitutes Markets". In: Proceedings of the 26th ACM Conference on Economics and Computation. 2025, pp. 389-389.
[CD11]
Yang Cai and Constantinos Daskalakis. "On minmax theorems for multiplayer games". In: Proceedings of the twenty-second ammual ACM-SIAM symposium on Discrete algo- rithms (SODA). 2011.
[Che+23]
Zaiwei Chen, Kaiqing Zhang, Eric Mazumdar, Asuman Ozdaglar, and Adam Wierman. "A finite-sample analysis of payoff- based independent learning in zero-sum stochastic games". In: Advances Neural Information Processing Systems 36 (2023), pp. 75826- 75883.
[Che+24] Zaiwei Chen, Kaiqing Zhang, Eric Mazumdar, Asuman Ozdaglar, and Adam Wier- man. "Last-Iterate Convergence Payoff- Independent Learning in Zero-Sum Stochastic Games". In: arXiv preprint Sitiv:2409.01444 (2024).
[CO722] Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. "Finite-Time Iter-eterate Con- vergence for Learning in Multi-Player Games". In: Advances in Neural Information Processing Systems (NeurIPS). 2022.
[CO724) Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. "Accelerated algorithms for constrained conconvex-nonconee
min-max optimization and comonotone inclusion". In: Proceedings of the 4 ssst International Conference on Machine Learning. 2024, pp. 5312-5347.
[CP20]
Xi Chen and Binghui Peng. "Hedging in games: Faster convergence of external and swap regrets". In: Advances in Neural Information Processing Systems (NeurIPS) 33 (2020), pp. 18990-18999
[Cut19]
Ashok Cutkosky. "Anytime online-to-batch optimism and acceleration". In: Interna- tional conference machine learning. PMLR. 2019, pp. 1446-1454 1454.
[CWC21]
Shicong Cen, Yuting Wei, and Yuejie Chi. "Fast policy extragradient methods for competitive games with entropy regularization". In: Advances in Neural Information Processing Systems 34 (2021), pp. 27922-22222 279644.
[CWC24] Shicong Cen, Yuting Wei, and Yuejie Chi. "Fast policy extragradient methods for com- petitive games with entropy regularization". In: Journal of machine learning Research 25.4 (2024). pp. 1-48.
[CZ23a]
Yang Cai and Weiqiang Zheng. "Accelerated Single-Call Methods for Constrained Min-Max Optimization", en. In: Proceedings of the 11th International Conference Learning Representations. Feb. 2023.
[CZ23b]
Yang Cai and Weiqiang Zheng. "Doubly optimal no-regret learning in monotone games". In: International Conference on Machine Learning. PMLR. 2023, pp. 3507-3524. Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. "Train- ing GANs with Optimism." In: International Conference on Learning Representutions (ICLR). 2018.
[Das+18]
[DDK11]
Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim. "Near-optimal no- regret algorithms for zero-sum games". In: Proceedings of the owenty-second annual ACM-SIAM symposium on Discrete Algorithms. SIAM. 201 pp. 235-254.
[DFG21]
Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. "Near-optimal no- regret learning in general games". In: Advances Neural Information Processing Systems (NeurIPS) (2021).
[Dia20]
Jelena Diakonikolas. "Halpemn Iteration for Near- Near-Optimall and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalitics". In: Conference on Learning Theory (COLT). 2020.
12

---

[DP18]
Constantinos Daskalakis and Ioannis Panageas. "The limit points of (optimistic) gra- dient descent in min max optimization", In: the 32nd Annual Conference on Neural Information Processing Systems (NeurIPS). 2018.
[DP19]
Constantinos Daskalakis and loannis Panageas. "Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization". In: 10th Innovations Theoretical Computer Science Conference (ITCS). 2019.
[DWY24)
Jing Dong, Baoxiang Wang, and Yaoliang Yu. "Uncoupled and Convergent Learning in Monotone Games under Bandit Feedback". . In: arXiv preprint arXiv:2408.0833 08395 (2024).
[FAI+22]
Meta Fundamental AI Research Diplomacy Team (FAIR)), Anton Bakhtin, Noam Brown, Emily Dinan, Gabriele Farina, Colin Flaherty, Daniel Fried, Andrew Goff, Jonathan Gray, Hengyuan Hu, et al. "Human-leve" play in the game of Diplomacy by combining language models with strategic reasoning". In: Science 378.6624 (2022), pp. 1067-1074.
[FS99]
Yoav Freund and Robert E Schapire. "Adaptive game playing using multiplicative weights". In: Games and Economic Behavior 29.1-2 (1999), pp. 79-103.
[Gol+20] Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, and Asuman Ozdaglar. "Laast iterate is slower than averaged iterate in smooth convex-concave saddle point problems". . In: Conference on Learning Theory (COLT). 2020.
[GPD20]
Noah Golowich, Sarath Pattathil, and Constantinos Daskalakis. "Tight last-iterate convergence rates for no-regret learning in multi-player games". In: Advances in neural information processing systems (NeurIPS) (2020).
[GTG22]
Eduard Gorbunov, Adrien Taylor, and Gauthier Gidel. "Last-Iterate Convergence of Optimistic Gradient Method for Monotone Variational Incqualities" In: Advances in Neural Information Processing Systems. 2022.
[GVM21]
Angeliki Giannou, Emmanouil- Vasileios Vlatakis Vlatakis-Gkarage Gkaragkounis, and Panayotis Mer- tikopoulos. "On the rate of convergence of regularized learning in games: From bandits and uncertainty to optimism and beyond". In: Advances in Neural Information Process- ing Systems 34 (2021), pp. 22655-226665
[Hal67]
Benjamin Halpern. "Fixed points of nonexpanding maps". In: Bulletin of the American Mathematical Society 73.6 (1967), pp. 957-961.
[HAM21]
Yu-Guan Hsieh, Kimon Antonakopoulos, and Panayotis Mertikopoulos. "Adaptive learn- ing in continuous games: Optimal regret bounds and convergence to Nash equilibrium". In: Conference on Learning Theory. PMLR. 2021, pp. 2288-2422.
[How72]
Joseph T Howson Jr. "Equilibria of polymatrix games". In: Management Science 18.5-part-1 (1972), pp. 312-318.
[Hsi+22]
Yu-Guan Hsich, Kimon Antonakopoulos, Volkan Cevher, and Panayotis Mertikopoulos. "No-regret learning in games with noisy feedback: Faster rates and adaptivity via learning rate separation". . In: Advances in Neural Information Processing Systems 35 (2022), pp. 6544-6556
[Jan68]
Elena Janovskaja. "Equilibrium points in polymatrix games". In: Lithuanian Mathemat- ical Journal 8.2 (1968), pp. 381-384.
[JL224]
Michael Jordan, Tianyi Lin, and Zhengyuan Zhou. "Adaptive, doubly optimal no-regret learning in strongly monotone and exp-concave games with gradient feedback". In: Operations Research (2024).
[Kor76]
G. M. Korpelevich. "The extragradient method for finding saddle points and other problems". In: Matecon 12 (1976), pp. 747-756.
[Liu+23]
Mingyang Liu, Asuman E Ozdaglar, Tiancheng Yu, and Kaiqing Zhang, "The Power of Regularization in Solving Extensive-Fone Games". In: The Eleventh International Conference on Learning Representations. 2023.
[Liu+24]
Yixin Liu, Argyris Oikonomou, Weiqiang Zheng, Yang Cai, and Arman Cohan, "CO- MAL: A Convergent Meta-Algorithm for Aligning LLMs with General Preferences". In: NewrIPS 2024 Workshop on Fine- Fine-Tuning Modern Machine Learning: Principles and Scalability. 2024.
[Liu425]
Kaizhao Liu, Qi Long, Zhekun Shi, Weijie J Su, and Jiancong Xiao. "Statistical im- possibility and possibility of aligning Ims with human preferences: From condorcet paradox to nash equilibrium". In: arXiv preprint arXiv: 10990 (2025).
13

---

[Mao+24]
Weichao Mao, Haoran Qiu, Chen Wang, Hubertus Franke, Zbigniew Kalbarezyk, and Tamer Başar. "O Convergence to (coarse) correlated equilibria in full-information general-sum Markov games". In: 6th Annual Learning for Dynamics & Control Confer- ence. PMLR. 2024, pp. 361-374.
[MPP18]
Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras. "Cycles in adversarial regularized learning". In: Proceedings of the twenty-ninth annual ACM- SIAM symposium on discrete algorithms. SIAM. 2018, pp. 2703-2717.
[Mun+23] Rémi Munos, Michal Valko, Daniele Calandriello, Mohammad Gheshlaghi Azar, Mark Rowland, Zhaohan Daniel Guo, Yunhao Tang, Matthieu Geist, Thomas Mesnard, An- drea Michi, Marco Selvi, Sertan Girgin, Nikola Momchev, Olivier Bachem, Daniel J. Mankowitz, Doina Precup, and Bilal Piot. Nash Learning from Human Feedback. 2XXiv22312.00833 [cs, stat]. Dec. 2023.
[Nas50]
John F Nash Jr. "Equilibrium points in n-person games". In: Proceedings of the national academy of sciences 36.1 (1950), pp. 48-49.
[OSZ21]
Asuman Ozdaglar, Muhammed O Sayin, and Kaiqing Zhang. "Independent learning in stochastic games". In: International Congress of Mathematicians. 2021.
[OX21]
Yuyuan Ouyang and Yangyang Xu. "Lower complexity bounds of first-order methods for convex-concar bilinear saddle-poing problems". In: Mathematical P Programming 185.1 (2021), pp. 1-35.
[Per+22]
Julien Perolat, Bart De Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome T Connor, Neil Burch, Thomas Anthony, et al. "Mastering the game of Stratego with model-free multiagent reinforcement learning.. In: Science 378.6623 (2022), pp. 990-996.
[Pop80]
Leonid Denisovich Popov. "A modification of the Arrow-Hurwicz method for search of saddle points". In: Mathematical notes of the Academy of Sciences of the USSR 28.5 (1980). Publisher: Springer, pp. 845-848.
[PZO23] Chanwoo Park, Kaiqing Zhang, and Asuman Ozdaglar. MMulii-player zero-sum markov games with networked separable interactions". In: Advances in Neural Information Processing Systems 36 (2023), pp. 37354-37369.
[RS13]
Sasha Rakhlin and Karthik Sridharan. "Optimization, learning, and games with pre- dictable sequences" In: Advances in Neural Information Processing Systems (2013). [Sil+17] David Silver, Julian Schrittweeser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. "Mas- tering the game of go without human knowledge". In: nature 550.7676 (2017), pp. 354- 359.
[SPF25]
Ashkan Soleymani, Georgios Piliouras, and Gabriele Farina. "Faster Rates for No- Regret Learning General Games via Cautious Optimism". In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing. 2025.
[Swa+24]
Gokul Swamy, Christoph Dann, Rahul Kidambi, Steven Wu, and Alekh Agarwal. "A Minimaximalist Approach to Reinforcement Learning from Human Feedback". In: Forty-first International Conference Machine Learning. 2024.
[Syr+15]
Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire. "Fast conver- gence of regularized learning in games". In: Advances in Neural Information Processing Systems (NeurIPS) (2015).
[Tam14]
Oskari Tammelin. Solving Large Imperfect Information Games Using CFR+.
NYY:11407.5022 [cs]. July 2014.
[Wei+21]
Chen- Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. "Linear Last-iterate Convergence in Constrained Saddle-point Optimization". In: International Conference on Learning Representations (ICLR). 2021.
[Wu+24]
Yue Wu, Zhiqing Sun, Huizhuo Yuan, Kaixuan Ji, Yiming Yang, and Quanquan Gu.
"Self-play preference optimization for language model alignment". In: arXiv preprint arXiv:2405. 00675 (2024).
[Wu+25]
Jiduan Wu, Anas Barakat, Ilyas Fatkhullin, and Niao He. "Learning zero-sum linear quadratic games with improved sample complexity and last-iterate convergence". In: SIAM Journal on Control and Optimization 63.5 (2025), pp. 3244-3271.
14

---

[WZ07]
Fang Wu and Li Zhang. "Proportional response dynamics leads to market equilibrium". In: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing.
2007, pp. 354-363.
[Ye+24]
Chenlu Ye, Wei Xiong, Yuheng Zhang, Nan Jiang, and Tong Zhang. "A theoretical analysis of nash learning from human feedback under general kl-regularized preference". In: arXiv preprint arXiv:2402.0733 (2024).
[YR21]
TaeHo Yoon and Ernest K Ryu. "Accelerated Algorithms for Smooth Convex-Concan Minimax Problems with O(1/k²) Rate on Squared Gradient Norm". In: International Conference on Machine Learning (ICML). PMLR. 2021, pp. 12098-12109,
[ZDR22]
Sihan Zeng. Thinh Doan, and Justin Romberg. "Regularized gradient descent ascent for two-player zero-sum Markov games". In: Advances in Neural Information Processing Systems 35 (2022), pp. 34546-34558.
[Zin03]
Martin Zinkevich. "Online convex programming and generalized infinitesimal gradient ascent". In: Proceedings of the 20th international conference machine learning (ICML). 2003.
Contents
1
Introduction
1.1 Related Works
2 Preliminaries
2.1 Games
2.2 Online Learning
3
A Reduction From Last-Iterate to Average-Iterate
4
Learning in Zero-Sum Games with Gradient Feedback
5 Learning in Zero-Sum Games with Bandit Feedback
6 Conclusion
10
A Proof of Lemma
16
B A2L Reduction for Proportional Response Dynamics in Fisher Markets
16
C Last-Iterate Convergence with Gradient Feedback
17
C.1 Proof of Theorem
17
C.2 Proof of Corollary 1
17
D Last-Iterate Convergence with Bandit Feedback
17
D.1 Analysis of Regret with Estimation Error
17
D.2 Proof of Theorem
20
D.3 Estimation
21
E Robustness against Adversaries in the Bandit Setting
23
15

---

A Proof of Lemma 1
Proof. By the zero-sum property and the linearity of the utility, we have
Ui (1; ux(TT)
max 26 XA4
max us (1(
Eaau((")) ui(x")=0 =0)
zEAA
Σ (1(11,)"""
(Linearity of us and x-1 Et=n
max mEAA
Σ
ui ue(Ts; x'
Σ us (z(("))
nh Uz(x²) = 0 for all t)
max #EAA%
Reg, (T).
T
This completes the proof.
B A2L Reduction for Proportional Response Dynamics in Fisher Markets
The Fisher market is classic model of allocating divisible goods, special case of the Arrow-Debreu market. In Fisher market, there are m agents and n divisible goods. Each agent E [y]] has budget B, > and each good j E [m]] has unit supply. Each agent also has a utility function u 12 + R such that (x,)) is her utility of receiving the bundle I, E Rg where 2i 2 0 is the amount of good j. Here we do not assume u, linear.
price vector E RR specifies a price pj > 0 for each good j. A Competitive Equilibrium (CE) of a Fisher market a pair of price vector and personalized allocations (p, {x;}) that satisfies the following properties:
1. Budget Feasible: (p, v2) S B, for each agent i.
2. Utility Maximizing: un (x(4))= = max ER cRg, (p.w)) uz(v/) for each agent i.
3. Market Clears: Σn <
for each good and Σ, æig = 1f > 0.
The proportional response dynamics (PRD) a distributed, independent dynamics leading to CE in Fisher market. PRD works as follows:
Budget Spending: each agent decides the allocation of her budget by, where bf is her spending on good j. It must hold that Σ, bLy ez.
Goods allocation: the amount of good allocated agent is proportional to their spending:
zi1 6/.
Moreover, the price of each good is defined the sum of agents' spending
p)- 633
Update: Based the allocation æt. each agent i then updates their spending of budget b,+1 in the next round using the following rule:
bi B, Σ (())
Although it has been shown that the price vector {p*) converges to a Market equilibrium price vector for Fisher markets in many settings including linear utilities [WZ07; BDX11]. PRD for Fisher markets with Gross Substitutes utilities has O11/T) convergence rate only in terms of the average price { Et= p*}. but not the last iterate price (p') [CCT25].
16

---

A2L-PRD for Last-Iterate Convergence We note that in PRD, the only feedback needed for their
bi update is her allocation zi, where good j's allocation 2i, En by, is proportional according to every agent's spending. Here, the key observation is that the feedback in PRD, arf, has nice proportional structure with the spending of despite each player having nonlinear utilities. We can then apply our A2L reduction. We just let each agent spend their averaged budget allocation i Ei= by and observe the induced allocation E. Due to the proportional structure, each agent can recover the original iterate {6] (ejm's allocation and then update according to the original PRD [CCT25]. this way, we get a modified A2 L2L-PRD whose last-iterate price vectors is equivalent to the averaged price vectors the original PRD. The A2L-PRD enjoys (1//T) last-iterate convergence rate in the price vectors.
C Last-Iterate Convergence with Gradient Feedback
C.1 Proof of Theorem 3
Proof. Let {x'} be the iterates of OMWU dynamics with v). Recall that we denote uf == uz(;,0" By Theorem have
n
Reg,(T) S
En log dl
n
nn|ut ut -
1 1 x 1 4n
i=1
5 i=l log ds
where use Lemma 2 and 1[ in the last incqualty. Invoking Lemma 1, the average-iterate
has total gap bounded by TGAP(#") <
En log d, for all T. By the A2L reduction guarantee in
Theorem 2, we conclude the proof.
C.2 Proof of Corollary
Proof. By Theorem 3, know x' is an E. log d: nt
approximate Nash equilibrium for any 2 1.
Thus, the dynamic regret of any player i e [n] bounded by
T
log di
log d3 EE
DReg! T = Σ
max u=(,;,,',)) ux(x') ZEEA"
1=
=
log T
nt
7
t=
1=1
This completes the proof.
D Last-Iterate Convergence with Bandit Feedback
D.1 Analysis of Regret with Estimation Error
We first analyze the sequence {ø'} generated in the subroutine (Line 8) of Algorithm 2, which is updated according to OMWU with the estimated utility sequence {ū{}.
We define A Ü Th the error of estimation in Line 6. The enror of estimation for ut, denoted as 6ā == at__ u/ can be bounded follows.
Proposition 1. For any 2 and | - ||tai|| [I(t 1)4;-111 |188 < 3||+_;11 31 - 1) -11 + 12
'I 2e,. This further implies
Proof. Let define ui,unif :- (u)))) the utility vector of i when other players use the uniform strategy. Since the utility uz ue(wi, x x=) is linear in x-i, we have
u=(:x"=e)) (1 - -xyJu + unif Vt.
17

---

Using the above equality and the definition of A and 8j, as well as E, = =t we have
t - (t - 1)4,-1
=t =t.0 - (t 1). - t- The + (t 10-1) -
= -ihee -6 ((1 - Ex) + ExULcnitt) + (1 -1) ((1 - -1 e)= + -x-1 11-1iinn)t)
1-1
thi (1 - =1) Σ c + - E
kml
km
i/15 ut + tuns + (Et EL-1)
u4
h=
= o + u + (E1 - Et-1)
u
(2)
Since ||u, S 1 for all k. the above equality implies
| x = | || + I|(t 1) + 22,.
| + [[ 1)4: || + + (t 1)(E: E1-1
We then apply the basic incquality (a + b c)² - 3(a² + +b² + c?) to bound 10%1l This completes the proof.
In the following, we show that the regret against the original utility sequence {u'} can be bounded by RVU terms with an additional summation of second-order error terms. We remark that a naive analysis would lead to summation of first-ordes terms, which gives a suboptimal convergence rate.
Lemma 3. Let { be the iterates of OMWU with step size 1j > and utilities {ūt}, we have
max 22 E
Cuttaat - xxi)
log di
41j
14
m
1-1
1
|
x 1
r
811
t=
T
T
+ 2
T 11.00
+
+261
2
+2
+2
E
16
Proof. Analysis By RVU property of OMWU (Theorem 1), we can bound the regret for the estimated utilities {ūt Vx E A4,
T Σ
log d
T Σ 11
T
Kūh x²) S
+ n
Σ
"
dn t=1
t=1
Then by definition of ifi ut + o% we can bound the regret for the true utilities fut)
by
Σ
T
(ut, 24 - 21) 5
log de
+ 41
T
|ut
u
11
1
Σ
T
|
- xt 112
4n
1=1
1=1
1=1
T
T
+
( x
-
ri)
+ 4n
(10% 2
+
1,o5 11
(3)
We note that the first three terms are standard terms in the RVU bound [Syr+15]. We focus on the error terms I and II. The term II is a summation of second-order terms in ||6| and we can bound it using Proposition 1 and Ee ef
Een
0o
II 4n > |108 2 oo
1160-1 1x) S 24n >
| + 961
E < 24m
|
167
(4)
18

---

However, a naive analysis of term I leads to a summation of first-order terms: by
we have I Σ |00 xill1 - 2 > |1 I O || xc) + O( Et). If we tune the parameters optimally, the existence of the first-order error term O || would result in an O(T-+) rate, worse than the claimed O(T +) rate.
Improved Analysis of Term I In the following, we give improved analysis that bounds term I by second-order error terms. The key is to rewrite term I and use the negative term > - 1.
By (2), we have
6 of
u t - (t- Erat - (Et EL-1)
Σ u
We note that || - (5t - e--1) E llo S 2s, as the utility is bounded in [0, 1]. This implies
T
(0 22))
1=1
T
T
(t - (t -t-1)
2-1 1
- - 23) +
Σ
Equ - (Et
EL-1)
|| xz xall1.
t=1
1=1
R=
T-1
S (TA of 24)
tA
x 4+1) +
Et
T-1 Σ
T
$ <
|
|1
1
+
Ct-
As result, we can combine ||a| to get
1 87
ΣT
|
x
and using basic inequality (a, ||6112 <
T
22
| 00
|
xf+111,
11
2
111
81
811
T-1
2 7 7
+ 2n
| _
+4 Et
+4
(5)
Combining (3), (4), and (5), we get
log d3
max #
a xz) 5
+ 4n Σ
1
1-1
x x.
t-1
17
87
T
T
+ TA, 11 + 261
|
2
+4
Et + 16
This completes the proof.
19

---

D.2 Proof of Theorem 4
Recall that d ma] d, By Lemma 3, we can bound the social regret of all players with respect the iterates {a*} and utilities {u'} by
a
logg d n
Reg. (T, (af) (u.)) <
4nllut
us
1
x 11?)
817
2 11 + 261
t |
+4n
+ 16nm² (6)
t=1
1=1
By Lemma and fact that vy S
6m we have I S
In the following. we analyze term II and conclude the last-iterate convergence rate of Algorithm 2 for fer = } and different choices of [B.]: All these choices give an O(k last-iterate convergence rate. The difference is that the choices BB = dt²) lead to better dependence on d but require knowledge about or ò, while the choice of {B, {*} is fully uncoupled as each player does not need know even an upper bound d.
Case 1: B. = d Σ Reg, (T, { {uf}) < nT = O(n log())). Thus x" is an O n log( approximate Nash equilibrium for all T Olog f). In the following, we focus on T > log ())
We note that for T = ((lo(g)))
trivially holds that
By Lemma 5, we have with probability - O(ndd))),
B.t2 dl log
max
A
22
Vt 2 log
in|n
Bis
For t - dllog()) we can use the trivial bound of || 1.
Then we can bound term II by
dlog
( BTT2
T-1 2 .llog B.f
II < 4n
+ 104mg
261 log
Brer
B.C.
Combining (6) and (7), and B, d and Et t we get
Reg, (T; (at), (uf))
n log d
An'T
dlog Br
+ 104mm)
d log
B,t2
8
+ 26 log
1
+ 4n
o + 16nx
BTET
8
0 ( <logg' (dd)
By Lemma 1, we have the average iterate n := + ΣT= x² is O log" 4T
7 approximate Nash equilibrium. Since Ey 4. then know x! := (1 )x + Er 8 Uniform(d,) is also an
O(" O mlog
(1TF) )-approximate Nash equilibrium for any T >
T/T
By the choice of the epoch length B, = d ts we have that the actual sequence {T*) generated by A2 A2I-OMMU--anddi satisfies /e x where L ((d=tk#). Thus we can conclude that with
probability at least Onn 8), it holds for all & > 1 that y² is a 3e-approximate Nash equilibrium with
(
n [olog
Bx O
d3 lak-
77
This completes the proof.
20

---

Case 2: B, = The proof is very similar to case We note that for T = (log(( (2)) ]), it trivially holds that Σ Reg, (T, { {u{} - nT = O(n log( Thus मF is an O mloog ( approximate Nash equilibrium for all T Olog 2)) In the following, we foeus T 2 )) By item 2 in Lemma with probability (nd 8), for all i 2 dllo())).
d dlog BBf²)
max Eiin]
| s 2/
Best
For 1. S log()) (,)) we can use the trivial bound of 11, S These gives
dlog
B
12 log Bdd2)
II A
104nn
Σ
+ 26n log( log(z)
(8)
Brer
Bieg
Now combine (6) and (8) with B, 14 and t- and get
Reg, (T, {2f), {uf))
n log d
+ AnI
dlog 8
+ 104nn
T- 12 d log B.t²
+ 26 log(
1 ②)
+ 4n Σ Et + 16n=.n
T
Brer
B,E
=o nd log (af)
Compared to case this regret bound has an additional dependence.
Similar to the analysis in the former case, we have 2= is an O Ind (
-aproximmate Nash equilibrium for all T 2 1. By the choice B = t4, we have that the actual sequence (r*} generated by A2L-OMNU-BarciL satisfies Te = W where t5 = O(kt). Thus we can conclude that with probability at least - (ndd it holds for all k 2 1 that 3" is a Br-approximate Nash equilibrium with
n log (
Bg 0
dk
17
This completes the proof.
D.3 Estimation
In this subsection, we analyze the estimation error A := 0 -he_ for any E [n]. Recall that d = max d,. Within the epoch of length B,, with high probability, each action receives least
2 Bece) samples. We have with high probability that (Ū), ut [a]] < Ō /Bie
va for all action
which implies |ا < <0ly Bie The formal guarantees are as follows.
Lemma 4. In Algorithm 2, with probability
db 22 dexpí (- 22 ), we have
Beg
B d log
| 11. = 01
us/
$ 22
Bies
Proof. Define No = EB. I|a
a] to be the number of samples for action a. Since Pr(a* By Hoeffding's inequality, have
d have E [[[!
>
Bast
B
B,e
Pr Nt. <
< exp
2d
2d
21

---

Thus with probability 1 d exp (-
Bic 2d
every action has been sampled at least
Biel 2d
times, i.e.
Nº 2 Bis. 2d
Note that the number of samples Nú for action random variable, we can not directly use
Kzuma-Hoeffding inequality to argue 10 [a] "aa[||| I V dloo(1/6] with probability
B.c:
We define sequence of random variables where at, x'=i,e and n* us(a, a²x),, and define
U |a] El= r². Thus Ü is unbiased estimator for [t_[[a] for all m B.). Then can use Azuma- Hoeffiio s inequality to get that
B 2 log
Pr
1 [a] ui,5(al)
0
N
2 2og ( B,t²
Pr
Em [Be], 10 [a]
T/,e110 [a]] 2
m
2 log
B.12 8
Pr
Ü [a]
u4.. 2 =V
m
B.
8
B,t
m=1
Recall that with probability 1 dexp( we get with probability 1
Bic
Bis for all a. By union bound over actions,
2d
d8
12 dexpl
B,e?
2d
dlog B
|010 Thic
22
BrE
This completes the proof.
Using union bound over all players E [n]] and epoch 1, we have the following guarantee, Lemma 5. Consider a polymatrix game in which each player has at most actions. Let { UH.-- h121 denote the estimation error vector produced by Algorithm 2 for player i round t. Suppose every player runs Algorithm with B₁ 2 ta and ε, -1. Then, with probability at least 1 - O(nd 8), simultaneously for all players i E [m] and all rounds t 2 log(})
log BBt
| $21
B,C,
Proof. By Lemma 4, for each fixed player E [n] and round 2 1, we have
Pr ||illl 2v
dog BBr²
d8
dexp
Bis²
B
2d
Applying union bound over all players i [n] and all rounds 2 log( ( gives that the claim holds with probability at least
Bie
1 1 ndo
nd
exp
t2
2d
1=1
b=log(
We have E 1 0(1). With Er 1- and
B.
ta we have B,5 +², the second
summation is bounded by
t
nd
< ndo
exp
S O(nd
2dl
2d
I=log(
[=1
So the overall failure probability is at most (fd 8). This completes the proof.
22

---

E Robustness against Adversaries in the Bandit Setting
Consider the following utility estimation subroutine equipped with Algorithm 2. Here, longer assume the other players employ the same algorithm, and they might behave adversarially. To this end. in each epoch I, we denote the true utility vectors for player as {u E [0, 1]4 Je(BB and the true accumulated utility within epoch /
Bi
U U
==1
In each epoch i, the player plays actions u; ["'[aa)) [e( it also maintains importance weighted estimator of the accumulated utility within epoch B;:
(a''
xie)) for [Br] and receives (r
r l = a²) vb E [d,),
B.
U =
Denote T; = Ek=n Be, the player maintains estimated regret
Reg
max ZEA";
U
Uh x4.5
while the true regret is
Reg
max rEA
(U
Σ Utt 2f)r)
Then we have the following
Proposition 2. Fix any 8 O. With probability at least
8, for any
and Tr = Ei= Br, we
huve
Reg To
E
Reg
4dl,
Σ k=1
B&) B&)log log
x²2,112
Reg
To
+ 4di,
Σ (k2 Be) log
722,112
35
38
Proof. The importance weighed estimator is unbiased as B, Blu
t [b]] w [b] for all b E [d:]. More-
over, since a//_e [b] 2 J.
det' have -1 < (b) 4 [b] d,t. By Aruma-Hoeffdind inequality,
have for any and b E [d.].
Pr Σ
-
s 2d,
Σ (A2 log
x²d112
2
65
38
πt d,
k=1
Using union bound over t 2 1 and E [d:] gives
t Σ
n2,,12
Pr Vt 2 1,
Ü U
s 2d
Σ (k22 (B2 log
2 8.
35
Since the max e max v' 5 ||0 ollocr we bound the error in regret estimation
Reg
Σ U U S Reg" < Reg
+
(OO U:hy
Am1
This implics with probability at least
6, for all 2 1 and Ti = Et=1
Bk. we have
Reg E
Reg
4d.
Σ (k2 B2) log
r²,t
Reg
T
+ 4di
Σ
(k:2 log
rdd,t²
35
This completes the proof.
23

---

Choosing B, = t we have T, = =E Bk 0(1b) and O(T,5). We have, with probability 1 6, for all T.
Reg = Reg
Ti
+ O de.1. log
dit
= Reg + 0 d.T. log
d.T:
8 )
8
We note that for general T [T,, Te+1
(denote To 1), we have Bi41 (t + 1) O(T;²)
T-T. Σ
T-
(utt =
Reg
T
max ZEA4
Σ (U +
ui
t+1
U aiie) Σ
5=1
S Reg" T: Bi+1
-Reg Ti
+ max
(TT²))
+ (1:)
0 d,
log
d,Ti
Reg
Th
max 10 {o
d log
d,7
Thus whenever Reg Ti = OTT.), we have Reg" = O ) for all iterations 7 E [Te, T+t1).
Robustness in Adversarial Setting The player could rum Algorithm and track its regret using the above estimation Reg at the end of each epoch Whenever she detects that Reg Ti 2(TF). which cannot happen if all the players employ Algorithm 2, she can switch to a standard no-regret bandit algorithm with worst-case optimal regret. This procedure guarantees worst-case ( regret.
24

---

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

---

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

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
This paper does not include experiements requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https: :ttpps:/nniie ///pssipp.///////////// cc/
publ c guides/ CodeSulmm ss onPoll Pyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: /nips. cc/ ttapps.ccpbblic....o heabbicc/giiess CooeeeeeeSSeeeeee Sumeeuubmmii.. cessooPolllo ooyicyyyyyy....cc for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
27

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: /ttpas:////uiipp/e httppp/lccc/tthcccciieeeeee
Answer: [Yes]
Justification: This paper is theoretical and is conducted with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper contains purely theoretical results and the authors not see any societal impact that needs to be discussed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
28

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper does not existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, papers' raw w thcode com/ data sets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
29

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
30

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the method development in this research does involve LLMs as any important, original, or non-standard components.
ccc Sacc/ooffeeeneees / 2025/ Please refer to our LLM policy (https: /tteerrrss.cc//offeeeeeeeeeee LLM) for what should should not described.
31


Reviews:
[{"review_id": "p4cqVncUiA", "reviewer": "Reviewer_yhjx", "summary": "average iterate convergence rates. There has been increasing interest\nin deriving last-iterate convergence guarantees for equilibrium\nlearning algorithms. Such guarantees are more practically useful, but\nalso harder to obtain.\n\nThe main contribution of the paper is an algorithm that takes an\nalgorithm with an average-iterate convergence guarantee, and turns it\ninto an algorithm with a last iterate convergence guarantee. The\nconstruction assumes that the utility function is linear in their own\nstrategy. They consider both settings with gradient feedback and\nbandit feedback.\n\nThe authors argue that in some cases, this leads to state of the art\nresults. By applying the approach to the OMWA algorithm for zero-sum\npolymatrix games, this leads to state of the art last-iterate\nconvergence guarantees.", "questions": "Minor remarks\n\nSecond inequality after 585 (proof of Theorem 3): Comparing with Lemma\n2, there seems to be a (n-1) factor missing. Do you need to assume\nsmaller eta?\n\nLine 598: Please give some more explanation for the expression for\ndelta^t.\n\nIt would have been nice to see the theoretical results complemented\nwith numerical experiments, e.g., comparing OMWU with A2L-OMWU on some\ninteresting games.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "This is an interesting result worthy of publishing. In particular, it\nmay provide an easier route to last-iterate guarantees. It is an open\nquestion how practically useful the approach it.\n\nThe paper is well presented, and I only have some minor suggested\nimprovements.\n\nThe proofs for the gradient-based setting are relatively short and\nstraightforward, while the bandit based settings are more involved. I\nhave read the proofs and only have a few remarks.", "was_revised": true, "final_justification": "I am satisfied with the authors' rebuttal to our reviews. This is a strong paper that deserves to be accepted.", "rebuttal": "We appreciate that reviewer yhjx finds our results interesting and well presented. We address the minor remarks below. \n\n>1. Second inequality after 585 (proof of Theorem 3): Comparing with Lemma 2, there seems to be a (n-1) factor missing. Do you need to assume smaller eta?\n\nA: Thank you very much for pointing out this typo. The correct version of the inequalities after 585 is\n$$\n\t\\\\sum_{i=1}^n reg_i (T) \\le \\frac{\\sum_{i=1}^n \\log d_i}{\\eta} + \\sum_{i=1}^n \\\\sum_{t=1}^T ( \\eta ||u^t\\_i - u^{t-1}\\_i||^2_{\\infty} - \\frac{1}{4\\eta} ||x^t\\_i -x^{t-1}\\_i||_1^2 )  \\\\le  \\frac{\\sum\\_{i=1}^n \\log d\\_i}{\\eta}, \n$$\nwhere the final inequality follows from Lemma 2 and the condition $\\eta \\le \\frac{1}{2(n-1)}$. With this correction, there is no need to impose a stricter constraint on $\\eta$. We will fix this in the revised version. Thank you again for your careful reading.\n\n> 2. Line 598: Please give some more explanation for the expression for delta^t.\n\nA: Thanks for the comment. In the A2L reduction with gradient feedback, we get gradient feedback $\\bar{u}^t:= u\\_i(\\cdot, \\bar{x}\\_{-i}^t) = \\frac{1}{t} \\sum\\_{k=1}^t u\\_i(\\cdot, x\\_{-i}^k)$ and then recover the true gradient $u^t:= u_i(\\cdot, x^t_{-i})$ via the identity $u^t = t \\cdot \\bar{u}^t - (t-1) \\bar{u}^{t-1}$, which follows from the linearity of the utility. \n\nIn the bandit setting, however, we do not observe $\\bar{u}^t$ directly. Instead, we obtain an estimate $\\hat{U}^t \\approx \\bar{u}^t$ (Line 6, Algorithm 3). Letting $\\Delta^t := \\hat{U}^t - \\bar{u}^t$ denote the estimation error in this step. Then the approximation $\\hat{u}^t := t \\cdot \\hat{U}^t - (t-1) \\cdot \\hat{U}^{t-1}$ (Line 7, Algorithm 3) differs from the true $u^t$ by \n$$\n\t\\delta^t = \\hat{u}^t - u^t =  t \\cdot \\hat{U}^t - (t-1)\\cdot \\hat{U}^{t-1} - t \\cdot \\bar{u}^t + (t-1) \\cdot \\bar{u}^{t-1} = t \\Delta^t - (t-1) \\Delta^{t-1}.\n$$\nThis explains the expression for $\\delta^t$. We will include this clarification in the revised version. Thank you again for your thoughtful question.\n\n\n> 3. It would have been nice to see the theoretical results complemented with numerical experiments, e.g., comparing OMWU with A2L-OMWU on some interesting games.\n\nA: Thanks for the suggestion! We will include numerical experiments on comparing OMWU and A2L-OMWU on the hard instance of [1]. As shown in [1], OMWU could have arbitrarily slow last-iterate convergence on these hard instances. But A2L-OMWU is equivalent to the average iterates of OMWU and would have a fast $O(1/T)$ last-iterate convergence rate. As also suggested by other reviewers, we will also include numerical experiments on comparing A2L-OMWU and EG/OG where the former is more favorable due to its logarithmic dependence on the number of actions. \n\n[1] Yang Cai, Gabriele Farina, Julien Grand-Clément, Christian Kroer, Chung-Wei Lee, Haipeng Luo, and Weiqiang Zheng. “Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms”. In: The Thirty-eighth Annual Conference on Neural Information Processing Systems. 2024."}, {"review_id": "wlUj9GoB5P", "reviewer": "Reviewer_Qfxk", "summary": "This paper proposes A2L, a black-box reduction that transforms any online learning algorithm with average-iterate convergence guarantees into one whose last iterates converge. The reduction applies to games with payoffs linear in players’ strategies, including zero-sum bimatrix games and multi-player polymatrix games. Furthermore, they show that applying A2L to Optimistic Multiplicative Weights Update  improved last-iterate convergence rates and the fastest known convergence under bandit feedback.", "questions": "1) The reduction reminds me of the paper by Cutkosky (2019), where they do anytime online to batch conversion. Can the authors comment on any similarities/differences with their approach. In general, I think it would be useful to cite it. \n\n2) Following from the previous question Cutkosky (2019) have a weighted average version in their reduction and I was wondering, if your reduction can also have such weights embedded and whether that could be useful?\n\n3) It is known that Cai et al. (2024) have this game defined as $A_{\\delta}$ in their paper that shows the lower bound for OMWU. If I understand your results correctly, the A2L-OMWU, in its rates does not have a game dependent constant? If so this must be highlighted.\n\n4) The reduction was shown through OMWU, but can it be applied to standard (non-optimistic) versions to get last-iterate convergence? Is it also applicable to general FTRL? \n\n5) It would be nice to see some experiments on large-scale games to see the performance of A2L-OMWU, OMWU and OGDA in practice, with respect to number of steps and also the wall-clock time.\n\n6) Could the authors also clarify the dependence on the other constants when compared to Cai et al. (2023)? in Theorem 4?\n\nReferences:\n\nCutkosky, Ashok. \"Anytime online-to-batch, optimism and acceleration.\" International conference on machine learning. PMLR, 2019.\n\nYang Cai, Haipeng Luo, Chen-Yu Wei, and Weiqiang Zheng. “Uncoupled and convergent learning in two-player zero-sum markov games with bandit feedback”. In: Advances in Neural Information Processing Systems 36 (2023), pp. 36364–36406. \n\nYang Cai, Gabriele Farina, Julien Grand-Clément, Christian Kroer, Chung-Wei Lee, Haipeng Luo, and Weiqiang Zheng. “Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms”. In: The Thirty-eighth Annual Conference on Neural Information Processing Systems. 2024.", "limitations": "NA", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1) The black box reduction is simple but able to provide stronger last-iterate convergence rates for zero-sum games, i.e., they get a last-iterate rate of $O(\\log d /T)$, when they apply their black-box reduction to OMWU.\n\n2) They also get improved rates for the gradient feedback and the bandit case for zero-sum games, where they show that the ``reduced'' versions of Bandit-OMWU achieve rates of $O(T^{-1/5})$, compared to prior approaches that achieve O($T^{-1/8}$).\n\nWeakness:\n\n1) They already state that their techniques are limited to games that satisfy the Linear utilities assumption (Assumption 1), such as bimatrix games and polymatrix games.\n\n2) Although it is mainly a theory paper, it would be nice to see how the A2L-OMWU performs in practice against OMWU and OGDA for instance.\n\nSee the questions section as I would like to seek further clarification.", "was_revised": true, "final_justification": "While I appreciate the theoretical results, it would may be help to see experimental comparisons, especially on wall-clock times between the reductions and using the original algorithms, to give a better view of the landscape of these algorithms for such games. In general, I would like to maintain my original (positive) score of the paper as I think it would be good for the community to explore this idea beyond games with linear utilities.", "rebuttal": "We thank the reviewer for appreciating the simplicity of our reduction and the strong convergence rate results. We also thank the reviewer for constructive comments and pointing a related work. We address the questions and comments below.\n\n> 1. The reduction reminds me of the paper by Cutkosky (2019), where they do anytime online to batch conversion. Can the authors comment on any similarities/differences with their approach. In general, I think it would be useful to cite it.\n\nA: Thank you for pointing us to the work of Cutkosky (2019). While our A2L reduction and the anytime online-to-batch (AO2B) reduction share the idea of playing the average of previous iterates, *they differ significantly in several key aspects:*\n\n1. **Problem setting**: AO2B is designed for static optimization, where the loss function remains fixed across rounds. A2L, on the other hand, applies to a dynamic multi-agent game setting, where each player’s loss function can change over time due to the actions of others.\n2. **Objective**: AO2B aims to solve a single offline optimization problem with improved convergence rates. AO2B does not guarantee equivalence between the last iterate of the new learning algorithm and the average iterate of the original algorithm (since the gradient feedbacks are different). In contrast, A2L aims to show that the last iterate of the new dynamics corresponds to the averaged iterate of the original dynamics.\n3. **Use of gradient**: In AO2B, the learner updates directly using the gradient at the average iterate $\\bar{x}^t = \\frac{1}{t} \\sum_{k=1}^t x^k$. In contrast, A2L requires post-processing the gradient feedback to recover the true gradient at the original iterate $x^t$, as shown in Line 4 of our Algorithm 1.\n\nWe will include this comparison with Cutkosky (2019) in the revised version of the paper. Thank you again for the helpful suggestion.\n\n\n> 2. Following from the previous question Cutkosky (2019) have a weighted average version in their reduction and I was wondering, if your reduction can also have such weights embedded and whether that could be useful?\n\nA: Thank you for the insightful question! \n\n**Our A2L reduction naturally extends to the weighted averaging setting**, provided all players agree on the weights in advance and incorporate them into the reduction. In this version, each player plays the weighted average of their past iterates. Due to the linearity of utilities, the gradient feedback can still be used to recover the gradient corresponding to the original iterate, as in the current A2L reduction. As a result, the last iterate of the new dynamics corresponds to the weighted average in the original dynamics. The correctness follows the same steps as in Theorem 2.\n\n**This weighted version of A2L provides additional flexibility and can be beneficial in practice.** For example, in regret matching algorithms—widely used for solving large-scale games like poker—linear averaging (i.e., giving the $k$-th iterate weight proportional to $k$) often empirically outperforms uniform averaging, despite having the same theoretical rate. We will include and discuss this weighted variant in the revised version. Thank you again for the suggestion.\n\n> 3. It is known that Cai et al. (2024) have this game defined as $A_\\delta$  in their paper that shows the lower bound for OMWU. If I understand your results correctly, the A2L-OMWU, in its rates does not have a game dependent constant? If so this must be highlighted.\n\nA: **A2L-OMWU’s last-iterate convergence rate is uniform and does not have a game-dependent constant.** Since our A2L reduction transforms average iterates of OMWU to the last iterate, the last-iterate convergence rate of A2L-OMWU is the same as the average-iterate convergence rate of OMWU. Then it follows from the fact that OMWU’s average-iterate convergence has no game-dependent constant (as shown in our Theorem 3), despite that its last-iterate convergence rate must have some game-dependent constant (as shown by Cai et al. (2024)). \n\n\n> 4. The reduction was shown through OMWU, but can it be applied to standard (non-optimistic) versions to get last-iterate convergence? Is it also applicable to general FTRL?\n\nA: **Our A2L reduction is a black-box framework that applies to any online learning algorithm.** For example, applying A2L to the standard (non-optimistic) version of MWU—which has $O(\\sqrt{T})$ regret—yields an A2L-MWU algorithm with an $O(1/\\sqrt{T})$ last-iterate convergence rate. More generally, A2L can be applied to any FTRL-based algorithm, resulting in an $O(1/\\sqrt{T})$ rate for non-optimistic versions and an improved $O(1/T)$ rate for optimistic FTRL algorithms.\n\n\n> 5. It would be nice to see some experiments on large-scale games to see the performance of A2L-OMWU, OMWU and OGDA in practice, with respect to number of steps and also the wall-clock time.\n\nA: Thanks for the suggestion. We will include numerical experiment results in the revised version. We would like to remark that OMWU could have an arbitrarily slow last-iterate convergence even in simple games, where our reduction A2L-OMWU gives fast last-iterate convergence. Also note that A2L-OMWU enjoys a logarithmic dependence on the dimension (i.e., the number of actions), whereas OGDA exhibits polynomial dependence. As a result, A2L-OMWU may be particularly preferred in high-dimensional settings. \n\n> 6. Could the authors also clarify the dependence on the other constants when compared to Cai et al. (2023)? in Theorem 4?\n\nA: Cai et al. (2023) study only the two-player zero-sum setting ($n = 2$) under bandit feedback and establish a high-probability convergence rate of $$O(d^{1/2} \\ln^{3/2}(dt/\\delta) t^{-1/8}),$$ where $d$ is the maximum number of actions, $t$ is the number of iterations, and $\\delta$ is the failure probability. In comparison, our Theorem 4 provides a rate of $$O(d^{1/5} \\ln^{11/5}(dt/\\delta) t^{-1/5})$$ for the same setting. Our result **improves the dependence on all parameters**—$d$, $t$, and $\\delta$—and thus offers a better high-probability guarantee.\n\n> Weakness: They already state that their techniques are limited to games that satisfy the Linear utilities assumption (Assumption 1), such as bimatrix games and polymatrix games.\n\nResponse: While our current analysis focuses on games satisfying the linear utilities assumption (e.g., bimatrix and polymatrix games), this assumption is a sufficient condition for applying our reduction—not a necessary one. **We recently found that the A2L reduction can apply to other structured settings with possibly nonlinear utilities.** We will first recall the core ideas of A2L reduction and then give one example of learning dynamics for market equilibrium. \n\nThe core of the A2L reduction lies in the “extraction” step: when players play the average of past iterates and observe corresponding feedback, they recover the feedback they would have received had they all played the original iterate. In our current framework, this is enabled by linearity, but similar structure-based recoverability can exist beyond linear settings.\n\n**One example is the proportional response dynamics (PRD) for market equilibrium in Fisher markets** [Cheung et al., 2025] (where utilities can be nonlinear). In a fisher market, there are $n$ agents and $m$ goods. Each agent $i$ has a budget $e_i$ and each good $j$ has a unit supply. The proportional response dynamic works as follows: \n- Budget Spending: each player $i$ decides the allocation of budget $\\{b^t_{ij} \\}$ where $b^t_{ij}$ is his spending on good $j$. It must hold that $\\sum_j b^t_{ij} = e_i$; \n- Goods allocation: the amount of good $j$ allocated to agent $i$ is proportional to their spending as $x^t_{ij} = b^t_{ij} / \\sum_{i} b^t_{i, j}$. Moreover, the price of each good $j$ is defined as the sum of agents’ spending $p^t_j:= \\sum_{i} b^t_{ij}$. \n- Update: Based on the allocation $x^t_{ij}$, each buyer then updates their spending of budget $\\{ b^{t+1}_{ij} \\}$ in the next round using certain rules. \n\nThe original PRD for GS utility has a $O(1/T)$ convergence rate only in terms of the average price, but not the last iterate price [Cheung et al., 2025]. However, by applying A2L reduction— let each agent spend their average budget allocation $\\bar{b}^t\\_i = \\frac{1}{t} \\sum_k b^k\\_i$ and observe the induced allocation $\\bar{x}^t$---we can recover the original iterate's allocation due to the proportional structure. Thus, we get a modified PRD with $O(1/T)$ last-iterate convergence in price. Here, the key observation is that the feedback in PRD is the allocation $x$, which has a nice proportional structure with the bidding $b$ despite each player having nonlinear utilities.\n\nThis example illustrates that our reduction can extend to other settings where feedback remains recoverable from averaged plays, even without linearity on the utility. We will include this example in the revised version. Identifying structures that enable A2L reduction in more general settings remains an interesting future direction.\n\n**References**\n\nCutkosky, Ashok. \"Anytime online-to-batch, optimism and acceleration.\" International conference on machine learning. PMLR, 2019.\n\nYang Cai, Haipeng Luo, Chen-Yu Wei, and Weiqiang Zheng. “Uncoupled and convergent learning in two-player zero-sum markov games with bandit feedback”. In: Advances in Neural Information Processing Systems 36 (2023), pp. 36364–36406.\n\nYang Cai, Gabriele Farina, Julien Grand-Clément, Christian Kroer, Chung-Wei Lee, Haipeng Luo, and Weiqiang Zheng. “Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms”. In: The Thirty-eighth Annual Conference on Neural Information Processing Systems. 2024.\n\nCheung, Yun Kuen, Richard Cole, and Yixin Tao. \"Proportional Response Dynamics in Gross Substitutes Markets.\" Proceedings of the 26th ACM Conference on Economics and Computation. 2025."}, {"review_id": "lO7ozco07n", "reviewer": "Reviewer_1VqX", "summary": "This paper studies the convergence of online learning algorithms in games, focusing on the theoretical and practically importance setting, the last-iterate convergence property of algorithms used in a large class of games. The technique of reduction from last iterates to average-iterate seems novel and significant. The results and techniques also implies generalizations in multi-player setting.", "questions": "I am not totally sure whether the reduction technique is an innovation compared to the literature. \nWhat are other related papers that might be considered inspiring to this approach?", "limitations": "Yes, the limitation of the results and method is clearly stated in the paper.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength\n\nThe paper is well written and easy to follow. I think the authors have done a great effort trying to make the paper accessable to readers who are not experts in the narrow area. \n\nThe contributions of this paper on the improvement of convergence rates are clear and comparison to related results are presented. \n\nThe importance of reduction is the improvement for uncoupled learning in multi-player zero-sum polymatrix games. This reduction technique enables authors to obtain a last-iterate convergence rate for OMWU that matches its average-iterate rate under the same setting, say the gradient feedback. The bandit feedback is analyzed based on the same reduction technique, and this paper propose a OMWU-bandit algorithm that achieves a SOTA convergence rate compared to existing results.\n\nWeakness\n\nI think a general reader might be interested in the reduction technique used in this paper. If the authors could have provided a pointer to literature or open a section to discuss the background, the current layout of Section 3 mainly focuses on the technical side of this paper, and the extensive study mentioned section 4 refers to Opmtimistic learning algorithms. Since the results of this paper already say for the power of this key technique, a detailed introduction to its idea based on related works will be more helpful to curious readers.", "was_revised": true, "final_justification": "I have no futher concerns after rebuttal.", "rebuttal": "We appreciate that the reviewer finds our paper well-written and easy to follow, and our theoretical contribution clear and important. We address the minor comment below. \n\n> I think a general reader might be interested in the reduction technique used in this paper. If the authors could have provided a pointer to literature or open a section to discuss the background, the current layout of Section 3 mainly focuses on the technical side of this paper, and the extensive study mentioned section 4 refers to Opmtimistic learning algorithms. Since the results of this paper already say for the power of this key technique, a detailed introduction to its idea based on related works will be more helpful to curious readers.\n\n> I am not totally sure whether the reduction technique is an innovation compared to the literature. What are other related papers that might be considered inspiring to this approach?\n\n\nA: \nWe thank the reviewer for the comment. While we were not aware of prior works that studied similar reductions when writing the paper, Reviewer Qfxk pointed out that Cutkosky (2019) is quite related to our work. The problem Cutkosky (2019) studied is the online-to-batch conversion, which solves an offline optimization problem using an online learning algorithm. While our A2L reduction and the anytime online-to-batch (AO2B) reduction share the idea of playing the average of previous iterates, *they differ significantly in several key aspects:*\n\n- **Problem setting**: AO2B is designed for static optimization, where the loss function remains fixed across rounds. A2L, on the other hand, applies to a dynamic multi-agent game setting, where each player’s loss function can change over time due to the actions of others.\n- **Objective**: AO2B aims to solve a single offline optimization problem with improved convergence rates. AO2B does not guarantee equivalence between the last iterate of the new learning algorithm and the average iterate of the original algorithm (since the gradient feedbacks are different). In contrast, A2L aims to show that the last iterate of the new dynamics corresponds to the averaged iterate of the original dynamics.\n- **Use of gradient**: In AO2B, the learner updates directly using the gradient at the average iterate $\\bar{x}^t = \\frac{1}{t} \\sum_{k=1}^t x^k$. In contrast, A2L requires post-processing the gradient feedback to recover the true gradient at the original iterate $x^t$, as shown in Line 4 of our algorithm.\n\nWe will include this comparison with Cutkosky (2019) in the revised version of the paper and elaborate more on the A2L reduction to make it more accessible to general readers. Thanks again for the suggestion! \n\nCutkosky, Ashok. \"Anytime online-to-batch, optimism and acceleration.\" International conference on machine learning. PMLR, 2019."}, {"review_id": "N0t7bd2xLu", "reviewer": "Reviewer_h8Tb", "summary": "The paper studies last-iterate-convergence methods for solving normal-form games. Instead of proposing a new method from scratch, it introduces a black-box reduction (A2L) that converts any online learning algorithm with average-iterate convergence into one that achieves last-iterate convergence, under the assumption of linear utilities. The authors apply the reduction to OMWU, and derive state-of-the-art convergence guarantees under gradient feedback and bandit feedback.", "questions": "1) I would be interested to see how A2L-OMWU compares with other EG/OG algorithms known to have last-iterate convergence that the authors referenced in Related Works (line 102 and below). The purpose is to see whether A2L-OMWU truly converges faster both in theory and in practice, or whether the other algorithms also perform well in practice, with their current inferior convergence rates being an artifact of analysis.\n\n2) Can any of the argument be generalized to Markov games (with linear reward function)? \n\n3) A few highly relevant references should be included and discussed that design last-iterate-convergent algorithms for zero-sum games based on perturbation/regularization, including Abe et al., 2022, Abe et al., 2023, Wu et al., 2023, Zeng et al., 2023.\n\nReferences\n\nAbe, K., Sakamoto, M., & Iwasaki, A. (2022, August). Mutation-driven follow the regularized leader for last-iterate convergence in zero-sum games. In Uncertainty in Artificial Intelligence (pp. 1-10). PMLR.\n\nAbe, K., Ariu, K., Sakamoto, M., Toyoshima, K., & Iwasaki, A. (2023). Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Games. In AISTATS 2023, International Conference on Artificial Intelligence and Statistics, 25-27 April 2023, Palau de Congressos, Valencia, Spain (Vol. 206, pp. 7999-8028). MLResearchPress.\n\nWu, J., Barakat, A., Fatkhullin, I., & He, N. (2023). Learning Zero-Sum Linear Quadratic Games with Improved Sample Complexity and Last-Iterate Convergence. arXiv preprint arXiv:2309.04272.\n\nZeng, S., Doan, T., & Romberg, J. (2022). Regularized gradient descent ascent for two-player zero-sum Markov games. Advances in Neural Information Processing Systems, 35, 34546-34558.", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\nThe paper is in general clear and well organized. Its significance and novelty over prior work are effectively communicated, with both the high-level intuition and technical contributions presented at appropriate points throughout the paper.\n\nThe reduction method is simple and intuitive. Though highly dependent on the linear utility assumption, the method still covers a number of important game classes. Clear theoretical benefits --  faster convergence rates, uncoupled learning dynamics, last-iterate convergence -- are shown in solving zero-sum games under gradient and bandit feedback, without requiring major algorithmic changes .\n\nWeakness\n\nThe authors explained the merit of last-iterate convergence a few times in the paper, but I am not fully convinced. From the perspectives of practical implementation, tracking the average iterates is simple to carry out and does not introduce any additional time or memory complexity. I wonder if there are more concrete practical benefits from last-iterate-convergent algorithms that can help provide a better motivation.\n\nAssumption 1 is another limitation, and I cannot see how any of the arguments in the paper can be applied/extended when the utility is nonlinear. However, this does not mean the work is unimportant. The normal-form game framework with linear utilities captures several fundamental and widely studied game classes, such as two-player bimatrix games and multi-player polymatrix games, including their zero-sum variants. Just being able to solve these games alone is a contribution.", "was_revised": true, "final_justification": "I do not think I missed any important contributions or weaknesses in my original evaluation and therefore would like to keep my rating unchanged.", "rebuttal": "We appreciate that reviewer h8Tb find our paper clear and well organized, our results significant and novel over prior work, and our reduction simple, intuitive, and has clear theoretical benefits. We address below the questions and comments.\n\n> 1. I would be interested to see how A2L-OMWU compares with other EG/OG algorithms known to have last-iterate convergence that the authors referenced in Related Works (line 102 and below). The purpose is to see whether A2L-OMWU truly converges faster both in theory and in practice, or whether the other algorithms also perform well in practice, with their current inferior convergence rates being an artifact of analysis.\n\nThank you for the suggestion! We will include numerical experiments comparing A2L-OMWU with EG and OG in the revised version. We would like to highlight that A2L-OMWU enjoys **logarithmic dependence** on the dimension (i.e., the number of actions), whereas EG and OG suffer polynomial dependence. This polynomial dependence is likely unavoidable (that is, not an artifact of the analysis) for EG/OG due to their reliance on Euclidean geometry, as discussed in [1, 2]. Consequently, A2L-OMWU may be particularly preferred in high-dimensional settings.\n\n[1] Levy, Daniel, and John C. Duchi. \"Necessary and sufficient geometries for gradient methods.\" Advances in Neural Information Processing Systems 32 (2019).\n\n[2] Cheng, Chen, Daniel Levy, and John C. Duchi. \"Geometry, Computation, and Optimality in Stochastic Optimization.\" arXiv 2025\n\n> 2.  Can any of the argument be generalized to Markov games (with linear reward function)?\n\nWe believe the core ideas behind our A2L reduction can be extended to Markov games, where normal-form games serve as a stateless special case. The main technical challenge lies in the state transitions: unlike in normal-form games, the utility of an action in a Markov game is governed by the Q-function, which incorporates both immediate and discounted future rewards and depends on evolving policies. This dynamic structure introduces significant complexity and requires a non-trivial extension of our current reduction. We view the generalization of A2L to Markov games as an important direction for future work.\n\n> 3. A few highly relevant references should be included and discussed that design last-iterate-convergent algorithms for zero-sum games based on perturbation/regularization, including Abe et al., 2022, Abe et al., 2023, Wu et al., 2023, Zeng et al., 2023.\n\nThank you for pointing out these related works! We will include and discuss them in the revised version of the paper.\n\n In particular, [Abe et al., 2022, 2023] and [Wu et al., 2023]  design algorithms based on perturbation and show last-iterate convergence to a stationary point near a Nash equilibrium in both gradient and noisy gradient feedback. [Abe et al., 2023] also show asymptotic convergence to an exact Nash equilibrium by adptively adjusting the perturbation. [Zeng et al., 2022] studies two-player zero-sum Markov games using the entropy-regularization approach and proposes a gradient-descent-ascent algorithm with a $O(T\\^{-1/3})$ last-iterate convergence. Their result requires an additional assumption (Assumption 2 in their paper) on the regularized Nash equilibrium that each entry (the probability of playing an action) has a uniform lower bound independent of the regularization strength.  \n\n- Abe, K., Sakamoto, M., & Iwasaki, A. (2022, August). Mutation-driven follow the regularized leader for last-iterate convergence in zero-sum games. In Uncertainty in Artificial Intelligence (pp. 1-10). PMLR.\n\n- Abe, K., Ariu, K., Sakamoto, M., Toyoshima, K., & Iwasaki, A. (2023). Last-Iterate Convergence with Full and Noisy Feedback in Two-Player Zero-Sum Games. In AISTATS 2023, International Conference on Artificial Intelligence and Statistics, 25-27 April 2023, Palau de Congressos, Valencia, Spain (Vol. 206, pp. 7999-8028). MLResearchPress.\n\n- Wu, J., Barakat, A., Fatkhullin, I., & He, N. (2023). Learning Zero-Sum Linear Quadratic Games with Improved Sample Complexity and Last-Iterate Convergence. arXiv preprint arXiv:2309.04272.\n\n- Zeng, S., Doan, T., & Romberg, J. (2022). Regularized gradient descent ascent for two-player zero-sum Markov games. Advances in Neural Information Processing Systems, 35, 34546-34558.\n\n> The authors explained the merit of last-iterate convergence a few times in the paper, but I am not fully convinced. From the perspectives of practical implementation, tracking the average iterates is simple to carry out and does not introduce any additional time or memory complexity. I wonder if there are more concrete practical benefits from last-iterate-convergent algorithms that can help provide a better motivation.\n\nResponse: Thanks for the comment. We would like to highlight that learning dynamics with last-iterate convergence offer important advantages over divergent dynamics that only guarantee convergence in the average. First, last-iterate convergence ensures that each player achieves stronger **sublinear dynamic regret** bounds [See e.g., [Cai-Zheng’23 Theorem 3] and our Corollary 1], whereas divergent dynamics typically only guarantee sublinear external regret and can incur linear dynamic regret.  Another advantage of last-iterate convergence is that it characterizes the **day-to-day behavior** of the learning dynamics and enables robust predictions on players’ behavior, which is not the case for divergent dynamics. \n\n- Cai, Yang, and Weiqiang Zheng. \"Doubly optimal no-regret learning in monotone games.\" International Conference on Machine Learning. PMLR, 2023.\n\n\n> Assumption 1 is another limitation, and I cannot see how any of the arguments in the paper can be applied/extended when the utility is nonlinear. However, this does not mean the work is unimportant. The normal-form game framework with linear utilities captures several fundamental and widely studied game classes, such as two-player bimatrix games and multi-player polymatrix games, including their zero-sum variants. Just being able to solve these games alone is a contribution.\n\nResponse: We thank the encouraging comment on our contribution. We recently found that the **A2L reduction can apply to other structured settings with possibly nonlinear utilities.** We will first recall the core ideas of A2L reduction and then give one example of learning dynamics for market equilibrium. \n\nThe core idea of the A2L reduction lies in the “extraction” step: when players play the average of past iterates and observe corresponding feedback, they recover the feedback they would have received had they all played the original iterate. In our current framework, this is enabled by linearity, but similar structure-based recoverability can exist beyond linear settings.\n\n**One example is the proportional response dynamics (PRD) for market equilibrium in Fisher markets** [Cheung et al., 2025] (where utilities can be nonlinear). In a fisher market, there are $n$ agents and $m$ goods. Each agent $i$ has a budget $e\\_i$ and each good $j$ has a unit supply. The proportional response dynamic works as follows: \n- Budget Spending: each player $i$ decides the allocation of budget $\\{b^t\\_{ij} \\}$ where $b^t_{ij}$ is his spending on good $j$. It must hold that $\\sum_j b^t_{ij} = e_i$; \n- Goods allocation: the amount of good $j$ allocated to agent $i$ is proportional to their spending as $x^t_{ij} = b^t_{ij} / \\sum_{i} b^t_{i, j}$. Moreover, the price of each good $j$ is defined as the sum of agents’ spending $p^t_j:= \\sum_{i} b^t_{ij}$. \n- Update: Based on the allocation $x^t_{ij}$, each buyer then updates their spending of budget $\\{ b^{t+1}_{ij} \\}$ in the next round using certain rules. \n\nThe original PRD (for GS utility) has a $O(1/T)$ convergence rate only in terms of the average price, but not the last iterate price. However, by applying A2L reduction— let each agent spend their average budget allocation $\\bar{b}^t_i = 1/t \\sum_k b^k_i$ and observe the induced allocation $\\bar{x}^t$---we can recover the original iterate's allocation due to the proportional structure. Thus, we get a modified PRD with $O(1/T)$ last-iterate convergence in price. Here, the key observation is that the feedback in PRD is the allocation $x$, which has a nice structure despite each player having nonlinear utilities.\n\nThis example illustrates that our reduction can extend to other settings where feedback remains recoverable from averaged plays, even without linearity on the utility. We will include this example in the revised version. Identifying structures that enable A2L reduction in more general settings remains an interesting future direction.\n\n- Cheung, Yun Kuen, Richard Cole, and Yixin Tao. \"Proportional Response Dynamics in Gross Substitutes Markets.\" Proceedings of the 26th ACM Conference on Economics and Computation. 2025."}]

Author rebuttal:

Meta-review: The paper provides a simple and elegant reduction from average iterate convergence to last iterate convergence in game settings of bilinear structure (this includes 2-player games and polymatrix games). Due to this reduction, the authors achieve faster convergence rates to Nash equilibrium than the state-of-the-art for full information and bandit feedback in 2-player zero-sum games. This is an important contribution as last-iterate convergence has received a lot of attention the last decade from the research community. All reviewers appreciated the contribution and so the AC. We recommend acceptance. We note that initially the paper was recommended for spotlight, but after a discussion between AC and SAC, it was pointed out that the description of the algorithm needs improvement and the decision was bumped down.
Decision: Accept (poster)