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 (\textit{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.

我们提出了第一个关于合作多智能体强化学习（MARL）中可证明效率的随机探索的研究，提出了一种统一的随机探索算法框架，以及两种基于 Thompson Sampling（TS）的算法。我们在多个并行强化学习环境中评估了我们的方法，包括深度探索问题，视频游戏和能源系统中的一个实际问题。实验证明，我们的框架即使在过渡模型误指定的条件下，也能达到更好的性能，此外，我们还建立了我们统一框架与联邦学习的实际应用之间的联系。