The Harder Path: Last Iterate Convergence For Uncoupled Learning In Zero-sum Games With Bandit Feedback

Abstract

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 \(\mathcal\{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

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyfiegel2026the

Related papers

• Last-iterate Convergence Of Payoff-based Independent Learning In Zero-sum Stochastic Games (2024)0.00
• Teaching An Old Dynamics New Tricks: Regularization-free Last-iterate Convergence In Zero-sum Games Via BNN Dynamics (2026)0.00
• Adversarial Learning In Games With Bandit Feedback: Logarithmic Pure-strategy Maximin Regret (2026)0.00
• Convergence Of Heterogeneous Learning Dynamics In Zero-sum Stochastic Games (2023)2.26
• Near Optimal Convergence To Coarse Correlated Equilibrium In General-sum Markov Games (2025)0.00
• Last-iterate Convergence Of Decentralized Optimistic Gradient Descent/ascent In Infinite-horizon Competitive Markov Games (2021)0.00
• Learning In Zero-sum Markov Games: Relaxing Strong Reachability And Mixing Time Assumptions (2023)0.00
• Faster Last-iterate Convergence Of Policy Optimization In Zero-sum Markov Games (2022)0.00