Convergence Of Multi-agent Learning With A Finite Step Size In General-sum Games

Abstract

Learning in a multi-agent system is challenging because agents are simultaneously learning and the environment is not stationary, undermining convergence guarantees. To address this challenge, this paper presents a new gradient-based learning algorithm, called Gradient Ascent with Shrinking Policy Prediction (GA-SPP), which augments the basic gradient ascent approach with the concept of shrinking policy prediction. The key idea behind this algorithm is that an agent adjusts its strategy in response to the forecasted strategy of the other agent, instead of its current one. GA-SPP is shown formally to have Nash convergence in larger settings than existing gradient-based multi-agent learning methods. Furthermore, unlike existing gradient-based methods, GA-SPP's theoretical guarantees do not assume the learning rate to be infinitesimal.

Stats

• citations1
• S2 citations—
• github stars0
• HF likes0
• heat score2.26
• arxiv keysong2019convergence

Related papers

• Convergence Analysis Of Gradient-based Learning With Non-uniform Learning Rates In Non-cooperative Multi-agent Settings (2019)0.00
• Symmetric (optimistic) Natural Policy Gradient For Multi-agent Learning With Parameter Convergence (2022)0.00
• Convergence Of Decentralized Actor-critic Algorithm In General-sum Markov Games (2024)3.58
• Asymptotic Convergence And Performance Of Multi-agent Q-learning Dynamics (2023)0.00
• Independent Policy Gradient For Large-scale Markov Potential Games: Sharper Rates, Function Approximation, And Game-agnostic Convergence (2022)0.00
• On The Convergence Of Policy Gradient Methods To Nash Equilibria In General Stochastic Games (2022)0.00
• On The Convergence Of Model Free Learning In Mean Field Games (2019)0.00
• Finite-time Last-iterate Convergence For Multi-agent Learning In Games (2020)0.00