acceptodds
Under review as a conference paper at ICLR 2027

High-Probability Last-Iterate Convergence for Adaptively Regularized Mirror Descent in Games with Bandit Feedback

Abstract

Regularization is a powerful technique for establishing last-iterate convergence, typically by augmenting the payoff functions with auxiliary terms that induce strong monotonicity of the game operator to stabilize learning dynamic. Existing approaches commonly rely on a gradually vanishing regularization coefficient so that the resulting last-iterate strategies can approach an NE of the original unregularized game. In this work, we study two-player zero-sum games under bandit feedback, where each player observes only the payoff associated with its sampled action, and introduce a fixed-coefficient regularization framework that perturbs the payoff based on the distance to an anchoring strategy. Specifically, we propose an adaptively regularized mirror descent algorithm equipped with a log-barrier regularizer, which periodically updates the anchoring strategy while keeping the regularization coefficient fixed. Through a dual-norm analysis, we prove that the resulting uncoupled algorithm achieves an anytime high-probability last-iterate convergence rate of in both matrix games and extensive-form games (EFGs). We further establish a constant-probability lower bound of over a fixed horizon under the same strictly uncoupled bandit information model, revealing the remaining gap between our upper bound and the best possible convergence rate suggested by the lower bound. Experiments on four EFG benchmarks demonstrate the competitive performance of our method against existing baselines.

Primary area:
learning theory
Keywords:
high-probability, last-iterate convergence, mirror descent, bandit, matrix game, extensive-form game

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_gxQUOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies last-iterate convergence to Nash equilibrium in two-player zero-sum games with bandit feedback. It proposes log-barrier mirror descent with a fixed regularization coefficient and periodically updated anchors, claiming an anytime, high-probability exploitability rate of O(t−1/4)O(t^{-1/4}) for matrix and extensive-form games. It also establishes a fixed-horizon, constant-probability Ω(T−1/2)\Omega(T^{-1/2}) lower bound. Experiments on four EFG benchmarks show competitive last-iterate performance.

Critical strengths
  • The paper studies an interesting and relevant theoretical problem. Convergence of the current strategy under limited feedback is valuable and substantially harder than convergence of averaged strategies. The theoretical results appear comprehensive and sound, though I did not check all of the proofs in detail.
Critical weaknesses
  • The theoretical contribution is only partially novel and feels incremental relative to prior works. The main convergence result appears to be primarily an algorithmic and analytical extension of Fiegel et al. (2026). It matches their O(t^{-1/4}) rate and retains the same overall proof architecture. The main additional technical work appears to involve controlling the anchor-induced bias ete_t and intra-epoch drift, together with a Taylor-based residual analysis and sharper bounds on the whitened game operator. These refinements may be useful, but their significance beyond adapting the existing framework to periodically updated anchors is not yet sufficiently clear.
  • Algorithms 1 and 2 require an initial strategy satisfying a small residual condition involving the unknown game operator. The paper does not provide an uncoupled bandit procedure, or sample-complexity accounting, for obtaining this initialization. Consequently, the guarantee appears conditional on a nontrivial starting point. How can each player obtain such an initialization using only its own bandit observations, and what additional sample complexity does this require?
Questions for authors

See weaknesses.

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

The paper gives an algorithm with fixed regulaization for two player zero sum games with an upper bound of O(T−1/4)O(T^{-1/4}) and a lower bound of Ω(T−1/2)\Omega (T^{-1/2}). The analysis is based on the dual norm, which is different from previous analysis.

Critical strengths

The analysis is new and the paper is generally well written.

Critical weaknesses
  1. Maybe I'm not getting this, but what's the main benefit of fixed regulaization? As it doesn't improve the known upper bound or the known lower bound, I am not sure whether this is a sufficient enough contribution. Despite this, I would be happy to recommend this paper if it provides a more insightful (for example, much simpler) analysis than previous ones, but this does not seems to be the case.
  2. The algorithm also seems to have game dependent initilization. As the initialisation depends on F(\omega_0), which requires knowledge of the unknown payoff matrix A.
  3. More question regarding the EFG results, see below.
Questions for authors

In the EFG analysis, it seems that the dilated log barrier requires ∇2Φ(ω)=diag(ωi−2)\nabla^2 \Phi(\omega) = \mathrm{diag}(\omega_i^{-2}). Can you give an example of dilated log barrier that satisfy this?

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

This paper investigates the last-iterate convergence for learning in two-player zero-sum games under bandit feedback. The authors propose a mirror descent-type algorithm with a fixed regularization coefficient and periodic anchor updates, and establish a high-probability anytime convergence guarantee of O~(T−1/4)\widetilde{O}(T^{-1/4}) for matrix games. They also extend their approach to extensive-form games and provide an Ω(T−1/2)\Omega(T^{-1/2}) lower bound for the fixed-horizon setting, along with a matching upper bound.

Critical strengths

Learning in matrix games under bandit feedback is an important research problem that has attracted considerable interest from the community, and this paper addresses this problem.

Critical weaknesses

There are several critical weaknesses in this paper.

The first and most serious weakness is the lack of clarity in the presentation, particularly in the discussion of the algorithm and theoretical analysis. The paper is extremely difficult to follow. Overall, the manuscript does not seem to have been carefully proofread by the authors, and I believe substantial revisions are necessary. In particular, Section 3 is very dense and consists of too many mathematical notions without sufficient explanation, making it difficult to understand the key ideas behind the analysis.

The second weakness is that the motivation for the research question is unclear. In Lines 70-72, the authors ask whether it is possible to achieve last-iterate convergence under bandit feedback without using a decreasing regularization coefficient. However, the paper does not explain why avoiding a decreasing regularization coefficient would be beneficial. Moreover, even if such an approach had clear advantages, the proposed algorithm relies on time-varying operations to construct the anchor (Algorithm 1). It is unclear what is gained by shifting the decay from the regularization coefficient to the anchor construction.

The third weakness is that the contribution of the lower bound does not seem particularly significant. The Ω(T−1/2)\Omega(T^{-1/2}) lower bound leaves a substantial gap compared with the O~(T−1/4)\widetilde{O}(T^{-1/4}) upper bound. Moreover, the difficulty of the problem can differ substantially depending on whether the time horizon is fixed, but this distinction does not seem to be sufficiently discussed. I believe the authors should explain more clearly why this result is valuable.

As a minor point, the experimental results also seem somewhat strange, as discussed in the questions below.

Questions for authors

In the Lewis signaling experiment in Figure 1, the proposed method seems to achieve significantly good performance even at just 100=110^0 = 1 episode. It is unclear from the figure why the proposed method performs so well from the very beginning of the game (before learning), and I would like the authors to explain this.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.