Non-Linear Coordination Graphs

• URL: http://arxiv.org/abs/2211.08404v1
• Date: Wed, 26 Oct 2022 18:11:31 GMT
• Title: Non-Linear Coordination Graphs
• Authors: Yipeng Kang, Tonghan Wang, Xiaoran Wu, Qianlan Yang, Chongjie Zhang
• Abstract summary: 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.
• Score: 22.29517436920317
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Value decomposition multi-agent reinforcement learning methods learn the global value function as a mixing of each agent's individual utility functions. Coordination graphs (CGs) represent a higher-order decomposition by incorporating pairwise payoff functions and thus is supposed to have a more powerful representational capacity. However, CGs decompose the global value function linearly over local value functions, severely limiting the complexity of the value function class that can be represented. In this paper, we propose the first non-linear coordination graph by extending CG value decomposition beyond the linear case. One major challenge is to conduct greedy action selections in this new function class to which commonly adopted DCOP algorithms are no longer applicable. We study how to solve this problem when mixing networks with LeakyReLU activation are used. An enumeration method with a global optimality guarantee is proposed and motivates an efficient iterative optimization method with a local optimality guarantee. We find that our method can achieve superior performance on challenging multi-agent coordination tasks like MACO.

Related papers

• Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update [0.09986418756990156]
  We introduce a novel algorithm, denoted hereafter as QRF-GNN, leveraging the power of GNNs to efficiently solve Combinatorial optimization (CO) problems. It relies on unsupervised learning by minimizing the loss function derived from QUBO relaxation. Results of experiments show that QRF-GNN drastically surpasses existing learning-based approaches and is comparable to the state-of-the-art conventionals.
  arXiv  Detail & Related papers  (2024-07-23T13:34:35Z)
• Optimally Improving Cooperative Learning in a Social Setting [4.200480236342444]
  We consider a cooperative learning scenario where a collection of networked agents with individually owned classifiers dynamically update their predictions. We show a time algorithm for optimizing the aggregate objective function, and show that optimizing the egalitarian objective function is NP-hard. The performance of all of our algorithms are guaranteed by mathematical analysis and backed by experiments on synthetic and real data.
  arXiv  Detail & Related papers  (2024-05-31T14:07:33Z)
• Rethinking and Accelerating Graph Condensation: A Training-Free Approach with Class Partition [56.26113670151363]
  Graph condensation is a data-centric solution to replace the large graph with a small yet informative condensed graph. Existing GC methods suffer from intricate optimization processes, necessitating excessive computing resources. We propose a training-free GC framework termed Class-partitioned Graph Condensation (CGC) CGC achieves state-of-the-art performance with a more efficient condensation process.
  arXiv  Detail & Related papers  (2024-05-22T14:57:09Z)
• Practical First-Order Bayesian Optimization Algorithms [0.0]
  We propose a class of practical FOBO algorithms that efficiently utilize the information from the gradient GP to identify potential query points with zero gradients. We validate the performance of our proposed algorithms on several test functions and show that our algorithms outperform state-of-the-art FOBO algorithms.
  arXiv  Detail & Related papers  (2023-06-19T10:05:41Z)
• Greedy based Value Representation for Optimal Coordination in Multi-agent Reinforcement Learning [64.05646120624287]
  We derive the expression of the joint Q value function of LVD and MVD. To ensure optimal consistency, the optimal node is required to be the unique STN. Our method outperforms state-of-the-art baselines in experiments on various benchmarks.
  arXiv  Detail & Related papers  (2022-11-22T08:14:50Z)
• Graph-adaptive Rectified Linear Unit for Graph Neural Networks [64.92221119723048]
  Graph Neural Networks (GNNs) have achieved remarkable success by extending traditional convolution to learning on non-Euclidean data. We propose Graph-adaptive Rectified Linear Unit (GReLU) which is a new parametric activation function incorporating the neighborhood information in a novel and efficient way. We conduct comprehensive experiments to show that our plug-and-play GReLU method is efficient and effective given different GNN backbones and various downstream tasks.
  arXiv  Detail & Related papers  (2022-02-13T10:54:59Z)
• 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)
• 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)
• Deep Reinforcement Learning of Graph Matching [63.469961545293756]
  Graph matching (GM) under node and pairwise constraints has been a building block in areas from optimization to computer vision. We present a reinforcement learning solver for GM i.e. RGM that seeks the node correspondence between pairwise graphs. Our method differs from the previous deep graph matching model in the sense that they are focused on the front-end feature extraction and affinity function learning.
  arXiv  Detail & Related papers  (2020-12-16T13:48:48Z)
• A Multi-Agent Primal-Dual Strategy for Composite Optimization over Distributed Features [52.856801164425086]
  We study multi-agent sharing optimization problems with the objective function being the sum of smooth local functions plus a convex (possibly non-smooth) coupling function.
  arXiv  Detail & Related papers  (2020-06-15T19:40:24Z)
• Learning to be Global Optimizer [28.88646928299302]
  We learn an optimal network and escaping capability algorithm for some benchmark functions. We show that the learned algorithm significantly outperforms some well-known classical optimization algorithms.
  arXiv  Detail & Related papers  (2020-03-10T03:46:25Z)

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.