Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation
This work addresses efficient cooperation in multi-agent systems for researchers in reinforcement learning, though it is incremental as it builds on existing methods with specific theoretical improvements.
The paper tackles the problem of multi-agent reinforcement learning with asynchronous communication and linear function approximation, proposing an algorithm that achieves an $ ilde{\mathcal{O}}(d^{3/2}H^2\sqrt{K})$ regret and $ ilde{\mathcal{O}}(dHM^2)$ communication complexity, while establishing a lower bound of $\Omega(dM)$ for collaboration.
We study multi-agent reinforcement learning in the setting of episodic Markov decision processes, where multiple agents cooperate via communication through a central server. We propose a provably efficient algorithm based on value iteration that enable asynchronous communication while ensuring the advantage of cooperation with low communication overhead. With linear function approximation, we prove that our algorithm enjoys an $\tilde{\mathcal{O}}(d^{3/2}H^2\sqrt{K})$ regret 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 a minimal $Ω(dM)$ communication complexity is required to improve the performance through collaboration.