Self-Organized Polynomial-Time Coordination Graphs
- URL: http://arxiv.org/abs/2112.03547v1
- Date: Tue, 7 Dec 2021 07:42:40 GMT
- Title: Self-Organized Polynomial-Time Coordination Graphs
- Authors: Qianlan Yang, Weijun Dong, Zhizhou Ren, Jianhao Wang, Tonghan Wang,
Chongjie Zhang
- Abstract summary: Coordination graph is a promising approach to model agent collaboration in reinforcement learning.
One challenge in this paradigm is the complexity of computing maximum-value actions for a graph-based value factorization.
This paper proposes a novel method, named Self-Organized Polynomial-time Coordination Graphs (SOP-CG), which uses structured graph classes to guarantee the optimality of the induced DCOPs.
- Score: 21.02670428540549
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Coordination graph is a promising approach to model agent collaboration in
multi-agent reinforcement learning. It factorizes a large multi-agent system
into a suite of overlapping groups that represent the underlying coordination
dependencies. One critical challenge in this paradigm is the complexity of
computing maximum-value actions for a graph-based value factorization. It
refers to the decentralized constraint optimization problem (DCOP), which and
whose constant-ratio approximation are NP-hard problems. To bypass this
fundamental hardness, this paper proposes a novel method, named Self-Organized
Polynomial-time Coordination Graphs (SOP-CG), which uses structured graph
classes to guarantee the optimality of the induced DCOPs with sufficient
function expressiveness. We extend the graph topology to be state-dependent,
formulate the graph selection as an imaginary agent, and finally derive an
end-to-end learning paradigm from the unified Bellman optimality equation. In
experiments, we show that our approach learns interpretable graph topologies,
induces effective coordination, and improves performance across a variety of
cooperative multi-agent tasks.
Related papers
- Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
An emerging strategy to tackle optimization problems involves the adoption of graph neural networks (GNNs) as an alternative to traditional algorithms.
Despite the growing popularity of GNNs and traditional algorithm solvers in the realm of CO, there is limited research on their integrated use and the correlation between them within an end-to-end framework.
We introduce a decision-focused framework that utilizes GNNs to address CO problems with auxiliary support.
arXiv Detail & Related papers (2024-06-05T22:52:27Z) - PGODE: Towards High-quality System Dynamics Modeling [40.76121531452706]
This paper studies the problem of modeling multi-agent dynamical systems, where agents could interact mutually to influence their behaviors.
Recent research predominantly uses geometric graphs to depict these mutual interactions, which are then captured by graph neural networks (GNNs)
We propose a new approach named Prototypical Graph ODE to address the problem.
arXiv Detail & Related papers (2023-11-11T12:04:47Z) - Non-Linear Coordination Graphs [22.29517436920317]
Coordination graphs (CGs) represent a higher-order decomposition by incorporating pairwise payoff functions.
We propose the first non-linear coordination graph by extending CG value decomposition beyond the linear case.
We find that our method can achieve superior performance on challenging multi-agent coordination tasks like MACO.
arXiv Detail & Related papers (2022-10-26T18:11:31Z) - Distributed Multi-Agent Reinforcement Learning Based on Graph-Induced Local Value Functions [7.6860514640178]
We propose a general computationally efficient distributed framework for cooperative multi-agent reinforcement learning (MARL)
We introduce three coupling graphs describing three types of inter-agent couplings in MARL.
We propose two distributed RL approaches based on local value-functions derived from the coupling graphs.
arXiv Detail & Related papers (2022-02-26T03:01:51Z) - Soft Hierarchical Graph Recurrent Networks for Many-Agent Partially
Observable Environments [9.067091068256747]
We propose a novel network structure called hierarchical graph recurrent network(HGRN) for multi-agent cooperation under partial observability.
Based on the above technologies, we proposed a value-based MADRL algorithm called Soft-HGRN and its actor-critic variant named SAC-HRGN.
arXiv Detail & Related papers (2021-09-05T09:51:25Z) - Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
We propose an efficient model-based reinforcement learning algorithm for learning in multi-agent systems.
Our main theoretical contributions are the first general regret bounds for model-based reinforcement learning for MFC.
We provide a practical parametrization of the core optimization problem.
arXiv Detail & Related papers (2021-07-08T18:01:02Z) - A Bi-Level Framework for Learning to Solve Combinatorial Optimization on
Graphs [91.07247251502564]
We propose a hybrid approach to combine the best of the two worlds, in which a bi-level framework is developed with an upper-level learning method to optimize the graph.
Such a bi-level approach simplifies the learning on the original hard CO and can effectively mitigate the demand for model capacity.
arXiv Detail & Related papers (2021-06-09T09:18:18Z) - Diversified Multiscale Graph Learning with Graph Self-Correction [55.43696999424127]
We propose a diversified multiscale graph learning model equipped with two core ingredients.
A graph self-correction (GSC) mechanism to generate informative embedded graphs, and a diversity boosting regularizer (DBR) to achieve a comprehensive characterization of the input graph.
Experiments on popular graph classification benchmarks show that the proposed GSC mechanism leads to significant improvements over state-of-the-art graph pooling methods.
arXiv Detail & Related papers (2021-03-17T16:22:24Z) - Multilayer Clustered Graph Learning [66.94201299553336]
We use contrastive loss as a data fidelity term, in order to properly aggregate the observed layers into a representative graph.
Experiments show that our method leads to a clustered clusters w.r.t.
We learn a clustering algorithm for solving clustering problems.
arXiv Detail & Related papers (2020-10-29T09:58:02Z) - Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
Graph representation learning has achieved a remarkable success in many graph-based applications, such as node classification, prediction, and community detection.
However, for some kind of graph applications, such as graph compression and edge partition, it is very hard to reduce them to some graph representation learning tasks.
In this paper, we propose to attack the graph ordering problem behind such applications by a novel learning approach.
arXiv Detail & Related papers (2020-01-18T09:14:16Z)
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.