Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation

Yifei Min, Jiafan He, Tianhao Wang, Quanquan Gu
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:24785-24811, 2023.

Abstract

We study multi-agent reinforcement learning in the setting of episodic Markov decision processes, where many agents cooperate via communication through a central server. We propose a provably efficient algorithm based on value iteration that can simultaneously allow asynchronous communication and guarantee the benefit of cooperation with low communication complexity. Under linear function approximation, we prove that our algorithm enjoys a $\tilde{\mathcal{O}}(d^{3/2}H^2\sqrt{K})$ regret upper bound with $\tilde{\mathcal{O}}(dHM^2)$ communication complexity, where $d$ is the feature dimension, $H$ is the horizon length, $M$ is the total number of agents, and $K$ is the total number of episodes. We also provide a lower bound showing that an $\Omega(dM)$ communication complexity is necessary to improve the performance through collaboration.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-min23a, title = {Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation}, author = {Min, Yifei and He, Jiafan and Wang, Tianhao and Gu, Quanquan}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {24785--24811}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/min23a/min23a.pdf}, url = {https://proceedings.mlr.press/v202/min23a.html}, abstract = {We study multi-agent reinforcement learning in the setting of episodic Markov decision processes, where many agents cooperate via communication through a central server. We propose a provably efficient algorithm based on value iteration that can simultaneously allow asynchronous communication and guarantee the benefit of cooperation with low communication complexity. Under linear function approximation, we prove that our algorithm enjoys a $\tilde{\mathcal{O}}(d^{3/2}H^2\sqrt{K})$ regret upper bound with $\tilde{\mathcal{O}}(dHM^2)$ communication complexity, where $d$ is the feature dimension, $H$ is the horizon length, $M$ is the total number of agents, and $K$ is the total number of episodes. We also provide a lower bound showing that an $\Omega(dM)$ communication complexity is necessary to improve the performance through collaboration.} }
Endnote
%0 Conference Paper %T Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation %A Yifei Min %A Jiafan He %A Tianhao Wang %A Quanquan Gu %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-min23a %I PMLR %P 24785--24811 %U https://proceedings.mlr.press/v202/min23a.html %V 202 %X We study multi-agent reinforcement learning in the setting of episodic Markov decision processes, where many agents cooperate via communication through a central server. We propose a provably efficient algorithm based on value iteration that can simultaneously allow asynchronous communication and guarantee the benefit of cooperation with low communication complexity. Under linear function approximation, we prove that our algorithm enjoys a $\tilde{\mathcal{O}}(d^{3/2}H^2\sqrt{K})$ regret upper bound with $\tilde{\mathcal{O}}(dHM^2)$ communication complexity, where $d$ is the feature dimension, $H$ is the horizon length, $M$ is the total number of agents, and $K$ is the total number of episodes. We also provide a lower bound showing that an $\Omega(dM)$ communication complexity is necessary to improve the performance through collaboration.
APA
Min, Y., He, J., Wang, T. & Gu, Q.. (2023). Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:24785-24811 Available from https://proceedings.mlr.press/v202/min23a.html.

Related Material