# [PERSON]: An HPC Job Scheduler Using Deep Reinforcement Learning and Remaining Time Prediction
## 3 RLSchert
### Five-Tuple Definition of RLSchert  
We used deep reinforcement learning to train the scheduler RLSchert, and a deep neural network represents the agent. According to the formal definition of the simulator,we modeled the scheduling process as an MDP and trained the policy based on the policy gradient. An MDP can be described by a five-tuple \((S,A,R,P,\gamma)\). The five-tuple of RLSchert is defined as follows.  
**S:** The state space defines the state of the environment visible to the scheduler. Figure 3 shows the state space of RLSchert. Specifically, the state is represented by a 2D matrix, where the horizontal dimension represents the resource and the vertical dimension represents time. The leftmost is the cluster status. Colors represent different jobs, and free resources are represented by 0. On the right is the status of \(num\_nw\) jobs in the waiting queue. Then, there is the status of the running queue. We extract features for each job as the input to the kill policy. Specifically, it contains five features, namely \(S_{1},S_{2},S_{3},S_{4},S_{5}\). The last column is the extra information, namely the arrival time of the latest job.  
**A:** The action space defines the actions that the scheduler could perform. Specifically, it contains \(num\_nw\) select actions, \(num\_kill\) kill actions, and a None action. The None action makes the simulator time move forward. The empty place in the queue is selected, which also represents the None action.  
**R:** The reward function guides the policy improvement, which is designed by the target of the scheduler. In this work, we considered two scheduler metrics: the average slowdown and completion time. The slowdown of job \(i\) is defined as \(S_{j}=(finish\_time-start\_time)/len\_real\), and the slowdown is always greater than one. The reward function for the average slowdown is defined in Equation (9), where \(Predictor(j)[curr\_time]\) represents the predicted remaining runtime of job \(j\) at the current time step. The sum of \(R_{t}\) at each time step \(t\) is equal to the sum of the slowdown. A reward function such as this is to make the reward dense and accelerate the learning of the policy.  
\[\begin{split} R_{t}=&\sum_{j\in RunningQueue}- \frac{1}{Predictor(j)[curr\_time]}+\sum_{j\in ReallyQueue}-\frac{1}{Predictor (j)[0]}\\ &+\sum_{j\in WaitingQueue}-\frac{1}{Predictor(j)[0]}+\sum_{j \in Backlog}-\frac{1}{Predictor(j)[0]}\end{split} \tag{9}\]  
Furthermore, the completion time of each job is defined as \(C_{j}=finish\_time-start\_time\). The completion time \(C_{j}\) represents the response time of job \(j\). The reward function of the  
Figure 3: The state space of RLSchert.  
completion time is defined in Equation (10). The sum of \(R_{t}\) at each time step \(t\) is equal to the sum of the completion time.  
\[R_{t}=\sum_{j\in RunningQueue}\ -\ 1+\sum_{j\in ReadyQueue}\ -\ 1+\sum_{j\in WaitingQueue}\ -\ 1+\sum_{j\in Backlog}\ -\ 1 \tag{10}\]  
**P.** The state transition function defines the next state \(S_{t+1}\)after executing action \(A_{t}\), that is \(P:S\times A\to S\). The state transition is determined by the process of the simulator, which is a function that the agent needs to learn implicitly.  
\(\gamma\)**:** This is the discount factor of the MDP. To ensure the finite value function and the convergence of the policy, the discount factor is less than or equal to one, as shown in the reward function. When the discount factor is equal to one, the cumulative reward is the slowdown or completion time. In the experiment, we set \(\gamma=0.99\), which also ensured the correct policy learning.