Approximate Global Convergence of Independent Learning in Multi-Agent Systems

Ruiyang Jin, Zaiwei Chen, Yiheng Lin, Jie Song, Adam Wierman
Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, PMLR 258:2818-2826, 2025.

Abstract

Independent learning (IL) is a popular approach for achieving scalability in large-scale multi-agent systems, yet it typically lacks global convergence guarantees. In this paper, we study two representative algorithms—independent $Q$-learning and independent natural actor-critic—within both value-based and policy-based frameworks, and provide the first finite-sample analysis for approximate global convergence. Our results show that IL can achieve global convergence up to a fixed error arising from agent interdependence, which characterizes the fundamental limit of IL in achieving true global convergence. To establish these results, we develop a novel approach by constructing a separable Markov decision process (MDP) for convergence analysis and then bounding the gap caused by the model discrepancy between this separable MDP and the original one. Finally, we present numerical experiments using a synthetic MDP and an electric vehicle charging example to demonstrate our findings and the practical applicability of IL.

Cite this Paper

BibTeX
@InProceedings{pmlr-v258-jin25a, title = {Approximate Global Convergence of Independent Learning in Multi-Agent Systems}, author = {Jin, Ruiyang and Chen, Zaiwei and Lin, Yiheng and Song, Jie and Wierman, Adam}, booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics}, pages = {2818--2826}, year = {2025}, editor = {Li, Yingzhen and Mandt, Stephan and Agrawal, Shipra and Khan, Emtiyaz}, volume = {258}, series = {Proceedings of Machine Learning Research}, month = {03--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v258/main/assets/jin25a/jin25a.pdf}, url = {https://proceedings.mlr.press/v258/jin25a.html}, abstract = {Independent learning (IL) is a popular approach for achieving scalability in large-scale multi-agent systems, yet it typically lacks global convergence guarantees. In this paper, we study two representative algorithms—independent $Q$-learning and independent natural actor-critic—within both value-based and policy-based frameworks, and provide the first finite-sample analysis for approximate global convergence. Our results show that IL can achieve global convergence up to a fixed error arising from agent interdependence, which characterizes the fundamental limit of IL in achieving true global convergence. To establish these results, we develop a novel approach by constructing a separable Markov decision process (MDP) for convergence analysis and then bounding the gap caused by the model discrepancy between this separable MDP and the original one. Finally, we present numerical experiments using a synthetic MDP and an electric vehicle charging example to demonstrate our findings and the practical applicability of IL.} }
Endnote
%0 Conference Paper %T Approximate Global Convergence of Independent Learning in Multi-Agent Systems %A Ruiyang Jin %A Zaiwei Chen %A Yiheng Lin %A Jie Song %A Adam Wierman %B Proceedings of The 28th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2025 %E Yingzhen Li %E Stephan Mandt %E Shipra Agrawal %E Emtiyaz Khan %F pmlr-v258-jin25a %I PMLR %P 2818--2826 %U https://proceedings.mlr.press/v258/jin25a.html %V 258 %X Independent learning (IL) is a popular approach for achieving scalability in large-scale multi-agent systems, yet it typically lacks global convergence guarantees. In this paper, we study two representative algorithms—independent $Q$-learning and independent natural actor-critic—within both value-based and policy-based frameworks, and provide the first finite-sample analysis for approximate global convergence. Our results show that IL can achieve global convergence up to a fixed error arising from agent interdependence, which characterizes the fundamental limit of IL in achieving true global convergence. To establish these results, we develop a novel approach by constructing a separable Markov decision process (MDP) for convergence analysis and then bounding the gap caused by the model discrepancy between this separable MDP and the original one. Finally, we present numerical experiments using a synthetic MDP and an electric vehicle charging example to demonstrate our findings and the practical applicability of IL.
APA
Jin, R., Chen, Z., Lin, Y., Song, J. & Wierman, A.. (2025). Approximate Global Convergence of Independent Learning in Multi-Agent Systems. Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 258:2818-2826 Available from https://proceedings.mlr.press/v258/jin25a.html.

Related Material