Finite-time Last-iterate Convergence For Multi-agent Learning In Games

Abstract

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,

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keylin2020finite

Related papers

• Convergence Analysis Of Gradient-based Learning With Non-uniform Learning Rates In Non-cooperative Multi-agent Settings (2019)0.00
• Multi-agent Online Learning In Time-varying Games (2018)8.82
• Asymptotic Convergence And Performance Of Multi-agent Q-learning Dynamics (2023)0.00
• Chaos Persists In Large-scale Multi-agent Learning Despite Adaptive Learning Rates (2023)0.00
• Last-iterate Convergence Of Decentralized Optimistic Gradient Descent/ascent In Infinite-horizon Competitive Markov Games (2021)0.00
• On Passivity, Reinforcement Learning And Higher-order Learning In Multi-agent Finite Games (2018)12.02
• Minimax-optimal Multi-agent RL In Markov Games With A Generative Model (2022)2.26
• Asynchronous Gradient Play In Zero-sum Multi-agent Games (2022)0.00