Graph Reinforcement Learning for Network Control via Bi-Level Optimization

• URL: http://arxiv.org/abs/2305.09129v1
• Date: Tue, 16 May 2023 03:20:22 GMT
• Title: Graph Reinforcement Learning for Network Control via Bi-Level Optimization
• Authors: Daniele Gammelli, James Harrison, Kaidi Yang, Marco Pavone, Filipe Rodrigues, Francisco C. Pereira
• Abstract summary: We argue that data-driven strategies can automate this process and learn efficient algorithms without compromising optimality. We present network control problems through the lens of reinforcement learning and propose a graph network-based framework to handle a broad class of problems.
• Score: 37.00510744883984
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Optimization problems over dynamic networks have been extensively studied and widely used in the past decades to formulate numerous real-world problems. However, (1) traditional optimization-based approaches do not scale to large networks, and (2) the design of good heuristics or approximation algorithms often requires significant manual trial-and-error. In this work, we argue that data-driven strategies can automate this process and learn efficient algorithms without compromising optimality. To do so, we present network control problems through the lens of reinforcement learning and propose a graph network-based framework to handle a broad class of problems. Instead of naively computing actions over high-dimensional graph elements, e.g., edges, we propose a bi-level formulation where we (1) specify a desired next state via RL, and (2) solve a convex program to best achieve it, leading to drastically improved scalability and performance. We further highlight a collection of desirable features to system designers, investigate design decisions, and present experiments on real-world control problems showing the utility, scalability, and flexibility of our framework.

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)
• Network Interdiction Goes Neural [26.308933674471895]
  Network interdiction problems are optimization problems involving two players. One aims to solve an optimization problem on a network, while the other seeks to modify the network to thwart the first player's objectives.
  arXiv  Detail & Related papers  (2024-05-26T02:34:26Z)
• GASE: Graph Attention Sampling with Edges Fusion for Solving Vehicle Routing Problems [6.084414764415137]
  We propose an adaptive Graph Attention Sampling with the Edges Fusion framework to solve vehicle routing problems. Our proposed model outperforms the existing methods by 2.08%-6.23% and shows stronger generalization ability.
  arXiv  Detail & Related papers  (2024-05-21T03:33:07Z)
• A hybrid deep-learning-metaheuristic framework for bi-level network design problems [2.741266294612776]
  This study proposes a hybrid deep-learning-metaheuristic framework with a bi-level architecture for road network design problems (NDPs) We train a graph neural network (GNN) to approximate the solution of the user equilibrium (UE) traffic assignment problem. We use inferences made by the trained model to calculate fitness function evaluations of a genetic algorithm (GA) to approximate solutions for NDPs.
  arXiv  Detail & Related papers  (2023-03-10T16:23:56Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  Permutation flow shop scheduling (PFSS) is widely used in manufacturing systems. We propose to train the model via expert-driven imitation learning, which accelerates convergence more stably and accurately. Our model's network parameters are reduced to only 37% of theirs, and the solution gap of our model towards the expert solutions decreases from 6.8% to 1.3% on average.
  arXiv  Detail & Related papers  (2022-10-31T09:46:26Z)
• MultiScale MeshGraphNets [65.26373813797409]
  We propose two complementary approaches to improve the framework from MeshGraphNets. First, we demonstrate that it is possible to learn accurate surrogate dynamics of a high-resolution system on a much coarser mesh. Second, we introduce a hierarchical approach (MultiScale MeshGraphNets) which passes messages on two different resolutions.
  arXiv  Detail & Related papers  (2022-10-02T20:16:20Z)
• Analysis and Design of Quadratic Neural Networks for Regression, Classification, and Lyapunov Control of Dynamical Systems [0.0]
  This paper addresses the analysis and design of quadratic neural networks. Networks offer several advantages, the most important of which are the fact that the architecture is a by-product of the design and is not determined a-priori. Several examples will show the effectiveness of quadratic neural networks in applications.
  arXiv  Detail & Related papers  (2022-07-26T18:10:05Z)
• On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Network [55.56019538079826]
  Bilevel optimization has been applied to a wide variety of machine learning models. Most existing algorithms restrict their single-machine setting so that they are incapable of handling distributed data. We develop novel decentralized bilevel optimization algorithms based on a gradient tracking communication mechanism and two different gradients.
  arXiv  Detail & Related papers  (2022-06-30T05:29:52Z)
• 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)
• Optimizing Wireless Systems Using Unsupervised and Reinforced-Unsupervised Deep Learning [96.01176486957226]
  Resource allocation and transceivers in wireless networks are usually designed by solving optimization problems. In this article, we introduce unsupervised and reinforced-unsupervised learning frameworks for solving both variable and functional optimization problems.
  arXiv  Detail & Related papers  (2020-01-03T11:01:52Z)

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.