Convergence of Decentralized Actor-Critic Algorithm in General–Sum Markov Games
- 2 December 2024
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Control Systems Letters
- Vol. 8, 2643-2648
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 strategies. We further strengthen our result under specific regularity conditions and with finite Nash equilibria.Keywords
All Related Versions
Funding Information
- NSF Collaborative Research: THEORINET (DMS-2031899)
This publication has 8 references indexed in Scilit:
- Learning Nash in Constrained Markov Games With an α -PotentialIEEE Control Systems Letters, 2024
- Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov GamesDynamic Games and Applications, 2022
- Decentralized Learning for Optimality in Stochastic Dynamic Teams and Games With Local Control and Global State InformationIEEE Transactions on Automatic Control, 2021
- Decentralized Q-Learning for Stochastic Teams and GamesIEEE Transactions on Automatic Control, 2016
- Dynamics in near-potential gamesGames and Economic Behavior, 2013
- Near-Potential GamesACM Transactions on Economics and Computation, 2013
- Asynchronous Stochastic Approximation with Differential InclusionsStochastic Systems, 2012
- A theory of regular Markov perfect equilibria in dynamic stochastic games: Genericity, stability, and purificationTheoretical Economics, 2010