Fast Last-Iterate Convergence in Zero-Sum Markov Games with Bandit Feedback

Yuheng Zhang

cs.LGOct 5, 2026

Fast Last-Iterate Convergence in Zero-Sum Markov Games with Bandit Feedback

Authors: Yuheng Zhang

Organizations: University of Illinois Urbana-Champaign

Abstract

We study last-iterate convergence in unknown two-player zero-sum discounted Markov games with bandit feedback. The players learn independently along a single trajectory without observing each other's actions. We develop Adaptive Regularized TD Learning (ARTD), which achieves a $\widetilde{\mathcal{O}}(t^{-1/4})$ duality gap bound for the current policies under a uniform hitting time assumption, with high probability simultaneously over all rounds and starting states. This improves the $\widetilde{\mathcal{O}}(t^{-1/(9+ν)})$ rate of Cai et al. (2023), for any fixed $ν>0$ , under the same feedback model and hitting time assumption. Our algorithm requires no knowledge of the hitting time bound, the time horizon, or the confidence level. To stabilize policy learning as value estimates change, we separate fast temporal difference averaging from bounded value updates. We adapt log-barrier regularization to the progress of value estimation, controlling both policy and value errors throughout learning. Together, these mechanisms enable fast convergence of the policies actually played, even when the players learn independently from bandit feedback.

Figures & tables

Work	Convergence guarantee	Duality gap bound
Wei et al. (2021a)	Final outer iterate; high probability	$\widetilde{\mathcal{O}}(t^{-1/8})$
Chen et al. (2024)	Final outer iterate; in expectation	$\widetilde{\mathcal{O}}(t^{-1/8})$
Cai et al. (2023)	All rounds; high probability	$\widetilde{\mathcal{O}}(t^{-1/(9+\nu)})$
ARTD (this work)	All rounds; high probability	$\widetilde{\mathcal{O}}(t^{-1/4})$

Table 1: Last-iterate guarantees under bandit feedback in two-player zero-sum discounted Markov games. Here

t

counts transition samples; fixed game parameters and logarithmic factors are suppressed, and

\nu>0

is fixed. Wei et al. (2021a) , Cai et al. (2023) , and ARTD use the same uniform hitting assumption (Assumption 1 ); Chen et al. (2024, Assumption 3.2) additionally require aperiodicity under every deterministic stationary policy pair. The first two rates use parameters tuned to the sample budget. Wei et al. (2021a) also require a hitting time bound, whereas Cai et al. (2023) and ARTD do not. For Wei et al. (2021a, Corollary 5) , we convert the bound on squared policy distance to a duality gap bound. Chen et al. (2024, Theorem 3.5) bound the expected gap under a fixed initial distribution; the other guarantees are uniform over starting states. All rounds means simultaneously on one high-probability event.

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

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

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

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