Convergence of Decentralized Actor-Critic Algorithm in General-sum Markov Games

2024-09-06 · Chinmay Maheshwari, Manxi Wu, Shankar Sastry

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 strategies. We further strengthen our result under specific regularity conditions and with finite Nash equilibria.

📄 PDF Abstract BibTeX arXiv:2409.04613

Code (0)

등록된 구현이 없습니다.

Methods 이 논문이 사용한 방법론

Focus 설명 없음

SET Dynamic Sparse Training method where weight mask is updated randomly periodically

Decentralized Deterministic Multi-Agent Reinforcement Learning

2021-02-19 · Antoine Grosnit, Desmond Cai, Laura Wynter

[Zhang, ICML 2018] provided the first decentralized actor-critic algorithm for multi-agent reinforcement learning (MARL) that offers convergence guarantees. In that work, policies are stochastic and are defined on finite…

Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized Multi-Agent Reinforcement Learning

2025-05-24 · Zhiyao Zhang, Myeung Suk Oh, FNU Hairi, Ziyue Luo 외

Actor-critic methods for decentralized multi-agent reinforcement learning (MARL) facilitate collaborative optimal decision making without centralized coordination, thus enabling a wide range of applications in practice. …

Decision Making Multi-agent Reinforcement Learning

Finite-Time Convergence and Sample Complexity of Multi-Agent Actor-Critic Reinforcement Learning with Average Reward

2021-09-29 · ICLR 2022 4 · FNU Hairi, Jia Liu, Songtao Lu

In this paper, we establish the first finite-time convergence result of the actor-critic algorithm for fully decentralized multi-agent reinforcement learning (MARL) problems with average reward. In this problem, a set o…

Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Finite-Time Analysis of Fully Decentralized Single-Timescale Actor-Critic

2022-06-12 · Qijun Luo, Xiao Li

Decentralized Actor-Critic (AC) algorithms have been widely utilized for multi-agent reinforcement learning (MARL) and have achieved remarkable success. Apart from its empirical success, the theoretical convergence prope…

Multi-agent Reinforcement Learning Privacy Preserving

Decentralized Policy Optimization

2022-11-06 · Kefan Su, Zongqing Lu

The study of decentralized learning or independent learning in cooperative multi-agent reinforcement learning has a history of decades. Recently empirical studies show that independent PPO (IPPO) can obtain good performa…

Multi-agent Reinforcement Learning