From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications

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.

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.

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?

A: We 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:

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

We 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!

Cutkosky, Ashok. "Anytime online-to-batch, optimism and acceleration." International conference on machine learning. PMLR, 2019.

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.

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.

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

[1] Levy, Daniel, and John C. Duchi. "Necessary and sufficient geometries for gradient methods." Advances in Neural Information Processing Systems 32 (2019).

[2] Cheng, Chen, Daniel Levy, and John C. Duchi. "Geometry, Computation, and Optimality in Stochastic Optimization." arXiv 2025

2. Can any of the argument be generalized to Markov games (with linear reward function)?

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

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.

Thank you for pointing out these related works! We will include and discuss them in the revised version of the paper.

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.

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

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

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

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

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.

Response: 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.

• Cai, Yang, and Weiqiang Zheng. "Doubly optimal no-regret learning in monotone games." International Conference on Machine Learning. PMLR, 2023.

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.

Response: 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.

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

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:

• 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$;
• 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}$.
• 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.

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

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

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

We appreciate that reviewer yhjx finds our results interesting and well presented. We address the minor remarks below.

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?

A: Thank you very much for pointing out this typo. The correct version of the inequalities after 585 is

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

2. Line 598: Please give some more explanation for the expression for delta^t.

A: 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.

In 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

This explains the expression for $\delta^t$. We will include this clarification in the revised version. Thank you again for your thoughtful question.

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.

A: 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.

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

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.

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.

A: 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:

1. 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.
2. 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.
3. 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.

We will include this comparison with Cutkosky (2019) in the revised version of the paper. Thank you again for the helpful suggestion.

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?

A: Thank you for the insightful question!

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.

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.

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.

A: 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)).

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?

A: 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.

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.

A: 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.

6. Could the authors also clarify the dependence on the other constants when compared to Cai et al. (2023)? in Theorem 4?

A: 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.

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.

Response: 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.

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

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:

• 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$;
• 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}$.
• 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.

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

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

References

Cutkosky, Ashok. "Anytime online-to-batch, optimism and acceleration." International conference on machine learning. PMLR, 2019.

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

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.

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.