We study last-iterate convergence in unknown two-player zero-sum matrix games with bandit payoff feedback and observed opponent actions. For games with d actions per player, we develop an algorithm achieving a duality gap of O(d/t) with high probability, simultaneously at every round t. This improves the dimension dependence of the best previously known guarantee by a factor of d3/2. The rate matches a standard bandit lower bound, establishing minimax optimality in both the number of actions and the number of rounds, up to logarithmic factors. The algorithm is computationally efficient, requiring only O(d) time and memory per round. Our technical contribution is a joint design of adaptive averaging and corrected exponential weights that absorbs estimation variance, together with a potential argument that bounds phase durations.
Figures & tables
Work
Opponent actions
Duality gap at round t
Rounds for gap ε
Cai et al. (2023)
Unobserved
O(dt−1/8)
O(d4/ε8)
Cai et al. (2025)
Unobserved
O(d1/5t−1/5)
O(d/ε5)
Fiegel et al. (2026a)
Unobserved
O(d2t−1/4)
O(d8/ε4)
Hait et al. (2026)
Observed
O(d2/t)
O(d4/ε2)
Bandit lower bound
Observed
Ω(d/t)
Ω(d/ε2)
Our work
Observed
O(d/t)
O(d/ε2)
Table 1: Representative last-iterate guarantees for zero-sum matrix games with d actions per player and bandit payoff feedback. All upper bounds hold with high probability uniformly over time. The last column gives sufficient rounds to attain and maintain duality gap at most ε ; the row for the lower bound gives necessary rounds at fixed confidence. The gap lower bound assumes t≥d . For Fiegel et al. (2026a) , the dependence on d is not stated in their paper, and the bounds reported here are derived from their proof (see details in Appendix B ).
Input: Number of actions d≥2 and confidence δ∈(0,1) .
Initialize p=q=1/d .
for k=0,1,2,… do
Set e=21−k and ρ=δ/2k+1 ; compute τ0,η by ( 5 ).
Initialize x=u=p , y=v=q , and τ=τ0 .
while τ<4τ0 do
Compute ri=ui/xi , sj=vj/yj , and a by ( 2 ); set ζ=ηa .
Last-iterate convergence of learning dynamics in games has attracted significant recent attention. In two-player zero-sum games with bandit feedback, where only the loss of the selected action pair is observed, Fiegel et al. (2025) show a separation between average-iterate and last-iterate convergence in duality gap: while the optimal t^(-1/2) rate after t rounds is achievable for the former via standard no-regret algorithms, the latter cannot converge faster than t^(-1/3) in expectation or t^(-1/4) with high probability. However, in many practical settings, such as preference learning, the players observe not only their loss but also the opponent's action. This raises a natural question: can such additional information enable faster last-iterate convergence? We answer this question affirmatively, showing that t^(-1/2) last-iterate convergence is achievable with high probability in this setting, via an efficient algorithm that updates its strategy infrequently by solving an estimated log-barrier-regularized game. We identify fundamental obstacles preventing standard analysis for multi-armed bandits, the single-player case, from generalizing to games, and develop a novel analysis to overcome them. Experiments confirm that our algorithm indeed converges faster than naive baselines and prior methods that do not exploit opponent-action feedback. Finally, we note that our results also improve those for dueling bandits, a special case with skew-symmetric game matrices.
Soumita Hait, Ping Li, Haipeng Luo +1
University of Southern California · Shanghai University of Finance and Economics · University of Iowa
We study the problem of learning minimax policies in zero-sum matrix games. Fiegel et al. (2025) recently showed that achieving last-iterate convergence in this setting is harder when the players are uncoupled, by proving a lower bound on the exploitability gap of Omega(t^{-1/4}). Some online mirror descent algorithms were proposed in the literature for this problem, but none have truly attained this rate yet. We show that the use of a log-barrier regularization, along with a dual-focused analysis, allows this O-tilde(t^{-1/4}) convergence with high-probability. We additionally extend our idea to the setting of extensive-form games, proving a bound with the same rate.
Come Fiegel, Pierre Menard, Tadashi Kozuno +2
ENSAE Paris – CREST, France · ENS Lyon, France · Isara Labs +2
We study the problem of learning in zero-sum matrix games with repeated play and bandit feedback. Specifically, we focus on developing uncoupled algorithms that guarantee, without communication between players, the convergence of the last-iterate to a Nash equilibrium. Although the non-bandit case has been studied extensively, this setting has only been explored recently, with a bound of O(T−1/8) on the exploitability gap. We show that, for uncoupled algorithms, guaranteeing convergence of the policy profiles to a Nash equilibrium is detrimental to the performance, with the best attainable rate being Ω(T−1/4) in contrast to the usual Ω(T−1/2) rate for convergence of the average iterates. We then propose two algorithms that achieve this optimal rate up to constant and logarithmic factors. The first algorithm leverages a straightforward trade-off between exploration and exploitation, while the second employs a regularization technique based on a two-step mirror descent approach.
Côme Fiegel, Pierre Ménard, Tadashi Kozuno +2
ENSAE Paris - CREST, Palaiseau, France · Inria - FairPlay · ENS Lyon, Lyon, France +3