Deep Reinforcement Learning for Uplink Multi-Carrier Non-Orthogonal Multiple Access Resource Allocation Using Buffer State Information

In RL, an agent tries to skillfully map actions to observed system states in order to maximize a numerical reward [9]. Starting at an observed state, the agent takes an action, receives a reward and follow-up state, takes another action, et cetera. This sequential decision making can be formalized as an MDP [19, Chap. 3]. Let $S$ denote a finite set of states, $A$ a finite set of actions and $S_t\in S$, $A_t\in A$ as well as $W_t\in R$ random variables describing the state, action and reward at time $t$. Assuming the Markov property is fulfilled, the dynamics of an MDP can be fully described by the state-transition probabilities $p(S_{t+1}=s^{\prime }|S_t=s,A_t=a):S\times S\times A\to [0,1]$ with $s^{\prime },s\in S$ and $a\in A$, as well as the expected reward $w(S_t=s,A_t=a,S_{t+1}=s^{\prime }):S\times A\times S\to R$ when taking action $A_t=a$ at state $S_t=s$ with follow-up state $S_{t+1}=s^{\prime }$ [19, Sec. 3.1].
With $G_t:={\sum }_{k=0}^{\infty }{\gamma }^k{W}_{t+k+1},\gamma \in [0,1]$ as the discounted return, the cumulative reward in the long run is calculated [19, Sec. 3.3]. A policy $\pi \left(a|s\right)$ defines probabilities of taking action $A_t=a$ given state $S_t=s$ in order to maximize $G_t$ [19, Sec 3.4]. Following a policy $\pi$, the action-value function $q_{\pi }(s,a)$ denotes the expected return for choosing an action $A_t=a$ at state $S_t=s$ [19, Sec. 3.5]:

A policy $\pi$ is called an optimal policy ${\pi }^{\ast }$, if its decisions maximize the action-value function

where $q^{\ast }(s,a)$ is called the optimal action-value function [19, Sec. 3.6]. Similarly, the value function $v_{\pi }\left(s\right)$ as the expected return when in $S_t=s$ and following $\pi$ can be defined by  [19, Sec. 3.5]. The RL problem can be solved using value-based or policy-based methods. While the former try to learn $q^{\ast }(s,a)$, the latter directly optimize the policy $\pi \left(a|s\right)$ [19, Chap. 13].

The objective of Q-learning is to use temporal difference learning to learn a function $Q(s,a)$ that approximates $q^{\ast }(s,a)$ [20]. Performing action $A_t=a$ at state $S_t=s$ and observing the reward $W_{t+1}=w$ and follow-up state $S_{t+1}=s^{\prime }$ yields the tuple $(s,a,w,s^{\prime })$. The approximated Q-function $Q(s,a)$ can be updated using

with the step-size $\alpha \in [0,1]$ [20]. Using a more accurate estimate incorporating the observed reward $w$ for state-action pair $(s,a)$, $Q(s,a)$ gets updated. Q-learning converges to the optimal action-value function $q^{\ast }(s,a)$ [20]. The optimal action $A_t=a^{\ast }$ given state $S_t=s$ is chosen greedily by $a^{\ast }=\underset{a\in A}{\text{arg}\text{max}}Q(s,a)$  [20].

Instead of learning $q^{\ast }(s,a)$, policy-based methods directly optimize the policy parameters $\theta \in R^d$ of a parametrized policy ${\pi }_{\theta }:=\pi (a|s,\theta )$. With the performance measure $J\left(\theta \right):=v_{{\pi }_{\theta }}\left(s_0\right)$ as the expected return when starting at state $S_0=s_0$ and following policy ${\pi }_{\theta }$, the policy can be updated using gradient ascent [19, Chap. 13]. Following the stochastic policy gradient theorem (PGT), it can be shown that [21]

$\nabla J\left(\theta \right)$ is proportional to the expectation of the gradient of the probability choosing action $a$ given state $S_t$, weighted with its expected return $q_{\pi }(s,a)$. Hence, the computation of the performance gradient is reduced to a simple expectation [22].
Using stochastic gradient ascent, $\theta$ can be updated by

where $ϵ$ is a step-size and $\hat{q}(S_t,a)$ is a learned approximation of $q_{\pi }(s,a)$ [19, Sec. 13.2]. Hence, policy-gradient methods require an estimate of the action-value function $q_{\pi }(S_t,a)$ [22].

While policy-based methods are able to handle large or continuous action spaces, value-based methods have a lower variance in the estimates of expected returns. Actor-critic methods combine the advantages of both [23]. A parametrized actor ${\pi }_{\theta }\left(s\right)$ with parameters $\theta$ is defined. Using, e.g., Q-learning, a critic with parameters $\Phi$ estimates the action-value function $Q(s,a|\Phi )\approx q_{\pi }(s,a)$ of the actor’s policy ${\pi }_{\theta }\left(s\right)$. As depicted in Fig. 1, both the actor and the critic receive a state $S_t$. The actor chooses an action $A_t$ following ${\pi }_{\theta }\left(s\right)$. Using the reward $W_{t+1}$, the critic updates its estimator $Q(s,a|\Phi )$. Afterwards, $Q(s,a|\Phi )$ is used to update the actor according to the stochastic PGT update step [24].

Now consider a deterministic parametrized policy ${\rho }_{\theta }\left(s\right)$ with parameters $\theta$, which maps exactly one action to every state. Given its performance measure $J\left(\theta \right):=v_{{\rho }_{\theta }}\left(s_0\right)$ when starting at state $S_0=s_0$, the deterministic PGT is given by [22]

where $q_{\rho }(s,a)$ is the action-value function following policy ${\rho }_{\theta }$. Compared to the stochastic PGT, deterministic PGT updates only for the taken action $a={\rho }_{\theta }\left(S_t\right)$. Moreover, instead of $q_{\rho }(s,a)$, only its gradient $\nabla q_{\rho }(s,a)$ is taken into account, which avoids the estimation of $q_{\rho }(s,a)$ and is computationally attractive. The stochastic policy gradient converges to the deterministic policy gradient for ${\sigma }^2\to 0$, where ${\sigma }^2$ is the output variance of the stochastic policy  [22].

In [11], the DDPG algorithm, an actor-critic setup using deterministic PGT, is introduced. Since feedforward neural networks define a parametrized mapping $y=f(x,\theta )$, RL algorithms can be implemented using deep neural networks (DNNs) [19, Sec. 9.7]. However, there are two challenges when using DNNs [11]: First, most DNN optimization algorithms assume that the samples used for optimization are i.i.d.. Storing observed transitions $(s_t,a_t,s_{t+1},r_{t+1})$ in a finite replay memory and randomly sampling from it ensures learning using (approximately) independent transitions. Second, using only a single DNN for, e.g., Q-learning, updating the DNN while using it for calculating the target $Q(s^{\prime },a^{\prime })$ destabilizes learning. Using a copy of the networks, the actual network is updated and the copy, called target, is used to estimate $Q(s^{\prime },a^{\prime })$. The target network gets periodically synchronized with the updated network. The full algorithm is given by [11, Alg. 1].

While the general DRL framework introduced in Sec. III receives $S_t$, takes $A_t$ and immediately receives $W_{t+1}$ and $S_{t+1}$, the uplink MC-NOMA scenario in Alg. 1 involves two major challenges. First, the BSI and, therefore, the state $S_t$ is updated after all NOMA-resources of a PRB are allocated. Thus, multiple sequential allocation actions, allocating the NOMA-resources of a PRB, need to be taken without new state information. If, e.g., UE $k$ is allowed to use the first NOMA-resource and is able to transmit all the packets inside its buffer, allocating the second NOMA resource to UE $k$ does not make sense. However, the state containing information about the occupancy of all UEs’ buffers is not updated and still assumes that UE $k$ has packets to transmit. To combat this issue, we introduce a sequential decision making structure, shown in Fig. 2, which is inspired by [25]. The rows $x_m\in R^{(K+1)},m=\{1,\dots M\}$, of the matrix $X\in R^{M\times (K+1)}$ contain the probabilities of the $K+1$ actions to be chosen for NOMA resource $m$. So, $X=(x_1\dots x_M{)}^T$ with $x_m=(x_{m,1}\dots x_{m,K+1})$ and $x_{m,k}\in [0,1]$. We initialize $X=0$ and iteratively decide for allocation, replacing the $m^{\text{th}}$ row of $X$ with the actor output $x_m$. The updated $X$ is used to enable prediction of the changes applied to the state, e.g., which UE’s buffers may have been emptied using already allocated NOMA-capabilites. After the actor decided for $x_M$, the actions $a=(a_1\dots a_M)$ are sampled from the probability distributions provided by $x_m$.

The second issue we face in the uplink MC-NOMA scenario are sparse rewards. While the state is updated after each PRB is processed, the rewards are calculated after all PRBs are processed. Thus, $M\cdot N$ actions have been carried out. Not getting rewards immediately on single actions, but on a group of actions, prolongs training. We combat sparse rewards by introducing early termination for training. Especially at the beginning of training, the actor decides for suboptimal actions, leading to full UE buffers and, therefore, to situations without a chance for choosing beneficial actions. We assume that a sufficiently trained agent is able to avoid such ill-conditioned situations. Therefore, we terminate a training episode early if the training reward $W_{\text{train}}<W_{\text{cap}}$, where $W_{\text{cap}}\in R$ is an empirically determined value. Since the reward penalizes packets that exceeded their PDB (punishment), the reward is solely negative $W_{t+1}\le 0$ (penalty-only) and it is $W_{\text{train}}<0$. With early termination, we save computation time in ill-conditioned situations and are able to combat the prolonged training due to sparse rewards.

To avoid the actor choosing UEs with empty buffers, we introduce traffic-based masking. By defining a Boolean mask $h\in \{0,1{\}}^{(K+1)}$, indicating whether a UE has packets in its buffer or not, the probability vector $x_m$ is updated by an elementwise multiplication $x_m\leftarrow x_m\odot h$. We apply normalization to ensure that after masking $x_m$ is a probability distribution.

In [9], we introduced encoder neural networks (ENNs) for effective state space compression. The state $s_k$ of every UE $k$, containing the size and ages of packets residing in a UE’s buffer as well as the UE’s CQI $c_k$ and QI $q_k$, is compressed to a vector $s_k^{\prime }\in R^3$ using ENNs. To remedy the issue of learning a bias towards a specific UE, we randomly shuffle the order of UEs by $s\leftarrow P_{\text{rand}}s$, where $P_{\text{rand}}$ is a random permutation matrix. Figure 3 shows the setup of the actor network. The compressed and randomly permuted UE information $s_k,k\in K$, $X$ as well as $n_{\text{PRB}}\in N$, denoting the current PRB to allocate, are fed to a DNN with a softmax-function at its output layer. Using $P_{\text{rand}}^{-1}$, the order of UEs is restored and the masking is applied. To ensure exploration during training, parameter space noise [26] is applied to the weights and biases of the output layer. To avoid overfitting of the DNN, we use dropout layers.
We furthermore use age capping for handling packets that exceeded their PDB [9]. The critic’s architecture is similar in terms of input information processing, however, the DNN’s output layer only has a single neuron, since solely the expected return for executing actions $X$ given state $S_t=\{s_1,\dots s_K,n_{\text{PRB}}\}$ needs to be estimated.

We employ the environment described in Sec. II. For a small environment (SE) with $K=20$ UEs, $N=10$ PRBs and $W_{\text{cap}}=-80000$, we show the success of masking. For a large environment (LE) with $K=32$ UEs, $N=25$ PRBs and $W_{\text{cap}}=-150000$, we show the necessity of dropout layers. All setups have $L=8$ buffer slots per UE and $M=2$. The parameters of the embedding and ENNs are given by [9, Tab. I]. Depending on SE and LE, the DNN architecture differs according to Tab. I. The different agents we train and test are summarized in Tab. II. We benchmark against the NOMA uplink proportional fair channel aware (NPFCA) agent, provided by  [15]. Given the infinite set of environment realizations $S$, we choose $|S_{\text{eval}}|=4$ realizations for the evaluation and $|S_{\text{test}}|=100$ for the test set, with $S_{\text{eval}}\cap S_{\text{test}}=\varnothing$. Furthermore, $S_{\text{train}}\subset S\setminus (S_{\text{\% eval}}\cup S_{\text{test}})$ denotes the training set, where the training realizations are sampled from. During training, an environment is stopped after $t_{\text{stop}}$, either after $T_{\text{max}}=600$ time steps are executed or by early termination, i.e., $t_{\text{stop}}\le 600$ time steps. After five training episodes, the agent is evaluated. To save computing time for LE, agents are only evaluated if they achieve a training reward better than the mean reward of the benchmark agent, which is $W_{\text{eval}}=-1552$. The evaluation and tests are limited to $65536$ allocation steps, resulting in $T_{\text{max,test}}=6553$ time steps for SE and $T_{\text{max,test}}=2621$ time steps for LE.