Convergence of Decentralized Actor-Critic Algorithm in General-sum Markov Games
This work addresses a gap in multi-agent reinforcement learning by providing convergence guarantees for decentralized algorithms in more realistic general-sum settings, which is incremental but important for applications like robotics or economics.
The paper tackles the problem of establishing convergence properties for decentralized learning algorithms in general-sum Markov games, which previously were only known for special cases like zero-sum or potential games, and demonstrates that under certain conditions, the algorithm converges to a set of strategies characterized by a Markov Near-Potential Function.
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.