Convergence Of Decentralized Actor-critic Algorithm In General-sum Markov Games

Abstract

Markov games provide a powerful framework for modeling strategic multi-agent interactions in dynamic environments. Traditionally, convergence properties of decentralized learning algorithms in these settings have been established only for special cases, such as Markov zero-sum and potential games, which do not fully capture real-world interactions. In this paper, we address this gap by studying the asymptotic properties of learning algorithms in general-sum Markov games. In particular, we focus on a decentralized algorithm where each agent adopts an actor-critic learning dynamic with asynchronous step sizes. This decentralized approach enables agents to operate independently, without requiring knowledge of others' strategies or payoffs. We introduce the concept of a Markov Near-Potential Function (MNPF) and demonstrate that it serves as an approximate Lyapunov function for the policy updates in the decentralized learning dynamics, which allows us to characterize the convergent set of s

Stats

• citations2
• S2 citations—
• github stars0
• HF likes0
• heat score3.58
• arxiv keymaheshwari2024convergence

Related papers

• Convergence Rates For Localized Actor-critic In Networked Markov Potential Games (2023)0.00
• Independent And Decentralized Learning In Markov Potential Games (2022)0.00
• Communication-efficient Actor-critic Methods For Homogeneous Markov Games (2022)0.00
• Actor-dual-critic Dynamics For Zero-sum And Identical-interest Stochastic Games (2026)0.00
• Last-iterate Convergence Of Decentralized Optimistic Gradient Descent/ascent In Infinite-horizon Competitive Markov Games (2021)0.00
• Convergence Of Actor-critic Learning For Mean Field Games And Mean Field Control In Continuous Spaces (2025)0.00
• Provably Efficient Reinforcement Learning In Decentralized General-sum Markov Games (2021)0.00
• Decentralized Q-learning In Zero-sum Markov Games (2021)0.00