Last-Iterate Convergence

Follow this topic Ask about this topic

Last-iterate convergence asks whether the actual sequence of updates ends near a solution, which matters when averaged outputs are impractical or do not reflect the algorithm’s ongoing behavior. The field studies stochastic optimization, variational inequalities, and learning in zero-sum games, using methods such as Halpern anchoring, extragradient and optimistic updates, and adaptive step sizes. Researchers analyze both rates and the assumptions needed for guarantees, including noise, smoothness, feedback, and whether the time horizon is known. A central tension is that final-iterate guarantees can be slower or more fragile than average-iterate ones, and lower bounds show that some costs cannot be avoided in particular settings.

Latest papers

42 papers14 papers in the last four weeks, up 180% on the four weeks before. 0.1% of all new papers.

Achieving $ε^{-2}$ Sample Complexity for Single-Loop Actor-Critic under Minimal Assumptions
May 13, 2026Ishaq Hamza, Zaiwei ChenPolicy Gradient Last-Iterate Convergence
IISc · Edwardson School of Industrial Engineering, Purdue University · Purdue IE
When and Why is Optimistic Multiplicative Weights Slow? The Geometry of Energy Dissipation
May 13, 2026John Lazarsfeld, Anas Barakat, Georgios Piliouras +2Nash Equilibrium Last-Iterate Convergence
SUTD · Google DeepMind · NUS CQT +2
Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs
May 12, 2026Michael Lu, Max Qiushi Lin, Mo Chen +1Markov Decision Processes Last-Iterate Convergence
Simon Fraser University
Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions
May 10, 2026Soumita Hait, Ping Li, Haipeng Luo +1Last-Iterate Convergence Imperfect-Information Games
University of Southern California · Shanghai University of Finance and Economics · University of Iowa
The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback
Apr 17, 2026Côme Fiegel, Pierre Ménard, Tadashi Kozuno +2Nash Equilibrium Last-Iterate Convergence
ENSAE Paris - CREST, Palaiseau, France · Inria - FairPlay · ENS Lyon, Lyon, France +3
Optimal last-iterate convergence in matrix games with bandit feedback using the log-barrier
Apr 16, 2026Come Fiegel, Pierre Menard, Tadashi Kozuno +2Last-Iterate Convergence Imperfect-Information Games
ENSAE Paris – CREST, France · ENS Lyon, France · Isara Labs +2
Gradient Descent's Last Iterate is Often (slightly) Suboptimal
Apr 15, 2026Guy Kornowski, Ohad ShamirLast-Iterate Convergence Gradient Descent
Institute for Advanced Study · Weizmann Institute of Science · University of Toronto and the Vector Institute
Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size
Apr 10, 2026Michał Dereziński, Xiaoyu DongLast-Iterate Convergence Stochastic Optimization
University of Michigan · National University of Singapore
Parameter-Free Non-Ergodic Extragradient Algorithms for Solving Monotone Variational Inequalities
Apr 9, 2026Lingqing Shen, Fatma Kılınç-KarzanExtragradient Methods Last-Iterate Convergence
Tepper School of Business, Carnegie Mellon University
An Improved Last-Iterate Convergence Rate for Anchored Gradient Descent Ascent
Apr 4, 2026Anja Surina, Arun Suggala, George Tsoukalas +5Last-Iterate Convergence Min-Max Optimization
Google DeepMind
Efficient Uncoupled Learning Dynamics with $\tilde{O}\!\left(T^{-1/4}\right)$ Last-Iterate Convergence in Bilinear Saddle-Point Problems over Convex Sets under Bandit Feedback
Feb 24, 2026Arnab Maiti, Claire Jie Zhang, Kevin Jamieson +3Bandit Learning Last-Iterate Convergence
University of Washington · Amazon · University of California, Irvine
Towards Weaker Variance Assumptions for Stochastic Optimization
Apr 14, 2025Ahmet Alacaoglu, Yura Malitsky, Stephen J. WrightStochastic Optimization Last-Iterate Convergence
Department of Mathematics, University of British Columbia · Faculty of Mathematics, University of Vienna · Department of Computer Sciences, University of Wisconsin–Madison

May 13, 2026J/K move · Enter open · S save

Achieving $ε^{-2}$ Sample Complexity for Single-Loop Actor-Critic under Minimal Assumptions

Ishaq Hamza, Zaiwei Chen

IISc · Edwardson School of Industrial Engineering, Purdue University · Purdue IE

Policy Gradient Last-Iterate Convergence Natural Policy Gradient Actor-Critic Methods Policy Learning Sample-Efficient RL+1

Open paper AskPDF arXiv

In this paper, we establish last-iterate convergence rates for off-policy actor--critic methods in reinforcement learning. In particular, under a single-loop, single-timescale implementation and a broad class of policy updates, including approximate policy iteration and natural policy gradient methods, we prove the first

\tilde{\mathcal{O}}(ε^{-2})

sample complexity guarantee for finding an

ε

-optimal policy under minimal assumptions, namely, the existence of a policy that induces an irreducible Markov chain. This stands in stark contrast to the existing literature, where an

\tilde{\mathcal{O}}(ε^{-2})

sample complexity is achieved only through nested-loop updates and/or under strong, algorithm-dependent assumptions on the policies, such as uniform mixing and uniform exploration. Technically, to address the challenges posed by the coupled update equations arising from the single-loop implementation, as well as the potentially unbounded iterates induced by off-policy learning, our analysis is based on a coupled Lyapunov drift framework. Specifically, we establish a geometric convergence rate for the actor and an

\tilde{\mathcal{O}}(1/T)

convergence rate for the critic, and combine the two Lyapunov drift inequalities through a cross-domination property. We believe this analytical framework is of independent interest and may be applicable to other coupled iterative algorithms with unbounded