  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 skill discovery either become
prohibitive or fail to directly discover joint skills that improve the
connectivity of the joint state space. In this paper, we propose multi-agent
skill discovery which enables 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 skills, and
significantly outperforms the state-of-the-art. Codes are available at:
https://github.itap.purdue.edu/Clan-labs/Scalable_MAOD_via_KP.
