The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
| Authors | Côme Fiegel et al. |
| Year | 2026 |
| Field | Machine Learning |
| arXiv | 2604.16087 |
| Download | |
| Categories | cs.LG, stat.ML |
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-step mirror descent approach.
Engineering Breakdown
Plain English
This paper tackles the problem of learning Nash equilibria in zero-sum matrix games where two players interact repeatedly but can only observe their own payoffs (bandit feedback), without communicating with each other. The authors prove a fundamental lower bound: uncoupled algorithms—those that don't require inter-player communication—cannot achieve better than O(T^-1/4) convergence rate for last-iterate convergence to Nash equilibrium, which is slower than the O(T^-1/2) rate achievable when tracking average iterates. They show this gap exists because guaranteeing convergence of individual policy profiles to Nash equilibrium inherently conflicts with sample efficiency in the bandit setting, a trade-off not present in the non-bandit case.
Core Technical Contribution
The paper's core contribution is proving a fundamental lower bound of Ω(T^-1/4) for uncoupled learning algorithms in zero-sum games with bandit feedback, establishing that last-iterate convergence guarantees are inherently more expensive than average-iterate convergence. Prior work only achieved O(T^-1/8) bounds, and this paper both tightens that understanding and reveals the theoretical barrier: ensuring individual policies converge to Nash without communication requires quadratically more samples than ensuring the empirical average converges. The authors propose two new algorithms that match or approach this lower bound, providing both negative results (what's impossible) and constructive algorithms (what is achievable).
How It Works
The setup involves two players playing a zero-sum game repeatedly over T rounds, where each player only observes their own reward after each round (bandit feedback), not the opponent's strategy or payoff. The algorithms are uncoupled, meaning each player runs their own learning procedure independently without any message-passing or coordination. The key technical approach involves analyzing the information-theoretic cost of learning a Nash equilibrium strategy profile: in the full-information case, players can estimate opponent strategies precisely, but with bandit feedback, they must simultaneously learn their own best response while maintaining compatibility with an equilibrium. The paper proves that any algorithm guaranteeing the last iterate (the final policy after T rounds) lies near a Nash equilibrium must suffer Ω(T^-1/4) convergence rate, then constructs explicit algorithms achieving this rate using variance-reduced gradient estimation and careful exploration-exploitation trade-offs.
Production Impact
In production systems using multi-agent reinforcement learning—such as pricing algorithms competing in auctions, trading systems, or game-playing agents—this work clarifies fundamental limits on how fast independent agents can converge to stable equilibria without communication. Engineers building decentralized learning systems should expect sample complexity roughly proportional to T^4 for strong guarantees on final policy stability, versus T^2 for weaker average-performance guarantees. This matters concretely: if you need agents to reach equilibrium in 1000 steps, the bandit setting may require 10-100x more experience than you'd initially estimate from full-information literature. The trade-off is worth understanding because many real systems genuinely have bandit feedback (you observe outcomes, not opponents' internal decision-making), making this analysis directly relevant to practical deployment where convergence speed and sample efficiency are critical.
Limitations and When Not to Use This
The paper focuses exclusively on zero-sum matrix games, which are a simplified model—real multi-agent systems involve continuous action spaces, partial observability, non-zero-sum incentives, and dynamic environments. The uncoupled learning assumption, while theoretically clean, doesn't capture scenarios where agents can send signals or use correlated randomization, which are sometimes available in practice. The lower bound applies to worst-case games; specific game structures may admit faster learning, but the paper doesn't characterize which properties enable this. The bandit feedback model assumes players only see their own payoff, but many real systems have access to richer signals (action counts, population statistics) that could potentially break the stated lower bounds.
Research Context
This work extends recent progress in learning Nash equilibria under bandit feedback, building on the O(T^-1/8) result mentioned in the abstract and earlier full-information learning theory. It connects to the broader literature on multi-agent reinforcement learning and game-theoretic learning dynamics, particularly the uncoupled learning framework initiated by Monderer and Tennenholtz. The paper contributes to our theoretical understanding of fundamental limits in decentralized learning, analogous to how communication complexity and information-theoretic lower bounds constrain distributed algorithms. This opens research directions in characterizing which game classes permit faster convergence and how partial communication or correlation might provably improve rates beyond T^-1/4.
:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::