# Interpretable Modeling of Deep Reinforcement Learning Driven Scheduling

Boyang Li  Department of Computer Science
Illinois Institute of Technology
Chicago, USA
<EMAIL_ADDRESS>Zhiling Lan  Department of Computer Science
University of Illinois Chicago
Chicago, USA
<EMAIL_ADDRESS>Michael E. Papka  Argonne National Laboratory
University of Illinois Chicago
Lemont, USA
<EMAIL_ADDRESS>
###### Abstract

In the field of high-performance computing (HPC), there has been recent
exploration into the use of deep reinforcement learning for cluster scheduling
(DRL scheduling), which has demonstrated promising outcomes. However, a
significant challenge arises from the lack of interpretability in deep neural
networks (DNN), rendering them as black-box models to system managers. This
lack of model interpretability hinders the practical deployment of DRL
scheduling. In this work, we present a framework called IRL (Interpretable
Reinforcement Learning) to address the issue of interpretability of DRL
scheduling. The core idea is to interpret DNN (i.e., the DRL policy) as a
decision tree by utilizing imitation learning. Unlike DNN, decision tree
models are non-parametric and easily comprehensible to humans. To extract an
effective and efficient decision tree, IRL incorporates the Dataset
Aggregation (DAgger) algorithm and introduces the notion of critical state to
prune the derived decision tree. Through trace-based experiments, we
demonstrate that IRL is capable of converting a black-box DNN policy into an
interpretable rule-based decision tree while maintaining comparable scheduling
performance. Additionally, IRL can contribute to the setting of rewards in DRL
scheduling.

###### Index Terms:

cluster scheduling; deep reinforcement learning; high-performance computing;
interpretation; decision tree

##  I Introduction

Cluster scheduling, also known as batch scheduling, is pivotal to high-
performance computing (HPC). It is responsible for determining the order in
which jobs are executed on an HPC system. Heuristics play a significant role
in cluster scheduling, with the first-come, first-served (FCFS) policy being a
widely employed scheduling approach on production systems [1]. To improve
system utilization, backfilling is commonly used in cluster scheduling to
enhance system utilization, which allows subsequent jobs to be moved ahead to
utilize available resources [1].

Reinforcement learning, a subfield of machine learning, focuses on the
automatic learning of decision-making strategies to maximize cumulative
rewards through interactions with the environment[2]. Deep reinforcement
learning (DRL), which combines reinforcement learning with deep neural
networks, has been employed for cluster scheduling [3, 4, 5, 6], demonstrating
promising results. Unfortunately, very few, if any, of these approaches have
been deployed on real-world production systems. One key hurdle is _the lack of
model interpretability_. The superior performance of DRL scheduling stems from
its deep neural network (DNN) [7]; however, DNN appears as a black-box to
system managers [8], making it challenging to comprehend, debug, deploy, and
adjust in practice. As a result, system managers have reservations about using
DRL scheduling on production systems. Therefore, it is essential to develop
interpretable models that facilitate the practical deployment of DRL
scheduling.

Many techniques have been developed to understand the behaviors of DNNs;
however, there are two issues when applying these techniques to interpret DRL
scheduling. First, existing techniques predominantly focus on monitoring
neuron activations to identify the features that trigger them [9].
Consequently, system managers still need to possess knowledge of machine
learning. Second, the current DNN interpretation methods are primarily
designed for well-structured vector inputs such as images [10, 11] and
sentences [12, 13], which are not applicable to the cluster scheduling
problem. We believe there is a pressing need to provide a simple,
deterministic, and easily understandable model for interpreting DRL
scheduling.

Decision tree is non-parametric, and easy for humans to understand. However,
training a decision tree in the context of DRL poses significant
challenges[14]. While some studies have attempted to train some decision tree
policies for reinforcement learning [15], subsequent work pointed out that
these approaches struggled with relatively simple problems such as cart-pole
[14]. Other efforts have sought to convert the DNNs employed in DRL to
decision trees [14, 16]. This conversion is built upon a teacher-student
training process, where the DNN policy serves as the teacher, generating
input-output samples to construct a student decision tree for classification
or regression. Compared to directly training decision tree policies for
reinforcement learning, these converted decision trees can achieve better
performance and handle more complex problems [14, 16].

In this work, we present IRL, an Interpretable modeling for deep Reinforcement
Learning scheduling. IRL is based on imitation learning [17]. In simple terms,
a decision tree is trained to mimic the DRL agent (i.e., deep neural network).
Specifically, once a DRL agent (deep neural network) is built for cluster
scheduling, this agent is used to generate input-output samples. These samples
are used to train a decision tree policy. However, we observe that the
decision tree obtained through this straightforward conversion process does
not closely resemble the original DRL agent as expected.

To overcome this issue, we employ the DAgger algorithm [18] to improve the
scheduling performance of the decision tree. Furthermore, we have found that
existing conversion algorithms[19] tend to produce a large decision tree with
an excessive number of branches, which will greatly impact the effectiveness
of the decision tree for decision making. To reduce the size of the decision
tree, we introduce the concept of critical state in the scheduling
environment. A critical state is defined as a system state that has a
nontrivial impact on scheduling performance. By utilizing the critical state,
we can decrease the size of the decision tree while still maintaining
effectiveness. Specifically, we make three major contributions in this work:

  * •

We present IRL, an interpretable modeling for DRL scheduling. IRL converts a
black-box DRL policy to an easy-to-understand decision tree policy, thereby
overcoming the lack of interpretability issue of DRL scheduling.

  * •

We showcase how the interpretability of IRL can assist in the design of DRL
scheduling, such as reward setting.

  * •

Our trace-based experiments demonstrate the decision tree derived from IRL
achieves comparable scheduling performance to the original DRL scheduling. In
contrast to the black-box deep neural network, the decision tree is
straightforward to comprehend, debug, and modify.

##  II Background

###  II-A Cluster Scheduling in HPC

A cluster scheduler is responsible for allocating resources and for
determining the order in which jobs are executed on an HPC system. When
submitting a job, a user is required to provide two pieces of information: the
number of compute nodes required for the job (i.e., job size) and job runtime
estimate (i.e., walltime). The scheduler determines when and where to execute
the job. The jobs are stored and sorted in the waiting queue based on a site’s
policy. The scheduler determines when and where to execute the jobs [20]. Once
a new job is submitted, the job scheduler sorts all the jobs in the waiting
queue based on a job prioritizing policy. A number of popular job prioritizing
policies have been proposed, and one of the widely used policies is FCFS [1],
which sorts jobs in the order of job arrivals.

In addition, backfilling is a commonly used approach to enhance job scheduling
by improving system utilization, where subsequent jobs are moved ahead to
utilize free resources. A widely used strategy is EASY backfilling which
allows short jobs to skip ahead under the condition that they do not delay the
job at the head of the queue [1].

While cluster scheduling is an active area of research in both HPC and cloud
computing, these two communities target different workloads, resulting in
divergent research approaches. In data centers such as those at Google or
Microsoft, typical workloads include long-running services and directed
acyclic graph (DAG) jobs. Each job comprises multiple tasks, and the resource
requirements for these tasks are often adjustable (i.e., malleability). In
this context, the smallest scheduling unit is typically a task. In contrast,
HPC is characterized by tightly-coupled parallel jobs (i.e., rigidity). Here,
the scheduling unit is usually an entire job.

TABLE I: Comparison of heuristics, DRL scheduling, and IRL (Interpretable Reinforcement Learning). Features Methods |  Heuristics [1] |  DRL scheduling [6, 4, 3] |  IRL
---|---|---|---
Not black-box | $\sqrt{}$ | $\times$ | $\sqrt{}$
Easy to comprehend | $\sqrt{}$ | $\times$ | $\sqrt{}$
Superior scheduling performance | $\times$ | $\sqrt{}$ | $\sqrt{}$
Rapid decision making | $\sqrt{}$ | $\times$ | $\sqrt{}$

###  II-B Deep Reinforcement Learning Scheduling

Figure 1: The interaction between environment and an agent in reinforcement
learning.

Reinforcement learning is an area of machine learning that is primarily
focused on dynamic decision making where an intelligent agent takes actions in
an environment with the goal of maximizing some reward [2]. The recent
advancement of reinforcement learning enhanced with deep neural networks has
yielded a number of promising performances for cluster scheduling [3, 4, 5,
6]. In DRL driven scheduling, the agent is trained to learn a proper
scheduling policy according to a specific scheduling objective (e.g., reward)
provided by system managers. Once trained, the agent can automatically
interact with the scheduling environment and dynamically adjust its policy as
workload changes. Since the state space is typically enormous, memorizing all
states becomes infeasible. DRL driven scheduling uses a deep neural network
for approximation [21]. Figure 1 shows an overview of typical DRL driven
scheduling. At each step, state is observed and fed to the scheduling agent.
The agent provides job selection and receives the reward as the feedback.

###  II-C Related Work

Interpreting deep neural networks is an active topic in the machine learning
area [10, 12, 22, 23]. The interpretation methods can be broadly classified
into two categories [24]. One is _local methods_ , such as LIME [25]. These
methods focus on explaining the prediction of a single instance in the
dataset. The other is _global methods_ [26], which aim to explain the average
behavior of a machine learning model. In this work, we adopt global methods
because our objective is to interpret the average behavior of a DRL-driven
scheduling model.

Many global interpretability approaches focus on understanding the mechanism
of DNNs, such as convolutional neural networks (CNN) [10, 12] and recurrent
neural networks (RNN) [22, 23]. These approaches still require the system
manager to have knowledge of machine learning, which is not the goal of IRL.
In addition, these approaches are designed for well-structured inputs such as
images and sentences, and thus are not suitable for deep reinforcement
learning driven scheduling problems.

Another way to achieve interpretability is to use only a subset of algorithms
that create interpretable models. A decision tree is a commonly used
interpretable model [27]. A decision tree is a decision-support hierarchical
model that uses a tree-like model of decisions and their possible
consequences. It can represent a complex policy. However, the main hurdle is
that the decision tree is hard to train directly in reinforcement learning
problems. There have been work training decision tree policies for
reinforcement learning [15], but the following research pointed out that this
method could not even achieve satisfactory performance in a not complicated
reinforcement learning problem such as cart-pole [14]. To overcome this
obstacle, some researchers refer to the idea of imitation learning to convert
the DNN to a decision tree [16, 14]. The conversion is built on top of a
teacher-student training process, where the DNN policy acts as the teacher and
generates input-output samples to construct the student decision tree.
Compared to directly training decision tree policies for reinforcement
learning, the converted decision tree achieves better performance in many
reinforcement learning problems [16, 14].

Interpreting DNNs to decision trees has shown promising results in many areas
[28, 29, 30]. Meng et al. presented Metis to interpret deep learning based
networking systems based on decision trees and hypergraphs [28]. Hu et al.
demonstrated the decision tree converted from DRL achieved satisfactory
performance in learning adaptive bitrate (ABR) algorithms [29]. Schmidt et al.
applied the conversion from DNN to the decision tree in autonomous driving
[30]. However, there is no effort made to interpret the DNNs in DRL driven
scheduling in HPC. _To the best of our knowledge, IRL is the first attempt to
interpret DRL scheduling in HPC_. Table I summarizes the key features of
heuristics, DRL scheduling, and the proposed IRL — interpretable reinforcement
learning scheduling.

Figure 2: Overview of IRL design. A cylinder represents a data repository
$\mathcal{D}$. A rounded rectangle denotes a scheduling policy, which is
either DRL or a decision tree. A rectangle represents a datatset. It is
sampled from $\mathcal{D}$, or produced by a scheduling policy (decision tree
or DRL).

##  III IRL Design

IRL, shown in Figure 2, is developed to provide an interpretable model for
general DRL scheduling in HPC. The design of IRL is based on imitation
learning, where the DNN policy of the DRL agent acts as the teacher and
generates input-output samples to construct the student decision tree.
Specifically, a trained deep neural network is obtained by training a workload
trace. This neural network acts as the teacher and generate input-output
samples from the original training workload trace. These generated input-
output samples are used as the training dataset to train an interpretable
decision tree.

There are two issues in the above process: (1) the derived decision tree might
not resemble the original deep neural network very well, and (2) the size of
the decision tree could be huge. To overcome these obstacles, we employ two
techniques. We integrate the DAgger algorithm [18] to address the former
issue, and then introduce the critical state concept for the latter one.

The details are described in the subsequent subsections. In order to make the
description of our method more straightforward, we use deep Q-network (DQN) as
an illustrative example. In Section III-A, we describe DQN driven scheduling.
In Section III-B, we present the conversion from the DQN policy to the
decision tree policy. We describe the generation of the input-output sample
datatset by DQN, and the generation of the decision tree with the sample
dataset. We also describe how to integrate DAgger in our design to improve the
scheduling performance of the decision tree, and how to reduce the size of the
decision tree via the concept of critical state.

###  III-A DQN Scheduling

Recent studies have employed various deep reinforcement learning (DRL) methods
for cluster scheduling [5, 6]. Regardless of the specific DRL method employed,
the underlying principle remains consistent. In this study, we utilize DQN
[21] as a practical example. The scheduling system, driven by a DRL agent,
follows the approach outlined in [6]. The DRL scheduling agent aims to
optimize scheduling performance by making decisions on when and which jobs in
the waiting queue should be allocated to available computer resources. At each
scheduling instance, the agent encodes both job and system information into a
vector, which is fed as an input to the neural network. Based on the neural
network’s output, the agent selects jobs from the wait queue and then receives
a reward signal from the scheduling environment.

In DQN, the deep neural network is utilized to approximate Q-value as
$Q(s_{k},a_{k})$ (i.e., the expected cumulative reward of taking an action
$a_{k}$ in the state of $s_{k}$). DQN processes one job at a time and produces
the expected Q-value for this job. The input of DQN is a 1-D vector containing
job size (i.e., number of nodes requested), job length (i.e., estimated job
runtime), and system utilization. The output is a single neuron corresponding
to the expected Q-value of the job. The scheduler enforces a window of jobs at
the front of the job wait queue. The window alleviates the job starvation
problem by providing higher priorities to older jobs.

In order to explore various actions, during the training, the agent follows
the $\epsilon$-greedy policy (i.e., the agent randomly chooses a job instead
of the job with the highest Q-value with probability $\epsilon$). During the
testing or inference time, the agent selects the job with the highest Q-value.

###  III-B Decision Tree Conversion

Decision tree is a supervised learning method commonly used for classification
or regression. In this work, we use decision tree for regression.
Specifically, in order to interpret the DQN policy, our IRL works as follows.
The input of the decision tree is the state, and the output of the decision
tree is the imitated output (Q-value) of DQN. The DQN scheduling agent replays
the workload trace to produce a trajectory of (state, Q-value) pairs. This
trajectory will be used as the training dataset $\mathcal{D}$ of the decision
tree so that the output of the decision tree will approximate the output of
the DQN.

The process of extracting an effective and efficient decision tree to
interpret the DQN policy presents several challenges. Firstly, we observed
that the decision tree trained once may not resemble the DQN policy well. When
replaying the same workload trace, the decision tree agent may choose a
different job from the DQN agent, since the imitated Q-value by the decision
tree is unlikely to precisely match the Q-value output by DQN. Consequently,
due to the varying job selection, the decision tree is prone to jump to a
state which it has never seen in the training dataset $\mathcal{D}$, and
behaves unpredictably in these unseen states.

To address this issue, we incorporate DAgger [18] into the decision tree
conversion. DAgger is an iterative training algorithm. Instead of training the
decision tree one time, we train it multiple times. After each training
iteration, the newly generated decision tree is used to replay the workload
trace and demonstrate its policy to the DQN agent. As a result, a new
trajectory of (state, Q-value) pairs following the newly generated decision
tree policy is produced, denoted as $\mathcal{D}_{i}$. This new trajectory may
contain unseen states in the training dataset $\mathcal{D}$. As a teacher, the
DQN agent assigns the Q-values to the states in this new trajectory, and
aggregate this newly produced trajectory $\mathcal{D^{\prime}}_{i}$ into the
training dataset $\mathcal{D}$. The updated dataset $\mathcal{D}$ is then used
to train the decision tree in the next iteration. This process repeats
multiple times until the maximum iteration is reached. In this work, the
maximum iteration is set to 5. The middle part of Figure 2 illustrates the
iterative process of generating the decision tree.

Next, another challenge of the decision tree conversion is that the generated
decision tree with DAgger is normally huge[14]. The cost of decision time is
proportional to the size of the decision tree. Hence a smaller-sized decision
tree without sacrificing scheduling performance is desired. To overcome the
issue, IRL introduces the concept of _critical state_ with the goal of
generating a reduced-sized decision tree.

Our design is based on a key observation, that is, when the system is
relatively idle (i.e., few jobs are in the waiting queue), the job selection
has less impact on the scheduling performance. There are two reasons. First,
the range of job selection is limited when there are a few jobs in the waiting
queue. For instance, when there is only one job in the waiting queue, this job
is selected anyway. Similarly, if the available resources can accommodate only
one job, it is chosen among all the waiting jobs. Second, even if a job is not
selected at this scheduling instance, it is likely to be scheduled shortly
thereafter.

In the design of IRL, we define critical state as the system state when the
number of jobs in the waiting queue is greater than a threshold, and non-
critical state as the state when the number of jobs in the waiting queue is
less than or equal to the threshold. The threshold should be chosen based on
the workload to balance the tree size and the scheduling performance. Only
samples with critical states ($\mathcal{D}_{critical}$) in the dataset
$\mathcal{D}$ are used to generate the decision tree. Put together, Algorithm
1 shows the complete pseudo code of the IRL method.

Algorithm 1 IRL algorithm

1:Initialize DataSet $\mathcal{D}$ $\leftarrow$ Trajectory (state, Q-value)
generated by DQN via workload trace replay

2:for i = 1 to N do

3: $\mathcal{D}_{critical}$ $\leftarrow$ $\mathcal{D}$ in critical states

4: Train decision tree $DT_{i}$ from $\mathcal{D}_{critical}$

5: DataSet $\mathcal{D}_{i}$ $\leftarrow$ Trajectory generated by $DT_{i}$ via
workload trace replay

6: $\mathcal{D^{\prime}}_{i}$ $\leftarrow$ Q-values are assigned by DQN for
the states in $\mathcal{D}_{i}$

7: $\mathcal{D}$ $\leftarrow$ $\mathcal{D}$ $\cup$ $\mathcal{D^{\prime}}_{i}$

8:end for

##  IV Evaluation

We have implemented IRL using TensorFlow [31]. Our deployment of IRL involves
integrating it with the discrete-event driven scheduling simulator CQSim [32].
To thoroughly evaluate the performance of IRL, we conduct extensive trace-
based simulations using actual workload traces.

In this section, we describe our evaluation methodology, and the experimental
results are listed in the next section.

###  IV-A Workload Traces

In our evaluation, two real workload traces are used [33, 34]. Table II
summarizes the two workload traces. For each trace, 10,000 jobs are employed
for training to build both the DQN policy and the decision tree. The
convergence of the DQN policy is confirmed by assessing its convergence rate.
Subsequently, an additional set of 2,500 unseen jobs is utilized for inference
testing.

###  IV-B Comparison Methods

We compare IRL with the following three methods.

  * •

FCFS represents first come first served method, which is the default
scheduling policy deployed on many production supercomputers [1]. FCFS
prioritizes jobs based on their arrival times.

  * •

DQN denotes the reinforcement learning scheduling policy [6]. It acts as the
teacher to construct the decision tree policy.

  * •

DAgger represents a generated decision tree policy without the introduction of
critical state.

In addition, backfilling is adopted in each of these methods to mitigate
resource fragmentation [1]. FCFS comes with EASY Backfilling [1]. In DQN and
IRL, the backfilled job is selected by the agent.

###  IV-C Experiment Setup

When training the DQN agent, the reward is set to $\sum_{j\in
J}-\frac{1}{t_{j}}$ [3], where $J$ is the set of jobs currently in the system,
$t_{j}$ is the (ideal) running time of the job. This reward function aims to
minimize the average job slowdown. The window size of the waiting queue is set
to 20. $\epsilon$ is set to 1.0 at the beginning of the training and decays at
the rate of $\alpha$ = 0.995. The input layer contains three neurons, and
three fully-connected hidden layers activated by rectified linear units (ReLU)
[35] with 32, 16, 8 neurons are used separately. The output layer contains one
neuron.

In our experiments, we set the critical state threshold to three, meaning a
critical state is defined when the number of jobs in the waiting queue is more
than three. Our sensitivity study indicates that for these workloads, this
configuration can balance the tree size and its performance. Scikit-learn
library is used to generate the decision tree [36].

###  IV-D Evaluation Metrics

Following the common practice[37], we use the following metrics to evaluate
different scheduling methods.

  1. 1.

_Average job wait time_ : the average interval between job submission to job
start time.

  2. 2.

_Average job slowdown_ : the average ratio of job response time (job runtime
plus wait time) to the actual runtime, representing the responsiveness of a
system.

TABLE II: Workload Traces Workload | Site | System Size | Period
---|---|---|---
SP2 | SDSC | 128 | April, 1998-April, 2000
DataStar | SDSC | 1,664 | March, 2004-April, 2005

##  V Results

In this section, we present the experimental results. Our analysis centers
upon four questions:

  1. 1.

What can IRL contribute to DRL driven scheduling? (Section V-A.)

  2. 2.

Does the decision tree obtained through IRL exhibit comparable scheduling
performance to DRL scheduling? (Section V-B)

  3. 3.

Does the use of critical state reduce the size of the decision tree? (Section
V-C)

  4. 4.

Does IRL introduce less runtime overhead than DRL scheduling? (Section V-D)

###  V-A Reward Setting

Neural networks used in DRL function as black-box models. However, since the
decision tree obtained through IRL imitates DRL, we can indirectly understand
the DRL scheduling policy by examining the resulting decision tree.

In order to illustrate the use of IRL, we conduct a case study to demonstrate
the contribution of IRL to DRL scheduling in terms of reward setting.
Specifically, we utilize the SP2 workload as our experimental scenario. Within
this case study, we explore two different reward settings: one that aligns
with our scheduling objective, and the other that fails to do so. Through this
use case, we showcase the interpretability of IRL in identifying key features
that significantly influence the decision-making process of the DRL agent.
Furthermore, IRL enables us to explain the rationale behind whether a
particular reward setting can achieve the scheduling objective or not.

In this case study, the objective of the DQN agent is to minimize the average
job slowdown. Two reward settings are used: (1) _Reward A_ — the reward is set
to $\sum_{j\in J}-\frac{1}{t_{j}}$ [3], and (2) _Reward I_ — the reward is set
to $\sum_{j\in J}-\frac{(w_{j}+t_{j})}{t_{j}}$, where $J$ is the set of jobs
currently in the system, $t_{j}$ is the (ideal) running time of the job, and
$w_{j}$ is the waiting time of the job. Reward I appears reasonable since it
aims to maximize the negative values of all the jobs’ slowdown in the system,
and our objective is to minimize the average job slowdown. Since job waiting
time is in the reward, we also add job waiting time in the input feature.

Figure 3: Decision tree (depth=10) generated by IRL from the DQN agent with
_Reward I_. Only the first two depths are presented in the figure due to the
space limitation. Note that the decision tree’s branches primarily revolve
around job wait time for decision-making.

Figure 3 shows the decision tree generated by IRL from this DQN agent using
_Reward I_. The depth of the decision tree is set to ten, and only the first
two depths are presented due to space limitation. It can be observed that this
decision tree primarily bases its decisions on job waiting time. Further
analysis reveals that this decision tree favors jobs with longer wait times,
and its approach closely aligns with FCFS. The underlying reason is that if we
want to maximize $\sum_{j\in J}-\frac{(w_{j}+t_{j})}{t_{j}}$, the DQN agent is
trained to select (remove) the job with the minimum value of
$-\frac{(w_{j}+t_{j})}{t_{j}}$. A longer wait time leads to a smaller value of
$-\frac{(w_{j}+t_{j})}{t_{j}}$. In the end, the DQN is trained to prefer early
coming jobs. If the scheduling objective is to minimize average slowdown, each
scheduling decision is supposed to consider the future job wait time instead
of the past job wait time. Therefore, the past job wait time should not be a
factor in either the reward or input feature.

Figure 4 shows the decision tree generated by IRL from the DQN agent using
_Reward A_. It can be observed that this decision tree primarily bases its
decisions on the job length (the requested running time). Further analysis
finds that the decision tree prefers to select short jobs. Indeed, according
to the definition of job slowdown, the scheduling objective of minimizing
average job slowdown tends to allow shorter jobs to wait less time. This
demonstrates that the interpreted DQN policy indicates that the reward setting
– _Reward A_ in the DQN is appropriate.

Figure 5 shows the DQN scheduling performance under different reward settings.
Appropriate reward setting (Reward A) can reduce the average job wait time and
slowdown by up to 66% compared to inappropriate reward setting. This study
clearly illustrates that IRL contributes to analyzing reward settings in DRL
driven scheduling.

Figure 4: Decision tree (depth=10) generated by IRL from the DQN agent with
_Reward A_. Only the first two depths are presented in the figure due to the
space limitation. Note that the decision tree’s branches mainly revolve around
requested running time for decision-making.

(a) Average job wait time (b) Average job slowdown

Figure 5:  Comparison of scheduling performance with DQN under different
reward settings.

(a) Average job wait time (b) Average job slowdown

Figure 6: Scheduling performance on SP2 workload trace. The tree depth is set
to 8, 10, 12 separately in IRL and DAgger.

(a) Average job wait time (b) Average job slowdown

Figure 7: Scheduling performance on DataStar workload trace. The tree depth is
set to 8, 10, 12 separately in IRL and DAgger.

###  V-B Scheduling Performance

Figure 6 and Figure 7 compare different scheduling methods under SP2 and
DataStar workloads in terms of average job slowdown and average job wait time.
Different tree depths are used in IRL and DAgger to observe the impact of the
tree depth on the scheduling performance.

We observe that IRL yields much better scheduling performance than FCFS. On
SP2, IRL can reduce average job wait time and average job slowdown by up to
70% compared to FCFS. On DataStar, the average job wait time and slowdown can
be shortened by up to 36% in comparison with FCFS. In addition, we notice that
IRL achieves comparable scheduling performance in contrast to DQN. On SP2,
when the tree depth is 10 or 12, the increase in average job wait time and
slowdown of IRL is within 3% compared to DQN. On DataStar, when the tree depth
is 10 or 12, the increase in average job wait time and slowdown of IRL
compared to DQN remains within 5%.

We also compare the performance between IRL and DAgger to examine the impact
of critical state on the scheduling performance. On SP2, when the tree depth
is 10 or 12, the scheduling performance loss between IRL and DAgger is within
1%. On DataStar, when the tree depth is 10 or 12, the increase in average job
wait time and slowdown remains within 2%. This suggests that the introduction
of critical state causes negligible performance loss.

###  V-C Tree Reduction

(a) SP2 (b) DataStar

Figure 8: Comparison of tree size generated by IRL and DAgger.

The time cost of making decisions with the decision tree is proportional to
the size of the tree. Thus, it is preferable to have a decision tree that is
compact in size. In this subsection, we analyze the impact of introducing
critical state on the size of the tree.

Figure 8 compares the sizes of the decision tree generated by IRL and DAgger.
On the SP2 workload, IRL reduces the tree size by up to 34% compared to
DAgger. On the DataStar workload, IRL delivers a reduction of up to 48% in
tree size. The reduction of tree size on the DataStar workload is larger than
that on the SP2 workload. We attribute this to the relative idleness of the
DataStar system compared to the SP2 system. As demonstrated in Figure 6 and
Figure 7, the average job wait time of the DataStar workload is significantly
less than that of the SP2 workload. Consequently, with the introduction of
critical state, IRL stands to benefit more in terms of tree size reduction.

###  V-D Runtime Overhead

In our experiments, with the tree depth set to 10, IRL takes approximately
0.0003 seconds for each job selection, whereas DQN requires around 0.02
seconds. Hence, IRL introduces significantly less overhead compared to DQN.
All the experiments were conducted on a personal computer configured with an
Intel 2 GHz quad-core CPU and 16 GB memory.

##  VI Conclusions

While DRL driven scheduling exhibits impressive performance compared to
heuristic and optimization methods, there are significant limitations that
hinder its practical deployment, particularly the lack of model
interpretability. The superior performance of DRL driven scheduling stems from
the neural network employed in the design; however, the neural network appears
as a black box model to system managers as it is incomprehensible to debug,
deploy, and adjust in practice.

In this work, we have presented IRL, an interpretable model for DRL driven
scheduling. IRL converts the black-box neural network employed in DRL driven
scheduling to an interpretable decision tree model, which not only can
represent a complex decision policy, but also is easy for humans to
understand. The design of IRL poses several technical challenges. In this
work, we have described the detailed strategies for the design of IRL.
Moreover, we have shown the use of IRL via several case studies. Specifically,
one case study demonstrates how IRL can contribute to the DRL scheduling
design (e.g., reward setting), and another case study shows that IRL can
deliver comparable scheduling performance as compared to the existing
scheduling methods including the widely used heuristic method and the DRL
scheduling method.

While this study focuses on DQN, IRL can be applied to other DRL methods as
well. As part of our future work, we will investigate other interpretable
models such as the regression model to IRL. To the best of our knowledge, this
study represents the first exploration of interpretable reinforcement learning
scheduling for HPC. We hope this work will pave the way for further
investigations in the field of interpretable reinforcement learning scheduling
for HPC.

## Acknowledgment

This work is supported in part by US National Science Foundation grants
CCF-2109316, CCF-2119294, and U.S. Department of Energy, Office of Science,
under contract DE-AC02-06CH11357.

## References

  * [1] A. W. Mu’alem and D. G. Feitelson, “Utilization, predictability, workloads, and user runtime estimates in scheduling the IBM SP2 with backfilling,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 12, no. 6, pp. 529–543, 2001.
  * [2] R. S. Sutton and A. G. Barto, _Reinforcement learning: An introduction_. MIT press, 2018.
  * [3] H. Mao, M. Alizadeh, I. Menache, and S. Kandula, “Resource management with deep reinforcement learning,” in _Proceedings of the 15th ACM workshop on hot topics in networks_ , 2016, pp. 50–56.
  * [4] B. Li, Y. Fan, M. E. Papka, and Z. Lan, “Encoding for reinforcement learning driven scheduling,” in _Workshop on Job Scheduling Strategies for Parallel Processing_. Springer, 2022, pp. 68–87.
  * [5] H. Mao, M. Schwarzkopf, S. B. Venkatakrishnan, Z. Meng, and M. Alizadeh, “Learning scheduling algorithms for data processing clusters,” in _Proceedings of the ACM Special Interest Group on Data Communication_ , 2019, pp. 270–288.
  * [6] Y. Fan, B. Li, D. Favorite, N. Singh, T. Childers, P. Rich, W. Allcock, M. E. Papka, and Z. Lan, “Dras: Deep reinforcement learning for cluster scheduling in high performance computing,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 33, no. 12, pp. 4903–4917, 2022.
  * [7] Y. LeCun, Y. Bengio, and G. Hinton, “Deep learning,” _nature_ , vol. 521, no. 7553, pp. 436–444, 2015.
  * [8] A. Dethise, M. Canini, and S. Kandula, “Cracking open the black box: What observations can tell us about reinforcement learning agents,” in _Proceedings of the 2019 Workshop on Network Meets AI & ML_, 2019, pp. 29–36.
  * [9] D. Bau, B. Zhou, A. Khosla, A. Oliva, and A. Torralba, “Network dissection: Quantifying interpretability of deep visual representations,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2017, pp. 6541–6549.
  * [10] M. Du, N. Liu, Q. Song, and X. Hu, “Towards explanation of dnn-based prediction with guided feature inversion,” in _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2018, pp. 1358–1367.
  * [11] J. Wang, L. Gou, W. Zhang, H. Yang, and H.-W. Shen, “Deepvid: Deep visual interpretation and diagnosis for image classifiers via knowledge distillation,” _IEEE transactions on visualization and computer graphics_ , vol. 25, no. 6, pp. 2168–2180, 2019.
  * [12] Q. Liu, Y. Zhu, Z. Liu, Y. Zhang, and S. Wu, “Deep active learning for text classification with diverse interpretations,” in _Proceedings of the 30th ACM International Conference on Information & Knowledge Management_, 2021, pp. 3263–3267.
  * [13] M. Toneva and L. Wehbe, “Interpreting and improving natural-language processing (in machines) with natural language-processing (in the brain),” _Advances in neural information processing systems_ , vol. 32, 2019.
  * [14] O. Bastani, Y. Pu, and A. Solar-Lezama, “Verifiable reinforcement learning via policy extraction,” _Advances in neural information processing systems_ , vol. 31, 2018.
  * [15] D. Ernst, P. Geurts, and L. Wehenkel, “Tree-based batch mode reinforcement learning,” _Journal of Machine Learning Research_ , vol. 6, 2005.
  * [16] N. Frosst and G. Hinton, “Distilling a neural network into a soft decision tree,” _arXiv preprint arXiv:1711.09784_ , 2017.
  * [17] A. Hussein, M. M. Gaber, E. Elyan, and C. Jayne, “Imitation learning: A survey of learning methods,” _ACM Computing Surveys (CSUR)_ , vol. 50, no. 2, pp. 1–35, 2017.
  * [18] S. Ross, G. Gordon, and D. Bagnell, “A reduction of imitation learning and structured prediction to no-regret online learning,” in _Proceedings of the fourteenth international conference on artificial intelligence and statistics_. JMLR Workshop and Conference Proceedings, 2011, pp. 627–635.
  * [19] W.-Y. Loh, “Classification and regression trees,” _Wiley interdisciplinary reviews: data mining and knowledge discovery_ , vol. 1, no. 1, pp. 14–23, 2011.
  * [20] B. Li, S. Chunduri, K. Harms, Y. Fan, and Z. Lan, “The effect of system utilization on application performance variability,” in _Proceedings of the 9th International Workshop on Runtime and Operating Systems for Supercomputers_ , 2019, pp. 11–18.
  * [21] V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller, “Playing atari with deep reinforcement learning,” _arXiv preprint arXiv:1312.5602_ , 2013.
  * [22] T. Feng and C. Yue, “Visualizing and interpreting rnn models in url-based phishing detection,” in _Proceedings of the 25th ACM Symposium on Access Control Models and Technologies_ , 2020, pp. 13–24.
  * [23] H. Wu, A. Huang, and J. W. Sutherland, “Layer-wise relevance propagation for interpreting lstm-rnn decisions in predictive maintenance,” _The International Journal of Advanced Manufacturing Technology_ , pp. 1–16, 2022.
  * [24] C. Molnar, _Interpretable machine learning_. Lulu.com, 2020.
  * [25] M. T. Ribeiro, S. Singh, and C. Guestrin, ““Why should I trust you?” Explaining the predictions of any classifier,” in _Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining_ , 2016, pp. 1135–1144.
  * [26] M. Du, N. Liu, and X. Hu, “Techniques for interpretable machine learning,” _Communications of the ACM_ , vol. 63, no. 1, pp. 68–77, 2019.
  * [27] S. B. Kotsiantis, “Decision trees: a recent overview,” _Artificial Intelligence Review_ , vol. 39, pp. 261–283, 2013.
  * [28] Z. Meng, M. Wang, J. Bai, M. Xu, H. Mao, and H. Hu, “Interpreting deep learning-based networking systems,” in _Proceedings of the Annual conference of the ACM Special Interest Group on Data Communication on the applications, technologies, architectures, and protocols for computer communication_ , 2020, pp. 154–171.
  * [29] Q. Hu, H. Nori, P. Sun, Y. Wen, and T. Zhang, “Primo: Practical Learning-Augmented Systems with Interpretable Models,” in _2022 USENIX Annual Technical Conference (USENIX ATC 22)_ , 2022, pp. 519–538.
  * [30] L. M. Schmidt, G. Kontes, A. Plinge, and C. Mutschler, “Can you trust your autonomous car? interpretable and verifiably safe reinforcement learning,” in _2021 IEEE Intelligent Vehicles Symposium (IV)_. IEEE, 2021, pp. 171–178.
  * [31] IRL on GitHub. [Online]. Available: https://github.com/SPEAR-UIC/IRL
  * [32] CQSim. [Online]. Available: https://github.com/SPEAR-UIC/CQSim
  * [33] D. G. Feitelson, D. Tsafrir, and D. Krakov, “Experience with using the parallel workloads archive,” _Journal of Parallel and Distributed Computing_ , vol. 74, no. 10, pp. 2967–2982, 2014.
  * [34] PWA. [Online]. Available: https://www.cs.huji.ac.il/labs/parallel/workload/
  * [35] A. F. Agarap, “Deep learning using rectified linear units (relu),” _arXiv preprint arXiv:1803.08375_ , 2018.
  * [36] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg _et al._ , “Scikit-learn: Machine learning in python,” _the Journal of machine Learning research_ , vol. 12, pp. 2825–2830, 2011.
  * [37] D. G. Feitelson and L. Rudolph, “Metrics and benchmarking for parallel job scheduling,” in _Job Scheduling Strategies for Parallel Processing: IPPS/SPDP’98 Workshop Orlando, Florida, USA, March 30, 1998 Proceedings 4_. Springer, 1998, pp. 1–24.