Covering skill (a.k.a., option) discovery has been developed to improve the
exploration of RL in single-agent scenarios with sparse reward signals, through
connecting the most distant states in the embedding space provided by the
Fiedler vector of the state transition graph. Given that joint state space
grows exponentially with the number of agents in multi-agent systems, existing
researches still relying on single-agent option discovery either become
prohibitive or fail to directly discover joint options that improve the
connectivity of the joint state space. In this paper, we show how to directly
compute multi-agent options with collaborative exploratory behaviors while
still enjoying the ease of decomposition. Our key idea is to approximate the
joint state space as a Kronecker graph, based on which we can directly estimate
its Fiedler vector using the Laplacian spectrum of individual agents'
transition graphs. Further, considering that directly computing the Laplacian
spectrum is intractable for tasks with infinite-scale state spaces, we further
propose a deep learning extension of our method by estimating eigenfunctions
through NN-based representation learning techniques. The evaluation on
multi-agent tasks built with simulators like Mujoco, shows that the proposed
algorithm can successfully identify multi-agent options, and significantly
outperforms the state-of-the-art. Codes are available at:
this https URL

通过直接计算多智能体任务的 Laplacian 谱，我们提出一种基于 Kronecker 图的多智能体选项发现方法，通过估计 Fiedler 向量来改善联合状态空间的连通性，并通过深度学习扩展方法来处理无限规模状态空间。在 Mujoco 等模拟器上的多智能体任务评估中，我们的方法成功地识别了多智能体选项，并显著优于现有技术。