Asynchronous Gradient Play In Zero-sum Multi-agent Games

Abstract

Finding equilibria via gradient play in competitive multi-agent games has been attracting a growing amount of attention in recent years, with emphasis on designing efficient strategies where the agents operate in a decentralized and symmetric manner with guaranteed convergence. While significant efforts have been made in understanding zero-sum two-player matrix games, the performance in zero-sum multi-agent games remains inadequately explored, especially in the presence of delayed feedbacks, leaving the scalability and resiliency of gradient play open to questions. In this paper, we make progress by studying asynchronous gradient plays in zero-sum polymatrix games under delayed feedbacks. We first establish that the last iterate of entropy-regularized optimistic multiplicative weight updates (OMWU) method converges linearly to the quantal response equilibrium (QRE), the solution concept under bounded rationality, in the absence of delays. While the linear convergence continues to hol

Stats

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

Related papers

• Last-iterate Convergence Of Decentralized Optimistic Gradient Descent/ascent In Infinite-horizon Competitive Markov Games (2021)0.00
• Fast Policy Extragradient Methods For Competitive Games With Entropy Regularization (2021)0.00
• Convergence Analysis Of Gradient-based Learning With Non-uniform Learning Rates In Non-cooperative Multi-agent Settings (2019)0.00
• Policy-gradient Algorithms Have No Guarantees Of Convergence In Linear Quadratic Games (2019)5.24
• Convergence Of Heterogeneous Learning Dynamics In Zero-sum Stochastic Games (2023)2.26
• Gradient Play In Stochastic Games: Stationary Points, Convergence, And Sample Complexity (2021)0.00
• Polymatrix Competitive Gradient Descent (2021)0.00
• Faster Last-iterate Convergence Of Policy Optimization In Zero-sum Markov Games (2022)0.00