  Covering skill (a.k.a., option) discovery has been developed to improve the
exploration of reinforcement learning 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. However,
these option discovery methods cannot be directly extended to multi-agent
scenarios, since the joint state space grows exponentially with the number of
agents in the system. Thus, existing researches on adopting options in
multi-agent scenarios still rely on single-agent option discovery and fail to
directly discover the joint options that can improve the connectivity of the
joint state space of agents. In this paper, we show that it is indeed possible
to directly compute multi-agent options with collaborative exploratory
behaviors among the agents, while still enjoying the ease of decomposition. Our
key idea is to approximate the joint state space as a Kronecker graph -- the
Kronecker product of individual agents' state transition graphs, based on which
we can directly estimate the Fiedler vector of the joint state space using the
Laplacian spectrum of individual agents' transition graphs. This decomposition
enables us to efficiently construct multi-agent joint options by encouraging
agents to connect the sub-goal joint states which are corresponding to the
minimum or maximum values of the estimated joint Fiedler vector. The evaluation
based on multi-agent collaborative tasks shows that the proposed algorithm can
successfully identify multi-agent options, and significantly outperforms prior
works using single-agent options or no options, in terms of both faster
exploration and higher cumulative rewards.
