Convergence Analysis Of Gradient-based Learning With Non-uniform Learning Rates In Non-cooperative Multi-agent Settings

Abstract

Considering a class of gradient-based multi-agent learning algorithms in non-cooperative settings, we provide local convergence guarantees to a neighborhood of a stable local Nash equilibrium. In particular, we consider continuous games where agents learn in (i) deterministic settings with oracle access to their gradient and (ii) stochastic settings with an unbiased estimator of their gradient. Utilizing the minimum and maximum singular values of the game Jacobian, we provide finite-time convergence guarantees in the deterministic case. On the other hand, in the stochastic case, we provide concentration bounds guaranteeing that with high probability agents will converge to a neighborhood of a stable local Nash equilibrium in finite time. Different than other works in this vein, we also study the effects of non-uniform learning rates on the learning dynamics and convergence rates. We find that much like preconditioning in optimization, non-uniform learning rates cause a distortion in th

Stats

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

Related papers

• Finite-time Last-iterate Convergence For Multi-agent Learning In Games (2020)0.00
• On The Convergence Of Policy Gradient Methods To Nash Equilibria In General Stochastic Games (2022)0.00
• Independent Policy Gradient Methods For Competitive Reinforcement Learning (2021)0.00
• Asymptotic Convergence And Performance Of Multi-agent Q-learning Dynamics (2023)0.00
• Convergence Of Multi-agent Learning With A Finite Step Size In General-sum Games (2019)2.26
• Policy-gradient Algorithms Have No Guarantees Of Convergence In Linear Quadratic Games (2019)5.24
• On The Stability Of Learning In Network Games With Many Players (2024)0.00
• Beyond Strict Competition: Approximate Convergence Of Multi Agent Q-learning Dynamics (2023)0.00