acceptodds
Under review as a conference paper at ICLR 2027

Faster Last-Iterate Convergence for Zero-Sum Games with Stochastic Feedback via Anchor-Regularized Learning

Abstract

We study uncoupled learning in two-player zero-sum matrix games under stochastic feedback. Each player updates from only its own feedback, without observing the opponent's action, strategy, or payoffs. We propose anchor-regularized follow-the-regularized-leader (AR-FTRL), which repeatedly solves the game regularized toward an anchor strategy profile, updating the anchor to each solution. As a warm-up, under unbiased noisy gradients with bounded second moment, the norm of the gap of the last strategy converges at rate . This guarantee exploits the metric subregularity of the zero-sum game's bilinear structure, under which the regularized equilibrium contracts toward the Nash equilibrium set by a constant factor at each anchor update. Our main result extends this to bandit feedback, where each player observes only the scalar payoff of its sampled action. Under a unique fully mixed Nash equilibrium, the norm of the gap of the last strategy converges at the same rate after observations, even though the importance-weighted gradient estimator has unbounded second moment near the boundary of the simplex. Both guarantees hold only at the anchor updates, not at every round. Under bandit feedback, this yields a faster rate than the of every-round guarantees, though the guarantee is no longer anytime.

Primary area:
optimization
Keywords:
learning in games, bandit feedback, uncoupled algorithm

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_eog7OpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies L2 norm of gap from Nash equilibrium in zero sum games where two players play according to their own feedback. The paper presents an algorithm where the two players can play accordingly and achieve expected last iterate convergence in the L2 norm. The paper explores both noisy gradient feedback setting and bandit feedback setting and shows a desirable O~(T−1/2)\tilde O(T^{-1/2}) in both cases.

Critical strengths

The paper is written clearly and easy to follow. The problem studied is interesting and last iterate convergence in this L2 metric is not studied before for this problem.

Critical weaknesses

None.

Questions for authors

None.

2 comments

We thank the reviewer for the positive assessment and support for our work. We appreciate your recognition of the clarity of the presentation and the novelty of our results.

Thank you for your constructive feedback and continued positive evaluation of our work.

Reviewer_7htqOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes Anchor-Regularized Follow-the-Regularized-Leader (AR-FTRL) for uncoupled learning in two-player zero-sum matrix games under stochastic feedback. The algorithm approximately solves an anchor-regularized game using log-barrier FTRL within each epoch and periodically updates the anchor to the terminal iterate.

The authors establish a last-iterate convergence rate of O~(T−1/2)\widetilde O(T^{-1/2}) in the root-mean-square duality gap under unbiased noisy-gradient feedback. Their main theorem extends this rate to bandit feedback under the assumption of a unique fully mixed Nash equilibrium. The guarantee holds only at prescribed epoch boundaries, rather than at every iteration.

Critical strengths

AR-FTRL achieves its checkpoint guarantee using inner-loop iterates instead of averaging strategies. Besides, the epoch schedule does not require prior knowledge of the metric-subregularity constant, the minimum equilibrium probability, or the final time horizon.

Critical weaknesses

The main claimed improvement from O~(t−1/4)\widetilde O(t^{-1/4}) to O~(T−1/2)\widetilde O(T^{-1/2}) is not directly comparable to existing every-round last-iterate guarantees. In particular, it appears possible to obtain the same checkpoint-only rate using a standard uncoupled no-regret bandit algorithm by occasionally playing its running-average strategies at predetermined checkpoints.

This simple construction would inherit the conventional $ \widetilde O(T^{-1/2}) $ average-strategy guarantee without requiring a unique fully mixed equilibrium. Therefore, the rate improvement itself does not to me appear to establish a fundamental advance over standard bandit-learning guarantees.

  1. The main bandit theorem requires a unique fully mixed Nash equilibrium, and its hidden constants depend on the minimum equilibrium probability and the metric-subregularity constant. These dependencies may lead to unfavorable finite-sample behavior in nearly degenerate games.

Only the biased Rock–Paper–Scissors benchmark is explicitly identified as satisfying the main theorem's assumptions. The remaining experiments do not systematically examine the interior-equilibrium margin, the onset of the predicted rate, or sensitivity to the regularization and epoch schedule. Moreover, the comparison table combines different convergence notions and problem classes, potentially overstating the strength of the rate improvement.

Questions for authors

The constant in Theorem 6.3 depends on $ \rho $, and Appendix C introduces a potentially unfavorable dependence on this quantity in the global-to-local recursion. Can the authors characterize the resulting finite-sample complexity more explicitly and evaluate performance as $ \rho $ approaches zero?

4 comments
AuthorsOpenReview ↗

Response to Reviewer 7htq (1/2)

Thank you for taking the time to review our work and for providing your valuable feedback. Our detailed responses to your comments and questions are provided below.


On Last-Iterate Convergence without Strategy Averaging

Playing running-average strategies at predetermined checkpoints would be expected to yield convergence at those checkpoints. However, our contribution is to attain the O~(T−1/2)\widetilde{\mathcal{O}}(T^{-1/2}) rate along AR-FTRL's own sequence of updates, without inserting time-averaged strategies at checkpoints. Avoiding this step is particularly important with function approximation, such as neural-network policies, where representing the average policy can require retaining past models or introducing additional approximation error. For this reason, avoiding strategy averaging is an important motivation for last-iterate convergence, as emphasized by Lee et al. (2021) and Fiegel et al. (2025).

Indeed, regularizing learning toward an evolving reference strategy, as in our method, has been used in large-scale applications to learn policies without strategy averaging. For example, Perolat et al. (2022) periodically reset the reference strategy when learning in large extensive-form games, a principle shared by our method. Munos et al. (2024) also use regularization toward an evolving reference strategy for LLM alignment. These applications highlight the practical importance of learning without strategy averaging.


References

  • Lee et al. Last-iterate convergence in extensive-form games. In NeurIPS, 2021.
  • Fiegel et al. The harder path: Last iterate convergence for uncoupled learning in zero-sum games with bandit feedback. In ICML, 2025.
  • Perolat et al. Mastering the game of Stratego with model-free multiagent reinforcement learning. Science, 2022.
  • Munos et al. Nash learning from human feedback. In ICML, 2024.
AuthorsOpenReview ↗

Response to Reviewer 7htq (2/2)

On the Dependence on ρ∗\rho_\ast and τ\tau

As the reviewer points out, the upper bound deteriorates as ρ∗\rho_\ast decreases. More explicitly, Lemmas C.2, C.5, and C.6 yield a sufficient sample complexity of O~(ρ∗−4ε−2)\widetilde{\mathcal{O}}(\rho_\ast^{-4}\varepsilon^{-2}) for attaining an L2L^2 duality gap of at most ε\varepsilon at an epoch boundary (with other parameters fixed). The bound also deteriorates as the metric subregularity constant τ\tau approaches zero.

To address the reviewer's question about the behavior as ρ∗\rho_\ast approaches zero, we conduct additional experiments on a family of 3×33\times3 zero-sum matrix games with varying ρ∗\rho_\ast. The games are defined by

A=1211⊤+14(I−1p⊤)(I−p1⊤),A=\frac12\mathbf{1}\mathbf{1}^{\top}+\frac14(I-\mathbf{1}p^{\top})(I-p\mathbf{1}^{\top}),

p=(ρ∗,1−ρ∗2,1−ρ∗2),p=\left(\rho_\ast,\frac{1-\rho_\ast}{2},\frac{1-\rho_\ast}{2}\right),

where 1=(1,1,1)⊤\mathbf{1}=(1,1,1)^\top and II is the 3×33\times3 identity matrix. For each ρ∗∈{1/4,1/20,1/100,1/500}\rho_\ast\in\{1/4,1/20,1/100,1/500\}, the game has a unique fully mixed Nash equilibrium x∗=y∗=px^\ast=y^\ast=p, and all payoff entries lie in [0,1][0,1]. Note that changing ρ∗\rho_\ast may also change τ\tau in this setting, so the effects of these two quantities cannot be fully separated in these experiments. We have added these experiments to Appendix G (Figure 3), using the same settings as in the main experiments, with 100100 evaluation seeds and T=105T=10^5 payoff observations.

In these experiments, we do not observe a systematic deterioration of the gap as ρ∗\rho_\ast decreases. These results suggest that the dependence on ρ∗\rho_\ast in our upper bound may be pessimistic for the gap, at least in the games considered in these experiments. Improving the dependence on ρ∗\rho_\ast and τ\tau and removing the fully mixed Nash equilibrium assumption remain open questions.


On Experimental Coverage and Parameter Sensitivity

To examine sensitivity to the regularization strength and learning rate, we have added experiments on the biased Rock–Paper–Scissors game under bandit feedback (Appendix H, Figure 4). Specifically, we vary μ∈{0.5,0.75,1,2}\mu\in\{0.5,0.75,1,2\} with η=0.1\eta=0.1 fixed, and vary η∈{0.01,0.1,1,10}\eta\in\{0.01,0.1,1,10\} with μ=1\mu=1 fixed. Each setting uses the same 100100 evaluation seeds and a budget of T=105T=10^5 payoff observations. The epoch schedule Nk=⌈exp⁡(k+1)⌉N_k=\lceil\exp(\sqrt{k+1})\rceil is prescribed by Theorem 6.3 and contains no tunable parameter. So, we use this same schedule throughout the sensitivity experiment.

Across the tested range of regularization strengths, we observe an overall decrease in the gap. In contrast, the largest tested learning rate yields less stable behavior. These observations are consistent with Theorem 6.3, whose convergence guarantee allows any fixed μ>0\mu>0 but requires ηB<1\eta B<1.


On the Comparison in Table 1

We recognize that the O~(t−1/4)\widetilde{\mathcal{O}}(t^{-1/4}) and O~(T−1/2)\widetilde{\mathcal{O}}(T^{-1/2}) rates are not directly comparable, because the assumptions and the times at which convergence is guaranteed differ. However, the primary purpose of Table 1 is to illustrate that a faster convergence rate is achievable in the more restricted setting of two-player zero-sum games when the requirement of convergence at every iteration is further relaxed. We have revised the caption of Table 1 and the discussion in Section 2 to clarify the qualifications of this comparison rather than suggest a direct rate improvement under identical conditions.

Thank you for the detailed responses. I appreciate the improvements, particularly the characterization of dependence on (ρ\*)(\rho_\*). However, my main concerns regarding the comparability of the convergence guarantees and the restrictive assumptions remain. Thus, I currently maintain my score.

Thank you for your response and thoughtful engagement with our rebuttal.

Reviewer_Q11uOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies the last-iterate convergence rate of anchor-regularized learning in the two-player zero-sum games. In their AR-FTRL algorithm, the learning dynamics evolves through many epochs, and within each epoch an anchor-perturbed game is approximately solved. After one epoch, the anchor is updated so the iterates keep getting closer to the original Nash equilibrium. Using this algorithm, they prove an O(1/T)O(1/\sqrt{T}) last-iterate convergence rate in both noisy gradient feedback and bandit feedback settings. Authors also implement numerical experiments to show the performance of their algorithm.

Critical strengths
  • The paper pushes the known rate in the bandit feedback setting from O~(1/T1/4)\tilde{O}(1/T^{1/4}) to O~(1/T1/2)\tilde{O}(1/T^{1/2}), matching the classic averaged-iterate convergence rate.
  • To handle the bandit feedback setting, one needs to overcome the difficulty from unbounded variance of the importance-weighted gradient estimate, which is nontrivial. I appreciate that the authors spent effort in explaining the technical details in the paper.
  • The paper is generally well written and easy to follow.
Critical weaknesses
  • Even though the rate is improved, the new last-iterate convergence rate depends on the metric subregularity constant, which is problem-dependent. However, I think most of the previous work does not have such dependency. If this is the case, in my opinion, this makes the comparison in Table 1 a bit unfair. It would be better if the authors can clarify this point in the paper.
  • The paper says that “To the best of our knowledge, this is the first last-iterate rate of this order in a constrained bilinear game under noisy gradient feedback.” There could be a more detailed discussion on this point. For example, under an error bound condition, which is closely related to metric subregularity [2], [1] showed that extragradient with variance reduction achieves linear last-iterate convergence.

[1] Nan, Tianlong, Yuan Gao, and Christian Kroer. "Convergence of Extragradient SVRG for Variational Inequalities: Error Bounds and Increasing Iterate Averaging." arXiv:2306.01796 (2023).

[2] Wei, Chen-Yu, Chung-Wei Lee, Mengxiao Zhang, and Haipeng Luo. "Linear last-iterate convergence in constrained saddle-point optimization." In ICLR, 2021.

  • The new convergence rate is restricted to games with a unique, fully mixed Nash equilibrium, but this is acceptable as a first step toward improving the convergence rate.
Questions for authors
  • Could you run a larger number of iterations to see whether AR-FTRL can achieve a small gap numerically?
3 comments

Thank you for taking the time to review our work and for providing your valuable feedback. Our detailed responses to your comments and questions are provided below.


On the Dependence on the Metric Subregularity Constant

We agree that our convergence bound depends on the problem-dependent metric subregularity constant τ\tau, and that this dependence matters when comparing the guarantees. The O~(T−1/2)\widetilde{\mathcal{O}}(T^{-1/2}) rate describes the dependence on the observation budget for a fixed game, with the dependence on τ\tau absorbed into the suppressed constant. Thus, our rate does not imply a uniformly smaller observation budget across games. We have revised the caption of Table 1 and the discussion following Theorem 6.3 to clarify this dependence. Characterizing the worst-case convergence rate as τ\tau approaches zero remains an important direction for future work.


On Linear Last-Iterate Convergence in [1]

We would like to emphasize that [1] considers a richer feedback setting than ours. Their method achieves linear last-iterate convergence under an error-bound condition but requires additional access to exact full gradients, which we do not assume. Our guarantees require only conditionally unbiased gradient observations with bounded second moment. We will cite [1] and clarify this distinction in the camera-ready version.


On Running More Iterations

Thank you for this suggestion. We have extended the AR-FTRL experiment on the biased Rock–Paper–Scissors game under bandit feedback to T=106T=10^6 payoff observations (Appendix I, Figure 5), using the same hyperparameters, epoch schedule, and uniform initialization as in the main experiments, with 100100 evaluation seeds. The gap continues to decrease over the extended horizon, showing that AR-FTRL can attain smaller gaps when run for more iterations.

I thank the author for the clarification. I appreciate the additional experiments. I will support the acceptance.

Thank you for your constructive feedback and continued positive evaluation of our work.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.