# Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Feb 2020.

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

- [Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium](https://mlsanity.com/paper/2104.12761/) (2021)
- [Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity](https://mlsanity.com/paper/2107.00052/) (2021)
- [Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2202.07262/) (2022)
- [Tight Last-Iterate Convergence of the Extragradient and the Optimistic Gradient Descent-Ascent Algorithm for Constrained Monotone Variational Inequalities](https://mlsanity.com/paper/2204.09228/) (2022)
- [No-Regret Learning in Games with Noisy Feedback: Faster Rates and Adaptivity via Learning Rate Separation](https://mlsanity.com/paper/2206.06015/) (2022)
- [Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback](https://mlsanity.com/paper/2112.02856/) (2021)
- [Doubly Optimal No-Regret Learning in Monotone Games](https://mlsanity.com/paper/2301.13120/) (2023)
- [Single-Call Stochastic Extragradient Methods for Structured Non-monotone Variational Inequalities: Improved Analysis under Weaker Conditions](https://mlsanity.com/paper/2302.14043/) (2023)
- [Communication-Efficient Distributionally Robust Decentralized Learning](https://mlsanity.com/paper/2205.15614/) (2022)
- [Adaptively Perturbed Mirror Descent for Learning in Games](https://mlsanity.com/paper/2305.16610/) (2023)
- [A Game-Theoretic Approach to Multi-Agent Trust Region Optimization](https://mlsanity.com/paper/2106.06828/) (2021)
- [Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinements](https://mlsanity.com/paper/2306.16502/) (2023)
- [Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback](https://mlsanity.com/paper/2310.14085/) (2023)
- [Risk-Averse No-Regret Learning in Online Convex Games](https://mlsanity.com/paper/2203.08957/) (2022)
- [Stochastic Extragradient with Random Reshuffling: Improved Convergence for Variational Inequalities](https://mlsanity.com/paper/2403.07148/) (2024)
- [MF-OML: Online Mean-Field Reinforcement Learning with Occupation Measures for Large Population Games](https://mlsanity.com/paper/2405.00282/) (2024)
- [Multiplayer Federated Learning: Reaching Equilibrium with Less Communication](https://mlsanity.com/paper/2501.08263/) (2025)
- [Corrupted Learning Dynamics in Games](https://mlsanity.com/paper/2412.07120/) (2024)
- [No-regret learning in harmonic games: Extrapolation in the face of conflicting interests](https://mlsanity.com/paper/2412.20203/) (2024)
- [Is Thompson Sampling Susceptible to Algorithmic Collusion?](https://mlsanity.com/paper/2405.17463/) (2024)
- [Layer-wise Quantization for Quantized Optimistic Dual Averaging](https://mlsanity.com/paper/2505.14371/) (2025)
- [Pure Exploration via Frank-Wolfe Self-Play](https://mlsanity.com/paper/2509.19901/) (2025)
- [Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGD](https://mlsanity.com/paper/2604.10373/) (2026)
- [Computing Pure-Strategy Nash Equilibria in a Two-Party Policy Competition: Existence and Algorithmic Approaches](https://mlsanity.com/paper/2512.22552/) (2025)
- [Last-Iterate Guarantees for Learning in Co-coercive Games](https://mlsanity.com/paper/2604.19065/) (2026)
- [Parametric Open Source Games](https://mlsanity.com/paper/2606.27068/) (2026)

## Abstract (arXiv)

In this paper, we consider multi-agent learning via online gradient descent in a class of games called λ-cocoercive games, a fairly broad class of games that admits many Nash equilibria and that properly includes unconstrained strongly monotone games. We characterize the finite-time last-iterate convergence rate for joint OGD learning on λ-cocoercive games; further, building on this result, we develop a fully adaptive OGD learning algorithm that does not require any knowledge of problem parameter (e.g. cocoercive constant λ) and show, via a novel double-stopping time technique, that this adaptive algorithm achieves same finite-time last-iterate convergence rate as non-adaptive counterpart. Subsequently, we extend OGD learning to the noisy gradient feedback case and establish last-iterate convergence results -- first qualitative almost sure convergence, then quantitative finite-time convergence rates -- all under non-decreasing step-sizes. To our knowledge, we provide the first set of results that fill in several gaps of the existing multi-agent online learning literature, where three aspects -- finite-time convergence rates, non-decreasing step-sizes, and fully adaptive algorithms have been unexplored before.