# A dynamic AI-based algorithm selection for Virtual Network Embedding

Abdelmounaim Bouroudi, Abdelkader Outtagarts, Yassine Hadjadj-Aoul

► To cite this version:

Abdelmounaim Bouroudi, Abdelkader Outtagarts, Yassine Hadjadj-Aoul. A dynamic AI-based algorithm selection for Virtual Network Embedding. Annals of Telecommunications - annales des télécommunications, 2024, 10.1007/s12243-024-01040-6. hal-04749254

HAL Id: hal-04749254

https://inria.hal.science/hal-04749254v1

Submitted on 22 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A Dynamic AI-Based Algorithm Selection for Virtual Network Embedding

Abdelmounaim Bouroudi¹, Abdelkader Outtagarts¹ and Yassine Hadjadj-Aoul²

¹Bell Labs, Nokia Networks France.

²INRIA, Univ Rennes, CNRS, IRISA, France.

Contributing authors: abdelmounaim.bouroudi@nokia.com; abdelkader.outtagarts@nokia-bell-labs.com; yassine.hadjadj-aoul@irisa.fr;

## Abstract

With the increasing sophistication and heterogeneity of network infras- tructures, the need for Virtual Network Embedding (VNE) is becoming more critical than ever. VNE consists of mapping virtual networks on top of the physical infrastructure, to optimize network resource use and improve overall network performance. Considered as one of the most important bricks of network slicing, it has been proven to be an NP-Hard problem with no exact solution. Several heuristics and meta-heuristics were proposed to solve it. As heuristics do not provide satisfactory solutions, meta-heuristics allow a good exploration of the solutions' space, though they require testing several solutions, which is generally unfeasible in a real world environment. Other methods relying on deep reinforcement learning (DRL) and combined with heuristics yield better performance without revealing issues such as sticking at local minima or poor space exploration limits. Nevertheless these algorithms present var- ied performances according to the employed approach and the problem to be treated, resulting in robustness problems. To overcome these limits, we propose a robust placement approach based on the Algorithm Selec- tion paradigm. The main idea is to dynamically select the best algorithm from a set of learning strategies regarding reward and sample efficiency at each time step. The proposed strategy acts as a meta-algorithm that brings more robustness to the network since it dynamically selects the best solution for a specific scenario. We propose two selection algo- rithms. First, we consider an offline selection in which the placement
strategies are updated outside the selection period. In the second algo-
rithm, the different agents are updated simultaneously with the selection
process, which we call an online selection. Both solutions proved their effi-
ciency and managed to dynamically select the best algorithm regarding
acceptance ratio of the deployed services. Besides, the proposed solu-
tions succeed in commuting to the best placement strategy depending on
the strategies' strengths while outperforming all stand-alone algorithms.

**Keywords:** Virtual Network Embedding, AI, Deep Reinforcement Learning, Algorithm Selection, B5G/6G

# 1 Introduction

The B5G/6G generations of mobile networks are expected to address the demands of new emerging applications from vertical industries. These new applications are characterized by ultra-low latency, high throughput, and a differentiated end-to-end flow with new Quality of Service (QoS) constraints [1].

To satisfy these requirements, mobile network operators are considering
new architectures and technology enablers like Network Function Virtualiza-
tion (NFV) and Software Defined Network (SDN)[2]. On one hand, NFV offers
more flexibility through the virtualization of the network functions, allowing
easy deployment and efficient resource sharing[3]. On the other hand, SDN
enables the transport programmability and automation through the separation
between the control and the data plans. Thanks to both these technologies,
the concept of network slicing has been actualized [4].

The coexistence of different network functions on the same substrate net-
work has led to a resource management challenge known as the Virtual
Network Embedding (VNE) problem, in which we aim to deploy a graph com-
posed of virtual network functions and virtual links with specific resource
requirements on a common restricted substrate network. The challenge in VNE
is to find the optimal placement decisions that allow the deployment of a max-
imum number of service graphs, which are described using a Virtual Network
Function-Forwarding Graph (VNF-FG).

The combinatorial nature of mapping virtual nodes and links onto the
physical substrate network makes solving the problem highly complex, even
for small network instances [5]. In fact, the VNE problem has been established
as an NP-hard problem, which implies that finding the optimal solution for
large network instances is computationally infeasible [6]. Therefore, various
approaches have been proposed to address the VNE problem and to find near
optimal or effective solutions.

Classical mathematical optimization methods are only capable of dealing
with very small network instances [7]. Methods based on heuristics converge
extremely fast but tend to get stuck in local minima [8]. Meta-heuristics-based
solutions offer a good exploration capacity, but are still susceptible to many
shortcomings. For example, they are only applicable to medium-sized networks
without built-in scalability. Moreover, whenever the network changes, a new
solution must be recalculated [9], as knowledge is not accumulated.

Given these limitations, new approaches, particularly Reinforcement Learn-
ing based approaches, have been explored. Combined with Deep Learning,
Deep Reinforcement Learning (DRL) is qualified to be the best adapted to
the unpredictable nature of the network. The Deep Deterministic Policy Gra-
dient (DDPG) algorithm [10], a model-free, off-policy actor-critic algorithm
using deep function approximators, is particularly notable in this context. It
can learn policies in high-dimensional, continuous action spaces, which is a key
advantage for complex network environments. The authors in [11, 12], proposed
a new algorithm to address the VNE problem. Based on the DDPG algorithm,
they proposed new enhancements in the exploration capacity of the solution
space combined with a placement heuristic to cope with the action space's
high dimensionality. The proposed solution, named EEDDPG for "Enhanced
Exploration Deep Deterministic Policy Gradient", gives significantly better
results compared to the vanilla DDPG with no placement heuristic. However,
it suffers from a lack of robustness. Despite the algorithm's good performance
in specific scenarios (relaxed networks, for example), the modification of the
context (restricted networks, topologies, requested resources, etc.) can result
in poor performance. As robustness and safety are critical considerations in
real-life use cases, learning-based strategies may pose a potential risk for next-
generation mobile network deployments [13]. In addition, these agents have
different learning abilities; some algorithms learn quickly but prematurely con-
verge to a local optimum, while others start slowly but perform better in the
end.

To solve these problems, we propose a new robust resource allocation algo-
rithm based on the Algorithm Selection paradigm. Inspired by the Epochal
Stochastic Bandit Algorithm Selection (ESBAS) framework [14], we present an
adapted version to the context of the VNE problem. Firstly presented in our
previous work [15], the main idea of ESBAS consists in selecting among a set
of RL algorithms the one maximizing the expected return in the recent num-
ber of iterations. In this work, we present a detailed version of this algorithm,
where we present the simulation platform and message exchanges with more
details on the competitive and cooperative mechanism. In addition, we propose
an online version of ESBAS using a weighted slicing window, hence the name
OWSAS, which stands for "Online Weighted Sliding window Algorithm Selec-
tion", that provides a sub-stationary system to the algorithm selector along
with an attention mechanism to assign more importance to agents exhibiting
significant growth in their returned reward.

The main contributions of this paper are:

* Formalizing the problem of reinforcement learning algorithms selection in the VNE context.
* Proposing a detailed version of the offline algorithms selection algorithm based on the ESBAS framework, first presented in [15].

* Proposing OWSAS an online version of ESBAS with continuous update of the different agents using a weighted sliding window.

* Providing a discussion on the obtained results and a comparison with standalone algorithms in both offline and online versions with different algorithm's performances and selection decisions.

The rest of this paper is organized as follows. We start with a background section, presenting the VNE problem and formulating it as a Markovian Decision Process (MDP) with a description of the different agent parameters. In the third section, we present a state of the art about the existing works that use the Algorithm Selection paradigm to solve complex problems. In the fourth section, we present a state-of-the-art about the Algorithm Selection Problem and its application for the VNE problem. In the fifth section, we present a unifying view of Reinforcement Learning algorithms allowing the application of Algorithm Selection solutions with RL algorithms. Then, we present the offline AS algorithm ESBAS, first presented in [15] with more details. We also present an online AS algorithm (named OWSAS) using the Weighted Sliding Window technique. In the fifth section, the simulation results of both algorithms are presented, alongside a discussion and a comparison with already existing standalone algorithms and using different placement heuristics. Finally, the conclusion of the work is presented in the sixth section.

# 2 Background

In this section, we introduce the modeling of the Virtual Network Function Embedding problem and its formulation using a Markov Decision Process. This formulation is common to all the learning techniques we consider in the following.

## 2.1 Formulation of the VNE problem

In the VNE problem, we have a set of $V$ VNF-Forwarding Graphs (VNF-FGs) denoted by $\mathcal{G} = \{G_1, ..., G_V\}$ which we aim to deploy on a substrate network. Each graph $G_{\zeta}$ is described by a set of $\mathcal{N}'$ Virtual Network Functions (VNFs), where each VNF $n'$ requests a set of $k_{VNF}$ types of resources represented by a vector $h_{n'} = [h_{n',0}, ..., h_{n',K_{VNF}-1}]$. These virtual functions are linked using a set of $\mathcal{L}'$ virtual links (VL), and each link $l'$ requests $k_{VL}$ types of resources denoted by a vector $f_{l'} = [f_{l',0}, ..., f_{l',K_{VL}-1}]$. The substrate network is also represented by a directed graph of nodes and links connecting these nodes, where each node $n$ has a specific amount of each resource $k$ denoted $r_{n,k}$, and each link also has a specific amount of resource $k$ denoted by $r_{l,k}$.

To deploy a VNF-FG, all its VNFs and VLs must be deployed.
A VNF can be deployed on a specific node if the latter has sufficient resources for each requested resource, i.e.:

$$ \sum_{n'} \Phi_n^{n'} h_{n',k} \le r_{n,k}, \quad \forall n, k \quad (1) $$

$$ \text{s.t. } \Phi_n^{n'} = \begin{cases} 1, & n' \text{ is hosted by } n \\ 0, & \text{otherwise} \end{cases} $$

Each VNF is deployed on only one substrate node, i.e.:

$$ \sum_n \Phi_n^{n'} \le 1, \quad \forall n' \quad (2) $$

A VL deployment requires that all the VNFs it connects are deployed. Additionally, the requirements of this VL must also be satisfied, i.e.:

$$ \sum_{l'} \Phi_{l'}^{l} f_{l',k} \le r_{l,k}, \quad \forall l, k \quad (3) $$

$$ \text{s.t., } \Phi_{l'}^{l} = \begin{cases} 1, & l' \text{ is hosted by } l \\ 0, & \text{otherwise} \end{cases} $$

We introduce an auxiliary binary variable $g_\zeta$ to indicate whether the VNF-FG $\zeta$ is deployed. The objective is to maximize the number of deployed VNF-FGs, respecting (1), (2), (3) referred to as Acceptance Ratio (AR), which is defined as follows:

$$ AR = \frac{\sum_{\zeta} g_{\zeta}}{|V|} \quad (4) $$

## 2.2 Markov Decision Process formulation

Reinforcement Learning consists of learning through trial and error using an agent that interacts with a stochastic environment [16]. At each time step $t$, the agent receives the state of the environment $s_t$, and based on it, the agent selects an action $a_t$ to be executed in the environment. The executed action changes the state of the environment. The value of this transition is communicated to the agent through the reward $r_t$, along with the new resulting state $s_{t+1}$. The agent uses this feedback to learn an optimal policy, $\pi^*$, mapping states to actions maximizing the expected return ($\pi: S \to A$). Since the transition probability $p$ from $s_t$ to $s_{t+1}$ depends only on the previous state, this problem has the Markovian property and can be formalized as a Markov Decision Process (MDP).

In this paper, we use the same MDP formulation presented in our previous paper [12]:

* **State representation:** The environment state is represented by the formulation of the VNF-FGs, which are described by a vector of size $|N'| \times K_{VNF} + |L'| \times K_{VL}$. This vector, describing the requests of VNFs and VLs
for all VNF-FGs, is fed into the DRL agent as the state of the environment to determine the next action.

* **Action:** Each action $a_t$ is a vector of size $|N| \times |N'| + |L| \times |L'|$ and $a_t = [a_t^{n,n'}, w_t^{l,l'}]$ where $a_t^{n,n'}, w_t^{l,l'} \in [0, 1]$ showing the favor of assigning VNF $n'$ to node $n$ (resp. virtual link $l$ to substrate link $l'$) at time-step $t$. Based on this formulation, the action space is sparse, and the proposed action may become unfeasible with more constraints on the network. To address this, we apply a mapping heuristic (e.g., First-Fit) to use a binary version of the action vector. WF2A [12].

* **Reward:** To assess the performance of the RL algorithm, the Acceptance Ratio (4) is adopted as a reward measure, which is defined as the number of graphs deployed over the total VNF-FGs requests. Other reward designs can be possible, such as the sum of deployed VNFs and VLs over the requested ones, i.e.,

$$R = \frac{VNF_{deployed}}{|N'|} + \frac{VL_{deployed}}{|L'|} \qquad (5)$$

In reward design (5), the objective of the DRL agent is to deploy a maximum of VNFs and VLs without taking care of the graph deployment, while in (4) we aim to deploy all VNFs and VLs of each graph allowing the maximization of the number of VNF-FGs deployment. In this work, we stick with the reward design in (4).

## 3 Related work

The idea of utilizing meta-algorithm selection techniques to solve specific problems has gained significant traction in recent years across various domains. [17] an innovative approach for dynamic algorithm selection utilizing reinforcement learning (RL). The core idea is to use RL to guide the selection of algorithms during runtime by adapting to the current computational state. This method is particularly beneficial in scenarios where multiple algorithms exist for solving a single problem, each with unique performance characteristics. Although this method differs from our work's methodology, the authors demonstrated its effectiveness in solving low-dimensional problems with rapid responses to dynamic system changes.

In [18], the authors present a collaborative framework based on evolution operations (mutation & crossover) to build a super learner that outperforms partial learners. The main idea behind their work is to use a portfolio of learners that explore different parts of the solution space with different time horizons, while resolving the same task. The experience acquired is shared through a reply buffer for better sample efficiency, and the policies of each learning agent undergo a mutation operation to expand their exploration area. The main drawback of this work is that it considers homogeneous learners and
takes a lot of time to achieve good performance due to parameter matching and
learners' binding. Another approach is to consider the selection problem as an
exploration/exploitation problem and use methods like *ε*-greedy and Upper
Confidence Bound (UCB) to solve it. This method was, also, considered in [19]
where authors model the problem as a Contextual Multi-Armed Bandit [20]
While this method gives good performance in terms of the overall reward
compared to stand-alone solutions, it requires a predefined previously known
set of contexts, which is in our case difficult to predict.

Another approach is to formulate the selection problem as an exploration-exploitation dilemma and employ methods like ε-greedy and Lower Confidence Bound (LCB) to address it. Authors in [19] introduce a reinforcement learning methodology for automatic online algorithm selection and empirically test it. It is designed to predict the performance of each available algorithm and select the best one. It explores the exploration vs. exploitation trade-off in online learning settings and investigates classic solution strategies for this trade-off in the context of automatic online algorithm selection. Through modeling the problem as a Contextual Multi-Armed Bandit [20] and particularly focusing on epsilon-greedy and lower confidence bound strategies. The findings suggest that a purely exploitative greedy strategy can outperform strategies that explicitly perform exploration. However, this method requires the use of pre-defined contexts, which depend on the use case and can be more challenging to use in complex problems like the VNE problem.

In this work [21], the authors propose the SFSSA framework (Scheduling Framework to Select the Scheduling Algorithms) to address the complexities of resource scheduling in hierarchical cloud computing systems. This novel approach utilizes two types of algorithm selectors: Deep Learning-based Algorithm Selectors (DLS), which are trained using labeled data, and Deep Reinforcement Learning-based Algorithm Selectors (DRLS), which are trained with feedback from dynamic scenarios. These selectors are designed to assist in choosing appropriate scheduling algorithms and adapting to the evolving needs and conditions of cloud computing environments. While this method presents a novel approach, particularly for simple deterministic scheduling algorithms, it may face challenges in convergence when applied to learning agents since it has to converge the selection agent and the selection agents in the portfolio at the same time.

In their paper [22], the authors address computational problems that can
be solved by multiple algorithms, with efficiency varying based on factors like
problem difficulty, size, and hardware characteristics. They propose a novel
approach using reinforcement learning, specifically an adapted Q-learning algo-
rithm that combines Monte-Carlo and Temporal Difference methods. This
method is designed to select algorithms dynamically based on execution time,
conceptualizing the selection process as a Markov Decision Process (MDP).
This approach demonstrates how adaptive learning methods can effectively
navigate the complexities of algorithm selection in diverse computational con-
texts. However, it appears that their method primarily focuses on problems
solvable through recursive, deterministic algorithms, suggesting a potential
area for expansion in future research.

In a comparable context, several studies have explored the application of reinforcement learning for selection processes in data analysis. Authors in [23] proposed a two-phase framework for automatic model selection, which utilizes reinforcement learning to optimize the process of choosing the most appropriate model for a given dataset, incorporating data preprocessing through meta-learning and a comprehensive model selection framework. Concurrently, in [24], authors focused on feature selection in classification tasks, employing a reinforcement learning approach that utilizes the Temporal Difference algorithm within a Markov Decision Process framework. Their methodology was evaluated using a robust, low-cost classifier, aiming to enhance prediction accuracy and reduce computational costs. Both studies underscore the versatility of reinforcement learning in streamlining algorithm and feature selection for more efficient and accurate data analysis.

In their work [25], the authors address the challenge of model selection in reinforcement learning, specifically focusing on batch or offline, non-interactive settings. They propose a complexity regularization-based model selection algorithm designed to select an action-value function with the smallest Bellman error. This novel approach is adaptive, aiming to perform nearly as well as if the optimal model parameters were known beforehand. While tailored for batch or offline learning contexts where interactive model tuning is not feasible, such an approach is particularly valuable in scenarios where real-time interaction is not possible or practical.

In the realm of reinforcement learning (RL), the work of [14] stands out for its innovative approach to algorithm selection. Their method treats RL algorithms as black boxes and utilizes the Upper Confidence Bound 1 (UCB1) strategy to choose the most effective algorithm systematically. They introduce two distinct models: the "offline version", where RL agents are not updated during exponentially sized epochs, and UCB1 is used to select the best algorithm in each epoch, and the "online version", where agents are updated after every interaction with the environment, with UCB1 adapting over a sliding window of recent selections. This work provides a comprehensive framework for evaluating and selecting RL algorithms based on their performance, contributing significantly to the field.

On another front, [26] proposes a novel competitive/cooperative framework for heterogeneous deep RL. In their model, agents with different exploration strategies compete for rewards and cooperatively share their experiences. High-value experiences are stored in a special memory, facilitating shared learning, while less significant experiences go to a default memory. This approach includes a range of algorithm categories, both gradient-based and gradient-free, underscoring its versatility. However, the paper stops short of providing a convergence analysis or addressing system stationarity. This framework offers a unique perspective on experience sharing and learning dynamics in multi-agent RL environments.
To the best of our knowledge, we are the first to propose the idea of using algorithm selection of meta-algorithms for the VNE problem in the B5G/6G context. In this work, we build on previous work, especially [14], where in a first step we adapt the offline version (called ESBAS) to the VNE problem, and then in a second step we propose an online version based on a novel idea that uses a weighted Sliding-Windows to create a sub-stationary system to apply UCB1 for online selection.

# 4 A new framework for DRL algorithms' selection for VNE

The performance of different algorithms varies according to problem instances. Therefore, it is crucial to associate each problem instance with the algorithm that yields the best performance, leading to the selection of an optimal algorithm for every instance.

Selecting the appropriate algorithm for a given problem is a sequential decision-making process, represented by the problem set $\mathcal{D}$. $\mathcal{D}$ consists of a set of instances $\mathcal{I}$ and a set of candidate algorithms $\mathcal{A} = A_1, A_2, \dots, A_n$ that can be used to solve $\mathcal{D}$. A performance metric $m: \mathcal{A} \times \mathcal{I} \to \mathbb{R}$ qualitatively measures each agent's performance for a given problem instance. The goal is to develop a selector $\mathcal{S}$ that maps each problem instance $i \in \mathcal{I}$ to an algorithm $\mathcal{S}(i) \in \mathcal{A}$, optimizing the overall performance according to the performance metric $m$ for the problem set $\mathcal{D}$ [27].

In our case, $\mathcal{D}$ represents the VNE problem, with the algorithms as various DRL agents, and the metric is the Acceptance Ratio returned by the agent. Constructing such a selection algorithm allows the combination of strengths from multiple heterogeneous agents. This is achieved through competition and cooperation mechanisms [26]. The competition mechanism relates to the exploitation part, where agents may exhibit diverse learning strategies and potentials. Indeed, some agents may learn quickly but get stuck in local optima, while others may learn slowly at the beginning but give better results at the end. Thus, the need arises to select the best algorithm to leverage these varied learning potentials. The second mechanism focuses on cooperation during exploration, ensuring that the agents share the same data collected through various exploration strategies, thus rapidly improving their policies.

In the following subsections, we first describe the architecture for efficiently unifying multiple agents, followed by introducing the proposed algorithms for selecting the best agent: offline and online.

## 4.1 Unifying view for Reinforcement Learning agents

To apply the Algorithm Selection framework for RL agents, it is necessary to establish a unified view for the different agents, independent of their learning mechanisms. This unified view enables the Algorithm Selection framework to treat these agents as black boxes, selecting the optimal one based solely on their returns. Hence, we use an interaction process for information sharing among
agents, as introduced in [14], fostering cooperation between heterogeneous agents.

For this purpose, we assume a set of RL algorithms, called a *portfolio* ($\mathcal{A}$ in the AS formulation), that are learning off-policy, leading to episodic RL problems. This assumption allows fair learning between the different algorithms and makes trajectory sharing fairer since all algorithms learn from the same dataset. To describe the sharing mechanism, we adopted the same approach as in [14], in which two time scales are defined:

* **Meta-time ($\tau$):** Defined as the time scale for executing one algorithm, including algorithm selection and generating a complete episode with the selected algorithm.

* **RL-time ($t$):** The time scale for a single interaction with the environment. This interaction generates the tuple (State or Observation, Action, and Reward).

During each meta-time $\tau$, a trajectory $\varepsilon$, consisting of sequences of observations, actions, and rewards is collected.

$$ \varepsilon_{\tau} = \langle o_{\tau}(t), a_{\tau}(t), r_{\tau}(t) \rangle_{t \in [1, \|\varepsilon\|]} \in \mathcal{E} \quad (6) $$

where $\mathcal{E}$ represents the space of trajectories.

For each collected trajectory, the discounted cumulative reward $\mu(\varepsilon_t)$ is calculated as follows:

$$ \mu(\varepsilon_t) = \sum_{t=1}^{\lvert\varepsilon_{\tau}\rvert} \gamma^{t-1} r_{\tau}(t) \quad (7) $$

Here, $0 \le \gamma < 1$ is the discount factor.

Each RL algorithm, denoted by $A_k$, is treated as a black box, taking a trajectory set $\delta$ as input and producing a policy $\pi_{\delta}^{A_k}$ as output. The goal of each agent is to find the policy $\pi^*$ that yields the optimal expected return. The flow diagram of the Algorithm Selection framework, as described herein, is presented in Figure 1.

To begin the process, an algorithm $A_i$ is selected from the portfolio, as described in step (1). This selected algorithm is then executed in the appropriate environment to generate a trajectory $\varepsilon_{\tau}$, as detailed in step (2). The cumulative reward of the algorithm, denoted $\mu(\varepsilon_{\tau})$, is calculated in step (4.2). Meanwhile, the trajectory generated by the algorithm in step (4.1) is stored in a shared memory (buffer). This shared memory (buffer) is used to update all algorithms in the portfolio, as indicated in step (5.2). Conversely, the cumulative reward obtained by the algorithm is used to update the policy governing the algorithm selection, as outlined in step (5.1).
<figure><img src="image_2.png" /><figcaption>Fig. 1 Algorithm selection flow diagram.</figcaption></figure>

The ultimate objective of this process is to optimize the expected cumulative reward, defined as follows:

$$ \mathbb{E}_S \left[ \sum_{\tau=1}^{T} \mu(\varepsilon_{\tau}) \right] \qquad (8) $$

Following [14], we also considered the optimal expected return $\mathbb{E}_{\mu_{\infty}}$, which is the highest expected return achievable by any policy in $\mathcal{A}$. Therefore, for meta-time $T$, the absolute regret of $\mathcal{S}$, as shown in equation (9), represents the loss from not choosing the best agent for trajectory control compared to the selection by the meta-algorithm $\mathcal{S}$.

$$ \rho_{abs}^{\mathcal{S}}(T) = T \mathbb{E}_{\mu_{\infty}} - \mathbb{E}_{S} \left[ \sum_{\tau=1}^{T} \mu(\varepsilon_{\tau}) \right] \qquad (9) $$

Based on the underlying assumptions and formulations, the subsequent section introduces two meta-algorithms. These algorithms enable the identification of DRL agents for address the VNE problem through two distinct approaches: offline selection and online selection with an attention mechanism.

## 4.2 Offline algorithm selection

In this work, we explore a new approach to solving the VNE problem by exploiting different solutions simultaneously, leveraging their exploration capabilities and strengths. Based on the Epochal Stochastic Bandit Algorithm Selection (ESBAS) framework, first introduced in [14], we propose an adapted version for the VNE problem. ESBAS is an offline selection meta-algorithm used to solve the general challenge of off-policy DRL algorithm selection. The main idea is to consider the selection problem as an Exploration/Exploitation problem, then utilize the Upper Confidence Bound (UCB1) [28] algorithm
shared memory $\delta$ for storing collected trajectories and a portfolio A containing concurrent agents. In the algorithm body, for each epoch $\beta$, we have two main parts: the update part and the selection part. In the update part, from lines 5 to 8, ESBAS updates the policies of each agent in the portfolio at the beginning of the iteration. Agents' policies are updated using recorded trajectories collected from previous iterations only if the update buffer threshold $G$ is exceeded. In the selection part (lines 9 to 23), the UCB1 parameters are reset for the upcoming exponential-sized epoch, as specified in line 9. Here, $x_k$ represents the cumulative mean reward, indicating the estimated value of selecting agent $k$, while $n_k$ denotes the number of selections for agent $k$. During each epoch, the meta-algorithm computes an optimistic guess using the UCB1 formula in line 11, and the selected agent is executed for a meta-time $T$ while collecting the generated set of trajectories. In each trajectory, from lines 14 to 16, we generate a set of random VNF-FGs considered as the current state $s_t$ for the selected agent. This state is fed to the selected agent to generate an action. Then, the generated action is converted to a feasible action $\tilde{a}_t$ using the W2FA heuristic to be executed. The returned reward and new state $s_{t+1}$ are stored in shared memory $\delta$ (lines 17 and 18). After collecting the set of trajectories, the UCB1 parameters are updated (lines 21 to 23) with the accumulated reward and the number of times the agent was selected. Since epochs are of exponential size, small epochs have less time to explore the different agents' potentials, while large ones give a more accurate selection since they sufficiently exploit each agent before starting to make a good selection.

In Figure 2, we illustrate the different interactions between the ESBAS algorithm's participating objects using a UML sequence diagram. In this diagram, we represent a single loop of the main program and the message exchanges between the following objects of the system: The main program, which represents the actor that starts the selection process; the UCB1, the DRL Portfolio, and the DRL Actors, which are entities within the same objects as described in Algorithm 1, and the Simulation Environment, which is the execution platform (the simulated network where actions are executed). For each loop, the main program starts by updating the agents in the DRL portfolio. Then, it resets the UCB1 parameters to prepare for the next epoch execution. For each epoch and each iteration, the main program asks the UCB1 object to perform a selection. This latter, gets the list of existing DRL agents in the DRL portfolio with their corresponding UCB1 parameters, and using these parameters, it calculates the optimistic choice and returns it to the main program. The selected agent will be executed for a meta-time, and in each iteration, it gets the environment state, generates an action, and executes it on the simulation environment. The collected trajectory is then returned to the main program to store it in the shared memory and accumulate the reward of the selected agent for this meta-time. At the end of the iteration, the accumulated reward is fed back to the UCB1 object to update its parameters. This process is repeated for each iteration in the epoch.
<figure><img src="image_3.png" /><figcaption>Fig. 2 ESBAS sequence diagram.</figcaption></figure>

To analyze the ESBAS algorithm's time complexity, we decompose it into two main parts: the initialization and the main loop. While initialization typically incurs constant time, the main loop will have the dominant time complexity. Given a number of iterations $\beta$, the following components are considered:

* Agent Policy Update 4 to 8: The time complexity depends on each DRL agent's specific learning algorithm implementation. If the learning algorithm has a complexity of $O(L)$ per agent, and there are $N$ agents, the complexity of this step would be $O(N \times L)$.

* Parameter Reset 9: Resetting UCB1 parameters for each agent is typically $O(N)$, as it needs to be done for each agent.

* Epoch-Based Iteration 10 to 23: The nested loop runs for $2^{\beta}$ to $2^{\beta+1}$, which can be considered as $O(2^{\beta})$ for each iteration of the outer loop.

* Agent Selection 11: The selection process involves computing the UCB1 score for one agent each time. Then, the cost of this action is $O(1)$.

* Trajectory Generation and Execution (Lines 12-20): This step's complexity depends on the specifics of the action generation, conversion, and execution
processes. If we denote these complexities as $O(A)$, $O(C)$, and $O(E)$, respectively, the overall complexity for one trajectory would be $O(A+C+E)$. Since this is done for T times (trajectory length), it becomes $O(T \times (A+C+E))$.

* UCB1 Parameters Update (Lines 21-23): Parameter updating is typically a constant-time operation, $O(1)$, per update. This step's complexity does not significantly influence the overall time complexity.

Combining these elements, the overall complexity for $\beta$ iterations is: $\beta[O(N \times L) + O(N) + O(2^\beta) \times [O(T \times (A + C + E))]]$.

Given the exponential nature of the epochs, $O(2^\beta)$, this term will dominate the time complexity as $\beta$ increases. Consequently, the ESBAS algorithm's time complexity is similar to any standalone algorithm, except for the update part in the main loop, where the standalone solution only update one agent instead of different agents in the algorithm selection version. Hence, no overhead cost results in the algorithm selection solution.

## 4.3 Online algorithm selection with weighted sliding window

As described in the previous subsection, the offline version blocks updates of the different agents for epochs of an exponentially growing size. This technique creates a stationary bandit system, allowing the application of a stationary selection technique such as UCB1. However, this approach prevents agents from having frequent updates. Indeed, allowing agents to update their policies after each interaction will outperform the epochal update version, underscoring the importance of considering an online version where all agents learn equally from the collected data.

Continuously updating agents leads to an unstable reward distribution that changes with each update, creating a non-stationary bandit system for which policies like UCB are inappropriate [29]. To handle this problem, we propose a Sliding Window UCB that relies on the empirical reward from each agent's last $w$ interactions, instead of averaging over all the past rewards. This technique was proposed in [30] and includes a theoretical regret bound and a tuned window size.

In our approach, rather than using the regret bound and specified window size, we propose to use an arbitrary window size, with $w < \tau$, combined with an attention weight $a_{w,t}(i)$ for each element $i$ in the window. The different steps for constructing the sliding window are illustrated in Figure 3. We start by calculating the attention weights (1,2) as follows:

$$a_w(i) = \frac{i}{w} |u_w - r(i)| \qquad (10)$$

where $u_w = \frac{1}{w} \sum_{i=1}^{w} r(i)$.

Using attention weights calculated with formula (10) and saved in the attention buffer, we construct a weighted window (3), where each element is associated with a weight that reflects its importance in the window. Thus, we
<figure><img src="image_4.png" /><figcaption>Fig. 3 Weighted sliding window mechanism.</figcaption></figure>

give more attention to new elements and elements with significant growth relative to the average window reward. Multiplying these weights multiplied by the actual window rewards creates a more stationary system for UCB since only the more important rewards are considered.

Algorithm 2 describes the Online Weighted Sliding window AS (OWSAS) algorithm. In line 3, we reset the UCB parameters for the upcoming epoch. Starting at line 4, an epoch of fixed size $τ$ begins with the selection of the optimal algorithm using rewards collected in the sliding window (line 5). From lines 6 to 7, we execute the selected agent's action on the environment, store the transition in the buffer, and record the returned reward in the sliding window. From lines 8 to 11, we calculate attention weights for the updated window and subsequently utilize these weights to update the UCB parameters for the considered algorithm (lines from 12 to 15). Finally, from lines 16 to 18, we update the agent's policies based on transitions accumulated across all previous epochs.

To illustrate the difference with the ESBAS algorithm, the sequence diagram in Figure 4 represents a single loop iteration of the OWSAS algorithm. As in ESBAS, we have the same participating objects in the different interactions. At the beginning of each epoch, we reset the UCB1 parameters in its instance. During the epoch, the main program requests the UCB1 instance to select the best algorithm in the DRL portfolio. It retrieves the list of existing agents and selects the most optimistic agent based on UCB1 parameters. The selected agent is executed for one iteration, acquiring the environment state, generating an action, and executing it within the simulation environment. The main program stores the returned trajectory in shared memory for later use in updating the agent's networks. The returned reward is utilized to create the new sliding window incorporating attention weights. After calculating the attention weights, the main program ask the UCB1 instance to update
<caption>**Algorithm 2: OWSAS for VNE problem**</caption>

**Input:** $\delta, \tau, w, A, G, W, \Phi$
1 &nbsp;&nbsp;&nbsp; $g \leftarrow 0$
2 &nbsp;&nbsp;&nbsp; **for** $\beta \leftarrow 0, \infty$ **do**
3 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\mu \leftarrow \{\}, n \leftarrow 0, \forall A_k \in A, n_{k,w} \leftarrow 0, x_{k,w} \leftarrow 0$
4 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **for** $t \leftarrow 0, \tau$ **do**
5 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $A_{kmax} = \text{argmax}_{A_k} \left( x_k + \sqrt{\xi \frac{\log(n \land w)}{n_{k,w}}} \right)$
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Execute $a_t^k$ generated by $A_{kmax} \rightarrow r_t, s_{t+1}$
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $(s_t, a_t^k, r_t, s_{t+1}) \rightarrow \delta$
8 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Store $r_t$ in the Sliding Window $r_t \rightarrow W$
8 &nbsp;&nbsp;&nbsp; Calculate attention vector:
9 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $u_w \leftarrow \frac{1}{w} \sum_{i=1}^{w} r_i$
10 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **for** $i \in W$ **do**
11 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\lfloor \mu(i) = \frac{i}{w} \|u_w - r(i)\| \rfloor$
12 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\Phi \leftarrow W \times \mu$
13 &nbsp;&nbsp;&nbsp; Update the WSW-UCB parameters:
14 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $n_{k,w} \leftarrow \sum_{w} 1[A_{kmax}]$
15 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $x_{k,w} \leftarrow \frac{1}{n_{k,w}} \sum_{i \in w} \Phi(i) 1[A_{kmax}]$
16 &nbsp;&nbsp;&nbsp; $n \leftarrow n + 1$
17 &nbsp;&nbsp;&nbsp; $g \leftarrow g + 1$
18 &nbsp;&nbsp;&nbsp; Update agent's policy:
19 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **for** $A_k \in A$ **do**
20 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **if** $g \ge G$ **then**
21 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\lfloor \pi_{\delta}^k \rfloor$ learns $\pi^k$ on all trajectories in buffer $\delta$

its parameters with these new weights. It then updates the portfolio agents using trajectories from recent iterations only if we exceed the buffer threshold. Unlike the ESBAS algorithm, where epochs grow exponentially, OWSAS employs fixed-size epochs and simultaneously updates various agents during selection, thanks to the weighted sliding window stabilization method.

The time complexity of the OWSAS algorithm primarily revolves around execution within fixed-size epochs, denoted as $\tau$. Key components of this algorithm and their associated complexities are as follows:

* Initialization of UCB Parameters (Line 3): At the beginning of each epoch, UCB parameters for each agent in the portfolio are initialized. For $N$ agents, the complexity is $O(N)$.

* Epoch-Based Iteration (Outer Loop): The main loop iterates $\tau$ times within each epoch. The significant operations within this loop include:
<figure><img src="image_5.png" /><figcaption>Fig. 4 OWSAS sequence diagram.</figcaption></figure>

- *Agent Selection (Line 4)*: The process of selecting the agent with the highest UCB value has a complexity of $O(1)$.

- *Execution of Selected Agent's Action (Line 5)*: Denoted as $O(E)$, this depends on the specifics of the action execution process.

- *Storing Transition and Reward (Lines 6-7)*: A constant-time operation, $O(1)$.

- *Calculating Attention Weights and Updating UCB Parameters (Lines 8-15)*: This process involves iterating over the sliding window of size $w$, computing attention weights, and updating UCB parameters. The complexity is $O(w)$ for calculating attention weights since we update the parameters of the selected agent.

- *Updating Agent's Policy (Lines 16-18)*: If updating one agent's policy has a complexity of $O(L)$, for $N$ agents, it results in $O(N \times L)$.

* **Overall Complexity per Epoch**: Calculated as $O(N) + O(\tau) \times [O(E) + O(w) + O(N \times L)]$, simplifying it becomes: $O(\beta \times [\tau \times (N+E+w+N \times L)])$, where $\beta$ represents the number of iterations.

The dominating factors in the complexity are the number of agents $N$, the complexity of executing an action $E$, the sliding window size $w$, and the complexity of learning $L$. Unlike the ESBAS algorithm, which has an exponential factor in its epochs, the OWSAS algorithm maintains a fixed epoch size,
Simulation Testbed

<figure><img src="image_6.png" /><figcaption>Fig. 5 Simulation test-bed.</figcaption></figure>

denoted as $\tau$, making its time complexity more predictable and potentially more manageable, especially for environments where the number of iterations within an epoch needs to be controlled. However, the introduction of the sliding window and attention mechanism in the OWSAS algorithm contributes additional complexity, which can impact its overall computational efficiency.

5 Simulation results

To test our proposed algorithms, we utilize a simulation test-bed, as shown in Figure 5, comprising two main parts: an orchestration part with a portfolio of placement algorithms, and a network part that simulates both the substrate network and the requested VNF-FGs. For network simulation, we use the OMNeT++ [31], simulation tool which is an open source modular framework used to build network simulators. Both parts are containerized using Docker images, featuring shared memory and a REST API. The test-bed is deployed by instantiating these images and starting the REST Server on the network part instance.

Before starting the simulation, we first configure the DRL parameters, as detailed in [12]. For the network part, we simulate the BtEurope network topology [32] comprising 24 nodes and 37 full-duplex links. The VNF-FG requests consist of 10 connected graphs, generated via the Erdos-Renyi model [33] (see more in [12]). In Table 1, we present the number of resources available on the substrate network, as well as the resource values requested by the VNF-FGs. For the substrate network, we use predefined resources for each node and link (Available Resources in the table). While for the requested Forwarding Graphs, we randomly select a value from the value set of each resource type as
<table><caption>**Table 1** Network Resources and VNF-FG Requests</caption><thead><tr><td>Resource Type</td><td>Available Resources</td><td>Requested Resources</td></tr></thead><tbody><tr><td>CPU</td><td>12-79.8</td><td>1, 2, 4, 8</td></tr><tr><td>RAM</td><td>128-1024</td><td>2, 4, 8, 16, 32</td></tr><tr><td>Storage</td><td>1000-10000</td><td>1, 5, 20, 100</td></tr><tr><td>Bandwidth</td><td>1000-10000</td><td>10, 20, 50, 100</td></tr></tbody></table>

presented in table 1 (Requested Resources), and consequently the VNF-FGs requests change from one execution to another.

For both the offline and online algorithms, we utilized three off-policy DRL agents previously employed to solve VNE problem:

* **W2FA_DDPG agent:** This agent is a modified version of the DDPG algorithm. In this approach, the actor network's output action is exploited by the W2FA heuristic [12]. Using this heuristic allows DDPG to compete with other agents. Otherwise, it would be a worse competitor and will be eliminated in the first steps. The W2FA heuristic is designed to address the limitations of the DDPG algorithm in handling large-scale discrete action spaces, a challenge commonly encountered in the VNE problem. Its goal is to efficiently embed feasible actions generated by a DRL agent. The heuristic operates iteratively, placing VNFs on substrate nodes based on descending action values while ensuring resource requirements are met. After assigning each VNF to a specific position, the heuristic zeroes out other action values for that VNF. Following VNF placement, it addresses the virtual links, calculating the shortest paths for these links based on where VNF edges are placed.

* **EEDDPG agent:** This agent implements the Enhanced Exploration DDPG algorithm proposed in [12] without the evolutionary operation applied to the set of critic networks.

* **EEDDPG Evolution agent:** Similar to EEDDPG, this agent applies an evolutionary function to the set of Critic Networks.

Each agent comprises actor and critic networks. Each network features a Dense layer with 300 hidden units each and a ReLU activation function. The output layer uses a Sigmoid activation function for the actor network and a linear activation function for critic networks. Table 2 presents different DRL agent parameters. These parameters are the same for all DRL agents used in these experiments. The only difference is their learning technique, number of networks and update strategies.

For the ESBAS algorithm, we run the algorithm for ten exponential-sized epochs with $\beta = [0, 9]$. Therefore, the first epochs are small epochs and the more the epochs are larger the more they improve their selection choices. For OWSAS, we utilized ten fixed-size epochs, each comprising 100 iterations ($\tau = 100$), with a sliding window size of $w = \tau/2$ and a corresponding weight attention vector $\Phi$ of the same size. To evaluate our solution's performances,
<table><caption>**Table 2** Configuration parameters of DRL agents</caption><thead><tr><td>Parameter</td><td>Value</td></tr></thead><tbody><tr><td>Learning rate of actor</td><td>10<sup>-4</sup></td></tr><tr><td>Learning rate of critic</td><td>10<sup>-3</sup></td></tr><tr><td>γ</td><td>0.99</td></tr><tr><td>τ</td><td>10<sup>-3</sup></td></tr><tr><td>μ</td><td>10<sup>-2</sup></td></tr><tr><td>Buffer size</td><td>50000</td></tr><tr><td>Batch size</td><td>32</td></tr><tr><td>Optimizer</td><td>Adam</td></tr></tbody></table>

<figure><img src="image_7.png" /><figcaption>**Fig. 6** Acceptance ratio of ESBAS compared with DDPG, EEDDPG and EEDDPG Evolution.</figcaption></figure>

we deployed the topology using OMNeT++ simulation tool, adhering to the specifications in [12].

## 5.1 ESBAS results

This section describes the evaluation of the performance of the ESBAS algorithm. We compare the acceptance ratio returned by the three standalone agents (W2FA_DDPG, EEDDPG, EEDDPG Evolution) to the acceptance ratio achieved by the ESBAS algorithm. Figure 6 shows the acceptance ratio of these three agents alongside with the ESBAS performance.

The EEDDPG with evolution agent performs the best among the standalone agents, followed by W2FA_DDPG and then EEDDPG without evolution. This result is consistent with the observations made in [12], where it was noted that EEDDPG Evolution demonstrates better learning efficiency and quickly achieves good acceptance ratios. However, during exponential epochs, where updates are less frequent, other agents do not perform as well
<figure><img src="image_8.png" /><figcaption>Fig. 7 Selection ratio of ESBAS.</figcaption></figure>

as EEDDPG Evolution. This is particularly evident with the EEDDPG without evolution, which lags behind the other agent, especially in achieving high acceptance ratio. This performance can be attributed mainly to the intrinsic design of EEDDPG when it operates without evolutionary enhancement, leading to limited exploration capabilities. Another factor contributing to this behavior is the low frequency of updates which are mainly performed at the end of each epoch. This infrequent updating contributes to its underperformance over extended epochs, a characteristic that is also observable in the original paper where EEDDPG was introduced [12]. Moreover, the initial parameter settings of the Actor and Critic networks within the EEDDPG agent play a significant role in its performance trajectory. Initially this impact is unclear in small epochs since we have a small number of VNFFGs to place. However, as the epochs increase in size, leading to a larger volume of placement requests, the limitation of these initial parameter settings becomes more pronounced. Compared with the standalone agents, the ESBAS algorithm outperformed all three in all large epochs from the third one onward. This shows the effectiveness of the selection strategy employed by ESBAS in maximizing the expected return in recent iterations. The performance improvement achieved by ESBAS is significant, especially in later epochs, where the acceptance ratio is crucial. Overall, these results demonstrate the effectiveness of the Algorithm Selection paradigm in solving complex problems like the VNE.

Figure 7 shows the selection decisions made by ESBAS as represented by the selection ratios of each agent during the epochs. During the initial epochs, which are small in size, the ESBAS does not perform well in selecting
agents as it lacks sufficient time to explore each agent's performance. However, from the fifth epoch forward, it begins making good selection decisions by selecting W2FA_DDPG and EEDDPG Evolution more often than EEDDPG. In the last three epochs, there is a noticeable decrease in the selection ratio of W2FA_DDPG and EEDDPG, while the EEDDPG Evolution shows an increasing selection ratio, reaching over 80% in the final epoch.

## 5.2 OWSAS results

The primary objective of our second contribution, as explained in the OWSAS algorithm description section (Section 2), is to investigate an online selection variant, which capitalizes on the continuous updating of the agents to achieve a high acceptance ratio. Similar to the offline version, we first evaluate each agent's performance and compare it with the algorithm selection strategy. Our initial observations, when individually running agents separately, indicate that the three agents exhibit convergent performance due to their common placement heuristic, W2FA, applied to the action vector. Accordingly, we first present a comparison of multiple executions of the three agents using the same placement heuristic, followed by a comparison with the OWSAS algorithm. We subsequently alter the agent heuristic by incorporating a First-Fit placement heuristic, and we demonstrate the selection ratio difference of OWSAS compared to the aforementioned case.

The performance of various agents, namely W2FA_DDPG, EEDDPG, EEDDPG Evolution, and the OWSAS-based strategy, are compared using box plots to illustrate the acceptance ratio. To ensure fair comparison, we conduct five simulation runs for each agent and calculate the mean acceptance ratio in each epoch. It is important to note that the comparison is based on the median values and the distribution of the mean acceptance ratios in each epoch.

### 5.2.1 Use case 1 : same placement heuristic for all agents

In this first use case, we employ the placement heuristic W2FA as described in [12] for all three agents: W2FA_DDPG, EEDDPG, and EEDDPG Evolution. Figures 8a, 8b, 8c, and 8d illustrate the acceptance ratio of these agents. As previously mentioned, the online version of the algorithm benefits from the continuous learning of the agents, which leads to a better acceptance ratio compared to epochal updates. In the first two epochs, the performance of the three agents is similar. However, starting from the third epoch onwards, we observe that EEDDPG without Evolution performs better than EEDDPG Evolution and W2FA_DDPG in terms of median acceptance ratio value. In the following three epochs (epochs 3 to 6), most median acceptance ratio values for EEDDPG without Evolution are over 45%. This result is consistent with the findings in [12], where EEDDPG outperforms EEDDPG Evolution in a non-congested network. This result could be explained by the fact that EEDDPG initially learns slowly due to the absence of the Evolutionary operator, and then it outperforms the other agents towards the end. From the
<figure><img src="image_9.png" /><figcaption>(a) Acceptance ratio of W2FA_DDPG.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>(b) Acceptance ratio of EEDDPG.</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>(c) Acceptance ratio of EEDDPG Evolution.</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>(d) Acceptance ratio of OWSAS.</figcaption></figure>

<caption>**Fig. 8** Acceptance ratio of OWSAS compared to the standalone algorithms.</caption>

seventh epoch onwards, we observed an improvement in the performance of all three agents. Notably, the EEDDPG agent consistently achieved the highest median acceptance ratio, while also exhibiting less variance than the other agents, namely W2FA_DDPG and EEDDPG Evolution. On the other hand, the OWSAS-based solution demonstrated strong performance compared to the autonomous agents. In particular, it achieved a high median score in the early epochs, which progressively improved throughout the training process, ultimately surpassing the performance of the autonomous solutions and achieving a high acceptance ratio in the later epochs.

Figure 9 illustrates the mean selection ratio of each agent by OWSAS across five simulation executions for each epoch. It can be observed that, except for the early epochs, OWSAS consistently selects EEDDPG as the best agent followed by EEDDPG Evolution and W2FA_DDPG. This selection behavior explains the stable growth of its acceptance ratio as shown in Figure 8d, where EEDDPG is frequently chosen for updates, while still selecting other agents.
<figure><img src="image_13.png" /><figcaption>Fig. 9 Selection ratio of OWSAS use Case 1.</figcaption></figure>

with good performance in the last epochs. By leveraging the strengths of different agents, the selection approach achieves a high acceptance ratio, which can account for the good performance of the algorithm depicted in Figure 8d.

### 5.2.2 Use case 2: different placement heuristics

Unlike the previous subsection, where the agents demonstrated similar acceptance ratios, we consider agents with differing learning potentials. Specifically, we replace the W2FA_DDPG agent with a simple First-Fit algorithm while retaining EEDDPG and EEDDPG Evolution agents with the W2FA heuristic. The First-Fit strategy selects the first physical node with the required resources and all the physical links that satisfy the requested bandwidth and latency requirements. The acceptance ratio of this new agent is shown in Figure 10. As expected, the First-Fit algorithm demonstrates lower and fixed performance compared to the other agents, since it lacks a learning mechanism, there is no improvement in its policy over time. Conversely, EEDDPG and EEDDPG Evolution consistently exhibit good performance, while OWSAS shows promising results from the first epochs and consistent growth over time.

Figure 11 shows the selection ratios of OWSAS for agents with varying learning potentials. Clearly, OWSAS consistently selects EEDDPG and EEDDPG Evolution over the First-Fit solution across all epochs. This highlights our solution's capability to early identify and eliminate the suboptimal agent from its selection list. However, we observe a slightly lower acceptance ratio compared to the first use case, which is due to the presence of a suboptimal agent in the portfolio, impacting the overall reward of the selection.
<figure><img src="image_14.png" /><figcaption>**Fig. 10** Acceptance ratio of OWSAS compared with FIRST-FIT, EEDDPG and EEDDPG Evolution.</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>**Fig. 11** Selection ratio of OWSAS use case 2.</figcaption></figure>

# 6 Conclusion

Virtual Network Embedding (VNE), also known as network slicing is a major challenge in B5G/6G networks that has gained significant attention from researchers. Due to the unpredictable behavior of services and heterogeneous nature of future networks, DRL algorithms are increasingly employed to address this challenge. In this paper, we propose a novel algorithm selection
method for VNE that leverages the strengths of different DRL algorithms used simultaneously. The proposed algorithm selection framework consists of two approaches: ESBAS and OWSAS. ESBAS employs offline selection in epochs of exponential size with blocked agent updates, while OWSAS is an online selection algorithm that uses a weighted sliding window with an attention mechanism. We demonstrate the superiority of our approach over standalone DRL algorithms in both offline and online cases. Our study also highlights the ability of OWSAS to make good choices even for competitive agents or agents with different performance levels. Overall, This research provides a robust solution for the VNE problem and offers a path towards developing more trustworthy orchestrators for future mobile network generations.

## Declarations

* **Competing interests** : The authors have no relevant financial or non-financial interests to disclose. The authors have no competing interests to declare that are relevant to the content of this article.

## References

[1] Dogra, A., Jha, R.K., Jain, S.: A survey on beyond 5g network with the advent of 6g: Architecture and emerging technologies. IEEE Access 9, 67512–67547 (2020)

[2] Zhang, S.: An overview of network slicing for 5g. IEEE Wireless Communications 26(3), 111–117 (2019). https://doi.org/10.1109/MWC.2019.1800234

[3] ETSI: Network functions virtualisation (nfv) release 2; management and orchestration; network service templates specification (2017-08)

[4] Brief, O.S.: Openflow-enabled sdn and network functions virtualization. Open Netw. Found 17, 1–12 (2014)

[5] Wu, W., Zhou, C., Li, M., Wu, H., Zhou, H., Zhang, N., Shen, X.S., Zhuang, W.: Ai-native network slicing for 6g networks. IEEE Wireless Communications 29(1), 96–103 (2022). https://doi.org/10.1109/MWC.001.2100338

[6] Amaldi, E., Coniglio, S., Koster, A.M., Tieves, M.: On the computational complexity of the virtual network embedding problem. Electronic Notes in Discrete Mathematics 52, 213–220 (2016)

[7] Allybokus, Z., Perrot, N., Leguay, J., Maggi, L., Gourdin, E.: Virtual function placement for service chaining with partial orders and anti-affinity rules. Networks 71(2), 97–106 (2018)
[8] Khebbache, S., Hadji, M., Zeghlache, D.: Scalable and cost-efficient algorithms for vnf chaining and placement problem. In: 2017 20th Conference on Innovations in Clouds, Internet and Networks (ICIN), pp. 92–99 (2017). IEEE

[9] Khebbache, S., Hadji, M., Zeghlache, D.: A multi-objective non-dominated sorting genetic algorithm for vnf chains placement. In: 2018 15th IEEE Annual Consumer Communications & Networking Conference (CCNC), pp. 1–4 (2018). IEEE

[10] Lillicrap, T.P., Hunt, J.J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., Wierstra, D.: Continuous control with deep reinforcement learning. arXiv preprint arXiv:1509.02971 (2015)

[11] Quang, P.T.A., Hadjadj-Aoul, Y., Outtagarts, A.: A deep reinforcement learning approach for vnf forwarding graph embedding. IEEE Transactions on Network and Service Management 16(4), 1318–1331 (2019)

[12] Quang, P.T.A., Hadjadj-Aoul, Y., Outtagarts, A.: Evolutionary actor-multi-critic model for vnf-fg embedding. In: 2020 IEEE 17th Annual Consumer Communications & Networking Conference (CCNC), pp. 1–6 (2020). IEEE

[13] Li, C., Guo, W., Sun, S.C., Al-Rubaye, S., Tsourdos, A.: Trustworthy deep learning in 6g-enabled mass autonomy: From concept to quality-of-trust key performance indicators. IEEE Vehicular Technology Magazine 15(4), 112–121 (2020)

[14] Laroche, R., Feraud, R.: Reinforcement learning algorithm selection. arXiv preprint arXiv:1701.08810 (2017)

[15] Bouroudi, A., Outtagarts, A., Hadjadj-Aoul, Y.: Robust deep reinforcement learning algorithm for vnf-fg embedding. In: 2022 IEEE 47th Conference on Local Computer Networks (LCN), pp. 351–354 (2022). https://doi.org/10.1109/LCN53696.2022.9843650

[16] Kaelbling, L.P., Littman, M.L., Moore, A.W.: Reinforcement learning: A survey. Journal of artificial intelligence research 4, 237–285 (1996)

[17] Armstrong, W., Christen, P., McCreath, E., Rendell, A.P.: Dynamic algorithm selection using reinforcement learning. In: 2006 International Workshop on Integrating Ai and Data Mining, pp. 18–25 (2006). IEEE

[18] Khadka, S., Majumdar, S., Nassar, T., Dwiel, Z., Tumer, E., Miret, S., Liu, Y., Tumer, K.: Collaborative evolutionary reinforcement learning. In: International Conference on Machine Learning, pp. 3341–3350 (2019).
[19] Degroote, H., Bischl, B., Kotthoff, L., De Causmaecker, P.: Reinforcement learning for automatic online algorithm selection-an empirical study. ITAT 2016 Proceedings **1649**, 93-101 (2016)

[20] Zhou, L.: A survey on contextual multi-armed bandits. arXiv preprint arXiv:1508.03326 (2015)

[21] Zhou, G., Wen, R., Tian, W., Buyya, R.: Deep reinforcement learning-based algorithms selectors for the resource scheduling in hierarchical cloud computing. Journal of Network and Computer Applications **208**, 103520 (2022)

[22] Lagoudakis, M.G., Littman, M.L., et al.: Algorithm selection using reinforcement learning. In: ICML, pp. 511-518 (2000)

[23] Shang, D., Sun, H., Zeng, Q.: A reinforcement-algorithm framework for automatic model selection. In: IOP Conference Series: Earth and Environmental Science, vol. 440, p. 022060 (2020). IOP Publishing

[24] Rasoul, S., Adewole, S., Akakpo, A.: Feature selection using reinforcement learning. arXiv preprint arXiv:2101.09460 (2021)

[25] Farahmand, A.-m., Szepesvári, C.: Model selection in reinforcement learning. Machine learning **85**(3), 299-332 (2011)

[26] Zheng, H., Jiang, J., Wei, P., Long, G., Zhang, C.: Competitive and cooperative heterogeneous deep reinforcement learning. In: Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS (2020)

[27] John, R.: Rice. The algorithm selection problem. volume 15 of Advances in Computers. Elsevier (1976)

[28] Katehakis, M.N., Veinott Jr, A.F.: The multi-armed bandit problem: decomposition and computation. Mathematics of Operations Research **12**(2), 262-268 (1987)

[29] Hartland, C., Gelly, S., Baskiotis, N., Teytaud, O., Sebag, M.: Multi-armed bandit, dynamic environments and meta-bandits (2006)

[30] Garivier, A., Moulines, E.: On upper-confidence bound policies for switching bandit problems. In: International Conference on Algorithmic Learning Theory, pp. 174-188 (2011). Springer

[31] Varga, A., Hornig, R.: An overview of the omnet++ simulation environment. In: 1st International ICST Conference on Simulation Tools and
[32] Knight, S.: The Internet Topology Zoo (2010). http://www.topology-zoo.org/dataset.html

[33] Erdős, P., Rényi, A., et al.: On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci 5(1), 17–60 (1960)