mlsanityData to 7 Oct 2026

Scalable Multi-agent Covering Option Discovery based on Kronecker Graphs

arXiv 2307.11629 ↗First posted 21 Jul 2023cs.LG cs.MAcited by 9

Not on the map. Why?

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.

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

Builds on

22 of 42 references.

References · 22

  1. 2017Attention Is All You Needcited by 59,932
  2. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,635
  3. 2017Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environmentscited by 1,519
  4. 2018Diversity is All You Need: Learning Skills without a Reward Functioncited by 734
  5. 2017Counterfactual Multi-Agent Policy Gradientscited by 733
  6. 2016Learning to Communicate with Deep Multi-Agent Reinforcement Learningcited by 561
  7. 2020Benchmarking Multi-Agent Deep Reinforcement Learning Algorithms in Cooperative Taskscited by 207
  8. 2020Weighted QMIX: Expanding Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learningcited by 197
  9. 2019MAVEN: Multi-Agent Variational Explorationcited by 181
  10. 2017A Laplacian Framework for Option Discovery in Reinforcement Learningcited by 108
  11. 2017Eigenoption Discovery through the Deep Successor Representationcited by 85
  12. 2018The Laplacian in RL: Learning Representations with Efficient Approximationscited by 83
10 more
  1. 2017When Waiting is not an Option : Learning Options with a Deliberation Costcited by 57
  2. 2019Hierarchical Cooperative Multi-Agent Reinforcement Learning with Skill Discoverycited by 42
  3. 2019Discovering Options for Exploration by Minimizing Cover Timecited by 30
  4. 2021Towards Better Laplacian Representation in Reinforcement Learning with Generalized Graph Drawingcited by 22
  5. 2018Finding Options that Minimize Planning Timecited by 17
  6. 2019Option-Critic in Cooperative Multi-agent Systemscited by 17
  7. 2016Adaptive Skills, Adaptive Partitions (ASAP)cited by 11
  8. 2015Estimation of Laplacian spectra of direct and strong product graphscited by 4
  9. 2022Learning Multi-agent Skills for Tabular Reinforcement Learning using Factor Graphscited by 4
  10. 2021Another estimation of Laplacian spectrum of the Kronecker product of graphscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 3; 2024: 4; 2025: 1; 2026: 1.

9 papers.

  1. 2023Every Parameter Matters: Ensuring the Convergence of Federated Learning with Dynamic Heterogeneous Models Reductioncited by 24
  2. 2024Variational Offline Multi-agent Skill Discoverycited by 6
  3. 2024Bayesian Optimization through Gaussian Cox Process Models for Spatio-temporal Datacited by 5
  4. 2023On-ramp and Off-ramp Traffic Flows Estimation Based on A Data-driven Transfer Learning Frameworkcited by 3
  5. 2024Enhancing the Resilience of Graph Neural Networks to Topological Perturbations in Sparse Graphscited by 3
  6. 2024Augmenting the action space with conventions to improve multi-agent cooperation in Hanabicited by 2
  7. 2023Statistically Efficient Variance Reduction with Double Policy Estimation for Off-Policy Evaluation in Sequence-Modeled Reinforcement Learningcited by 0
  8. 2025Inter-Agent Relative Representations for Multi-Agent Option Discoverycited by 0
  9. 2026A Recipe for Stable Offline Multi-agent Reinforcement Learningcited by 0