Minimax Last-Iterate Convergence in Matrix Games with Observed Actions

Yuheng Zhang

cs.LGSep 28, 2026

Minimax Last-Iterate Convergence in Matrix Games with Observed Actions

Authors: Yuheng Zhang

Organizations: University of Illinois Urbana-Champaign

Abstract

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 $\widetilde{\mathcal{O}}(\sqrt{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 $d^{3/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 $\mathcal{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 $\varepsilon$
Cai et al. (2023)	Unobserved	$\widetilde{\mathcal{O}}(\sqrt{d}\,t^{-1/8})$	$\widetilde{\mathcal{O}}(d^{4}/\varepsilon^{8})$
Cai et al. (2025)	Unobserved	$\widetilde{\mathcal{O}}(d^{1/5}t^{-1/5})$	$\widetilde{\mathcal{O}}(d/\varepsilon^{5})$
Fiegel et al. (2026a)	Unobserved	$\widetilde{\mathcal{O}}(d^{2}t^{-1/4})$	$\widetilde{\mathcal{O}}(d^{8}/\varepsilon^{4})$
Hait et al. (2026)	Observed	$\widetilde{\mathcal{O}}(d^{2}/\sqrt{t})$	$\widetilde{\mathcal{O}}(d^{4}/\varepsilon^{2})$
Bandit lower bound	Observed	$\Omega(\sqrt{d/t})$	$\Omega(d/\varepsilon^{2})$
Our work	Observed	$\boldsymbol{\widetilde{\mathcal{O}}(\sqrt{d/t})}$	$\boldsymbol{\widetilde{\mathcal{O}}(d/\varepsilon^{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

\varepsilon

; the row for the lower bound gives necessary rounds at fixed confidence. The gap lower bound assumes

t\geq 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\geq 2$ and confidence $\delta\in(0,1)$ .
Initialize $p=q=\mathbf{1}/d$ .
for $k=0,1,2,\ldots$ do
	Set $e=2^{1-k}$ and $\rho=\delta/2^{k+1}$ ; compute $\tau_{0},\eta$ by ( 5 ).
	Initialize $x=u=p$ , $y=v=q$ , and $\tau=\tau_{0}$ .
	while $\tau<4\tau_{0}$ do
		Compute $r_{i}=u_{i}/x_{i}$ , $s_{j}=v_{j}/y_{j}$ , and $a$ by ( 2 ); set $\zeta=\eta a$ .

Table 2

Explore similar work

Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions
May 10, 2026Soumita Hait, Ping Li, Haipeng Luo +1Imperfect-Information Games Bandits
University of Southern California · Shanghai University of Finance and Economics · University of Iowa
Optimal last-iterate convergence in matrix games with bandit feedback using the log-barrier
Apr 16, 2026Come Fiegel, Pierre Menard, Tadashi Kozuno +2Imperfect-Information Games Minimax
ENSAE Paris – CREST, France · ENS Lyon, France · Isara Labs +2
The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
Apr 17, 2026Côme Fiegel, Pierre Ménard, Tadashi Kozuno +2Imperfect-Information Games Mirror Descent
ENSAE Paris - CREST, Palaiseau, France · Inria - FairPlay · ENS Lyon, Lyon, France +3

May 10, 2026, cs.LGJ/K move · Enter open · S save

Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions

Soumita Hait, Ping Li, Haipeng Luo, Mengxiao Zhang

University of Southern California · Shanghai University of Finance and Economics · University of Iowa

Imperfect-Information Games Bandits Convergence

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions

Optimal last-iterate convergence in matrix games with bandit feedback using the log-barrier

The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback