Learning Multi-agent Skills for Tabular Reinforcement Learning using
Factor Graphs
- URL: http://arxiv.org/abs/2201.08227v3
- Date: Fri, 21 Jul 2023 13:42:59 GMT
- Title: Learning Multi-agent Skills for Tabular Reinforcement Learning using
Factor Graphs
- Authors: Jiayu Chen, Jingdi Chen, Tian Lan, Vaneet Aggarwal
- Abstract summary: We show that it is possible to directly compute multi-agent options with collaborative exploratory behaviors among the agents.
The proposed algorithm can successfully identify multi-agent options, and significantly outperforms prior works using single-agent options or no options.
- Score: 41.17714498464354
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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.
Related papers
- Scaling Large-Language-Model-based Multi-Agent Collaboration [75.5241464256688]
Pioneering advancements in large language model-powered agents have underscored the design pattern of multi-agent collaboration.
Inspired by the neural scaling law, this study investigates whether a similar principle applies to increasing agents in multi-agent collaboration.
arXiv Detail & Related papers (2024-06-11T11:02:04Z) - Reaching Consensus in Cooperative Multi-Agent Reinforcement Learning
with Goal Imagination [16.74629849552254]
We propose a model-based consensus mechanism to explicitly coordinate multiple agents.
The proposed Multi-agent Goal Imagination (MAGI) framework guides agents to reach consensus with an Imagined common goal.
We show that such efficient consensus mechanism can guide all agents cooperatively reaching valuable future states.
arXiv Detail & Related papers (2024-03-05T18:07:34Z) - Decentralized Multi-Agent Active Search and Tracking when Targets
Outnumber Agents [8.692007892160913]
We propose a decentralized multi-agent, multi-target, simultaneous active search-and-tracking algorithm called DecSTER.
Our proposed algorithm uses a sequential monte carlo implementation of the probability hypothesis density filter for posterior inference combined with Thompson sampling for decentralized multi-agent decision making.
In simulation, we demonstrate that DecSTER is robust to unreliable inter-agent communication and outperforms information-greedy baselines in terms of the Optimal Sub-Pattern Assignment (OSPA) metric.
arXiv Detail & Related papers (2024-01-06T08:10:58Z) - Scalable Multi-agent Covering Option Discovery based on Kronecker Graphs [49.71319907864573]
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.
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.
arXiv Detail & Related papers (2023-07-21T14:53:12Z) - Graph Exploration for Effective Multi-agent Q-Learning [46.723361065955544]
This paper proposes an exploration technique for multi-agent reinforcement learning (MARL) with graph-based communication among agents.
We assume the individual rewards received by the agents are independent of the actions by the other agents, while their policies are coupled.
In the proposed framework, neighbouring agents collaborate to estimate the uncertainty about the state-action space in order to execute more efficient explorative behaviour.
arXiv Detail & Related papers (2023-04-19T10:28:28Z) - Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
Modern robotics often involves multiple embodied agents operating within a shared environment.
Standard sampling-based algorithms can be used to search for solutions in the robots' joint space.
We integrate the concept of factorization into sampling-based algorithms, which requires only minimal modifications to existing methods.
We present a general implementation of a factorized SBA, derive an analytical gain in terms of sample complexity for PRM*, and showcase empirical results for RRG.
arXiv Detail & Related papers (2023-04-01T15:50:18Z) - Multi-agent Deep Covering Skill Discovery [50.812414209206054]
We propose Multi-agent Deep Covering Option Discovery, which constructs the multi-agent options through minimizing the expected cover time of the multiple agents' joint state space.
Also, we propose a novel framework to adopt the multi-agent options in the MARL process.
We show that the proposed algorithm can effectively capture the agent interactions with the attention mechanism, successfully identify multi-agent options, and significantly outperforms prior works using single-agent options or no options.
arXiv Detail & Related papers (2022-10-07T00:40:59Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.