# Efficient Uncoupled Learning Dynamics with tildeO!left(T-1/4right) Last-Iterate Convergence in Bilinear Saddle-Point Problems over Convex Sets under Bandit Feedback

arXiv: https://arxiv.org/abs/2602.21436 · HTML: https://mlsanity.com/paper/2602.21436/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 42 references that are in the map.
- First posted on arXiv 24 Feb 2026.

## Builds on (most cited first, 21 of 21)

- [Nash Learning from Human Feedback](https://mlsanity.com/paper/2312.00886/) (2023)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Fast Convergence of Regularized Learning in Games](https://mlsanity.com/paper/1507.00407/) (2015)
- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization](https://mlsanity.com/paper/1807.04252/) (2018)
- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networks](https://mlsanity.com/paper/1802.06132/) (2018)
- [Hedging in games: Faster convergence of external and swap regrets](https://mlsanity.com/paper/2006.04953/) (2020)
- [Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Games](https://mlsanity.com/paper/2204.11417/) (2022)
- [On Last-Iterate Convergence Beyond Zero-Sum Games](https://mlsanity.com/paper/2203.12056/) (2022)
- [Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback](https://mlsanity.com/paper/2303.02738/) (2023)
- [Volumetric Spanners: an Efficient Exploration Basis for Learning](https://mlsanity.com/paper/1312.6214/) (2013)
- [Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback](https://mlsanity.com/paper/2112.02856/) (2021)
- [A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Games](https://mlsanity.com/paper/2303.03100/) (2023)
- [Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms](https://mlsanity.com/paper/2406.10631/) (2024)
- [Learning Nash Equilibria in Monotone Games](https://mlsanity.com/paper/1904.01882/) (2019)
- [From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications](https://mlsanity.com/paper/2506.03464/) (2025)
- [Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback](https://mlsanity.com/paper/2310.14085/) (2023)
- [Uncoupled and Convergent Learning in Monotone Games under Bandit Feedback](https://mlsanity.com/paper/2408.08395/) (2024)
- [Boosting Perturbed Gradient Ascent for Last-Iterate Convergence in Games](https://mlsanity.com/paper/2410.02388/) (2024)

## Built on by (most cited first, 4 of 4)

- [Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions](https://mlsanity.com/paper/2605.09363/) (2026)
- [Minimax Last-Iterate Convergence in Matrix Games with Observed Actions](https://mlsanity.com/paper/2609.34656/) (2026)
- [Polylogarithmic Nash Regret in Matrix Games with Bandit Feedback](https://mlsanity.com/paper/2609.34812/) (2026)
- [Fast Last-Iterate Convergence in Zero-Sum Markov Games with Bandit Feedback](https://mlsanity.com/paper/2610.05968/) (2026)

## Abstract (arXiv)

In this paper, we study last-iterate convergence of learning algorithms in bilinear saddle-point problems, a preferable notion of convergence that captures the day-to-day behavior of learning dynamics. We focus on the challenging setting where players select actions from compact convex sets and receive only bandit feedback. Our main contribution is the design of an uncoupled learning algorithm that guarantees last-iterate convergence to the Nash equilibrium with high probability. We establish a convergence rate of tildeO(T-1/4) up to polynomial factors in problem parameters. Crucially, our proposed algorithm is computationally efficient, requiring only an efficient linear optimization oracle over the players' compact action sets. The algorithm is obtained by combining techniques from experimental design and the classic Follow-The-Regularized-Leader (FTRL) framework, with a carefully chosen regularizer function tailored to the geometry of the action set of each learner.