Decentralized Learning in General-sum Markov Games
<|reference_start|>Decentralized Learning in General-sum Markov Games: The Markov game framework is widely used to model interactions among agents with heterogeneous utilities in dynamic, uncertain, societal-scale systems. In these settings, agents typically operate in a decentralized manner due to privacy and scalability concerns, often without knowledge of others' strategies. Designing decentralized learning algorithms that provably converge to rational outcomes remains challenging, especially beyond Markov zero-sum and potential games, which do not fully capture the mixed cooperative-competitive nature of real-world interactions. Our paper focuses on designing decentralized learning algorithms for general-sum Markov games, aiming to provide guarantees of convergence to approximate Nash equilibria. We introduce a Markov Near-Potential Function (MNPF), and show that MNPF plays a central role in the analysis of convergence of an actor-critic-based decentralized learning dynamics to approximate Nash equilibria. Our analysis leverages the two-timescale nature of actor-critic algorithms, where Q-function updates occur faster than policy updates. This result is further strengthened under certain regularity conditions and when the set of Nash equilibria is finite. Our findings provide a new perspective on the analysis of decentralized learning in multi-agent systems, addressing the complexities of real-world interactions.<|reference_end|>
@article{maheshwari2024convergence,
    title={Convergence of Decentralized Actor-Critic Algorithm in General-sum
  Markov Games},
    author={Chinmay Maheshwari and Manxi Wu and Shankar Sastry},
    journal={arXiv preprint arXiv:2409.04613},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.04613},
    primaryClass={cs.MA cs.AI cs.GT cs.SY eess.SY math.OC}
}