\section{Introduction}
\input{sec/1_introduction}

\section{Related Work}
\input{sec/2_related_work}

\section{System Model}
\input{sec/3_system_model}

\section{Problem Formulation and NP-Hardness}
\input{sec/4_problem_formulation}

\section{Single-Agent Multi-Agent Reinforcement Learning Based RAN Resource Slicing}
\input{sec/5_rl_algo}

\section{Simulation Results}
\input{sec/6_simulation_results}

\section{Conclusion}
\input{sec/7_conclusion}

\bibliographystyle{IEEEtran}




\subsection{Problem Formulation}
The main question of RB allocation problem in RAN is how to derive a two-level optimal allocation of RBs to URLLC and eMBB end-users that meet their QoS requirements in terms of data rate and delay. For this purpose, the global RB allocation optimization problem is formulated as follows:
\begin{maxi!}[3
	{x}{\sum_{b \in \mathcal{B}}\sum_{s\in \{s_u,s_e\}}\sum_{u_b \in \mathcal{U}_b} r_{u_b}^s \label{Obj}}
	{\label{opt}}{}
	\addConstraint{\sum_{k \in \mathcal{K}}x_{u_b}^{k}}{\leq K_{\text{max}}, \forall u_b \in \mathcal{U}_b, \forall b \in \mathcal{B} \label{C1}}
	\addConstraint{\sum_{u_b \in \mathcal{U}_b} x_{u_b}^k}{\leq 1, \forall k \in \mathcal{K}, \forall b  \in \mathcal{B}  \label{C2}}
	\addConstraint{x_{u_b}^{k'}\times |\mathcal{K}_b|}{\leq\sum_{u_b\in\mathcal{U}_b}\sum_{k \in \mathcal{K}_b }x_{u_b}^{k}, \forall k' \in \mathcal{K} \setminus \mathcal{K}_b, \forall u_b \in \mathcal{U}_b, \forall b\in \mathcal{B} \label{C3}}
	\addConstraint{r_{u_b}^{s_e}}{\geq \mathcal{R}_{min}, \forall u_b \in \mathcal{U}_b, \forall b \in \mathcal{B}  \label{C4}}
	\addConstraint {d_{u_b}^{s_u}}{\leq \mathcal{D}_{max}, \forall u_b \in \mathcal{U}_b, \forall b \in \mathcal{B} \label{C5}}
	\addConstraint{x_{u_b}^{k} \in \{0,1\}, \forall k \in \mathcal{K}, \forall u_b \in \mathcal{U}_b, \forall b \in \mathcal{B} \label{C6}}.
\end{maxi!}

The objective function in~\eqref{Obj} maximizes the total sum data rates of the URLLC and eMBB end-users. Constraints~\eqref{C1} guarantee a fair RBs allocation by forcing the number of RBs allocated to each end-user $u_b$ to not exceed a maximum number $K_{\text{max}}$. Constraints~\eqref{C2} respect the OFDMA constraints by ensuring that each RB is allocated to only one end-user at a time. Constraints~\eqref{C3} guarantee that a gNodeB $b$ can request additonal RBs from other gNodeBs if and only if all of its pre-allocated RBs are used by its end-users. Constraints~\eqref{C4} state that the data rate of the eMBB end-users must be greater than a minimum required threshold $\mathcal{R}_{min}$. Constraints~\eqref{C5} ensure that the delay of URLLC end-users cannot exceed a maximum required threshold $\mathcal{D}_{max}$. Finally, constraints~\eqref{C6}) list the optimization variables.

 Note that the dynamic resource allocation problem considers limited resources. In fact, the formulated RB allocation problem consists of maximizing the total achievable data rate of eMBB and URLLC end-users subject to QoS constraints and limited resources constraints represented by the set of constraints given in \eqref{C1}. These constraints guarantee that every end-user cannot be allocated more than a maximum number of resources. They limit the number of resources that each end-user can have and thus can allocate the remaining resources more efficiently and in a fair manner between end-users. The limitation of resources in the considered problem is also stated by the borrowing concept. Once a gNodeB is out of resources because all of its SDN-allocated resources are used, it can borrow other gNodeBs-resources.

Due mainly to the binary nature of the optimization variables and the non-linearity of the delay experienced by an end-user defined in Eq.~\eqref{DL}, the RB allocation problem is a non-linear binary programming problem. It is thus very challenging to solve~\eqref{opt} in general. In the sequel, we study its NP-hardness.

\subsection{NP-hardness}
Here, we denote the problem~\eqref{opt} by $P$. To prove that $P$ is NP-hard, we reduce the 0-1 knapsack problem \cite{Knapsack}, which is NP-hard, to an instance of $P$.

\begin{definition}[0-1 knapsack problem]
A 0-1 knapsack problem is defined as follows: given a set $\mathcal{N}$ of $n$ items, each one with its profit $p_i$ and weight $w_i$, and a knapsack of capacity $C$. Each item can be put into the knapsack or not (1 or 0). The objective of this problem is to find a subset $\mathcal{N}' \subseteq \mathcal{N}$ such that the total value of items $\sum_{n_i\in \mathcal{N}'} p_i$ is maximized and the total weight of the selected items is less than or equal to the knapsack capacity, i.e., $\sum_{n_i \in \mathcal{N}'} w_i \leq C$.
\end{definition}

\begin{theorem}
    $P$ is NP-hard.
\end{theorem}

\begin{IEEEproof}
    We prove the theorem by considering a restricted version of $P$. This shows that the problem is NP-hard in the general case as well. We consider the following restricted version of $P$:  
    \begin{itemize}
        \item there is only one gNodeB denoted by $b$ with its associated end-users set $\mathcal{U}_b$.
        \item there is only the eMBB slice.
        \item the RBs pre-allocated by the SDN controller $\mathcal{K}_b$ for $b$ are known, i.e., the first level of the RB allocation procedure is already performed by the SDN controller.
    \end{itemize}
    In this case, $P$ becomes equivalent to the following:
    \begin{maxi!}[3
	    {x}{\sum_{u_b \in \mathcal{U}_b} r_{u_b}^{s_e} \label{Obj2}}
	    {\label{opt2}}{}
	    \addConstraint{\sum_{k \in \mathcal{K}_b}x_{u_b}^{k}}{\leq |\mathcal{K}_b|, \forall u_b \in \mathcal{U}_b \label{C2_1}}
	    \addConstraint{\sum_{u_b \in \mathcal{U}_b} x_{u_b}^k}{\leq 1, \forall k \in \mathcal{K}_b  \label{C2_2}}
	    \addConstraint{r_{u_b}^{s_e}}{\geq \mathcal{R}_{min}, \forall u_b \in \mathcal{U}_b, \label{C2_3}}
	    \addConstraint{x_{u_b}^{k} \in \{0,1\}, \forall k \in \mathcal{K}_b, \forall u_b \in \mathcal{U}_b, \label{C2_4}}.
    \end{maxi!}
    
    The mathematical statement of the problem in Eq.~\eqref{opt2} is equivalent to finding an allocation of the RBs set $\mathcal{K}_b$ to the eMBB end-user set $\mathcal{U}_b$ such that: (i) the sum data rates of the end-users is maximized, (ii) the maximum number of pre-allocated RBs to gNodeB $b$ does not exceed $K_{max}=|\mathcal{K}_b|$ \eqref{C2_1}, (iii) each RB is allocated to only one end-user at a time \eqref{C2_2}, and (iv) the data rate of the eMBB end-users must be greater than a minimum required threshold $\mathcal{R}_{min}$ \eqref{C2_3}.

    To reduce the 0-1 knapsack problem to~\eqref{opt2}, we let (i) the number of items $N$ be the number of eMBB end-users, (ii) the profit $p_i$ for item $i$ be the achievable data rate $r_{u_b}^{s_e}$ for eMBB end-user $u_b$, (iii) the weight $w_i$ for item $i$ be the allocated RBs for eMBB end-user $u_b$, and (iv) the knapsack capacity $C$ be the number of the pre-allocated RBs to gNodeB $b$. Problem $P$ is now clearly reduced to a knapsack problem. The knapsack capacity is respected and, thus, the number of allocated RBs to all eMBB end-users does not exceed $|\mathcal{K}_b|$.
    
    Since the reduction is clearly done in a polynomial-time and the 0-1 knapsack problem is NP-hard, we conclude that the restricted problem formulated in Eq.~\eqref{opt2} is also NP-hard, which proves the theorem.
\end{IEEEproof}
\subsection{MDP formulation of the SDN allocation level}
The MDP of the first resource allocation level is given by the triplet $(\mathscr{S}_c, \mathscr{A}_c, \mathscr{R}_c)$ where $\mathscr{S}_c$ represents the state space, $\mathscr{A}_c$ designates the action space and $\mathscr{R}_c$ is the reward function.
\subsubsection{The state space} ~

As discussed previously, the central agent is incorporated into the SDN controller which has a global view of the network. In fact, the central agent's state contains information about its previously allocated RBs to the gNodeBs and other global parameters of the network. More precisely, the state space of the central agent is composed of the triple $\mathscr{S}_c$ given as follows:
\begin{equation}\label{ctrlState}
    \mathscr{S}_c = (\mathcal{B},\mathcal{K},\boldsymbol{\mathcal{K}_h}),
\end{equation}
where $ \boldsymbol{\mathcal{K}_h}= \{ \mathcal{K}_b, \forall b \in \mathcal{B} \}$ represents the allocated RBs previously to each gNodeB. Also, the central agent' state includes the sets $\mathcal{B}$ and $\mathcal{K}$ that represent the sets of gNodeBs and RBs, respectively.  

\subsubsection{The action space} ~

Since the central agent performs the RB allocation in a large time-scale, it has to decide which subset $\mathcal{K}_b \subseteq \mathcal{K}$ of RBs it should allocate to each gNodeB $b \in \mathcal{B}$. Note that the central agent has to make sure that an RB is assigned to only one gNodeB each time it performs the RB allocation. Therefore, the action space of the central agent, denoted by $\mathscr{A}_c$, is defined as follows:

\begin{equation}\label{ctrlAction}
    \mathscr{A}_c = \{0,1\}^{|\mathcal{K}| \times |\mathcal{B}|},
\end{equation}
where an action $\boldsymbol{a_c} \in A_c$ is given by the row vector $ [a_1^1,\ldots,a_1^{|\mathcal{K}|},a_2^1,\ldots,a_2^{|\mathcal{K}|},\ldots,a_{|\mathcal{B}|}^1,\ldots,a_{|\mathcal{B}|}^{|\mathcal{K}|}] $. If an element $a_b^k$ of vector $\boldsymbol{a_c}$ is equal to 1, it means that the central agent has decided to allocate RB $k$ to gNodeB $b$. Also, to avoid assigning the same RB $k$ to several gNodeBs, the central agent has to make sure that the constraints $a_b^k \neq a_{b'}^k, \forall k \in \mathcal{K}$ and $b \neq b' \in \mathcal{B}$ are satisfied. 

\subsubsection{The reward function} ~

Once the central agent observes the environment through its current state, it chooses an action $\boldsymbol{a_c}$ from the set $\mathscr{A}_c$. After choosing an action from the action space $\mathscr{A}_c$, the central agent receives a reward $\mathscr{R}_c$. Since the objective is to maximize the total sum-rate, the objective of the central agent has to be related to the sum-rate of the network given in Eq.~\eqref{Obj}. We define the reward as how the assigned RBs to gNodeBs affect the achieved data rate of the entire system. In other words, the more the total data rate of the system is higher, the better is the action chosen by the central agent.
Thus, the reward of the central agent is given by Eq.~\eqref{Obj}, where:

\begin{equation}\label{ctrlReward}
    \mathscr{R}_c = \sum_{b \in \mathcal{B}}\sum_{s\in \{s_u,s_e\}}\sum_{u_b \in \mathcal{U}_b} r_{u_b}^s    
\end{equation}

According to Eq. \eqref{ctrlReward}, the value of $\mathscr{R}_c$ depends on the RB allocation decisions in the gNodeB level. Indeed, the central agent should wait for the results of the second resource allocation level in order to efficiently explore its environment. Therefore, the RB allocation is performed in a joint manner between the two allocation levels.

\subsection{MDP formulation of the gNodeB allocation level}
The MDP of the second resource allocation level is given by the triplet $(\mathscr{S}_b, \mathscr{A}_b, \mathscr{R}_b)$ where $\mathscr{S}_b$ represents the state space of agent $b$, $\mathscr{A}_b$ designates the action space of agent $b$ and $\mathscr{R}_b$ is the reward function of agent $b$.
\subsubsection{The state space} ~

As illustrated in Fig. 2, we propose a multi-agent DQL algorithm, with each gNodeB acts as an agent, to allocate the required RBs to eMBB and URLLC end-users and performs RBs sharing between gNodeBs, if necessary. Indeed, based on the chosen action by the central agent in the SDN allocation level, each agent observes its local state $\mathscr{S}_b$. In our model, we consider that the controller communicates to each agent the information about the RBs allocated to all other agents. Accordingly, each agent $b$'s state $\mathscr{S}_b, \forall b \in \mathcal{B}$, is given by the following tuple:
\begin{equation}\label{BSState}
    \mathscr{S}_b = (\mathcal{G}_b,\mathcal{U}_b,\mathcal{K}_b,\mathcal{R}_{min},\mathcal{D}_{max}),
\end{equation}
where $\mathcal{U}_b$ and $\mathcal{K}_b$ represents the set of associated end-users with agent $b$ and the set of pre-allocated RBs to agent $b$ respectively. The term $\mathcal{G}_b = (G_{{u_b},k}:u \in U_b, k \in \mathcal{K})$ represents the DL channel gain between agent $b$ and its associated end-users in each RB $k \in \mathcal{K}$. The channel gains $\mathcal{G}_b$ can be easily collected by agent $b$ as follows: (i) agent $b$ broadcasts pilot signals to all of its associated end-users. Then, each end-user estimates the channel state information and sends it back to the corresponding agent through a feedback channel. The estimation of $\mathcal{G}_b$ between each associated end-user over each RB in the system helps agent $b$ to take good decisions, especially to borrow the needed RBs from the other agents. The state $\mathscr{S}_b$ also includes the minimum data rate threshold $\mathcal{R}_{min}$ and the maximum delay threshold $\mathcal{D}_{max}$ that corresponds to the requirements of eMBB and URLLC slices, respectively.

\subsubsection{The action space} ~

In the gNodeB allocation level, each agent takes actions according to its own allocation policy. In fact, the agent has to (i) assign the pre-allocated RBs to its associated end-users and (ii) request additional RBs from other agents when its pre-allocated RBs are not sufficient. Also, it is assumed that each agent is aware of the number of RBs present in the entire system. This information is acquired as follows: in each round of the SDN allocation level, the controller communicates with each agent the information on the RBs allocated to the other agents. Therefore, we define the space action of agent $b$, denoted by $\mathscr{A}_b$, as follows: 
\begin{equation}\label{BSAction}
    \mathscr{A}_b = \{0,1\}^{|\mathcal{K}| \times |\mathcal{U}_b|},
\end{equation}
where an action $\boldsymbol{a_b} \in \mathscr{A}_b$ is given by the row vector $ [a_1^1,\ldots,a_1^{|\mathcal{K}|},a_2^1,\ldots,a_2^{|\mathcal{K}|},\ldots,a_{|\mathcal{U}_b|}^1,\ldots,a_{|\mathcal{U}_b|}^{|\mathcal{K}|}] $. Note that a vector $\boldsymbol{a_b}$ is equivalent to an association matrix $[x_{u_b}^k]$ because each element $a_{u_b}^k$ of vector $\boldsymbol{a_b}$ corresponds to the assignment of an RB $k \in \mathcal{K}$  to an associated end-user $u_b \in \mathcal{U}_b$. In other words, if an element $a_{u_b}^k$ of vector $\boldsymbol{a_b}$ is equal to 1, it means that agent $b$ has decided to allocate RB $k$ to end-user $u_b$. Also, if all elements $ a_{u_b}^{k'}, \forall k' \in \mathcal{K} \setminus \mathcal{K}_b$, of vector $\boldsymbol{a_b}$ are equal to 0, it means that agent $b$ does not request additional resources from the other gNodeBs. When constructing the action space $\mathscr{A}_b$ of agent $b$, the constraints \eqref{C1}, \eqref{C2} and \eqref{C3} should be respected. By applying these constraints, we significantly reduce the action space $\mathscr{A}_b$. As a result, the exploration phase is significantly improved to discover better strategies, which considerably accelerates the learning process of agent $b$. Further, considering that agents should cooperate to dynamically share the unexploited RBs among themselves, each agent communicates its chosen action to the others. Therefore, each agent $b$ forms a joint action $\boldsymbol{a}=(\boldsymbol{a}_b,\boldsymbol{a}_{-b})$ where $\boldsymbol{a}_{-b}$ denotes the actions chosen by the other agents. 

\subsubsection{The reward function} ~

Multi-agent reinforcement learning methods seek to learn a policy that achieves the maximum expected total reward for all agents. Indeed, the learning process of all agents is driven by the reward function. In our model, the main objective is to maximize the total achievable data rate of the entire system to meet the QoS requirement of eMBB and URLLC end-users. Therefore, the reward function of agent $b$ relates to its total sum-rate subject to the ultra-low latency requirements of the URLLC services as well as to the minimum data rate requirements of the eMBB services.

The reward of agent $b$ depends on whether or not it has successfully allocated the needed RBs to its associated end-users. An RB allocation operation is considered to be feasible if the chosen action $\boldsymbol{a_b}$ satisfies the constraints \eqref{C1}, \eqref{C2}, \eqref{C3}, \eqref{C4} and \eqref{C5}, otherwise it is considered as an infeasible operation. The constraints (7b), (7c) and (7d) are already verified in the action space construction phase. However, as an allocation operation can require borrowing some RBs from other agents, it is necessary to verify if a borrowed RB is: (i) exploited by its owner and (ii) also chosen by at least one agent other than its owner. Since each agent forms the joint action $\boldsymbol{a}$, (i) and (ii) can be easily verified by agent $b$. If at least one of them is correct, the constraint \eqref{C3} is not satisfied and thus the action chosen by agent $b$ is not feasible. As a result, the individual reward of agent $b$, denoted by $\mathscr{R}_b$ is expressed as follows:
\begin{equation}\label{BSReward}
    \mathscr{R}_b= 
    \begin{cases}
    \sum\limits_{s\in \{s_u,s_e\}}\sum\limits_{u_b \in \mathcal{U}_b} r_{u_b}^s, & \text{if } \boldsymbol{a_b} \text{ is feasible}, \\
    -1, & \text{if } \boldsymbol{a_b} \text{ is not feasible}.
    \end{cases}
\end{equation}

When an action $\boldsymbol{a_b} \in \mathscr{A}_b$ is not feasible, it is penalized with a negative reward, $\mathscr{R}_b=-1$, to prevent the agent from choosing infeasible actions in the future. 

\subsection{Single-agent EXP3 algorithm}
In order to solve the SDN allocation level problem, we adopt an online learning algorithm that is based on the multi-armed bandit (MAB) approach \cite{MAB}. In MAB, a player needs to choose, at each round of the game, one arm from a finite set of arms, each characterized by an unknown reward, with the objective of maximizing his expected cumulative reward. The single-agent MDP is modeled as a MAB as follows. The central agent, i.e., the SDN controller, represents the player and the set of arms is given by its action space $\mathscr{A}_c$. We propose the EXP3 algorithm as a popular bandit strategy to solve the SDN allocation level problem \cite{z_iot}.  The SDN controller runs the EXP3 algorithm where each action is assigned a weight to evaluate how good the action is for the SDN controller, \textit{i.e.,}\xspace the higher the weight of an action, the better the action is. At the beginning of the algorithm, the weights of all actions are uniformly distributed. Then, the algorithm iterates several rounds. For each round, the SDN controller:

\begin{enumerate}
    \item calculates the probability of choosing each action, which is proportional to its weights;
    \item chooses an action according to the probability distribution calculated previously and receives a reward; and 
    \item uses the received reward to update the weights of each action by applying an exponential weighting scheme. The advantage of such a scheme is that it rapidly increases the probability of good actions, while rapidly reducing the probability of bad actions.
\end{enumerate}
The pseudo-code of the EXP3 algorithm is presented in Algorithm~\ref{alg:Exp3}.


In detail, the EXP3 algorithm takes as input an exploration parameter $\alpha \in [0,1]$ that controls the desire to choose an action uniformly at random. It starts by assigning a weight $\psi_i$ to each action $\boldsymbol{a_{c,i}}$, which is initialized to 1. Then, it iterates the rounds. For each round, the central agent calculates the probability $\pi_i$, given in Eq.~\eqref{PiExp3}, of choosing action $\boldsymbol{a_{c,i}}$. Based on $\pi$, it selects an action $\boldsymbol{a_{c,i}}$ and receives a reward $\mathscr{R}_{c,i}$. The obtained reward is scaled to the range $[0,1]$ and it is denoted by $\mathscr{\bar{R}}_{c,i}$. Since $\mathscr{R}_{c,i}$ is the total achievable data rate of the system, it can be scaled using Eq.~\eqref{ScaledReward}. After scaling the obtained reward, the central agent calculates an estimated reward $\mathscr{\hat{R}}_{c,i}$ using Eq.~\eqref{EstimatedReward}. The idea behind estimating the reward in such manner is to compensate for a potentially low probability of obtaining the observed reward. Finally, the weights are updated as $\psi_i = \psi_i \exp{(\alpha \mathscr{\hat{R}}_{c,j}/|\mathscr{A}_c|)}$.
\begin{equation}\label{PiExp3}
    \pi_i = (1-\alpha)\frac{\psi_i}{\sum_{j=1}^{|\mathscr{A}_c|}\psi_j} + \frac{\alpha}{|\mathscr{A}_c|}
\end{equation}
\begin{equation}\label{ScaledReward}
    \mathscr{\bar{R}}_{c,i} = 1 - \frac{1}{(1+\mathscr{R}_{c,i})}
\end{equation}
\begin{equation}\label{EstimatedReward}
    \mathscr{\hat{R}}_{c,i} =  \frac{\mathscr{\bar{R}}_{c,i}}{\pi_i}
\end{equation}

\begin{algorithm}[t]
	\caption{EXP3-based SDN allocation level}
	\label{alg:Exp3}
	\begin{flushleft}
	    Parameters: $\alpha \in [0,1]$ \\
		Initialize $\psi_i = 1$ for all $i \in \{1,2,\ldots,|\mathscr{A}_c| \}$
	\end{flushleft}
	\begin{algorithmic}[1]
		\FOR{\textit{each round}}
		    \FOR{$i=1,2,\ldots,|\mathscr{A}_c|$}
		       \STATE Calculate $\pi_i$ using Eq.~\eqref{PiExp3}
		    \ENDFOR
		    
    		\STATE Select an action $\boldsymbol{a_{c,i}}$ according to
    		$\pi_i$
    		\STATE Receive reward $\mathscr{R}_{c,i}$
    		\STATE Calculate $\mathscr{\bar{R}}_{c,i}$ using Eq.~\eqref{ScaledReward}
    		\FOR{$j=1,2,\ldots,|\mathscr{A}_c|$}
    		    \STATE $\mathscr{\hat{R}}_{c,j} \leftarrow \mathscr{\Bar{R}}_{c,j}/\pi_i \cdot \mathbbm{1}_{j=i}$ 
    		    
    		    \STATE $\psi_i \leftarrow \psi_i \exp{(\alpha \frac{\mathscr{\hat{R}}_{c,j}}{|\mathscr{A}_c|})}$
    		\ENDFOR
		\ENDFOR
	\end{algorithmic}	
\end{algorithm}

The EXP3 algorithm is simple to implement and does not require enormous computational complexity since it simply updates the weights of choosing actions by increasing or decreasing their probabilities according to their performance.
 Note that the EXP3 algorithm is an online learning algorithm that enables the SDN controller to increase or decrease the weight of the actions according to the feedback received from the gNodeBs. Precisely, the SDN controller selects an action $\boldsymbol{a_{c,i}}$ to allocate the RBs to the gNodeBs. Then, it waits for the results of the second RB allocation level, which is performed by the gNodeBs. Once the gNodeBs have assigned the RBs, chosen by the SDN controller, to their end-users, each gNodeB: 1) calculates its achieved data rate, and 2) communicates this information to the SDN controller. The total sum-data rate of all gNodeBs will be the reward received by the SDN controller after choosing action the $\boldsymbol{a_{c,i}}$, that will be used by the EXP3 algorithm to update the actions' weights.

\subsection{Multi-agent deep Q-Learning algorithm}
 The DQL algorithm \cite{DQL} extends the classical Q-learning RL \cite{QL} algorithm by approximating the Q-function using a deep neural network known as deep Q-network (DQN). In order to be used as an efficient non-linear approximator, such a network must be trained to observe the state of the agent and learn weights in order to play actions that yield the highest rewards. Once the DQN is properly trained, it is exploited by the agent to take actions based on the observed state~\cite{z_dqn}. To solve the multi-agent MDP model, we propose a multi-agent DQL algorithm. This algorithm consists of two main phases: the training phase and the implementation phase. In the training phase, each agent trains a deep neural network (DNN) in an offline manner using a large amount of experiences (collected dataset). In the implementation phase, each agent chooses actions in an online manner using its trained model. We describe, in the following, the training and implementation phases of the proposed multi-agent DQL approach.
\subsubsection{The training phase of DQL}~

DQN approximates the Q-value function $\mathscr{Q}(s,a)$ through a neural network that performs a mapping between states and actions. In other words, this network returns, for any given state-action pair, the estimated Q-value $\mathscr{Q}(s,a;w)$, where $w$ represents the parameters of the network (i.e., the weights). In order to improve the learning performance, DQN introduces the experience replay memory strategy that overcomes the learning stability issues. Indeed, this strategy stores the agent’s experiences that include state transitions, actions and rewards, and then randomly samples from these experiences to perform Q-learning. As a result, the experience replay memory strategy reduces the correlation between the training samples, which prevents the optimal policy from being conducted to a local minimum. Although DQN can be effective, it still suffers from the problem of overestimating action Q-values. Double DQN (DDQN) \cite{DDQN} is proposed to mitigate this limitation and improve learning performance. The idea behind DDQN is to decouple action selection from evaluation. To achieve this, two neural networks are used, a main Q-network that selects an action and a target Q-network that calculates the Q-value of the selected action. In our DQL-based MARL algorithm, each agent $b$ has a DDQN that takes the current state as input and outputs the Q-value function of all actions. The training phase of the proposed multi-agent DDQN is given in Algorithm~\ref{alg:trainingPhase}. 
\begin{algorithm}[t]
	\caption{DQL Algorithm Training Phase}
	\label{alg:trainingPhase}
	\begin{flushleft}
		\textbf{Input:} Agents and environment\\
		\textbf{Output:} Trained DDQNs
	\end{flushleft}
	Start simulator: generate end-users and network parameters; \\
	Initialize for each agent $b$: the main DQN, the target DQN and the replay memory $\mathscr{M}_b$;
	\begin{algorithmic}[1]
        \FOR{\textit{each episode}}
            \STATE Reset and build the agents' environment;
            \FOR {\textit{each step}}
                \FOR {\textit{each agent} $b$}
                    \STATE Get observation $\mathscr{S}_b$;
                    \STATE Choose an action $\boldsymbol{a}_b$ using $\epsilon$-greedy;
                \ENDFOR
                \FOR {\textit{each agent} $b$}
                    \STATE Obtain the joint action $\boldsymbol{a}$ and receive reward $\mathscr{R}_b$;
                    \STATE Obtain the next observation $\mathscr{S}_b'$;
                    \STATE Store the experience $exp_b$\ in replay buffer $\mathscr{M}_b$;
                    \IF{\textit{batch size}}
                        \STATE Randomly sample a mini-batch from $\mathscr{M}_b$;
                        \STATE Calculate target Q-value;
                        \STATE Calculate loss between the main network and the target network;
                        \STATE Update the parameters of the main network using gradient descent to minimze loss;
                    \ENDIF
                    \IF{\textit{target step}}
                        \STATE Update the target network parameters;
                    \ENDIF
                \ENDFOR
            \ENDFOR
        \ENDFOR
    \end{algorithmic}
\end{algorithm}

In detail, the training phase requires as input the environment of each agent which includes gNodeBs, end-users, pre-allocated RBs, service requirements and channel state information. As output, it returns the trained DQN of each agent. The training starts by : (1) generating the network parameters, the end-users including their positions on the grid, the service required (i.e., eMBB or URLLC) and their packet sizes, and (2) initializing the DQN of each agent. Next, DQL iterates the episodes. At the beginning of each episode, each agent’s environment is built by updating the end-user locations and the channel coefficients (i.e., large scale fading). In each step, each agent $b$ observes the current state $\mathscr{S}_b$ of its environment and takes an action $\boldsymbol{a_b}$ from its action space $\mathscr{A}_b$ by using the $\epsilon$-greedy policy. With the $\epsilon$-greedy policy, an agent selects an action randomly or using the Q-network. Precisely, this policy chooses the action with the highest Q-value with probability $1 - \epsilon$, where the exploration rate $\epsilon$ represents the probability that an agent will explore its environment rather than exploit it. As we go forward (i.e., after each step), each agent learns more about its environment and $\epsilon$ decays by some rate, so that exploring the environment becomes less probable. Once all agents choose their action following the $\epsilon$-greedy policy, they communicate them to each other. Accordingly, each agent $b$ forms its joint action, calculates its reward $\mathscr{R}_b$ using Eq. \eqref{BSReward} and moves to a new state $\mathscr{S}_b'$. Next, the obtained tuple $(\mathscr{S}_b,\boldsymbol{a_b},\mathscr{R}_b,\mathscr{S}_b')$, called agent’s $b$ experience and denoted by $exp_b$, is stored in its replay memory $\mathscr{M}_b$. In practice, since the size of the replay memory is limited to a defined threshold $\mathcal{M}$, only the last $\mathcal{M}$ experiences can be stored. After storing enough experiences, each agent samples a random mini-batch from its replay memory. Note that the size of the replay memory should be large enough to reduce the correlation between the data that will be sampled from it. The obtained dataset is used by the agent to perform the training. With the objective of minimizing the loss function, given by Eq. \eqref{loss}, the main Q-network is used to approximate the Q-value function while the target Q-network is used to outputs the target Q-value. 

\begin{equation}\label{loss}
    L_b(w_b)= \mathbbm{E}[(y_b - \mathscr{Q}(\mathscr{S}_b,\boldsymbol{a_b};w_b))^2],
\end{equation}
where $\mathscr{Q}_b(\mathscr{S}_b,\boldsymbol{a_b};w_b)$ is the approximated Q-value function given by the main Q-network of agent $b$ with weight parameter $w_b$ and $y_b$ denotes the target Q-value and it is given as follows:
\begin{equation}\label{targetV}
    y_b= \mathscr{R}_b + \gamma\mathscr{Q}(\mathscr{S}_b,\underset{\boldsymbol{a_b}}{max} \,\{ \mathscr{Q}(\mathscr{S}_b,\boldsymbol{a_b};w_b)\};w^{-}_b),
\end{equation}
where $0 \leq \gamma \leq 1 $ is called the discount factor, $w^{-}_b$ is the weight parameter of the target Q-network. Note that the value of $y_b$ is not necessarily the largest Q-value in the target Q-network, which allows to avoid chossing an overestimated action. 

After calculating the loss function, each agent performs a gradient descent to update the parameters of the main Q-network. Finally, the parameters of the target Q-network are updated, at each fixed target step, by copying the parameters of the main Q-network.

Since the learning of the DDQNs is computationally heavy, the training phase of the DQL algorithm is performed in an offline manner. Accordingly, the training can be conducted using a large amount of dataset resulting from different network topologies and channel conditions. 
\begin{algorithm}[t]
	\caption{DQL Algorithm Implementation Phase}
	\label{alg:implementationPhase}
	\begin{flushleft}
		\textbf{Input:} The trained DDQNs\\
		\textbf{Output:} RB allocation for end-users
	\end{flushleft}
	Load the DDQN of each agent;
	\begin{algorithmic}[1]
        \FOR{\textit{each episode}}
            \STATE Reset and build the agents' environment;
            \FOR {\textit{each step}}
                \FOR {\textit{each agent} $b$}
                    \STATE Obtain observation $\mathscr{S}_b$;
                    \STATE Choose $\boldsymbol{a}_b$ that maximize the Q-function;
                \ENDFOR
                \STATE Obtain the joint action $\boldsymbol{a}$;
                \STATE Find a solution to RB allocation for end-users;
            \ENDFOR
        \ENDFOR
    \end{algorithmic}        
\end{algorithm}
\subsubsection{The implementation phase of DQL}~

After the training phase, the parameters of the main Q-networks are used to find an RB allocation solution for the end-users in the online implementation phase of the DQL algorithm. The implementation phase is presented in Algorithm~\ref{alg:implementationPhase}. This phase uses the trained DDQNs of the agents. At the beginning of each episode, it builds the environment of each agent. Then, for each step, when a new state is observed, each agent $b$ selects the action that maximizes the Q-value of current state. Once all agents have chosen their actions, each agent can form a joint action. Accordingly, an RBs allocation solution is obtained.
\subsection{Experiment scenarios and setup}
We consider an SDN-enabled RAN architecture where the gNodeBs are deployed in a square of area $1 \text{Km}^2$. The end-users are uniformly distributed across the entire coverage area where each one of them is associated to only one gNodeB. Each end-user is assumed to be either an eMBB end-user or a URLLC end-user. For the sake of simplicity, the transmission power $P_{u_b}^s$ is the same for all $ u_b \in \mathcal{U}_b$ and $ b \in \mathcal{B}$. The key parameters of the simulations are summarized in Table \ref{tab:1}. In order to select an effective Q-network model, the training phase of the DQL algorithm is performed on a laptop with an Intel Core i7-8750H processor, 16 GB of RAM and NVIDIA GeForce GTX 1070 graphic card. We create and train the DDQNs of the agents using the PyTorch framework.   To select the best hyperparameters values for training the DDQN models, extensive simulations are performed. Indeed, we tested random combinations of hyperparameters in a fine-grained set of values chosen based on common settings in the literature \cite{rw8,9177109}. In particular, each DDQN consists of two fully connected hidden layers, each with 256 neurons. Rectified linear unit (ReLU) is used as the activation function to avoid the vanishing gradient problem in backpropagation, which accelerates the learning process. The Adam optimizer is used with a learning rate of 0.001 since it is computationally efficient. During the training process, the weights of the main Q-network are copied to the weights of the target Q-network every 1000 steps to avoid overestimating the Q-values. In addition, we consider end-users with low mobility, so the channel gains between a gNodeB and an end-user remain unchanged for a certain period of time. To do so, we fix the location of the end-user for a few training episodes, which helps the learning algorithm to better acquire the dynamics of the end-users and, at the same time, stabilize the training. The other hyperparameters of DDQN are given in Table \ref{tab:2}.

\begin{table}[t]
	\centering
	\caption{Simulation parameters.}
	\label{tab:1}
	\begin{tabular}{|C{6cm}|C{2cm}|}
		\hline
		
		\textbf{Parameter} & \textbf{Value} \\ \hline
		
		\multicolumn{1}{|l|} {Number of gNodeBs} & 2 \\\hline
		\multicolumn{1}{|l|} {Total number of end-users} & 8 \\\hline
		\multicolumn{1}{|l|} {Bandwidth of an RB} & 180 KHz \\\hline
		\multicolumn{1}{|l|} {Transmit power of gNodeB, $P_{u_b}^s$} & 30 dBm \\\hline
		\multicolumn{1}{|l|} {Power of AWGN, $\sigma^2$} & -114 dBm\\\hline
		\multicolumn{1}{|l|} {Packet arriving rate per end-user, $\lambda_{u_b}^s$} & 100 pachets/s\\\hline
		\multicolumn{1}{|l|} {Packet length for an eMBB \& URLLC end-user} & 400 \& 120 bits\\\hline 
		\multicolumn{1}{|l|} {Minimum data rate for eMBB end-user, $\mathcal{R}_{min}$} & 100 kbps\\\hline
		\multicolumn{1}{|l|} {Maxim delay for URLLC end-user, $\mathcal{D}_{max}$} & 10 ms\\\hline
        
	\end{tabular}
\end{table}
\begin{table}[t]
	\centering
	\caption{Retained hyper-parameters for DDQN.}
	\label{tab:2}
	\begin{tabular}{|C{5cm}|C{3cm}|}
		\hline
		
		\textbf{Hyper-parameter} & \textbf{Value}    \\\hline
		
		\multicolumn{1}{|l|} {Learning rate} & 0.001                       \\\hline
		\multicolumn{1}{|l|} {Epsilon/$\epsilon$-greedy} & 1               \\\hline
		\multicolumn{1}{|l|} {Discount factor} & 0.996                     \\\hline
		\multicolumn{1}{|l|} {$\epsilon$-min} & 0.01                       \\\hline
		\multicolumn{1}{|l|} {Size of replay memory} & 100000              \\\hline
		\multicolumn{1}{|l|} {Size of mini-batch} & 64                     \\\hline
		\multicolumn{1}{|l|} {Target network update interval} & 1000 steps \\\hline
		\multicolumn{1}{|l|} {Loss function} &  Mean squared error         \\\hline
		\multicolumn{1}{|l|} {Optimizer} & Adam                            \\\hline 
		\multicolumn{1}{|l|} {Activation function} & ReLu                  \\\hline
        
	\end{tabular}
\end{table}

\subsection{DDQN training results}
To assess the training performance of the proposed multi-agent DRL approach, we observe the cumulative rewards per training episode and the behavior of the loss function during the training process.

Fig.~\ref{fig:3} shows the cumulative average rewards of agents per episode. From this figure, the cumulative rewards improve as the number of training episodes increases, which demonstrates the effectiveness of the proposed training algorithm. When the training episode approximatively reaches 1800, the agents gain interesting experiences and start to exploit better actions. Accordingly, the cumulative reward approaches to a maximum value, indicating that the training process converges after an acceptable number of training episodes. Note that the convergence of the DQL algorithm does not present large fluctuations which are principally due to the low-mobility of the end-users in the environment.

\begin{figure}[ht]
	\includegraphics[width=\linewidth]{Figures/fig_3}
	\caption{Training rewards.}
	\label{fig:3}
\end{figure}
Fig.~\ref{fig:4} illustrates the convergence of the loss function, Eq.~\eqref{loss}, during the training process of the DDQNs. It plots the average of the agents’ loss results versus the episodes. The loss decreases with the increase in training episodes. In the first few episodes, the loss declines gradually because various new actions were explored randomly and as learning progressed, good actions were selectively performed based on the Q-value function that had become more reliable. Consequently, after episode 2500, the loss converges to a minimum value, which demonstrates the accurate Q-value approximation.
\begin{figure}[ht]
	\includegraphics[width=\linewidth]{Figures/fig_4}
	\caption{Training loss.}
	\label{fig:4}
\end{figure}

 It is worth noting that the convergence results of the reward and loss function are obtained by assuming that the gNodeBs have perfect knowledge of the channel state information, which is used as input of the DDQN algorithm. In the case of imperfect channel state information, the convergence time of the DDQN algorithm may increase \cite{kaur2020imperfect}. Therefore, the DDQN algorithm takes more time to accurately learn the appropriate policies. But, once the offline training of the DDQN algorithm is performed, the learned policy can be applied rapidly to obtain the resource allocation solution.

\subsection{SAMA-RL performance evaluation}
 To benchmark our SAMA-RL approach, we implemented two schemes from the literature, which we called 3-SRA \cite{rw2} and 1-SRA \cite{ofdma} for three-stage resource allocation and one-stage resource allocation, respectively.  3-SRA allocates radio resources to end-users by considering two types of slices, namely the rate constrained slice (i.e., eMBB slice) and the delay constrained slice (i.e., URLLC slice). In the first stage, a central controller uses a heuristic algorithm to reserve radio resources (i.e., a fraction of the system bandwidth) to the eMBB and URLLC slices in each gNodeB. In the second stage, the reserved radio resources for each slice in each gNodeB are adjusted using a DRL algorithm. In the final stage, a heuristic algorithm is deployed to map the fraction of bandwidth assigned to a slice with the physical RBs. Accordingly, we have chosen 3-SRA since it: (i) is a competitive approach that performs the slicing operation of radio resources in a hierarchical manner, (ii) is integrated into a network architecture similar to our proposed architecture, for instance, the presence of a central controller that has a global view of the RAN, (iii) considers two types of slices, namely the eMBB slice and the URLLC slice, and (iv) is based on a DRL algorithm to solve the radio resource allocation problem in the RAN. 

 1-SRA performs the allocation of RBs to end-users in a single-stage process using a greedy heuristic algorithm. Each gNodeB uses this algorithm to assign the required RBs to its associated eMBB and URLLC end-users. This algorithm computes the received signal-to-noise ratio (SNR) of the end-users on all the available RBs of a gNodeB. Then, for each end-user, it: (1) identifies the highest SNR given by an RB, (2) calculates the spectral efficiency (SE) that corresponds to the highest SNR, (3) calculates the required number of RBs, which is defined as the ratio of the traffic queue length to the calculated SE, and (4) assigns the required RBs to it. Note that URLLC end-users are prioritized over eMBB end-users, thus the proposed algorithm schedules URLLC end-users first.  We have chosen 1-SRA as a benchmark scheme since: (i) it considers two types of slices, namely the eMBB slice and the URLLC slice, (ii) the objective function is similar to our formulated objective function, which maximizes the total sum data rates of the URLLC and eMBB end-users, and (iii) it considers a minimum data rate for the eMBB end-user and a maximum latency requirement for the URLLC end-users in the problem formulation, which is similar to our optimization problem.

 We adapt 3-SRA and 1-SRA to meet the requirements of our system model. Specifically, in 3-SRA, two gNodeBs cannot serve a single end-user under the 3-SRA algorithm. On the other hand, in 1-SRA, we calculate the achievable data rate of each RB using the Shannon rate formula instead of the modulation and coding scheme and the queue length is given by the packet size of each end-user. To fairly benchmark the performance of SAM-RL against 3-SRA and 1-SRA, most of the simulation parameters are chosen similarly to those used in \cite{rw2} and \cite{ofdma}. Note that the comparison results are averaged over 1000 trials.

\begin{figure}[ht]
	\includegraphics[width=\linewidth]{Figures/fig_5}
	\caption{Impact of the number of end-users on the objective function.}
	\label{fig:5}
\end{figure}

Fig.~\ref{fig:5} shows the performance of SAMA-RL compared to the benchmark approaches when varying the number of end-users. SAMA-RL always achieves the best performance in terms of the objective function value when the number of end-users increases. We notice, for the three approaches, that the value of the objective function, which represents the total sum data rates of the URLLC and eMBB end-users, decreases as the number of end-users increases. This is due to the increase of the competitiveness among end-users to obtain a sufficient number of RBs that guarantees their requirements. Indeed, in the case of a low number of end-users, several RBs can be assigned to one end-user to guarantee its requirements in terms of data rate and delay. On the other hand, when the number of end-users is large, each approach seeks to allocate a minimum number of RBs to each end-user in order to satisfy as many end-users as possible in terms of data rate and delay requirements. SAMA-RL maximizes the total sum data rates of the end-users better than 3-SRA since the latter assigns the RBs to the end-users according to the required data rate of the entire slice, which includes a set of end-users, instead of relying on the required data rate of each end-user individually. Therefore, it cannot efficiently allocate the required RBs to the end-users. In the 1-SRA approach, the allocation of RBs is based only on the highest estimated SNR for each end-user, which may poorly determine the RBs required to satisfy the QoS of end-users.


Fig.~\ref{fig:6} illustrates the impact of the minimum data rate threshold ($\mathcal{R}_{min}$) on the objective function Eq.~\eqref{Obj}. Based on these results, we make the following observations: (1) SAMA-RL outperforms 3-SRA and 1-SRA for all minimum data rate thresholds; (2) the higher is the minimum data rate threshold, the larger is the performance gap between SAMA-RL and both benchmark approaches. This is due to the multi-agent approach proposed in the gNodeB allocation level where a gNodeB can borrow RBs from other adjacent gNodeBs when the RBs pre-allocated by the SDN controller are insufficient. This indeed illustrates the effectiveness of the proposed multi-agent method and demonstrates its robustness.


\begin{figure}[ht]
	\includegraphics[width=\linewidth]{Figures/fig_6}
	\caption{Impact of the minimum data rate threshold ($\mathcal{R}_{min}$) on the objective function.}
	\label{fig:6}
\end{figure}

Fig.~\ref{fig:7} presents the comparison of SAMA-RL and both benchmark approaches, i.e., 3-SRA and 1-SRA, in terms of the average number of end-users whose achieved data rate is greater than or equal to the minimum data rate threshold $\mathcal{R}_{min}$. We can see that SAMA-RL always outperforms 3-SRA and 1-SRA for all minimum data rate thresholds. These results can be justified as follows: in 3-SRA, if the reserved resources for a given slice are not sufficient to provide the required service, i.e., minimum data rate threshold, the slice must wait for the next resources reservation update, while in SAMA-RL, a gNodeB can request, if necessary, some RBs from other gNodeB.  In 1-SRA, if the SNR is not appropriately estimated, the RBs allocated to end -users may not be sufficient to provide the required service, thus the end-users will be served in the next resource allocation operation.

\begin{figure}[ht]
	\includegraphics[width=\linewidth]{Figures/fig_7}
	\caption{Impact of the minimum data rate threshold ($\mathcal{R}_{min}$) on the number of end-users.}
	\label{fig:7}
\end{figure}
\begin{figure}[ht]
	\includegraphics[width=\linewidth]{Figures/fig_8}
	\caption{Impact of the the maximum delay threshold ($\mathcal{D}_{max}$) on the number of end-users.}
	\label{fig:8}
\end{figure}

 In Fig.~\ref{fig:8}, we compare the performance of SAMA-RL against the performance both benchmark approaches in terms of the average number of end-users whose delay experienced by a packet is less than or equal to the maximum delay threshold $\mathcal{D}_{max}$. Similar to the obtained results in Fig.~\ref{fig:7}, we can once again confirm that SAMA-RL gives better performance compared to 3-SRA and 1-SRA for all maximum delay thresholds.




