Timezone: »

Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation
Yifei Min · Jiafan He · Tianhao Wang · Quanquan Gu

Thu Jul 27 04:30 PM -- 06:00 PM (PDT) @ Exhibit Hall 1 #623
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.

Author Information

Yifei Min (Yale University)
Jiafan He (University of California, Los Angeles)
Tianhao Wang (Yale University)
Quanquan Gu (University of California, Los Angeles)

More from the Same Authors