Finite-time last-iterate convergence for multi-agent learning in games - Archive ouverte HAL Access content directly
Conference Papers Year :

Finite-time last-iterate convergence for multi-agent learning in games

(1) , (2, 3) , (4, 5) , (1)
1
2
3
4
5

Abstract

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 lastiterate 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 nonadaptive 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.
Fichier principal
Vignette du fichier
ICML-2020-finite-time-last-iterate-convergence-for-multi-agent-learning-in-games-Paper.pdf (346.26 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03043711 , version 1 (07-12-2020)

Identifiers

  • HAL Id : hal-03043711 , version 1

Cite

Tianyi Lin, Zhengyuan Zhou, Panayotis Mertikopoulos, Michael I Jordan. Finite-time last-iterate convergence for multi-agent learning in games. ICML 2020 - 37th International Conference on Machine Learning, Jul 2020, Vienna, Austria. pp.1-11. ⟨hal-03043711⟩
33 View
160 Download

Share

Gmail Facebook Twitter LinkedIn More