Randomized Exploration in Cooperative Multi-Agent Reinforcement Learning
This addresses the challenge of efficient exploration in multi-agent systems for researchers and practitioners in reinforcement learning, though it is incremental as it builds on existing randomized exploration methods.
The paper tackles the problem of provably efficient randomized exploration in cooperative multi-agent reinforcement learning by proposing two Thompson Sampling-type algorithms, CoopTS-PHE and CoopTS-LMC, which achieve a regret bound of $\widetilde{\mathcal{O}}(d^{3/2}H^2\sqrt{MK})$ with communication complexity $\widetilde{\mathcal{O}}(dHM^2)$ for linear transition models and show better performance in experiments including a deep exploration problem, video game, and real-world energy system.
We present the first study on provably efficient randomized exploration in cooperative multi-agent reinforcement learning (MARL). We propose a unified algorithm framework for randomized exploration in parallel Markov Decision Processes (MDPs), and two Thompson Sampling (TS)-type algorithms, CoopTS-PHE and CoopTS-LMC, incorporating the perturbed-history exploration (PHE) strategy and the Langevin Monte Carlo exploration (LMC) strategy, respectively, which are flexible in design and easy to implement in practice. For a special class of parallel MDPs where the transition is (approximately) linear, we theoretically prove that both CoopTS-PHE and CoopTS-LMC achieve a $\widetilde{\mathcal{O}}(d^{3/2}H^2\sqrt{MK})$ regret bound with communication complexity $\widetilde{\mathcal{O}}(dHM^2)$, where $d$ is the feature dimension, $H$ is the horizon length, $M$ is the number of agents, and $K$ is the number of episodes. This is the first theoretical result for randomized exploration in cooperative MARL. We evaluate our proposed method on multiple parallel RL environments, including a deep exploration problem (i.e., $N$-chain), a video game, and a real-world problem in energy systems. Our experimental results support that our framework can achieve better performance, even under conditions of misspecified transition models. Additionally, we establish a connection between our unified framework and the practical application of federated learning.