mlsanityData to 7 Oct 2026

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 2602.21436 ↗First posted 24 Feb 2026stat.ML cs.GT cs.LGcited by 3

Not on the map. Why?

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.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 21 of its 42 references that are in the map. First posted on arXiv 24 Feb 2026.

Builds on

21 of 42 references.

References · 21

  1. 2023Nash Learning from Human Feedbackcited by 220
  2. 2017Training GANs with Optimismcited by 217
  3. 2015Fast Convergence of Regularized Learning in Gamescited by 149
  4. 2017Cycles in adversarial regularized learningcited by 122
  5. 2015Explore no more: Improved high-probability regret bounds for non-stochastic banditscited by 120
  6. 2018Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimizationcited by 97
  7. 2021Near-Optimal No-Regret Learning in General Gamescited by 85
  8. 2018Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networkscited by 68
  9. 2020Hedging in games: Faster convergence of external and swap regretscited by 57
  10. 2022Uncoupled Learning Dynamics with O(log T) Swap Regret in Multiplayer Gamescited by 35
  11. 2022On Last-Iterate Convergence Beyond Zero-Sum Gamescited by 30
  12. 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 28
9 more
  1. 2013Volumetric Spanners: an Efficient Exploration Basis for Learningcited by 23
  2. 2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
  3. 2021Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedbackcited by 14
  4. 2024Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithmscited by 14
  5. 2019Learning Nash Equilibria in Monotone Gamescited by 10
  6. 2023Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedbackcited by 6
  7. 2025From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applicationscited by 6
  8. 2024Uncoupled and Convergent Learning in Monotone Games under Bandit Feedbackcited by 5
  9. 2024Boosting Perturbed Gradient Ascent for Last-Iterate Convergence in Gamescited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 3.

3 papers.

  1. 2026Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actionscited by 2
  2. 2026Minimax Last-Iterate Convergence in Matrix Games with Observed Actionscited by 0
  3. 2026Polylogarithmic Nash Regret in Matrix Games with Bandit Feedbackcited by 0