# Scalable Multi-agent Covering Option Discovery based on Kronecker Graphs

arXiv: https://arxiv.org/abs/2307.11629 · HTML: https://mlsanity.com/paper/2307.11629/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 42 references that are in the map.
- First posted on arXiv 21 Jul 2023.

## Builds on (most cited first, 22 of 22)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [Diversity is All You Need: Learning Skills without a Reward Function](https://mlsanity.com/paper/1802.06070/) (2018)
- [Counterfactual Multi-Agent Policy Gradients](https://mlsanity.com/paper/1705.08926/) (2017)
- [Learning to Communicate with Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/1605.06676/) (2016)
- [Benchmarking Multi-Agent Deep Reinforcement Learning Algorithms in Cooperative Tasks](https://mlsanity.com/paper/2006.07869/) (2020)
- [Weighted QMIX: Expanding Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2006.10800/) (2020)
- [MAVEN: Multi-Agent Variational Exploration](https://mlsanity.com/paper/1910.07483/) (2019)
- [A Laplacian Framework for Option Discovery in Reinforcement Learning](https://mlsanity.com/paper/1703.00956/) (2017)
- [Eigenoption Discovery through the Deep Successor Representation](https://mlsanity.com/paper/1710.11089/) (2017)
- [The Laplacian in RL: Learning Representations with Efficient Approximations](https://mlsanity.com/paper/1810.04586/) (2018)
- [When Waiting is not an Option : Learning Options with a Deliberation Cost](https://mlsanity.com/paper/1709.04571/) (2017)
- [Hierarchical Cooperative Multi-Agent Reinforcement Learning with Skill Discovery](https://mlsanity.com/paper/1912.03558/) (2019)
- [Discovering Options for Exploration by Minimizing Cover Time](https://mlsanity.com/paper/1903.00606/) (2019)
- [Towards Better Laplacian Representation in Reinforcement Learning with Generalized Graph Drawing](https://mlsanity.com/paper/2107.05545/) (2021)
- [Finding Options that Minimize Planning Time](https://mlsanity.com/paper/1810.07311/) (2018)
- [Option-Critic in Cooperative Multi-agent Systems](https://mlsanity.com/paper/1911.12825/) (2019)
- [Adaptive Skills, Adaptive Partitions (ASAP)](https://mlsanity.com/paper/1602.03351/) (2016)
- [Estimation of Laplacian spectra of direct and strong product graphs](https://mlsanity.com/paper/1507.03030/) (2015)
- [Learning Multi-agent Skills for Tabular Reinforcement Learning using Factor Graphs](https://mlsanity.com/paper/2201.08227/) (2022)
- [Another estimation of Laplacian spectrum of the Kronecker product of graphs](https://mlsanity.com/paper/2102.02924/) (2021)

## Built on by (most cited first, 9 of 9)

- [Every Parameter Matters: Ensuring the Convergence of Federated Learning with Dynamic Heterogeneous Models Reduction](https://mlsanity.com/paper/2310.08670/) (2023)
- [Variational Offline Multi-agent Skill Discovery](https://mlsanity.com/paper/2405.16386/) (2024)
- [Bayesian Optimization through Gaussian Cox Process Models for Spatio-temporal Data](https://mlsanity.com/paper/2401.14544/) (2024)
- [On-ramp and Off-ramp Traffic Flows Estimation Based on A Data-driven Transfer Learning Framework](https://mlsanity.com/paper/2308.03538/) (2023)
- [Enhancing the Resilience of Graph Neural Networks to Topological Perturbations in Sparse Graphs](https://mlsanity.com/paper/2406.03097/) (2024)
- [Augmenting the action space with conventions to improve multi-agent cooperation in Hanabi](https://mlsanity.com/paper/2412.06333/) (2024)
- [A Recipe for Stable Offline Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2603.08399/) (2026)
- [Statistically Efficient Variance Reduction with Double Policy Estimation for Off-Policy Evaluation in Sequence-Modeled Reinforcement Learning](https://mlsanity.com/paper/2308.14897/) (2023)
- [Inter-Agent Relative Representations for Multi-Agent Option Discovery](https://mlsanity.com/paper/2512.24827/) (2025)

## Abstract (arXiv)

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.