# Learning Multi-agent Skills for Tabular Reinforcement Learning using Factor Graphs

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 55 references that are in the map.
- First posted on arXiv 20 Jan 2022.

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

- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [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)
- [FeUdal Networks for Hierarchical Reinforcement Learning](https://mlsanity.com/paper/1703.01161/) (2017)
- [Visual Foresight: Model-Based Deep Reinforcement Learning for Vision-Based Robotic Control](https://mlsanity.com/paper/1812.00568/) (2018)
- [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)
- [Playing Atari Games with Deep Reinforcement Learning and Human Checkpoint Replay](https://mlsanity.com/paper/1607.05077/) (2016)
- [Exploration--Exploitation in MDPs with Options](https://mlsanity.com/paper/1703.08667/) (2017)
- [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)
- [Another estimation of Laplacian spectrum of the Kronecker product of graphs](https://mlsanity.com/paper/2102.02924/) (2021)

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

- [Scalable Multi-agent Covering Option Discovery based on Kronecker Graphs](https://mlsanity.com/paper/2307.11629/) (2023)
- [A Unified Algorithm Framework for Unsupervised Discovery of Skills based on Determinantal Point Process](https://mlsanity.com/paper/2212.00211/) (2022)
- [Hierarchical Deep Counterfactual Regret Minimization](https://mlsanity.com/paper/2305.17327/) (2023)
- [Enhancing the Resilience of Graph Neural Networks to Topological Perturbations in Sparse Graphs](https://mlsanity.com/paper/2406.03097/) (2024)

## Abstract (arXiv)

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.