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

By Tianyi Lin, Zhengyuan Zhou, Panayotis Mertikopoulos, Michael I. Jordan. 2020

59 citations recorded by the source corpus.

In this paper, we consider multi-agent learning via online gradient descent in a class of games called $\lambda$-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 $\lambda$-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 $\lambda$) 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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Management Science and Operations Research, Reinforcement Learning, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Gauthier Gidel
2. Simon Lacoste-Julien
3. Nicolas Loizou
4. Ioannis Mitliagkas
5. Hugo Berard
6. Peter Richtárik
7. Sebastian U. Stich
8. Martin Jaggi

In Computational Theory and Mathematics

1. Nicolas Loizou
2. Hugo Berard
3. Gauthier Gidel
4. Simon Lacoste-Julien
5. Ioannis Mitliagkas
6. Peter Richtárik
7. Zeyuan Allen-Zhu
8. Jakub Konecný

In Management Science and Operations Research

1. Simon Lacoste-Julien
2. Gauthier Gidel
3. Ioannis Mitliagkas
4. Hugo Berard
5. Nicolas Loizou
6. Peter Richtárik

In Reinforcement Learning

1. Simon Lacoste-Julien
2. Nicolas Loizou
3. Ioannis Mitliagkas
4. Hugo Berard
5. Gauthier Gidel

In Optimization & Training

1. Gauthier Gidel
2. Simon Lacoste-Julien
3. Nicolas Loizou
4. Ioannis Mitliagkas
5. Hugo Berard
6. Peter Richtárik
7. Sebastian U. Stich
8. Martin Jaggi

Citations in the corpus

• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, background): “Even more, Theorem 4.6 in Lin et al. [2020b] requires that the sequence, τ k , goes to zero with k in order to get convergence; ii) for an absolute random noise model, noise variance is uniformly bounded by σ k , a bounded variance assumption.”