Distributed Multi-Agent Reinforcement Learning Based on Graph-Induced Local Value Functions

• URL: http://arxiv.org/abs/2202.13046v5
• Date: Fri, 12 Apr 2024 03:41:09 GMT
• Title: Distributed Multi-Agent Reinforcement Learning Based on Graph-Induced Local Value Functions
• Authors: Gangshan Jing, He Bai, Jemin George, Aranya Chakrabortty, Piyush K. Sharma,
• Abstract summary: 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.
• Score: 7.6860514640178
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Achieving distributed reinforcement learning (RL) for large-scale cooperative multi-agent systems (MASs) is challenging because: (i) each agent has access to only limited information; (ii) issues on convergence or computational complexity emerge due to the curse of dimensionality. In this paper, we propose a general computationally efficient distributed framework for cooperative multi-agent reinforcement learning (MARL) by utilizing the structures of graphs involved in this problem. We introduce three coupling graphs describing three types of inter-agent couplings in MARL, namely, the state graph, the observation graph and the reward graph. By further considering a communication graph, we propose two distributed RL approaches based on local value-functions derived from the coupling graphs. The first approach is able to reduce sample complexity significantly under specific conditions on the aforementioned four graphs. The second approach provides an approximate solution and can be efficient even for problems with dense coupling graphs. Here there is a trade-off between minimizing the approximation error and reducing the computational complexity. Simulations show that our RL algorithms have a significantly improved scalability to large-scale MASs compared with centralized and consensus-based distributed RL algorithms.

Related papers

• Scalable and Accurate Graph Reasoning with LLM-based Multi-Agents [27.4884498301785]
  We introduce GraphAgent-Reasoner, a fine-tuning-free framework for explicit and precise graph reasoning. Inspired by distributed graph computation theory, our framework decomposes graph problems into smaller, node-centric tasks that are distributed among multiple agents. Our framework demonstrates the capability to handle real-world graph reasoning applications such as webpage importance analysis.
  arXiv  Detail & Related papers  (2024-10-07T15:34:14Z)
• Symmetry-preserving graph attention network to solve routing problems at multiple resolutions [1.9304772860080408]
  We introduce the first-ever completely equivariant model and training to solve problems. It is essential to capture the multiscale structure of the input graph. We propose a Multiresolution scheme in combination with Equi Graph Attention network (mEGAT) architecture.
  arXiv  Detail & Related papers  (2023-10-24T06:22:20Z)
• Distributed Learning over Networks with Graph-Attention-Based Personalization [49.90052709285814]
  We propose a graph-based personalized algorithm (GATTA) for distributed deep learning. In particular, the personalized model in each agent is composed of a global part and a node-specific part. By treating each agent as one node in a graph the node-specific parameters as its features, the benefits of the graph attention mechanism can be inherited.
  arXiv  Detail & Related papers  (2023-05-22T13:48:30Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  We show how to enforce a one-step normalized cut for bipartite graphs, especially with linear-time complexity. In this paper, we first characterize a novel one-step bipartite graph cut criterion with normalized constraints, and theoretically prove its equivalence to a trace problem. We extend this cut criterion to a scalable subspace clustering approach, where adaptive anchor learning, bipartite graph learning, and one-step normalized bipartite graph partitioning are simultaneously modeled.
  arXiv  Detail & Related papers  (2023-05-12T11:27:20Z)
• Localized Contrastive Learning on Graphs [110.54606263711385]
  We introduce a simple yet effective contrastive model named Localized Graph Contrastive Learning (Local-GCL) In spite of its simplicity, Local-GCL achieves quite competitive performance in self-supervised node representation learning tasks on graphs with various scales and properties.
  arXiv  Detail & Related papers  (2022-12-08T23:36:00Z)
• Graph Reinforcement Learning for Radio Resource Allocation [13.290246410488727]
  We resort to graph reinforcement learning for exploiting two kinds of relational priors inherent in many problems in wireless communications. To design graph reinforcement learning framework systematically, we first conceive a method to transform state matrix into state graph. We then propose a general method for graph neural networks to satisfy desirable permutation properties.
  arXiv  Detail & Related papers  (2022-03-08T08:02:54Z)
• Self-Organized Polynomial-Time Coordination Graphs [21.02670428540549]
  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.
  arXiv  Detail & Related papers  (2021-12-07T07:42:40Z)
• StairwayGraphNet for Inter- and Intra-modality Multi-resolution Brain Graph Alignment and Synthesis [1.6114012813668934]
  We propose a multi-resolution StairwayGraphNet (SG-Net) framework to infer a target graph modality based on a given modality and super-resolve brain graphs in both inter and intra domains. Our SG-Net is grounded in three main contributions: (i) predicting a target graph from a source one based on a novel graph generative adversarial network in both inter and intra domains, (ii) generating high-resolution brain graphs without resorting to the time consuming and expensive MRI processing steps, and (iii) enforcing the source distribution to match that of the ground truth graphs.
  arXiv  Detail & Related papers  (2021-10-06T09:49:38Z)
• 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 Representation Learning via Graphical Mutual Information Maximization [86.32278001019854]
  We propose a novel concept, Graphical Mutual Information (GMI), to measure the correlation between input graphs and high-level hidden representations. We develop an unsupervised learning model trained by maximizing GMI between the input and output of a graph neural encoder.
  arXiv  Detail & Related papers  (2020-02-04T08:33:49Z)
• 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.