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

arXiv:2604.16087v1 Announce Type: new 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 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 Omega(T^{-1/4}) in contrast to the usual Omega(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.

Related

• Optimal last-iterate convergence in matrix games with bandit feedback using the log-barrier
• Beyond Pessimism: Offline Learning in KL-regularized Games
• Exploitation Over Exploration: Unmasking the Bias in Linear Bandit Recommender Offline Evaluation
• Restless Bandits with Individual Penalty Constraints: A New Near-Optimal Index Policy and How to Learn It

Source: arXiv cs.LG | 2026-04-20