{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,24]],"date-time":"2026-06-24T16:15:52Z","timestamp":1782317752197,"version":"3.54.5"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,2,27]],"date-time":"2023-02-27T00:00:00Z","timestamp":1677456000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["2154171, 2146814, 2136197, 2106403,, 2105648"],"award-info":[{"award-number":["2154171, 2146814, 2136197, 2106403,, 2105648"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2023,2,27]]},"abstract":"<jats:p>We study a multi-agent reinforcement learning (MARL) problem where the agents interact over a given network. The goal of the agents is to cooperatively maximize the average of their entropy-regularized long-term rewards. To overcome the curse of dimensionality and to reduce communication, we propose a Localized Policy Iteration (LPI) algorithm that provably learns a near-globally-optimal policy using only local information. In particular, we show that, despite restricting each agent's attention to only its \u03ba-hop neighborhood, the agents are able to learn a policy with an optimality gap that decays polynomially in \u03ba. In addition, we show the finite-sample convergence of LPI to the global optimal policy, which explicitly captures the trade-off between optimality and computational complexity in choosing \u03ba. Numerical simulations demonstrate the effectiveness of LPI.<\/jats:p>","DOI":"10.1145\/3579443","type":"journal-article","created":{"date-parts":[[2023,3,2]],"date-time":"2023-03-02T23:50:57Z","timestamp":1677801057000},"page":"1-51","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Global Convergence of Localized Policy Iteration in Networked Multi-Agent Reinforcement Learning"],"prefix":"10.1145","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5677-4748","authenticated-orcid":false,"given":"Yizhou","family":"Zhang","sequence":"first","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5466-3550","authenticated-orcid":false,"given":"Guannan","family":"Qu","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2559-8622","authenticated-orcid":false,"given":"Pan","family":"Xu","sequence":"additional","affiliation":[{"name":"Duke University, Durham, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6524-2877","authenticated-orcid":false,"given":"Yiheng","family":"Lin","sequence":"additional","affiliation":[{"name":"California Institute of Technology, Pasadena, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9915-5595","authenticated-orcid":false,"given":"Zaiwei","family":"Chen","sequence":"additional","affiliation":[{"name":"California Institute of Technology, Pasadena, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5923-0199","authenticated-orcid":false,"given":"Adam","family":"Wierman","sequence":"additional","affiliation":[{"name":"California Institute of Technology, Pasadena, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,3,2]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Conference on Learning Theory. PMLR, 64--66","author":"Agarwal Alekh","year":"2020","unstructured":"Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. 2020. Optimality and approximation with policy gradient methods in markov decision processes. In Conference on Learning Theory. PMLR, 64--66."},{"key":"e_1_2_1_2_1","first-page":"1","article-title":"On the theory of policy gradient methods: Optimality, approximation, and distribution shift","volume":"22","author":"Agarwal Alekh","year":"2021","unstructured":"Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. 2021. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, Vol. 22, 98 (2021), 1--76.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2002.800646"},{"key":"e_1_2_1_4_1","volume-title":"Neuro-dynamic programming","author":"Bertsekas Dimitri P","unstructured":"Dimitri P Bertsekas and John N Tsitsiklis. 1996. Neuro-dynamic programming. Vol. 5. Athena Scientific Belmont, MA."},{"key":"e_1_2_1_5_1","volume-title":"Global optimality guarantees for policy gradient methods. arXiv preprint arXiv:1906.01786","author":"Bhandari Jalaj","year":"2019","unstructured":"Jalaj Bhandari and Daniel Russo. 2019. Global optimality guarantees for policy gradient methods. arXiv preprint arXiv:1906.01786 (2019)."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMCC.2007.913919"},{"key":"e_1_2_1_7_1","volume-title":"Linear convergence of entropy-regularized natural policy gradient with linear function approximation. Preprint arXiv:2106.04096","author":"Cayci Semih","year":"2021","unstructured":"Semih Cayci, Niao He, and R Srikant. 2021. Linear convergence of entropy-regularized natural policy gradient with linear function approximation. Preprint arXiv:2106.04096 (2021)."},{"key":"e_1_2_1_8_1","volume-title":"Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research","author":"Cen Shicong","year":"2021","unstructured":"Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. 2021. Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research (2021)."},{"key":"e_1_2_1_9_1","volume-title":"Reinforcement learning for selective key applications in power systems: Recent advances and future challenges","author":"Chen Xin","year":"2022","unstructured":"Xin Chen, Guannan Qu, Yujie Tang, Steven Low, and Na Li. 2022. Reinforcement learning for selective key applications in power systems: Recent advances and future challenges. IEEE Transactions on Smart Grid (2022)."},{"key":"e_1_2_1_10_1","first-page":"746","article-title":"The dynamics of reinforcement learning in cooperative multiagent systems","volume":"1998","author":"Claus Caroline","year":"1998","unstructured":"Caroline Claus and Craig Boutilier. 1998. The dynamics of reinforcement learning in cooperative multiagent systems. AAAI\/IAAI, Vol. 1998 (1998), 746--752.","journal-title":"AAAI\/IAAI"},{"key":"e_1_2_1_11_1","volume-title":"International Conference on Machine Learning. PMLR, 5166--5220","author":"Ding Dongsheng","year":"2022","unstructured":"Dongsheng Ding, Chen-Yu Wei, Kaiqing Zhang, and Mihailo Jovanovic. 2022. Independent policy gradient for large-scale markov potential games: Sharper rates, function approximation, and game-agnostic convergence. In International Conference on Machine Learning. PMLR, 5166--5220."},{"key":"e_1_2_1_12_1","volume-title":"International Conference on Machine Learning. PMLR, 1626--1635","author":"Doan Thinh","year":"2019","unstructured":"Thinh Doan, Siva Maguluri, and Justin Romberg. 2019. Finite-time analysis of distributed TD (0) with linear function approximation on multi-agent reinforcement learning. In International Conference on Machine Learning. PMLR, 1626--1635."},{"key":"e_1_2_1_13_1","volume-title":"Nando De Freitas, and Shimon Whiteson.","author":"Foerster Jakob","year":"2016","unstructured":"Jakob Foerster, Ioannis Alexandros Assael, Nando De Freitas, and Shimon Whiteson. 2016. Learning to communicate with deep multi-agent reinforcement learning. Advances in neural information processing systems, Vol. 29 (2016)."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"David Gamarnik. 2013. Correlation decay method for decision optimization and inference in large-scale networks. In Theory Driven by Influential Applications. INFORMS 108--121.","DOI":"10.1287\/educ.2013.0119"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0609"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622434.1622447"},{"key":"e_1_2_1_17_1","volume-title":"Jordan","author":"Jin Chi","year":"2018","unstructured":"Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I. Jordan. 2018. Is Q-learning Provably Efficient? arXiv:1807.03765 [cs, math, stat] (July 2018). http:\/\/arxiv.org\/abs\/1807.03765 arXiv: 1807.03765."},{"key":"e_1_2_1_18_1","first-page":"740","article-title":"Efficient reinforcement learning in factored MDPs","volume":"16","author":"Kearns Michael","year":"1999","unstructured":"Michael Kearns and Daphne Koller. 1999. Efficient reinforcement learning in factored MDPs. In IJCAI, Vol. 16. 740--747.","journal-title":"IJCAI"},{"key":"e_1_2_1_19_1","volume-title":"Global convergence of multi-agent policy gradient in markov potential games. arXiv preprint arXiv:2106.01969","author":"Leonardos Stefanos","year":"2021","unstructured":"Stefanos Leonardos, Will Overman, Ioannis Panageas, and Georgios Piliouras. 2021. Global convergence of multi-agent policy gradient in markov potential games. arXiv preprint arXiv:2106.01969 (2021)."},{"key":"e_1_2_1_20_1","volume-title":"Markov chains and mixing times","author":"Levin David A","unstructured":"David A Levin and Yuval Peres. 2017. Markov chains and mixing times. Vol. 107. American Mathematical Soc."},{"key":"e_1_2_1_21_1","first-page":"7825","article-title":"Multi-agent reinforcement learning in stochastic networked systems","volume":"34","author":"Lin Yiheng","year":"2021","unstructured":"Yiheng Lin, Guannan Qu, Longbo Huang, and Adam Wierman. 2021. Multi-agent reinforcement learning in stochastic networked systems. Advances in Neural Information Processing Systems, Vol. 34 (2021), 7825--7837.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/3091574.3091594"},{"key":"e_1_2_1_23_1","volume-title":"OpenAI Pieter Abbeel, and Igor Mordatch","author":"Lowe Ryan","year":"2017","unstructured":"Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAI Pieter Abbeel, and Igor Mordatch. 2017. Multi-agent actor-critic for mixed cooperative-competitive environments. In Advances in Neural Information Processing Systems. 6379--6390."},{"key":"e_1_2_1_24_1","volume-title":"International Conference on Machine Learning. PMLR, 6820--6829","author":"Mei Jincheng","year":"2020","unstructured":"Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. 2020. On the global convergence rates of softmax policy gradient methods. In International Conference on Machine Learning. PMLR, 6820--6829."},{"key":"e_1_2_1_25_1","volume-title":"International conference on machine learning. PMLR","author":"Mnih Volodymyr","year":"2016","unstructured":"Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. 2016. Asynchronous methods for deep reinforcement learning. In International conference on machine learning. PMLR, 1928--1937."},{"key":"e_1_2_1_26_1","volume-title":"Nature","volume":"518","author":"Mnih Volodymyr","year":"2015","unstructured":"Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. 2015. Human-level control through deep reinforcement learning. Nature, Vol. 518, 7540 (2015), 529."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2008.929366"},{"key":"e_1_2_1_28_1","first-page":"2074","article-title":"Scalable multi-agent reinforcement learning for networked systems with average reward","volume":"33","author":"Qu Guannan","year":"2020","unstructured":"Guannan Qu, Yiheng Lin, Adam Wierman, and Na Li. 2020a. Scalable multi-agent reinforcement learning for networked systems with average reward. Advances in Neural Information Processing Systems, Vol. 33 (2020), 2074--2086.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_29_1","unstructured":"Guannan Qu Adam Wierman and Na Li. 2020b. Scalable reinforcement learning of localized policies for multi-agent networked systems. In Learning for Dynamics and Control. PMLR 256--266."},{"key":"e_1_2_1_30_1","volume-title":"Near-Optimal Distributed Linear-Quadratic Regulator for Networked Systems. arXiv preprint arXiv:2204.05551","author":"Shin Sungho","year":"2022","unstructured":"Sungho Shin, Yiheng Lin, Guannan Qu, Adam Wierman, and Mihai Anitescu. 2022. Near-Optimal Distributed Linear-Quadratic Regulator for Networked Systems. arXiv preprint arXiv:2204.05551 (2022)."},{"key":"e_1_2_1_31_1","volume-title":"Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al.","author":"Silver David","year":"2016","unstructured":"David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. 2016. Mastering the game of Go with deep neural networks and tree search. nature, Vol. 529, 7587 (2016), 484."},{"key":"e_1_2_1_32_1","unstructured":"Sainbayar Sukhbaatar Rob Fergus et al. 2016. Learning multiagent communication with backpropagation. Advances in neural information processing systems Vol. 29 (2016)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ifacol.2020.12.2021"},{"key":"e_1_2_1_34_1","volume-title":"Reinforcement learning: An introduction","author":"Sutton Richard S","unstructured":"Richard S Sutton and Andrew G Barto. 2018. Reinforcement learning: An introduction. MIT press."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/3091529.3091572"},{"key":"e_1_2_1_36_1","first-page":"12163","article-title":"Leverage the average: an analysis of KL regularization in reinforcement learning","volume":"33","author":"Vieillard Nino","year":"2020","unstructured":"Nino Vieillard, Tadashi Kozuno, Bruno Scherrer, Olivier Pietquin, R\u00e9mi Munos, and Matthieu Geist. 2020. Leverage the average: an analysis of KL regularization in reinforcement learning. Advances in Neural Information Processing Systems, Vol. 33 (2020), 12163--12174.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Neil Walton and Kuang Xu. 2021. Learning and information in stochastic networks and queues. In Tutorials in Operations Research: Emerging Optimization Methods and Modeling Techniques with Applications. INFORMS 161--198.","DOI":"10.1287\/educ.2021.0235"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1080\/09540099108946587"},{"key":"e_1_2_1_39_1","volume-title":"International conference on machine learning. PMLR, 5571--5580","author":"Yang Yaodong","year":"2018","unstructured":"Yaodong Yang, Rui Luo, Minne Li, Ming Zhou, Weinan Zhang, and Jun Wang. 2018. Mean field multi-agent reinforcement learning. In International conference on machine learning. PMLR, 5571--5580."},{"key":"e_1_2_1_40_1","volume-title":"Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control","author":"Zhang Kaiqing","year":"2021","unstructured":"Kaiqing Zhang, Zhuoran Yang, and Tamer Bacs ar. 2021b. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control (2021), 321--384."},{"key":"e_1_2_1_41_1","volume-title":"International Conference on Machine Learning. PMLR, 5872--5881","author":"Zhang Kaiqing","year":"2018","unstructured":"Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Basar. 2018. Fully decentralized multi-agent reinforcement learning with networked agents. In International Conference on Machine Learning. PMLR, 5872--5881."},{"key":"e_1_2_1_42_1","volume-title":"On the Optimal Control of Network LQR with Spatially-Exponential Decaying Structure. arXiv preprint arXiv:2209.14376","author":"Zhang Runyu","year":"2022","unstructured":"Runyu Zhang, Weiyu Li, and Na Li. 2022. On the Optimal Control of Network LQR with Spatially-Exponential Decaying Structure. arXiv preprint arXiv:2209.14376 (2022)."},{"key":"e_1_2_1_43_1","volume-title":"Global optimality and finite sample analysis of softmax off-policy actor critic under state distribution mismatch. Preprint arXiv:2111.02997","author":"Zhang Shangtong","year":"2021","unstructured":"Shangtong Zhang, Remi Tachet, and Romain Laroche. 2021a. Global optimality and finite sample analysis of softmax off-policy actor critic under state distribution mismatch. Preprint arXiv:2111.02997 (2021)."}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3579443","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3579443","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3579443","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:41Z","timestamp":1750178801000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3579443"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,27]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,2,27]]}},"alternative-id":["10.1145\/3579443"],"URL":"https:\/\/doi.org\/10.1145\/3579443","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,2,27]]},"assertion":[{"value":"2023-03-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}