  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 $\Omega(dM)$ communication complexity is required to improve the
performance through collaboration.
