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 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 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
O(t−1/8)
Chen et al. (2024)
Final outer iterate; in expectation
O(t−1/8)
Cai et al. (2023)
All rounds; high probability
O(t−1/(9+ν))
ARTD (this work)
All rounds; high probability
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 ν>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.
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 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
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