Monkey Business: Reinforcement learning meets neighborhood search for Virtual Network Embedding

• URL: http://arxiv.org/abs/2202.13706v1
• Date: Mon, 28 Feb 2022 12:00:56 GMT
• Title: Monkey Business: Reinforcement learning meets neighborhood search for Virtual Network Embedding
• Authors: Maxime Elkael, Massinissa Ait Aba, Andrea Araldo, Hind Castel, Badii Jouaber
• Abstract summary: We consider the Virtual Network Embedding (VNE) problem for 5G networks slicing. Inspired by the Nested Rollout Policy Adaptation (NRPA) algorithm, we propose a new algorithm that we call Neighborhood Enhanced Policy Adaptation (NEPA) NEPA learns by combining NRPA with Neighbordhood Search in a frugal manner which improves only promising solutions.
• Score: 0.8312192184427761
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this article, we consider the Virtual Network Embedding (VNE) problem for 5G networks slicing. This problem requires to allocate multiple Virtual Networks (VN) on a substrate virtualized physical network while maximizing among others, resource utilization, maximum number of placed VNs and network operator's benefit. We solve the online version of the problem where slices arrive over time. Inspired by the Nested Rollout Policy Adaptation (NRPA) algorithm, a variant of the well known Monte Carlo Tree Search (MCTS) that learns how to perform good simulations over time, we propose a new algorithm that we call Neighborhood Enhanced Policy Adaptation (NEPA). The key feature of our algorithm is to observe NRPA cannot exploit knowledge acquired in one branch of the state tree for another one which starts differently. NEPA learns by combining NRPA with Neighbordhood Search in a frugal manner which improves only promising solutions while keeping the running time low. We call this technique a monkey business because it comes down to jumping from one interesting branch to the other, similar to how monkeys jump from tree to tree instead of going down everytime. NEPA achieves better results in terms of acceptance ratio and revenue-to-cost ratio compared to other state-of-the-art algorithms, both on real and synthetic topologies.

Related papers

• Unveiling Options with Neural Decomposition [11.975013522386538]
  In reinforcement learning, agents often learn policies for specific tasks without the ability to generalize this knowledge to related tasks. This paper introduces an algorithm that attempts to address this limitation by decomposing neural networks encoding policies for Markov Decision Processes into reusable sub-policies. We turn each of these sub-policies into options by wrapping them with while-loops of varied number of iterations.
  arXiv  Detail & Related papers  (2024-10-15T04:36:44Z)
• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  This study introduces a novel guided tree search algorithm with dynamic node selection and node-level exploration budget. Experiments conducted on the GSM8K and TabMWP datasets demonstrate that our approach enjoys significantly lower computational costs compared to baseline methods.
  arXiv  Detail & Related papers  (2024-06-29T05:14:04Z)
• VN Network: Embedding Newly Emerging Entities with Virtual Neighbors [59.906332784508706]
  We propose a novel framework, namely Virtual Neighbor (VN) network, to address three key challenges. First, to reduce the neighbor sparsity problem, we introduce the concept of the virtual neighbors inferred by rules. Secondly, we identify both logic and symmetric path rules to capture complex patterns.
  arXiv  Detail & Related papers  (2024-02-21T03:04:34Z)
• Learning to Compare Nodes in Branch and Bound with Graph Neural Networks [5.08128537391027]
  Branch-and-bound approaches in integer programming require ordering portions of the space to explore next. We propose a new siamese graph neural network model to tackle this problem, where the nodes are represented as bipartite graphs with attributes. We evaluate our method by solving the instances in a plain framework where the nodes are explored according to their rank.
  arXiv  Detail & Related papers  (2022-10-30T19:38:23Z)
• Symbolic Distillation for Learned TCP Congestion Control [70.27367981153299]
  TCP congestion control has achieved tremendous success with deep reinforcement learning (RL) approaches. Black-box policies lack interpretability and reliability, and often, they need to operate outside the traditional TCP datapath. This paper proposes a novel two-stage solution to achieve the best of both worlds: first, to train a deep RL agent, then distill its NN policy into white-box, light-weight rules.
  arXiv  Detail & Related papers  (2022-10-24T00:58:16Z)
• Recursive Least Squares for Training and Pruning Convolutional Neural Networks [27.089496826735672]
  Convolutional neural networks (CNNs) have succeeded in many practical applications. High computation and storage requirements make them difficult to deploy on resource-constrained devices. We propose a novel algorithm for training and pruning CNNs.
  arXiv  Detail & Related papers  (2022-01-13T07:14:08Z)
• Waypoint Planning Networks [66.72790309889432]
  We propose a hybrid algorithm based on LSTMs with a local kernel - a classic algorithm such as A*, and a global kernel using a learned algorithm. We compare WPN against A*, as well as related works including motion planning networks (MPNet) and value networks (VIN) It is shown that WPN's search space is considerably less than A*, while being able to generate near optimal results.
  arXiv  Detail & Related papers  (2021-05-01T18:02:01Z)
• Growing Deep Forests Efficiently with Soft Routing and Learned Connectivity [79.83903179393164]
  This paper further extends the deep forest idea in several important aspects. We employ a probabilistic tree whose nodes make probabilistic routing decisions, a.k.a., soft routing, rather than hard binary decisions. Experiments on the MNIST dataset demonstrate that our empowered deep forests can achieve better or comparable performance than [1],[3].
  arXiv  Detail & Related papers  (2020-12-29T18:05:05Z)
• Neural Contextual Bandits with Deep Representation and Shallow Exploration [105.8099566651448]
  We propose a novel learning algorithm that transforms the raw feature vector using the last hidden layer of a deep ReLU neural network. Compared with existing neural contextual bandit algorithms, our approach is computationally much more efficient since it only needs to explore in the last layer of the deep neural network.
  arXiv  Detail & Related papers  (2020-12-03T09:17:55Z)
• The Tree Ensemble Layer: Differentiability meets Conditional Computation [8.40843862024745]
  We introduce a new layer for neural networks composed of an ensemble of differentiable decision trees (a.k.a. soft trees) Differentiable trees demonstrate promising results in the literature, but are typically slow in training and inference as they do not support conditional computation. We develop specialized forward and backward propagation algorithms that exploit sparsity.
  arXiv  Detail & Related papers  (2020-02-18T18:05:31Z)

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.