Effective Multi-User Delay-Constrained Scheduling with
Deep Recurrent Reinforcement Learning

We consider the scheduling problem illustrated in Figure 2. Time is divided into discrete slots $t\in \{0,1,2,...\}$. At the beginning of each time slot, the scheduler first receives job arrivals, e.g., data packets in a network or parcels in a delivery station. The number of job arrivals for user $i$ at time slot $t$ is denoted as $A_i\left(t\right)$. We denote $A\left(t\right)=\left[A_1\right(t),...,A_N(t\left)\right]$. Each job for user $i$ is associated with a strict delay constraint ${\tau }_i$, i.e., a job needs to be served within ${\tau }_i$ slots upon its arrival and will be outdated and discarded otherwise.

Define the following Lagrangian function of problem (1) for handling the average resource budget $E_0$:

with respect to control policy $\pi$ and Lagrange multiplier $\lambda$. Denote $g\left(\lambda \right)$ the Lagrange dual function for fixed Lagrange multiplier $\lambda$:

where the maximizer is denoted as ${\pi }^{\ast }\left(\lambda \right)$. Using Lemma 3 in (Singh and Kumar, 2018), the optimal timely throughput $T^{\ast }$ equals the optimal value of the dual problem, i.e., $T^{\ast }={min}_{\lambda \ge 0}g\left(\lambda \right)=g\left({\lambda }^{\ast }\right)$, where ${\lambda }^{\ast }$ is the optimal Lagrange multiplier. To find the optimal policy ${\pi }^{\ast }\left({\lambda }^{\ast }\right)=\arg {max}_{\pi }L(\pi ,{\lambda }^{\ast })$, it suffices to find optimal Lagrangian multiplier ${\lambda }^{\ast }$. Denote the consumed resource under policy $\pi$ in time slot $t$ as $E_{\pi }\left(t\right)$. The Danskin’s Theorem in (Bertsekas et al., 2003) states that $g^{\prime }\left(\lambda \right)=\frac{\partial L({\pi }^{\ast },\lambda )}{\partial \lambda }=E_0-E_{{\pi }^{\ast }\left(\lambda \right)}$, where $E_{{\pi }^{\ast }\left(\lambda \right)}={lim}_{T\to \infty }\frac{1}{T}{\sum }_{t=1}^T{E}_{{\pi }^{\ast }\left(\lambda \right)}\left(t\right)$ denotes the average resource consumption. Thus, the optimal policy ${\pi }^{\ast }\left({\lambda }^{\ast }\right)$ can be obtained by recovering the dual function $g\left(\lambda \right)$ for some $\lambda$ and taking gradient descent to find the optimal ${\lambda }^{\ast }$. While the theoretical understanding is clear, finding the optimal ${\pi }^{\ast }\left(\lambda \right)$ for a given $\lambda$ in a practical system is non-trivial, due to the following main reasons:

• System dynamics are hard to trace since distributions can be highly dynamic and correlated in many scenarios.

• The system can only be partially observed, e.g., due to sensing limitation and noise and other hidden factors.

• Practical scheduling systems usually have a large number of users and complex multi-hop topology, which demand highly scalable solutions.

Prior works (Singh and Kumar, 2018; Chen and Huang, 2018) uses DP to find the maximizer ${\pi }^{\ast }\left(\lambda \right)$, which requires the prior knowledge of system dynamics and suffers from the curse-of-dimensionality in large systems, and may not directly apply to partially observable systems. These motivate us to design a DRL-based framework with POMDP formulation in Section 4.

We now specify the POMDP formulation for the scheduling problem, under which the $RSD4$ can be applied to find the optimal policy ${\pi }^{\ast }\left({\lambda }^{\ast }\right)$. Specifically, the POMDP is represented by $M=⟨S,O,A,r,P,\gamma ⟩$, where $S$ is the state space, $O$ is the observation space, $A$ is the action space, $r$ is the reward function, $P$ denotes the transition matrix, and $\gamma$ stands for the discount factor.

The system state contains the buffer information whose size is proportional to the user number. This makes learning much harder in large-scale systems, due to the need to train neural networks with more hyperparameters, which largely limits the scalability of DRL-based methods. To overcome this issue, we propose a user-level decomposition technique, such that $RSD4$ finds the optimal policy with small neural networks even under large-scale scenarios. Our user-level decomposition is different from the packet-level decomposition in (Singh and Kumar, 2018; Chen and Huang, 2018), primarily due to the fact that packet-level decomposition requires a much larger number of neural network parameters, resulting in poor performance.

Specifically, we define the user-level decomposed Lagrangian function for user $i$ as

where ${\pi }_i$ is the decomposed policy for scheduling user $i$’s jobs in the buffer. Consequently, maximizing the Lagrangian function in (2) for a fixed $\lambda$ can be accomplished by maximizing (5) for each user $i$’s sub-problem separately with ${\lambda }_i=\lambda$. Denote the optimal policy for user $i$’s sub-problem as ${\pi }_i^{\ast }\left({\lambda }_i\right)$ with multiplier ${\lambda }_i$. After solving Problem (5) for each user with a fixed ${\lambda }_i$, the optimal policy ${\pi }^{\ast }\left(\lambda \right)$ that maximizes the Lagrangian (2) can be derived by letting each user take its own optimal scheduling policy ${\pi }_i^{\ast }\left({\lambda }_i\right)$ with ${\lambda }_i=\lambda$.

We present the multi-hop setting here and describe a technique called node-level merging for reducing complexity in this case. Specifically, in multi-hop networks, each flow can traverse multiple hops and the agent needs to decide which flows to serve and how many resources to allocate at each node. Besides, each node has an average resource constraint. Take Figure 4(a) as an example. There are three flows passing through three paths respectively, i.e., $F_1=\{1\to 2\to 3\to 5\}$ with deadline ${\tau }_1$, $F_2=\{2\to 4\to 6\}$ with deadline ${\tau }_2$, and $F_3=\{2\to 3\}$ with deadline ${\tau }_3$.

The idea of node-level merging is to augment the state, observation, action, and reward in the POMDP formulation for multihop scheduling. Figure 5 shows one example with the detailed procedure below.

• State and Observation: The system state is obtained by merging buffer and channel states in different hops, as shown in Figure 5. Since jobs in a multi-hop flow differ only in node position and remaining time until expiration, we encode the system state by an aggregation of buffer states at the nodes. Besides, the buffer state at hop $j$ for flow $i$ is denoted as $B_i^{\left(j\right)}\left(t\right)=\left[B_i^{0\left(j\right)}\right(t),B_i^{2\left(j\right)}(t),...,B_i^{{\tau }_i\left(j\right)}(t\left)\right]$ where $B_i^{\tau \left(j\right)}\left(t\right)$ denotes the number of jobs for flow $i$ at hop $j$ with a remaining time of $\tau$ timeslots until expiration for $0\le \tau \le {\tau }_i$. Denote the path length flow $i$ as $h_i$. The node-level merging idea is to set the overall observation $o_t$ to be $\left[B_1^{\left(1\right)}\right(t),...,B_1^{\left(h_1\right)}(t),...,B_N^{\left(h_N\right)}(t),c(t\left)\right]$ and potentially other factors in the environment. Figure 5 shows a case when $o_t=\left[B_1^{\left(1\right)}\right(t),...,B_1^{\left(h_1\right)}(t),...,B_N^{\left(h_N\right)}(t),c(t\left)\right]$.

• Action: The action is similarly obtained by merging actions at different nodes, i.e., $a_t=\left[e_1^{\left(1\right)}\right(t),...,e_1^{\left(h_1\right)}(t),...,e_N^{\left(h_N\right)}(t\left)\right]$, where $e_i^{\left(j\right)}\left(t\right)$ represent the resource allocated to user $i$’s $j$-th node for $1\le j\le h_i$.

• Reward: The reward is set to $r_t=D\left(t\right)-{\sum }_{k=1}^M{\lambda }_k{E}^{\left(k\right)}\left(t\right)$, where ${\lambda }_k$ and $E^{\left(k\right)}\left(t\right)$ correspond to the Lagrangian multiplier and resource consumption at node $i$ for $1\le k\le M$, and $M$ is the number of nodes involved in the scheduling.

A common approach for multi-hop scheduling is to address the scheduling problem in each node separately. However, in delay-constrained multi-hop networks, scheduling each node separately cannot satisfy the hard delay constraint. Multi-agent architecture (Xu et al., 2020; Zhou et al., 2021) has been adopted for multi-hop networks but with more computation resource requirements and is hard to train. Node-level merging provides a novel way of concatenating buffers of different hops in flows together, making its training similar to that for a single-hop scheduling problem except with a higher input dimension. This avoids training multiple agents for multi-hop networks, and efficiently reduces the complexity in training. It allows $RSD4$ to perform well and outperforms other methods, even when the system scale in terms of state dimension is significantly increased in multihop networks (see Section 6.5).

$RSD4$ uses double actor-networks and double critic-networks. The architecture of critic networks in Figure 6, and actor networks are similar, with the difference being removing the action $a_t$ in the input and changing the output value $Q(s_t,a_t)$ to action $a_t$. The recurrent layers build upon Long-Short-Term-Memory (LSTM) (Hochreiter and Schmidhuber, 1997) to perform RDPG in Eq. (7), and there are two parallel branches, i.e., the fully connected branch and the LSTM branch. This architecture is firstly proposed in (Peng et al., 2018) and is effective for our scheduling problem, as validated in our experiments.

The LSTM branch is designed to strengthen the memory ability of $RSD4$ algorithm, since it allows the agent to incorporate a large amount of network measurement history into its state space to capture the long-term temporal dependencies of actual system dynamics. The LSTM layer is embedded in the second layer of the multilayer perceptron feature extractor. Consequently, our $RSD4$ algorithm can well handle various partially observable settings. The fully connected branch is designed to capture more information and improve expressiveness in the current time slot, which provides subsequent layers with more direct access to the current state without requiring information to filter through the LSTM branch. This makes $RSD4$ more sensitive to the current system state, so that abrupt changes of environmental conditions, e.g., a sudden burst of arrivals or temporal channel condition degradation, can be detected rapidly (shown in Section 6.4.3).

Below, we specify the single-hop environment based on the network in Figure 2. The multi-hop environment is constructed in a similar way and will be specified in Section 6.5.

We first present an ablation study on network architectures and important hyperparameters including policy update frequency and learning rate in this subsection. The results will guide us in our algorithm parameter setting. To keep the underlying MDP well-defined with time-invariant distributions, in the ablation study, we use simulated arrivals and channels in the environment by pre-specifying their distributions.

We compare performances of $RSD4$ with existing DRL algorithms and classical non-DRL methods. The benchmark DRL algorithms include Twin Delayed DDPG (TD3) (Fujimoto et al., 2018) and Softmax DDPG (SD3) (Pan et al., 2020), both are state-of-the-art algorithms. We apply them with Lagrangian dual to ensure average resource constraints. The non-DRL algorithms include Programming, Uniform, and Earliest Deadline First (EDF) (Elsayed and Khattab, 2006):

(i) Programming: Solve the following static constrained programming problem $P_s$ for each time slot $t$ with resource constraint using convex programming (Shen and Yu, 2018) (time index $t$ omitted):

The optimal value $T_{static}^{\ast }$ for $P_s$ serves as the static optimal throughput for the Problem $P$ in Eq. (1).

(ii) Uniform: Assign resources to different packets uniformly.

(iii) Earliest Deadline First (EDF): Assign all resources to packets in each user’s queue with the shortest deadline equally.

To also evaluate the case when the resource expenditure at each time may be strictly bounded, we consider the hard resource constraint $E_{max}$ for each time slot, i.e., scheduling decisions in each time slot cannot exceed $E_{max}$. We introduce two ways to ensure this. The first way is to scale each component equally of $RSD4$’s decision to ensure the total expenditure is bounded by $E_{max}$ (denoted as $RSD4$-$E_{max}$-1). The second way is to allocate resources to packets with smaller remaining time until the total expenditure is $E_{max}$ and set all other allocations to zero (denoted as $RSD4$-$E_{max}$-2).

The comparison of $RSD4$ with other algorithms is shown in Figure 11 with $0\le E_0\le 10$, where arrivals and channel conditions are set according to real datasets summarized in Table 1. Here the channels are assumed to be unobservable to the scheduler. This scenario simulates a multi-user resource-constrained wireless base-station providing delay-constrained scheduling services. We find that performances of $RSD4$-$E_{max}$-1 and $RSD4$-$E_{max}$-2 are quite similar to $RSD4$ when setting $E_{max}=2E_0$ in each group of experiments, which means that hard resource constraint can be achieved with our methods without much performance degradation. Besides, from Figure 11(a), we see that $RSD4$ outperforms all benchmarks in each resource limit. In the small-medium resource regime with $0\le E_0\le 7$, the static optimality obtained by Programming ranks only lower than $RSD4$. However, in the large resource regime with $8\le E_0\le 10$, $RSD4$ and TD3 outperform classical methods significantly. From Figure 11(b), we see that all DRL algorithms satisfy the average resource limit, while EDF fails to fully utilize available resources since packets with the shortest deadline are too few to consume all available resources. Results in Figure 11 illustrate the superiority of $RSD4$ over the benchmarks.

We compare the performance of $RSD4$ with other DRL algorithms to further validate the effectiveness of its recurrent module. Our comparison focuses on maximizing the Lagrangian function in Eq. (2) with the same environment of Section 6.3, which is essentially equivalent to the task of throughput maximization. In fact, each average resource limit $E_0$ corresponds to an optimal ${\lambda }^{\ast }$ according to Section 3.2. Thus, maxmizing the Lagrangian function on some $\lambda$ is equivalent to throughput maximization under some average resource limit of $E_0\left(\lambda \right)$ determined by $\lambda$. Thus, focusing on maximizing the Lagrangian function in Eq. (2) allows us to examine a wide range of problems parameterized by $\lambda$.

We now turn to investigate the scalability of the algorithm by conducting experiments in systems with a large number of users and with multi-hop structures. We focus on the setting where the channel states are assumed to be unobservable. We will show that the user-level decomposition and node-level techniques in $RSD4$ make it a highly scalable solution.