Design and Scheduling of an AI-based Queueing System

Jiung Lee1 Hongseok Namkoong2 Yibo Zeng2

Coupang1 Columbia University2

<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

To leverage prediction models to make optimal scheduling decisions in service
systems, we must understand how predictive errors impact congestion due to
externalities on the delay of other jobs. Motivated by applications where
prediction models interact with human servers (e.g., content moderation), we
consider a large queueing system comprising of many single server queues where
the _class_ of a job is estimated using a prediction model. By characterizing
the impact of mispredictions on congestion cost in heavy traffic, we design an
index-based policy that incorporates the predicted class information in a
near-optimal manner. Our theoretical results guide the design of predictive
models by providing a simple model selection procedure with downstream
queueing performance as a central concern, and offer novel insights on how to
design queueing systems with AI-based triage. We illustrate our framework on a
content moderation task based on real online comments, where we construct
toxicity classifiers by finetuning large language models.

###  1 Introduction

Recent advances in predictive models present significant opportunities for
utilizing unstructured information such as images and text to solve real-world
sequential decision-making problems. A major challenge to effective decision-
making is modeling complex endogenous interactions. For instance, prioritizing
a particular job in a service system incurs negative externalities that affect
the congestion of other jobs. Building effective scheduling policies requires
a fundamental understanding of how decisions based on (potentially erroneous)
predictions propagate through the system.

In this paper, we explore the use of predictive information to allocate scarce
resources across stochastic workloads. We are motivated by content moderation
systems on social media, a critical process for maintaining the health and
sustainability of online platforms. Delays in removing violating posts (e.g.,
hate speech) can exacerbate their negative impact. While clear-cut cases can
be filtered out by an initial AI-based filtering system, nuanced moderation
requires human reviewers to account for nonstationary social contexts and
avoid unnecessary censorship and violations of freedom of speech [3, 39].

We model content moderation as a large-scale service system involving human
reviewers and state-of-the-art AI models (Figure 1). To ensure fairness and
similar workload between human reviewers, jobs are typically assigned to
different human reviewers in an identically random manner. The dynamic
scheduling problem can thus be reduced to a single-server queuing system for
each human reviewer, where jobs are categorized into different classes
according to toxicity and whether the content targets protected demographic
features such as race or religion. Online platforms incur differential cost of
delay across job classes depending on their potential harm, and AI models
present opportunities to utilize predictions of harm based on sophisticated
content and user features.

Figure 1: Schematic of a content moderation system as a triage system. Each
content may be violating the user agreement (red toxicity symbol) or
considered safe (green checkmark). This ground truth requires human review to
uncover (“service”). Contents are flagged for review by users or automated
filters, which we view as “entering” the triage system. The online platform
uses an initial AI model to filter out contents most deemed to be safe. Then,
remaining jobs/contents are randomly assigned to the human reviewers, a common
practice due to fairness considerations in terms of mental workload. An AI
model classifies each content into different classes (e.g., hate speech on a
protected group), placing them in the corresponding virtual queue for the
predicted class.

The random assignment assumption allows us to model the system as a set of
single-server queues where job classes (e.g., toxicity) are a priori unknown.
Here, misclassifications have _endogenous_ impact on congestion since
prioritizing a job delays the processing of others. To minimize the overall
cost, we must balance heterogeneous service rates—such as political
misinformation being harder to review than nudity—and the adverse effects of
congestion, like toxic content going viral, by accounting for how
misclassification errors reverberates through the queueing system.

When the class of every job is known, a simple index-based myopic policy—the
oracle G$c\mu$-rule—is optimal in highly congested systems [63, 40].
Concretely, consider a single-server queue with $K$ distinct job classes with
arrival and service rates $\lambda_{k}$ and $\mu_{k}$, which we assume are
known to the modeler. Let $C_{k}(\cdot)$ be a convex cost function defined on
sojourn time of jobs in class $k=1,\ldots,K$ (time between job arrival and
service completion). The oracle G$c\mu$-rule is intuitive and simple: it
greedily prioritizes jobs with the highest marginal cost of delay

$\mathop{\rm
argmax}_{k\in[K]}\mu_{k}(t)(C_{k})^{\prime}(a_{k}(t))\qquad\qquad\mbox{Oracle
G$c\mu$-rule},$ (1.1)

where $a_{k}(\cdot)$ is the age or the waiting time of the oldest unfinished
job of class $k$.

When the true classes are unknown, we predict the job class using a
classifier. Letting $\underline{\lambda}_{l}$ and $\underline{\mu}_{l}$ be the
arrival and service rates for a _predicted_ class $l$, a naive adaptation of
the G$c\mu$-rule is

$\mathop{\rm
argmax}_{l\in[K]}\underline{\mu}_{l}(t)(C_{l})^{\prime}(\underline{a}_{l}(t))\qquad\qquad\mbox{Naive
G$c\mu$-rule},$ (1.2)

where $\underline{a}_{l}(\cdot)$ is the age or the waiting time of the oldest
unfinished job with predicted class $l$ (Definition 2). This index policy does
not consider misclassifications and ignores the fact that delay cost depends
on the true class label instead of the predicted class: the delay cost of a
content depends on whether it is toxic, rather than the prediction of
toxicity. This mismatch leads to suboptimal scheduling decisions as we show in
Theorem 3 to come.

We propose and analyze an index policy that optimally incorporates the impact
of prediction errors in the overall cost of delay. We consider the weighted
average of true class costs $C_{k}$ using the conditional probability that a
job predicted as class $l$ belongs to class $k$

$\underline{C}_{l}(t):=\sum_{k=1}^{K}\frac{p_{k}\underline{q}_{kl}}{\sum_{k^{\prime}=1}^{K}p_{k^{\prime}}\underline{q}_{k^{\prime}l}}\cdot
C_{k}(t),~{}~{}~{}t\in[0,\infty),$ (1.3)

where $p_{k}$ is the probability that an arbitrary job in the system belongs
to class $k$, and $\underline{q}_{kl}$ is the probability that an arbitrary
class $k$ job is predicted as class $l$. This gives rise to the index rule

$\mathop{\rm
argmax}_{l\in[K]}\underline{\mu}_{l}(t)(\underline{C}_{l})^{\prime}(\underline{a}_{l}(t))\qquad\qquad\mbox{P$c\mu$-rule},$
(1.4)

which is easy to implement since the arrival rates and misclassification
errors that determine $\underline{C}_{l}(t)$ can be efficiently estimated. In
the specific case of linear delay costs and steady-state waiting time as the
performance metric, the Pc$\mu$-rule bears resemblance to Argon and Ziya [4,
Section 8]’s policy defined with conditional distributions of the true classes
given the signal from a job. In contrast, we model increasing marginal cost of
delay in content moderation through strongly convex cost functions and prove
(heavy traffic) _optimality_ over _all feasible_ policies, in contrast to
Argon and Ziya [4]’s analysis focusing on dominance over first-come-first-
serve policies.

Offline deep reinforcement learning (DRL) methods are a popular contender to
sequential decision-making. While flexible, DRL methods require significant
engineering efforts to be reliably trained [29, 66, 16], and the performance
of DRL methods is known to be highly sensitive to hyperparameters,
implementation details, and even random seeds [29]. On a single-server queue
with 10 classes, we observe that deep Q-learning policies with experience
replay exhibits substantial variation in performance across hyperparameters,
even when using identical instant rewards functions, training/testing
enviroments, and same random seeds across training runs (Figure 3). The simple
index policy P$c\mu$-rule significantly outperforms the best-performing DRL
hyperparameter configuration (Figure 3), as we illustrate in detail in Section
5.

Figure 2: Histogram of average cumulative queueing cost of deep Q-learning
policies over 672 hyperparameter configurations.

Figure 3: Cumulative cost with 2$\times$ standard errors

In contrast to the growing body of work on learning in queueing that develop
_online_ learning algorithms [13, 34, 36, 59, 65, 22], we propose an off-
policy method to model applications where experimentation is risky or
unwieldy. This reflects operational constraints that arise from modern AI-
based service systems where models are trained offline using previously
collected data. Since we assume service times are determined by true classes,
in principle observed service times contain information about true class
labels that can be used to improve the classifier in real time. Even in the
largest industrial scenarios, however, online learning requires prohibitive
infrastructure due to the high engineering complexity required for
implementation. Any prediction model must be thoroughly validated prior to
deployment, and the timescale for model development is typically longer (weeks
to months) than that for scheduling decisions (hours to days). We thus view
our offline heavy traffic analysis to be an useful analytic device for
modeling AI-based queueing systems that operate close to system capacity. See
Section 8 for a thorough literature review.

###### Contributions

Our work contributes to the growing literature studying the interface between
predictive models and decision-making [4, 41, 57, 33, 12, 60]. Prediction is
rarely the end goal in operational scenarios, but the link between predictive
performance and downstream decision-making performance is complex due to
endogeneity—misclassifications have downstream impact on delays. This work
crystallizes how classical tools from queueing theory can be modified to
provide managerial insights on the control and design of AI-based service
systems.

Since solving for the optimal scheduling policy is computationally intractable
even when job classes are known due to large state/policy spaces [46], we
study highly congested systems in the heavy traffic limit as is standard in
the queueing literature [50, 63, 28, 68, 40]. Our theoretical framework
characterizes the optimal queueing performance in the presence of
misclassification errors (Sections 3, 4), and offers several insights on the
design of AI-based service systems like the one we study in Figure 1. Along
the way, we identify a number of technical errors in the classical framework
[63] and identify conditions under which prior results hold by giving
corrected proofs based on our new techniques.

First, we derive a simple scheduling algorithm (1.4) with strong optimality
and robustness guarantees by analyzing the stochastic fluctuations in the
queue lengths of the unobservable true class jobs, and aggregating them to
represent the fluctuation in the queue length of each predicted class (Section
3). We quantify the optimal workload allocation across the predicted classes
and derive the P$c\mu$ cost function from the KKT conditions of the optimal
resource allocation problem in the heavy traffic limit (3.4) (Section 4). Our
theoretical results show that the P$c\mu$-rule induces queueing dynamics that
achieve the asymptotic optimality with exogenous costs
$\underline{C}_{l}(\cdot)$.

Next, we study the design of AI models with a central focus on decision-
making. Although predictive performance is rarely the final goal, models are
typically validated based on predictive measures such as precision or recall
for convenience. But overparameterized models (e.g., neural networks) can
achieve the same predictive performance, yet exhibit very different downstream
decision performance [17, 8]. We quantify the connection between predictive
performance and the cost of delay, allowing us to design AI models with
downstream decision-making performance as a central concern (Section 6). We
propose a model selection procedure based on the _cumulative queueing cost_ ,
and demonstrate its advantages in contrast to conventional model selection
approaches in ML that solely rely on predictive measures.

Finally, we use our characterization of the optimal queueing cost under
misclassifications to inform the design of the queueing system itself. In the
context of our motivating content moderation problem, we design an AI-based
triaging system that helps determine staffing levels and corresponding
filtering levels based on predictions from an initial round AI model (which
may or may not be the same model used to classify jobs into classes). We
propose a holistic framework trading off filtering cost, predictive
performance, hiring costs, and congestion in the queueing system (Section 7).
Our formulation significantly contributes to the practical discussion on
designing content moderation systems, which traditionally focuses on pure
prediction metrics [2, 54, 67, 1]. In Section 7.4, we demonstrate that
traditional prediction-based metrics may accurately reflect the overall costs
of a triage system when either filtering costs or hiring costs are the
predominant factor. However, these metrics fall short in more complex
scenarios where there are trade-offs between different types of costs. As a
result, optimizing for these metrics typically requires computationally
expensive queueing simulations. In contrast, our method reliably determines
the optimal staffing and filtering levels across all scenarios by simulating a
(reflected) Brownian motion.

###  2 Model

We begin by presenting our analytic framework in the heavy traffic regime.
There are two possible data generating processes we can study. We could view
jobs as originating from a _single_ common arrival process, where interarrival
times are independent of job features, true classes labels, and service times.
This single arrival stream allows us to disentangle the arrival and service
processes of predicted classes, and directly use the diffusion limit to show
optimality of the P$c\mu$-rule. On the other hand, we may consider a more
general generating process where the arrival and service processes for
different classes are exogenously given. In this setting, we can still show
similar mathematical guarantees as under the single stream model using heavy
traffic analysis techniques pioneered by Mandelbaum and Stolyar [40]. However,
this proof approach weakens our optimality results: we can only show
optimality of the P$c\mu$-rule over first-come-first-serve policies, whereas
under the single stream model, the direct analysis allows proving optimality
over all feasible policies (see Section B.4). Furthermore, this proof approach
requires more restrictive regularity conditions than the direct method that is
possible under the single arrival stream model—see Section E.3 for a detailed
discussion. We view the practical modeling capabilities of the two data
generating assumptions to be similar; the singe arrival stream is a good model
of the content moderation system (as depicted in Figure 1). Henceforth, we
thus focus on the single common arrival process for expositional clarity and
crisp mathematical results.

We consider a sequence of single-server multi-class queueing systems indexed
by $n\in\mathbb{N}$, connected through a heavy traffic condition. Each system
$n$ operates on a finite time horizon $[0,n]$, and starts empty. Let
$u_{i}^{n}$ be i.i.d. interarrival times with an arrival rate $\lambda^{n}$.
For $t\in[0,n]$, let $U_{0}^{n}(t):=\sum_{i=1}^{\lfloor t\rfloor}u_{i}^{n}$ be
the arrival time of the $\lfloor t\rfloor$th job in the system and
$A_{0}^{n}(t)=\max\\{m:U_{0}^{n}(m)\leq t\\}$ be the total number of jobs that
arrive up to time $t$. For each class $k$, let
$p_{k}^{n}:=\mathbb{P}^{n}[Y_{1k}^{n}=1]$ be the class prevalence and
$(\mu_{k}^{n})^{-1}:=\mathbb{E}^{n}[v_{1}^{n}\mid Y_{1k}^{n}=1]$ the expected
service time. For each job, a tuple $(X_{i}^{n},Y_{i}^{n},v_{i})$ is generated
independently of its interarrival time $u_{i}^{n}$ where
$X_{i}^{n}\in\mathbb{R}^{d}$ represents the feature vector associated with the
$i$th job, $v_{i}^{n}$ indicates the time required to serve the $i$th job, and
$Y_{i}^{n}=(Y_{i1}^{n},...,Y_{iK}^{n})$ denotes the one-hot encoded
representation of its true class label. Let $V_{0}^{n}(t):=\sum_{i=1}^{\lfloor
t\rfloor}v_{i}^{n},~{}\forall~{}t\in[0,n]$ be the total service time required
by the first $\lfloor t\rfloor$ jobs.

A classifier $f_{\theta}$ predicts a class for each job $i$ using observed
features $X_{i}^{n}$, and the job $i$ joins the (virtual) queue corresponding
to the (one-hot encoded) _predicted class_
$\underline{Y}_{i}^{n}:=f_{\theta}(X_{i}^{n})$ to wait for service. Let
$\underline{q}_{kl}^{n}:=\mathbb{P}^{n}[\underline{Y}_{1l}^{n}=1\mid
Y_{1k}^{n}=1]$ be the probability of a class $k$ job being predicted as class
$l$; $Q^{n}:=(\underline{q}_{kl}^{n})_{k,l\in[K]}$ is the confusion matrix.

We assume service time is conditionally independent of the covariates given
the true class label $Y^{n}_{i}$, $v_{i}^{n}\perp X^{n}_{i}\mid Y^{n}_{i}$,
which simplies our anlysis by only considering true class label’s impact on
service time. In practice, if covariates influence service time (e.g., content
length), we can mitigate such dependency by creating more fine-grained true
classes. We summarize our data generating process as in the following
assumption.

######  Assumption A (Data Generating Processes).

For any system $n\in\mathbb{N}$, i)
$\\{(u_{i}^{n},v_{i}^{n},X_{i}^{n},Y_{i}^{n}):i\in\mathbb{N}\\}$ is a sequence
of i.i.d. random vectors, ii) $\\{u_{i}^{n}:i\in\mathbb{N}\\}$ and
$\\{(v_{i}^{n},X_{i}^{n},Y_{i}^{n}):i\in\mathbb{N}\\}$ are independent, and
iii) for any $i\in\mathbb{N}$, $v^{n}_{i}$ and $X^{n}_{i}$ are conditionally
independent given $Y^{n}_{i}$.

The following assumption formalizes the notion of heavy traffic.

######  Assumption B (Heavy Traffic Condition).

Given a classifier $f_{\theta}$ and a sequence of queueing systems, there
exist $p_{k},\underline{q}_{kl}\in[0,1]$ and $\lambda,\mu_{k}$ such that
$\sum_{k=1}^{K}p_{k}\underline{q}_{kl}>0$,
$\lambda\sum_{k=1}^{K}\frac{p_{k}}{\mu_{k}}=1$, and

$n^{1/2}\big{(}\lambda^{n}-\lambda\big{)}\rightarrow 0,\quad
n^{1/2}\big{(}\mu_{k}^{n}-\mu_{k}\big{)}\rightarrow 0,\quad
n^{1/2}\big{(}p_{k}^{n}-p_{k}\big{)}\rightarrow 0,\quad
n^{1/2}\big{(}\underline{q}_{kl}^{n}-\underline{q}_{kl}\big{)}\rightarrow 0.$
(2.1)

$\lambda^{n}-\lambda=o(n^{-1/2})$ and $\mu_{k}^{n}-\mu_{k}=o(n^{-1/2})$ aligns
with classical assumptions [40, Eq. (2)], and as usual we have that traffic
intensity $\rho^{n}:=\lambda^{n}\sum_{k}p_{k}^{n}/\mu_{k}^{n}$ converges to
$1$ at $o(n^{-1/2})$-rate

$\displaystyle n^{1/2}[\rho^{n}-1]$
$\displaystyle=n^{1/2}\Big{[}\lambda^{n}\sum\limits_{k=1}^{K}\frac{p_{k}^{n}}{\mu_{k}^{n}}-1\Big{]}\rightarrow
0.$ (2.2)

The convergence rates in Assumption B are necessary for the results in Theorem
2 and Theorem 3 to come.

###### Notation

Let $\mathcal{C}$ be the space of continuous $[0,1]\mapsto\mathbb{R}$
functions, $\mathcal{D}$ the set of the right-continuous with left limits
(RCLL); all stochastic processes will be RCLL. Let $\mathcal{D}^{k}$ be its
product space and $\|\mathbf{x}(t)\|:=\max_{i\in[k]}|x_{i}(t)|$. Define
$d_{J_{1}}(\cdot,\cdot):\mathcal{D}\times\mathcal{D}\rightarrow\mathbb{R}_{+}$
to be the $J_{1}$ (Skhorohod) metic [68, Page 79]. For any vector-valued
functions $\mathbf{x}(t),\mathbf{y}(t)\in\mathcal{D}^{k}$, define
$d_{p}(\mathbf{x},\mathbf{y})=\sum_{i=1}^{k}d_{J_{1}}(x_{i},y_{i})$ [68, Page
83] and its topology $WJ_{1}$ (weak $J_{1}$ topology). For a stochastic
process, $A^{n}_{k}(t)$, the underlined format is used to denote the
counterpart process associated with the predicted class,
$\underline{A}^{n}_{l}(t)$.

###  3 Lower bound on queueing cost

Our analysis relies on a diffusion limit for _predicted classes_ of the model.
Scheduling is based on predicted classes, but service times are determined by
the true classes. We characterize how misclassifications incur externalities
on other jobs, and derive the optimal queueing cost in Theorem 2 to come.
Compared to classical results in queueing that assume job classes are known
[63, Proposition 6], our analysis requires handling the unobservable queue
lengths of true classes as mentioned earlier; see the discussion in Section
C.1.

When the job classifier is “perfect”, we have $Q^{n}=I$ where $Q^{n}$ is the
confusion matrix defined in the previous section. In this case, our setting
reduces to the classical setting where true classes are known, and our proofs
to come give the counterpart results in Van Mieghem [63] and Mandelbaum and
Stolyar [40]. Even in this classical setting, our analysis identifies missing
assumptions (e.g., the zero limits in Assumption B) and provides proofs of
missing arguments in Van Mieghem [63], Mandelbaum and Stolyar [40].

####  3.1 Convergence of endogenous processes

Define the counting processes for arrivals and service completions in the
predicted classes. Let the $l$-th component of
$\underline{\mathbf{A}}^{n}:[0,n]\rightarrow\mathbb{N}^{K}$ be the number of
jobs that are predicted as class $l$ until time $t\in[0,n]$, and similarly let
$\underline{\mathbf{S}}^{n}:[0,n]\rightarrow\mathbb{N}^{K}$ count service
completions as a function of the total time that the server dedicates to each
predicted class. Let $\underline{\mu}_{l}^{n}$ be the service rate of jobs in
predicted class $l$, with $\underline{\mu}_{l}$ as the corresponding limit.
For ease of exposition, we defer a formal discussion of diffusion limits
Section A and defer precise definitions to Section B.3.

###### Feasible Policies

A scheduling policy $\text{$\pi$}_{n}$ is characterized by an allocation
process $\underline{\mathbf{T}}^{n}:[0,n]\rightarrow\mathbb{R}^{K}$ whose
$l$-th coordinate denotes the total time dedicated to predicted class $l$ up
to $t\in[0,n]$. We use $\text{$\pi$}_{n}$ and $\underline{\mathbf{T}}^{n}$
interchangably. Let
$\underline{\mathbf{N}}^{n}(t):[0,n]\rightarrow\mathbb{N}^{K}$ be the queue
length process; its $l$-th coordinate denotes total jobs from predicted class
$l$ remaining in system at $t\in[0,n]$. Let
$I^{n}(t):=t-\sum_{l}\underline{T}^{n}_{l}(t)$ be the cumulative idling time
up to $t\in[0,n]$. The scheduler has full knowledge of arrivals and the queue
of _predicted_ classes.

######  Definition 1 (Feasible Policies).

The sequence of scheduling policies $\\{\text{$\pi$}_{n}\\}$ is feasible if
the associated processes
$\\{\underline{\mathbf{T}}^{n}(t),\underline{\mathbf{N}}^{n}(t),I^{n}(t)\\}$
satisfy for all $n\in\mathbb{N}$,

  1. (i)

$\underline{\mathbf{T}}^{n}(0)=\mathbf{0}$, $\underline{\mathbf{T}}^{n}$ is
continuous and nondecreasing, $\underline{\mathbf{N}}^{n}\geq 0$, and $I^{n}$
is nondecreasing;

  2. (ii)

$\\{\underline{\mathbf{T}}^{n}(t),t\in[0,n]\\}$ is adapted to the filtration
$\sigma\\{(\underline{\mathbf{A}}^{n}(s),\underline{\mathbf{N}}^{n}(s)):0\leq
s<t\\}$.

Condition (i) is natural, and condition (ii) ensures that $\\{\pi_{n}\\}$ only
relies on arrivals and queue status of predicted classes up to time $t$. We
allow preemption (preemptive-resume policy) so that the server is able to
pause serving one job and switch to another in a different predicted class.
Preemption is not allowed between jobs from the same predicted class,
consistent with classical settings [40].

###### Cumulative Queueing Cost

Our goal is to minimize the cumulative queueing cost determined by true class
labels. For a true class $k$ job, its queueing cost is $C_{k}^{n}(\tau)$ where
$\tau$ is sojourn time. Let $\underline{\tau}_{lj}^{n}$ be the sojourn time of
the $j$th job of predicted class $l$, and
$\underline{\boldsymbol{\tau}}^{n}=\\{\underline{\tau}^{n}_{l}\\}_{l\in[K]}$
be the sojourn time process tracking that of the most recently arriving job in
predicted class $l$ by time $t$, i.e.,
$\underline{\tau}^{n}_{l}(t)=\underline{\tau}^{n}_{l\underline{A}_{l}^{n}(t)}$.
Since $(\underline{\tau}_{l}^{n})_{l\in[K]}$ is of order $n^{1/2}$ (see
Proposition 1 to come), we also assume commensurate scaling on
$\\{C^{n}_{k}\\}_{k\in[K]}$ in Assumption C.

######  Assumption C (Cost functions I).

For all $k\in[K]$, $C_{k}^{n}(\cdot)$ is differentiable, nondecreasing, and
convex for all $n$. There exists a continuously differentiable and strictly
convex function $C_{k}$ with $C_{k}^{\prime}(0)=0$ such that
$C_{k}^{n}(n^{1/2}\cdot)\rightarrow C_{k}(\cdot)$ and
$n^{1/2}(C^{n}_{k})^{\prime}(n^{1/2}\cdot)\rightarrow C^{\prime}_{k}(\cdot)$
uniformly on compact sets.

The scaled cumulative cost function incurred by $\pi_{n}$ is

$\displaystyle\tilde{J}^{n}_{\text{$\pi_{n}$}}(t;Q^{n})=n^{-1}\sum\limits_{l=1}^{K}\sum\limits_{k=1}^{K}\int_{0}^{nt}C_{k}^{n}(\underline{\tau}_{l}^{n}(s))\mathrm{d}\underline{A}_{kl}^{n}(s),~{}\forall~{}t\in[0,1],$
(3.1)

where $\mathrm{d}\underline{A}_{kl}^{n}$ is the the Lebesgue-Stieltjes measure
induced by $\underline{A}_{kl}^{n}$.
$\tilde{J}^{n}_{\text{$\pi_{n}$}}(t;Q^{n})$ relies on the scheduling policy
via the sojourn time process $\\{\underline{\tau}^{n}_{l}\\}$. Similar to the
classical settings [63, 40], we study _p-FCFS_ policies—those serving each
predicted class in a first-come-first-served manner. Given a feasible policy
$\pi_{n}$, we can reorder service within each predicted class to derive a
feasible p-FCFS counterpart, $\text{$\pi$}_{n,\text{p-FCFS}}$, which dominates
the original policy stochastically, i.e.,
$\mathbb{P}^{n}[\tilde{J}^{n}_{\text{$\pi$}_{n,\text{p-FCFS}}}(t)>x]\leq\mathbb{P}^{n}[\tilde{J}^{n}_{\text{$\pi_{n}$}}(t)>x],~{}\forall~{}x\in\mathbb{R},~{}t\in[0,1]$
(see Lemma 11). Since the objective (3.1) does not include preemption cost
like [63, 40], _work-conserving_ policies—the server never idles when jobs are
present—dominates non-work-conserving policies in cumulative cost
$\tilde{J}^{n}$ a.s. (see Lemma 12). Thus, we henceforth focus on p-FCFS and
work-conserving feasible policies.

###### Sample path analysis

Let $\tilde{U}_{0}^{n},\tilde{V}_{0}^{n}$ be diffusion-scaled versions of
partial sums of interarrival and service times:

$\tilde{U}_{0}^{n}(t)=n^{-1/2}[U_{0}^{n}(nt)-(\lambda^{n})^{-1}\cdot
nt],\quad\tilde{V}_{0}^{n}(t)=n^{-1/2}[V_{0}^{n}(nt)-\sum_{k=1}^{n}\frac{p^{n}_{k}}{\mu^{n}_{k}}\cdot
nt],\quad t\in[0,1].$ (3.2)

In Lemma 3 to come, we show there exist Brownian motions
$(\tilde{U}_{0},\tilde{V}_{0})$ such that
$(\tilde{U}_{0}^{n},\underline{\tilde{V}}_{0}^{n})\Rightarrow(\tilde{U}_{0},\underline{\tilde{V}}_{0})$
in $(D^{2},WJ_{1})$. Building off of our diffusion limit, we can strengthen
the convergence to the _uniform_ topology using standard tools (e.g., see
Lemma 6 and Lemma 7), and conduct a _sample path analysis_ where we construct
_copies_ of $(\tilde{U}_{0}^{n},\tilde{V}_{0}^{n})$ and
$(\tilde{U}_{0},\tilde{V}_{0})$ that are identical in distribution with their
original counterparts and converge almost surely under a common probability
space. With a slight abuse of notations, we use the same notation for the
newly construced processes.

Sample path analysis allows us to leverage properties of uniform convergence
and significantly simplifies our analysis. All subsequent results and their
proofs in the appendix, will be established on the copied processes in the
common probability space
$(\Omega_{\text{copy}},\mathcal{F}_{\text{copy}},\mathbb{P}_{\text{copy}})$
with probability one, i.e., $\mathbb{P}_{\text{copy}}\text{-}a.s.$, and all of
the convergence results will be understood to hold in the uniform norm
$\|\cdot\|$. For instance, Lemma 3 can be strengthen to
$(\tilde{U}_{0}^{n},\underline{\tilde{V}}_{0}^{n})\Rightarrow(\tilde{U}_{0},\underline{\tilde{V}}_{0})$
in $(D^{2},\|\cdot\|)$, $\mathbb{P}_{\text{copy}}-a.s.$ as shown in Lemma 4.
Also, in Lemma 10 to come, the diffusion-scaled process for $A_{0}^{n}$
converges to $\tilde{A}_{0}$ in $(D^{2},WJ_{1})$,
$\mathbb{P}_{\text{copy}}-a.s.$, where $\tilde{A}_{0}$ a function of
$\tilde{U}_{0}$. In addition, since these newly constructed processes are
identical in distribution with their original counterparts, all subsequent
results regarding almost sure convergence for the copied processes can be
converted into corresponding weak convergence results for the original
processes; see more discussion in Theorems 2 and 3.

###### Convergence of the Endogenous processes

Let $\underline{\mathbf{W}}^{n}:[0,n]\rightarrow\mathbb{R}^{K}$ be the
remaining workload process representing the service requirement of
remaining—waiting or being served—jobs predicted as class $l$ at $t\in[0,n]$.
Then, $W_{+}^{n}(t)=\sum_{l}\underline{W}_{l}^{n}(t)$ is the total remaining
workload. Let $\tilde{W}_{+}^{n}$, $\underline{\tilde{\mathbf{W}}}^{n}$,
$\underline{\tilde{\boldsymbol{\tau}}}^{n}$, and
$\underline{\tilde{\mathbf{N}}}^{n}$ be the diffusion-scaled processes
corresponding to $W_{+}^{n}$, $\underline{\mathbf{W}}^{n}$,
$\underline{\boldsymbol{\tau}}^{n}$, and $\underline{\mathbf{N}}^{n}$.

######  Proposition 1 (Fundamental Convergence Results).

Under Assumptions A, B, and H, and any work-conserving p-FCFS feasible policy

  1. (i)

(Invariant Convergence)
$\tilde{W}_{+}^{n}\rightarrow\tilde{W}_{+}:=\phi\Big{(}\tilde{V}_{0}\circ\lambda
e+\sum_{k=1}^{K}\frac{p_{k}}{\mu_{k}}\tilde{A}_{0}\Big{)}$, where $\phi$ is
the reflection mapping as defined in [68, Page 140, (2.5)];

  2. (ii)

(Equivalence of Convergence) For any predicted class $l\in[K]$,
$\limsup_{n}\|\underline{\tilde{T}}_{l}^{n}\|$,
$\limsup_{n}\|\underline{\tilde{N}}_{l}^{n}\|$,
$\limsup_{n}\|\underline{\tilde{\tau}}_{l}^{n}\|$, and
$\limsup_{n}\|\underline{\tilde{W}}_{l}^{n}\|$ are all bounded for any
predicted class $l\in[K]$. Moreover, if any of the processes
$\underline{\tilde{T}}_{l}^{n},\underline{\tilde{N}}_{l}^{n},\underline{\tilde{\tau}}_{l}^{n},$
or $\underline{\tilde{W}}_{l}^{n}$ converges, then all of
$\underline{\tilde{T}}_{l}^{n},\underline{\tilde{N}}_{l}^{n},\underline{\tilde{\tau}}_{l}^{n},$
and $\underline{\tilde{W}}_{l}^{n}$ converge.

Proposition 1 extends the classical results of Van Mieghem [63, Proposition 2]
by relaxing the assumption that true classes are known. When true classes are
known, convergence for arrival and service processes of true classes
($\tilde{\mathbf{A}}^{n}$ and $\tilde{\mathbf{S}}^{n}$) can be derived
directly via the the Functional Central Limit Theorem (FCLT) [63, Assumption
1]. In comparison, our generalization requires novel analysis approaches to
establish convergence of diffusion-scaled arrival and service processes of
predicted classes ($\underline{\tilde{\mathbf{A}}}^{n}$ and
$\underline{\tilde{\mathbf{S}}}^{n}$) in Proposition 6. Specifically, we
exploit the joint convergence result in Lemma 4 and characterize how
misclassifications impact each subprocess. We develop novel connections from
the primitives $\underline{\tilde{\mathbf{Z}}}^{n}$ and
$\underline{\tilde{\mathbf{R}}}^{n}$ to $\underline{\tilde{\mathbf{A}}}^{n}$
and $\underline{\tilde{\mathbf{S}}}^{n}$, which involves techniques of random
time change and continuous mapping approach. We give the full proof in Section
B.1.

####  3.2 Asymptotic lower bound of the scaled delay cost function

We are now ready to present the main result of this section, the asymptotic
lower bound for the cumulative queueing cost in the heavy traffic limit. Our
lower bound motivates the design of the P$c\mu$-rule in Section 4. For
predicted class $l\in[K]$, we let $\underline{\rho}_{l}:=\sum_{k}\frac{\lambda
p_{k}\underline{q}_{kl}}{\mu_{k}}>0$ (Assumption B).

######  Theorem 2 (Heavy-traffic lower bound).

Given a classifier $f_{\theta}$ and a sequence of queueing systems, suppose
that Assumptions A, B, C, and H hold. Under any feasible scheduling policies
$\\{\text{$\pi_{n}$}\\}$, the associated sequence of cumulative costs
$\\{\tilde{J}^{n}_{\text{$\pi_{n}$}}(\cdot;Q^{n}):n\in\mathbb{N}\\}$ satisfies

$\liminf_{n\rightarrow\infty}\tilde{J}^{n}_{\text{$\pi_{n}$}}(t;Q^{n})\geq\tilde{J}^{*}(t;Q):=\sum_{k=1}^{K}\sum_{l=1}^{K}\int_{0}^{t}\lambda
p_{k}\underline{q}_{kl}C_{k}\Big{(}\frac{\big{[}h\big{(}\tilde{W}_{+}(s)\big{)}\big{]}_{l}}{\underline{\rho}_{l}}\Big{)}\mathrm{d}s,~{}\forall
t\in[0,1],$ (3.3)

$\mathbb{P}_{\text{copy}}\text{-}a.s.,$ where $h(r)$ is an optimal solution to
the following resource allocation problem

$\displaystyle\text{Opt}(r):=$ $\displaystyle\min_{x}$
$\displaystyle\sum\limits_{l=1}^{K}\sum\limits_{k=1}^{K}\lambda
p_{k}\underline{q}_{kl}C_{k}\Big{(}\frac{x_{l}}{\underline{\rho}_{l}}\Big{)}$
(3.4) s.t. $\displaystyle\sum\limits_{l=1}^{K}x_{l}=r,\quad x_{l}\geq
0,~{}\forall~{}l\in[K].$

Moreover, for the original processes under $\mathbb{P}^{n}$, under any
feasible policies $\\{\pi^{\prime}_{n}\\}$,

$\liminf_{n\rightarrow\infty}\mathbb{P}^{n}[\tilde{J}^{n}_{\pi^{\prime}_{n}}(t;Q^{n})>x]\geq\mathbb{P}_{\text{copy}}[\tilde{J}^{*}(t;Q)>x],~{}\forall~{}x\in\mathbb{R},~{}\forall~{}t\in[0,1].$
(3.5)

According to Proposition 1, $\tilde{W}_{+}$ is solely determined by the
exogenous processes $\tilde{A}_{0}$ and $\tilde{V}_{0}$. Consequently, the
lower bound in Theorem 2 is independent of the scheduling policy
$\underline{\mathbf{T}}^{n}$. Our proof is involved and deferred to Section C,
where we also contrast our analytic approach to classical proof techniques.

###  4 Heavy-traffic optimality of the P$c\mu$-rule

We are ready to formally derive the P$c\mu$-rule, which is motivated by the
convex optimization problem (3.4). We prove heavy traffic optimality of the
P$c\mu$-rule by showing that it attains the lower bound in Theorem 2. Our
result (Theorem 3) extends the classical result in Van Mieghem [63,
Proposition 7].

While not the main contribution of this work, our analytic framework extend
the standard heavy traffic analysis techniques [63, 40] in subtle ways as we
detail in Sections E.2 and E.3. Even when specialized to the classical setting
of known true classes, our analysis fills gaps in classical proofs for the
optimality of the G$c\mu$-rule [63] and $D\text{-}Gc\mu$ [40]. The two methods
use _ages_ of waiting jobs, but only establish optimality stated in terms of
the _sojourn times_. To bridge this gap, we provide a rigorous proof in
Proposition 13. The proof of the proposition is nontrivial (to us) and reveals
a necessary condition that was previously unstated in [63]: strong convexity
of the cost functions. Also, our analysis circumvents the stronger assumptions
on the cost functions in [40] in the single-server case by directly analyzing
the age dynamics. See Sections E.3 for details.

We first characterize the limiting cumulative cost of a convergent policy. Let
let $\underline{\bar{A}}_{kl}$ be the limit of
$n^{-1}\underline{A}^{n}_{kl}(n\cdot)$ (see Definition 10 for a formal
statement). In the following, $\tilde{J}_{\text{$\pi$}}(t;Q)$ is dependent on
$\underline{\tilde{\boldsymbol{\tau}}}=\\{\underline{\tilde{\tau}}_{l}\\}_{l\in[K]}$
through the subscript $\pi$.

######  Lemma 1 (Convergence of
$\tilde{J}^{n}_{\text{$\pi_{n}$}}(\cdot;Q^{n})$).

Given a classifier $f_{\theta}$, suppose that Assumption A, B, C, and H hold.
For feasible policies $\\{\text{$\pi_{n}$}\\}$ satisfying
$\underline{\tilde{\tau}}^{n}_{l}\rightarrow\underline{\tilde{\tau}}_{l},~{}\forall~{}l\in[K]$,

$\sup\limits_{t\in[0,1]}|\tilde{J}^{n}_{\text{$\pi_{n}$}}(t;Q^{n})-\tilde{J}_{\text{$\pi$}}(t;Q)|\rightarrow
0,$ (4.1)

where the limiting cumulative cost $\tilde{J}_{\text{$\pi$}}(t;Q)$ is defined
by

$\tilde{J}_{\text{$\pi$}}(t;Q):=\sum\limits_{l=1}^{K}\sum\limits_{k=1}^{K}\int_{0}^{t}C_{k}(\underline{\tilde{\tau}}_{l}(s))\mathrm{d}\underline{\bar{A}}_{kl}(s)=\sum\limits_{l=1}^{K}\sum\limits_{k=1}^{K}\int_{0}^{t}\lambda
p_{k}\underline{q}_{kl}C_{k}(\underline{\tilde{\tau}}_{l}(s))~{}\mathrm{d}s.$

See Section B.5 for the proof.

Combining our characterization of the cumulative cost with the lower bound in
Theorem 2, we conclude that $\\{\text{$\pi_{n}$}\\}$ is asymptotically optimal
if the following conditions are satisfied: i) the scaled sojourn time
processes converge, i.e.,
$\underline{\tilde{\tau}}_{l}^{n}\rightarrow\underline{\tilde{\tau}}_{l},~{}\forall~{}l\in[K]$,
and ii) the limiting sojourn time processes satisfy
$\underline{\tilde{\tau}}_{l}(t)=[h(\tilde{W}_{+}(t))]_{l}/\underline{\rho}_{l},~{}\forall~{}t\in[0,1],~{}l\in[K]$,
where $h(\cdot)$ is an optimal solution to the optimization problem (3.4).
Recalling $\text{Opt}(\tilde{W}_{+}(t))$, the optimization problem (3.4), is
convex with linear constraints, its KKT conditions characterize the optimal
workload allocation $h$. For predicted class $l$, recall its limiting service
rate $\underline{\mu}_{l}$ and the P$c\mu$ cost function (1.3).

######  Lemma 2 (KKT conditions).

$\\{x_{l}\\}_{l\in[K]}$ is an optimal solution for
$\text{Opt}(\tilde{W}_{+}(t))$ if $x_{l}>0,~{}\forall~{}l\in[K]$ and is a
solution to

$\displaystyle\underline{\mu}_{l}\underline{C}_{l}^{\prime}\Big{(}\frac{x_{l}}{\underline{\rho}_{l}}\Big{)}=\underline{\mu}_{m}\underline{C}_{m}^{\prime}\Big{(}\frac{x_{m}}{\underline{\rho}_{m}}\Big{)},~{}\forall~{}l,m\in[K],\quad\sum\limits_{l=1}^{K}x_{l}=\tilde{W}_{+}(t).$
(4.2)

We also show that the KKT conditions (4.2) have a unique solution (Proposition
15, Section C) and thus $h(\tilde{W}_{+}(t))$ is well-defined.

The cost function $\underline{C}_{l}(t)$ (1.3) arises from the KKT conditions
of $\text{Opt}(\tilde{W}_{+}(t))$ as a weighted average with weights
proportional to $p_{k}\underline{q}_{kl}$, reflecting how predicted class $l$
is composed of jobs from different true classes. As $p_{k}$ and
$\underline{q}_{kl}$ rely on the arrival rates and misclassification errors,
$\underline{C}_{l}(t)$ can be viewed as the exogenous average cost function
associated with predicted class $l$. We aim to develop a scheduling policy
that induces the workload allocation to align with the exogenous cost
$\underline{C}_{l}(t)$, in the sense that the conditions (4.2) are satisfied
for all $t\in[0,1]$.

According to Proposition 1, convergence of the sojourn time process
$\underline{\tilde{\boldsymbol{\tau}}}^{n}\rightarrow\underline{\tilde{\boldsymbol{\tau}}}$
is equivalent to convergence of workload
$\underline{\tilde{\mathbf{W}}}^{n}\rightarrow\underline{\tilde{\mathbf{W}}}$.
Moreover, if $\underline{\tilde{\mathbf{W}}}^{n}$ converges, then
$\underline{\tilde{\tau}}_{l}=\underline{\tilde{W}}_{l}/\underline{\rho}_{l},\forall~{}l\in[K]$
(see Lemma 8 and Lemma 16). Consequently, our goal is to develop a policy that
satisfies
$\underline{\tilde{\boldsymbol{\tau}}}^{n}\rightarrow\underline{\tilde{\boldsymbol{\tau}}}$
and

$\underline{\mu}_{l}\underline{C}^{\prime}_{l}(\underline{\tilde{\tau}}_{l})=\underline{\mu}_{m}\underline{C}^{\prime}_{m}(\underline{\tilde{\tau}}_{m}),~{}\forall~{}l,m\in[K],$
(4.3)

in the heavy traffic limit. When the balance (4.3) is achieved, the limiting
workload allocation
$\underline{\tilde{W}}_{l}=x_{l}:=\underline{\tilde{\tau}}_{l}\underline{\rho}_{l}$
satisfies the KKT conditions (4.2) and both conditions (a) and (b) are met,
which leads to the policy’s optimality.

Since the sojourn time—time between job arrival and service completion—is
_not_ observable, we substitute
$\underline{\boldsymbol{\tau}}^{n}=\\{\underline{\tau}_{l}^{n}\\}_{l\in[K]}$
with the observable age processes.

######  Definition 2 (Age Process).

Given a classifier $f_{\theta}$ and feasible policies
$\\{\text{$\pi_{n}$}\\}$, a predicted class $l$ and time $t\in[0,n]$, let
$\underline{a}_{l}^{n}(t)$ be the waiting time of the oldest job in predicted
class $l$ at time $t$, where a job being served is defined to be waiting in
the system. Let $\underline{a}_{l}^{n}$ be the _age_ process of the predicted
class $l\in[K]$ in system $n$, and let
$\underline{\tilde{a}}_{l}^{n}(t):=n^{-1/2}\underline{a}_{l}^{n}(nt),~{}t\in[0,1]$
and
$\underline{\tilde{\mathbf{a}}}^{n}:=\\{\underline{\tilde{a}}_{l}^{n}\\}_{l\in[K]}$
be the corresponding diffusion-scaled process and its vector-valued version.

If either $\\{\underline{\tilde{a}}_{l}^{n}\\}_{l\in[K]}$ or
$\\{\underline{\tilde{\tau}}_{l}^{n}\\}_{l\in[K]}$ converges, then both of the
processes converge to the same limit, i.e.,
$\underline{\tilde{\tau}}_{l}(t)=\underline{\tilde{a}}_{l}(t),~{}\forall~{}l\in[K],t\in[0,1]$
(see Proposition 12). Thus, we can equivalently reformulate the optimality
condition for sojourn time (4.3) into that with observable age processes

$\underline{\mu}_{l}\underline{C}^{\prime}_{l}(\underline{\tilde{a}}_{l})=\underline{\mu}_{m}\underline{C}^{\prime}_{m}(\underline{\tilde{a}}_{m}),~{}\forall~{}l,m\in[K].$
(4.4)

###### Heavy-Traffic Optimality

We design the P$c\mu$-rule in the _prelimit_ systems to achieve (4.4) in the
heavy traffic limit. The P$c\mu$-rule prioritizes predicted classes with the
highest prelimit Pc$\mu$ index, defined as follows.

######  Definition 3 (P$c\mu$-rule).

Given a classifier $f_{\theta}$, for any system $n$ at time $nt$ with
$t\in[0,1]$, the P$c\mu$-rule serves the oldest job in the predicted class
having the maximum P$c\mu$-rule index, i.e.,
$l\in\arg\max_{m\in[K]}\underline{\mathcal{I}}^{n}_{m}(t)$, with preemption,
where

$\underline{\mathcal{I}}^{n}_{l}(t):=\underline{\mu}^{n}_{l}\cdot
n^{1/2}(\underline{C}^{n}_{l})^{\prime}(\underline{a}_{l}^{n}(nt)),~{}\forall~{}t\in[0,1],$
(4.5)

is the P$c\mu$-rule index for predicted class $l$ at time $nt$ in system $n$,
and
$\underline{C}_{l}^{n}(t):=\frac{\sum_{k}p^{n}_{k}\underline{q}^{n}_{kl}C^{n}_{k}(t)}{\sum_{k^{\prime}}p^{n}_{k^{\prime}}\underline{q}^{n}_{k^{\prime}l}},~{}t\in[0,\infty),~{}l\in[K]$,
is the weighted average of $C^{n}_{k}$ and the prelimit counterpart of
$\underline{C}_{l}(t)$.

The P$c\mu$-rule is a work-conserving p-FCFS policy by definition, and the
$n^{1/2}$ scaling ensures a well-defined heavy traffic limit. The P$c\mu$-rule
naturally allows for _preemption_ : since we consider jobs being served as
waiting in the system, the age process $a_{l}^{n}$ corresponds to the same job
waiting in the queue until its service completion. We adopt preemption for
analysis purposes. In particular, we can develop a non-preemptive counterpart
of the P$c\mu$-rule and show its optimality using the same analytic framework.

We are now ready to present our optimality result, which shows that the
cumulative queueing cost associated with the P$c\mu$-rule,
$\tilde{J}^{n}_{\text{Pc$\mu$}}(\cdot;Q^{n})$, converges to the asymptotic
lower bound $\tilde{J}^{*}(\cdot;Q)$. Our proof relies on the fact that the
P$c\mu$-rule is a greedy method minimizing the largest difference of the
P$c\mu$ indices ,
$\sup_{t\in[0,1]}\,\max_{l,m\in[K]}|\underline{\mathcal{I}}^{n}_{l}(t)-\underline{\mathcal{I}}^{n}_{m}(t)|$,
which guarantees (Proposition 13, Section E.1)

$\sup_{t\in[0,1]}\,\max_{l,m\in[K]}|\underline{\mathcal{I}}^{n}_{l}(t)-\underline{\mathcal{I}}^{n}_{m}(t)|\rightarrow
0.$ (4.6)

We develop novel analysis techniques to show the convergence (4.6), which
requires strong convexity of the cost function.

######  Assumption D (Cost functions II).

The limiting cost $C_{k}$ is strongly convex for all $k\in[K]$.

######  Theorem 3 (Optimality of P$c\mu$-rule).

Given a classifier $f_{\theta}$ and a sequence of queueing systems, suppose
that Assumptions A, B, C, D, and H hold. Then,
$\tilde{J}^{n}_{\text{Pc$\mu$}}(\cdot;Q^{n})\rightarrow\tilde{J}^{*}(\cdot;Q)$
in $(\mathcal{D},\|\cdot\|)$ $\mathbb{P}_{\text{copy}}$-a.s.. For the original
processes under $\mathbb{P}^{n}$,
$\tilde{J}^{n}_{\text{Pc$\mu$}}(\cdot;Q^{n})\Rightarrow\tilde{J}^{*}(\cdot;Q)$
in $(\mathcal{D},J_{1})$, and in particular,
$\mathbb{P}^{n}[\tilde{J}^{n}(t;Q^{n})>x]\rightarrow\mathbb{P}_{\text{copy}}[\tilde{J}^{*}(t;Q)>x],~{}\forall~{}x\in\mathbb{R},~{}t\in[0,1].$

Our proof is highly involved so we provide a brief overview in Section E.1 and
defer detailed arguments to Section D and E. Our analytic framework extends
upon prior work in subtle ways; see Sections E.2 and E.3 for an in-depth
discussion of our proof compared to Van Mieghem [63] and Mandelbaum and
Stolyar [40].

###  5 Empirical demonstration of the P$c\mu$-rule

We demonstrate the effectiveness of P$c\mu$-rule on a content moderation
problem using real-world user-generated text comments with the data generating
process in Section 2. To operate at a massive scale, online platforms use AI
models to provide initial toxicity predictions. However, these models are
imperfect due to the inherent nonstationarity in the system; for example, they
cannot reliably detect context related to hate speech following a recent
terrorist attack. As a result, platforms must rely on human reviewers as the
final inspectors [39], especially since they bear the cost of mistakenly
removing non-violating comments. Our goal is to analyze the downstream impact
of prediction errors on scheduling decisions in the content moderation
queueing system.

Different comments incur varying levels of negative impact on the platform. If
not removed in a timely manner, toxic comments attacking historically
marginalized or oppressed groups can have particularly harmful effects. We
model this using heterogeneous delay costs based on the level of toxicity and
the demographic group targeted by the comment. These factors also affect
processing time; for instance, reviewing comments about an ethnic minority
group in a foreign nation is more challenging and time-consuming compared to
domestic content.

We use real user-generated text comments on online articles from the
CivilComments dataset [10]. Each comment has been labeled by at least ten
crowdsourcing workers with binary toxicity labels and whether it mentions one
of the 8 demographic identities: _male, female, LGBTQ, Christian, Muslim,
other religions, Black, White_. For simplicity, we focus on comments that
mention one and only one of the common groups _white, black, male, female,
LGBTQ_. By crossing them with binary toxicity labels, we derive 10 job
classes. We assume the system has exact knowledge of target group (using
simple rule-based logic), but can only predict the toxicity through an AI
model.

The toxicity predictor, which can also be viewed as the job class predictor
$f_{\theta}$, utilizes the same neural network architecture and training
approach as described in Koh et al. [32]. To showcase the versatility of our
scheduling algorithm regardless of the underlying prediction model, we study
three models fine-tuned based on a pre-trained language model (DistilBERT-
base-uncased [53]): empirical risk minimization (ERM), reweighted ERM that
upsamples toxic comments, and a simple distributionally robust model trained
to optimize worst-group performance over target demographic groups (GroupDRO
[52]). We observe significant variation in predictive performance across the
10 job classes defined by $\\{$toxicity $\times$ target demographic$\\}$.
Across the three models (ERM, Reweighted, GroupDRO), the worst-class accuracy
(55%, 68%, 67%) is significantly lower than the mean accuracy (88%, 84%, 84%),
leading to diverse patterns in the confusion matrix $Q$.

###### Queueing system

We assume jobs are assigned to reviewers randomly to ensure fairness, as
mentioned in Section 1, and view each reviewer as a single-server queueing
system. For simplicity, we consider a queueing model operating in a finite
time interval $[0,1]$ with 10 job classes. New jobs/comments arrive with
i.i.d. exponential interarrival times with rate 100 (uniformly drawn from the
test set). Toxic comments have a lower service rate and toxic comments
mentioning minority groups have an even lower service rate. The service times
follow exponentially distributions that solely depend on the true class label
$Y$: for _white, black, male, female, LGBTQ_ , respectively,
$\mu_{\text{toxic}}=[100,30,110,25,15]$ and $\mu_{\text{non-
toxic}}=[150,150,150,150,150]$. (If the service rate depends on the covariate
$X$, e.g., length of the comment, we can create further classes by splitting
on relevant covariates.) Our queueing system operates in heavy traffic with
overall traffic intensity $\approx 1$, aligning with Assumption B. We set
higher delay costs for toxic comments and coments targeting historically
marginalized or oppressed groups. Specifically, for each demographic group
$i$, we set the delay cost as $C_{i,\cdot}(t)=c_{i,\cdot}t^{2}/2,$ with
$c_{i,\text{toxic}}=[10,22,12,20,25]$ and $c_{i,\text{non-toxic}}=[1,1,1,1,1]$
for toxic and nontoxic comments mentioning the aforementioned demographic
groups, respectively.

###### Queueing policies

We compare our proposed P$c\mu$-rule against three scheduling approaches.
First, we consider the Naive G$c\mu$-rule (1.2) that treats the predicted
classes as true, and employs the usual Gc$\mu$-rule. For both P$c\mu$-rule and
Naive G$c\mu$-rule, we assume the scheduler has complete knowledge of the
arrival/service rates of the predicted classes, and use the confusion matrix
$Q$ computed on the validation dataset. Second, we study a black-box approach
scheduling using deep reinforcement learning methods (DRL), where we use a
Q-learning method to estimate the value function using a feedforward neural
network (deep Q-Networks [42]). Finally, we consider the Oracle Gc$\mu$
policy, which knows the true class as well as associated arrival/service
rates. All policies are evaluated in the aforementioned setup, where the
scheduler predicts the class label using the AI model $f_{\theta}$.

To train our DRL policy, we use Namkoong et al. [44]’s discrete event queueing
simulator. We use $\\{(\text{queue length, age of the oldest job})\\}$ of all
predicted classes as our state space and let the predicted classes
$\\{1,\ldots,K=10\\}$ be the action space. We learn a Q-function parameterized
by a three-layer fully connected network, and serve the oldest job in the
predicted class that maximizes the Q-function. As instantaneous rewards, we
use the sum of cost rates, $c_{i,\cdot}$ times the age, for all classes. We
employ a similar training procedure as described in [44, Section D.1], and
impose a large penalty to discourage the policy from serving empty queues.

Figure 4: We present the cumulative cost for different policies under
different testing environments (with 2$\times$ the standard error encapsulated
in the orange bracket).

###### Instability of reinforcement learning

We run the deep Q-learning method with experience replay over 672 distinct
sets of hyperparameters and evaluate them based on the average cumulative
queuing cost over $5000$ independent sample paths simulated from the testing
enviroment. In Figure 3, we observe substantial variation in queueing
performance across hyperparameters even when using identical instant reward
functions and training/testing enviroments. (We also use the same random seed
across training runs.) In particular, the minimum, bottom & top deciles of
cumulative costs are 7.98, 9.79, and 60.46. Our empirical observation
highlights the significant engineering effort required to apply DRL approaches
to scheduling and replicates previous findings in the RL literature (e.g.,
[29]). In the rest of the experiments, we select the best hyperparameter based
on average queueing costs reported in Figure 3.

###### Main results

In Figure 4, we present cumulative cost averaged over $50K$ sample paths. In
the first column of Figure 4, we test scheduling policies under the
environment they were designed for: constant arrival/service rates as we
described above, with traffic intensity $\approx$ 1\. The P$c\mu$-rule
outperforms Naive G$c\mu$-rule by $\sim 30\%$ and DRL by $60-70\%$ in terms of
the cost gap towards the Oracle G$c\mu$-rule. While we expect the DRL policy
can be further improved by additional engineering (reward shaping, neural
network architecture search etc), we view the simplicity of our index-based
policy as a significant practical advantage. Next, we assess the robustness of
the scheduling policies against nonstationarity in the system. We consider two
additional testing enviroments with heavy traffic conditions that differ from
that the policies were designed for. We observe the performance gains of the
P$c\mu$-rule hold over nonstationarities in the system.

The Pc$\mu$-rule consistently shows superior performance across different
scenarios, demonstrating its robustness and practical utility in real-world
content moderation tasks.

###  6 Model selection based on queueing cost

Predictive models with similar accuracy levels can exhibit significant
differences in queueing performance. By explicitly deriving the optimal
queueing cost under misclassification, our theoretical results allow designing
AI models with queueing cost as a central concern. Since the P$c\mu$-rule is
optimal in the heavy traffic limit, the corresponding $\tilde{J}^{*}(t;Q)$
represents the best possible cost when employing the given classifer,
$f_{\theta}$, and the relative regret $\tilde{J}^{*}(t;Q)/\tilde{J}^{*}(t;I)$
serves as an evaluation metric with queueing performance as the central
consideration. We empirically demonstrate that this simple model selection
criteria based on our theory can provide substantial practical benefits in our
content moderation simulator.

For quadratic cost functions, we can explicitly solve the optimization problem
(3.4) and derive analytic expressions for $\tilde{J}^{*}(\cdot;Q)$ and
$\tilde{J}^{*}(\cdot;I)$.

######  Assumption E (Quadratic Cost Functions).

For all $k\in[K]$, the cost functions are defined as
$C^{n}_{k}(t)=\frac{1}{2n}c^{n}_{k}t^{2},~{}t\in[0,n],~{}n\in\mathbb{N}$, and
$C_{k}(t)=\frac{1}{2}c_{k}t^{2},~{}t\in[0,1]$, where
$\\{c^{n}_{k}\\}_{n\in\mathbb{N}}$ and $c_{k}$ are positive constants such
that $c_{k}^{n}\rightarrow c_{k}$ as $n\rightarrow\infty.$

The following formulas are easy to approximate since the confusion matrix $Q$
can be effectively estimated on held-out data.

######  Proposition 4 (Cumulative Cost Rate of the P$c\mu$-rule).

Given a classifier $f_{\theta}$ and a sequence of queueing systems, suppose
that Assumptions A, B, E, and H hold. Then, we have that

$\tilde{J}^{*}(t;Q)=\frac{1}{\sum_{m=1}^{K}(\beta_{m}(Q))^{-1}}\cdot\frac{1}{2}\int_{0}^{t}\tilde{W}_{+}(s)^{2}\mathrm{d}s,~{}\forall~{}t\in[0,1],$

where
$\beta_{l}(Q):=\underline{\mu}_{l}\underline{c}_{l}/\underline{\rho}_{l}$.
Under the Naive G$c\mu$-rule, the scaled cumulative queueing cost
$\tilde{J}^{n}_{\text{Naive}}(\cdot;Q^{n})$ has the limit

$\tilde{J}_{\text{Naive}}(t;Q)=\sum\limits_{l=1}^{K}\frac{\beta_{l}(Q)}{\Big{(}\sum_{m}\frac{\beta_{l,\text{Naive}}(Q)}{\beta_{m,\text{Naive}}(Q)}\Big{)}^{2}}\cdot\frac{1}{2}\int_{0}^{t}\tilde{W}_{+}(s)^{2}\mathrm{d}s,$

where
$\beta_{l,\text{Naive}}(Q)=\underline{\mu}_{l}c_{l}/\underline{\rho}_{l}$.

See Section F.1 for the proof of Proposition 4. $\tilde{J}^{*}(\cdot;Q)$ is
dominated by small values of $\beta_{m}(Q)$, as is the case for the limiting
workload $\underline{\tilde{W}}_{m}$ under the P$c\mu$-rule(see Section F.1).
Small $\beta_{m}(Q)$ implies either high intensity or low priority of the
predicted class, meaning the impact of $f_{\theta}$ is determined by the
“imbalance” of $\\{\beta_{m}(Q):m\in[K]\\}$ between the predicted classes.

In what follows, we heavily rely on the independence between $\tilde{W}_{+}$
and misclassification errors from Proposition 1.

(a) High arrival rate of positive class

(b) Low arrival rate of positive class

(c) Theoretical gap under different accuracy levels

Figure 5: Maximum and minimum relative regret
$\tilde{J}(t;Q)/\tilde{J}^{*}(t;I)$ in the heavy traffic limit (“theoretical
criteria”) across accuracy levels. Each green dot corresponds to theoretical
criteria and accuracy of a simulated confusion matrix $Q$.

###### Model Multiplicity

It is well known that models of equal prediction accuracy can perform
differently in downstream decision-making tasks [17, 8]. This phenomenon,
known as model multiplicity [8], is particularly important in our setting,
since prediction errors over different classes can have disproportionate
impacts on downstream queueing performance. We consider a two-class toy
example to showcase that models with high accuracy levels can still exhibit
significant differences in queueing performances.

We simplify the setting from Section 5 to two classes: toxic comments
(positive class, class 1), and non-toxic comments (negative class, class 2),
where delay costs are set as $C_{k}(t)=c_{k}t^{2}/2$ with $c_{1}=15,c_{2}=1$.
We examine two settings: (i) high arrival rate of the positive class, with
$[\lambda_{1},\lambda_{2}]=[25,100]$, $[\mu_{1},\mu_{2}]=[50,200]$; and (ii)
low arrival rate of the positive class, with
$[\lambda_{1},\lambda_{2}]=[1,100]$, $[\mu_{1},\mu_{2}]=[2,200]$. The arrival
and service rates are chosen to achieve an overall traffic intensity close to
1 and approximate heavy traffic limits.

Given fixed costs, arrival rates, and service rates, we can explcitly quantify
the relative regret $\tilde{J}^{*}(t;Q)/\tilde{J}^{*}(t;I)$ for different
classifiers through the confusion matrix $Q$, considering the maximum and
minimum possible relative regret given a fixed accuracy level. In Figure
5(a)-(b), we study systems with two different arrival rates. We randomly
generate 500 confusion matrix $Q$
($\underline{q}_{11},\underline{q}_{22}\stackrel{{\scriptstyle\rm
iid}}{{\sim}}\mbox{Unif}[0,1]$) and plot the resulting accuracy level and
theoretical criteria in green dots. The variation in relative regret is
substantial in both settings, and in Figure 5(c), even at high accuracy levels
($75\%,80\%,85\%$), the relative regret can vary by $30\%$ to $80\%$. This
indicates that model multiplicity significantly affects queuing performance,
which highlights the potential of using our evaluation metric in guiding model
selection.

(a) threshold selection for a fixed classifer

(b) model training

Figure 6: Our model selection approach vs. traditional weighted-accuracy-based
methods. For thresholds or models optimized for each criteria, we present
normalized simulated queueing cost (simulated critera) and relative regret in
the heavy traffic limit (theoretical criteria). Our method reduces cumulative
queueing costs; traditional methods exhibit varying rankings across settings.

(a) Threshold selection

(b) Model selection

Figure 7: For different policies, we present our proposed model selection
criteria (theoretical criteria) based on the relative regret
$\tilde{J}(t;Q)/\tilde{J}^{*}(t;I)$ in the heavy traffic limit. To test its
validity, we plot the simulated/acutal counterpart (simulated criteria) in the
left. The relative ranking of policies based on our theoretical criteria
exactly matches that given by the simulated quantities.

###### Comparison to Traditional Model Selection Criterias

Next, we explore the effectiveness of our model selection criterion by
comparing it with traditional criteria that focus on predictive performance,
such as accuracy, precision, recall, or their weighted combinations. In
particular, we compare our evaluation metric
$\tilde{J}^{*}(t;Q)/\tilde{J}^{*}(t;I)$ against two straightforward criteria:
(i) cost-weighted accuracy, defined as
$\frac{c_{1}q_{11}+c_{2}q_{22}}{c_{1}+c_{2}}$, and (ii) frequency-weighted
accuracy, defined as
$\frac{\lambda_{1}q_{11}+\lambda_{2}q_{22}}{\lambda_{1}+\lambda_{2}}$. As we
observe below, model rankings under the traditional methods change across
arrival rates, indicating their unreliability in queueing tasks.

We consider two different approaches for utilizing our metric: (i) setting the
threshold for predicting the positive class for a fixed classifier, and (ii)
model training. For threshold selection, we adopt the two environments from
the above and generate covariates $X$ for positive and negative classes from
independent normal distributions, $\mathcal{N}(0,0.5)$ and
$\mathcal{N}(1,0.5)$, respectively. We focus on
$f_{\theta}(X):=\mathbb{I}(X\geq\theta),~{}\forall~{}\theta\in[0,1]$, study
thresholds selected by our method, cost-weighted accuracy, and frequency-
weighted accuracy, and present corresponding simulated queueing cost under the
P$c\mu$-rule in Figure 6 (a). (We use line search to to optimize each
critera.) In Figure 6, we show the average simulated queueing costs (simulated
criteria) at $T=1$ over $3\times 10^{6}$ independent sample paths using solid
bars, with 2$\times$ the standard error encapsulated in the orange brackets.
The shaded bar depicts the relative regret (theoretical criteria)
corresponding to the selected thresholds in the heavy traffic limit. To
facilitate comparison with our method, we normalize the theoretical and
simulated criteria by the relative regret and the average simulated cumulative
cost associated with our method, respectively.

We also study model training using relative regret. Specifically, we consider
the 2 dimensional logistic regression problem, where covariates
$\mathbf{X}\in\mathbb{R}^{2}$ for positive and negative classes are generated
from $\mathcal{N}([1,0],[[1,-0.25],[-0.25,1]])$ and
$\mathcal{N}([-1,0],[[1,0.75],[0.75,1]])$, respectively. For simplicity, we
fix the threshold at 0.5 and focus on classifiers defined as:
$f_{\mathbf{a},b}(\mathbf{X}):=\mathbb{I}([1+\exp\\{-(\mathbf{a}^{\top}\mathbf{X}+b)\\}]^{-1}\geq
0.5),~{}\forall~{}\mathbf{a}\in\mathbb{R}^{2},b\in\mathbb{R}.$ Due to the
simplicity of the toy problem, we can directly minimize relative regret by
grid search.

We compare our method with traditional methods using weighted cross-entropy
loss as the training objective. Given weight $\mathbf{w}=[w_{1},w_{2}]$,
predicted logits pred, and true labels $\mathbf{Y}$, the loss function is
defined as
$\ell_{w}(\mathbf{\texttt{pred}},\mathbf{Y}):=-\sum_{i:Y_{i}=1}w_{1}\log(\texttt{pred}_{i})-\sum_{j:Y_{j}=2}w_{2}\log(1-\texttt{pred}_{j})$.
We study two straightforward methods: (i) cost-weighted loss, where
$w_{1}=c_{1}/\lambda_{1},w_{2}=c_{2}/\lambda_{2}$, and (ii) frequency-weighted
loss, where $w_{1}=1,w_{2}=1$. For both methods, we use the Adam optimizer
with a learning rate of $0.1$, a batch size of 512, and train the model over
$5$ epochs using $10^{5}$ datas points. We present the normalized theoretical
and simulated criteria in Figure 6 (b).

As shown in Figure 6, in this simplified toy example, our method still
outperforms traditional methods by $\sim 1-4\%$ in cumulative queueing costs.
This demonstrates the effectiveness of our evaluation metric when queueing
performance is the major concern. However, we note that there are
discrepancies between the theoretical and simulated criteria in Figure 6 due
to deviations from the heavy traffic limit. While we conduct a brute force
grid search over classifier parameters in this simple setting, developing a
practical and scalable training algorithm in more complex scenarios is an
important direction of future work. As an interim solution, we can select
between several candidate classifiers as we present next.

###### Numerical Experiments on CivilComments Dataset

To further understand the validity of our proposed model selection criteria,
we revisit the fully general testing enviroment from Section 5. We study the
performance of the P$c\mu$-rule, Oracle Gc$\mu$, and Naive G$c\mu$-rule, using
the cumulative queueing cost at $T=1$ across $5\times 10^{4}$ independent
sample paths. As the queueing cost of the Oracle Gc$\mu$-rule converges to
$\tilde{J}^{*}(t;I)$, we normalize all simulated cumulative cost over each
sample path by the average cumulative cost of the Oracle Gc$\mu$-rule. We
refer to this quantity as “simulated” relative regret.

We demonstrate the utility of selecting and evaluating classifiers based on
$\tilde{J}^{*}(t,Q)/\tilde{J}^{*}(t,I)$ using two tasks: (i) threshold
selection for a fixed classifier, and (ii) model selection for a given
collection of classifiers. In both cases, the ranking according to our
proposed criteria aligns with simulated counterparts, illustrating how an
analytic characterization of queueing cost can provide an effective comparison
between ML models without extensive queueing simulation. For threshold
selection, we consider the P$c\mu$-rule using the aforementioned ERM predictor
and compare its queueing performance with thresholds being $[0.05,0.5,0.95]$,
positioned from left to right in Figure 7 (a). In Figure 7, we present
simulated relative regret using solid bars, with 2$\times$ the standard error
encapsulated in the orange brackets. The shaded bar depicts our proposed model
selection (theoretical criteria) given by the relative regret in the heavy
traffic limit. For model selection, we consider the aforementioned three
different classifiers: GroupDRO, Reweighted, and ERM with thresholds 0.05,
0.05, and 0.95. (These thresholds are chosen to showcase diverse queueing
performances). In Figure 7 (b), we evaluate the P$c\mu$-rule using these
models. We also compare P$c\mu$-rule to the Naive G$c\mu$-rule, where the
classifier is fixed to the aforementeioned ERM classifier with threshold 0.5
in Figure 7 (a)(b).

We demonstrated that our proposed evaluation metric
$\tilde{J}^{*}(t,Q)/\tilde{J}^{*}(t,I)$ effectively guides model selection by
focusing on queueing performance. This approach ensures that the selected
models optimize overall system performance, not just predictive accuracy,
providing a robust basis for designing and selecting AI models in service
systems.

###  7 Design of an AI-based triage system

Our characterization of queueing cost can be further utilized to design
comprehensive job processing systems assisted by AI models. Motivated by
content moderation systems on social media platforms [11, 64, 62], we study a
triage system where an initial AI model filters out clear-cut cases, after
which the queueing system serves remaining jobs (Figure 1). Standard triage
systems in online platforms determine the filtering level using simple metrics
such as maximizing recall subject to a fixed high precision level (e.g.,
[11]). These designs [2, 54, 67, 1] lead to suboptimal system performance as
they do not consider the downstream operational cost such as hiring cost of
human reviewers and queueing costs.

In this section, we provide a novel framework for designing AI-assisted triage
systems that jointly optimize the filtering and queueing systems, taking into
account all four types of costs: filtering costs, hiring costs,
misclassification costs, and queueing congestion costs. Our objective can be
easily estimated using a small set of validation data and a simple simulation
of a (reflected) Brownian motion, allowing us to find the optimal filtering
level through methods like line search. In Section 7.4, we conduct numerical
experiments to demonstrate effectiveness of this approach. We find that
prediction-based metrics, which is a norm in practice, may align with the
total cost when either filtering cost or hiring cost dominates, but it fails
to do so in more complicated settings with trade-offs between different types
of costs. Our method avoids computationally expensive queueing simulations,
and consistently identifies the optimal filtering and staffing levels in all
of these scenarios by simply simulating a (reflected) Brownian motion.

####  7.1 Model of the AI-based triage system

We consider a sequence of single-stream incoming jobs that arrive at the
triage system. We assume the $n$th system operates on a finite time horizon
$[0,n]$, starts empty, has i.i.d. interarrival times with an arrival rate of
$\Lambda^{n}$. With a slight abuse of notation, we let $u^{n}_{i}$ be the
interarrival time of the $i$th job in system $n$, $U^{n}_{0}(t)$ be the
arrival time of the $\lfloor t\rfloor$th job in system $n$, and $A^{n}_{0}(t)$
be the total number of jobs arriving in the triage system $n$ up to time $t$.
For simplicity, we consider a two-class setting, with class 1 representing
toxic content and class 2 representing non-toxic content. For each job, a
tuple of (observed features, true class label, service time), denoted as
$(X^{n}_{i},Y^{n}_{i},v^{n}_{i})$, is generated _identically_ and
_indepedently_ of its arrival time $u^{n}_{i}$. Similar to our model in
Section 2, $v^{n}_{i}$ and $X^{n}_{i}$ are conditionally independent given
$Y^{n}_{i}$.

We use the binary classifier $f_{\theta}$ for the filtering procedure across
all systems $n$. With a slight abuse of notation, let
$f_{\theta}(\cdot)\in[0,1]$ now be the toxicity score instead of the predicted
class label. Specifically, the classifier outputs
$f_{\theta}(X^{n}_{i})\in[0,1]$ based on the observed features $X^{n}_{i}$ for
each job $i$. The system designer is tasked with choosing a threshold
$z_{\text{FL}}$ that affects the (triage) filtering level: an arriving job in
system $n$ can pass the filtering system and enter the queueing system if and
only if $f_{\theta}(X^{n}_{i})\geq z_{\text{FL}}$.111For simplicity, we only
consider filtering out clearly safe content in this section, though in
practice, the system designer can choose another threshold to filter out
clearly toxic contents from the human review process and directly take further
actions. Content that are filtered out are not reviewed and can remain on the
platform. A higher filtering level $z_{\text{FL}}$ filters more jobs out,
resulting in higher false negative rate (more filtering and misclassification
costs), fewer human reviewers required (lower hiring cost), and a complex
effect on the downstream queueing cost.

Each job that passes the filtering system is subsequently sent to human
reviewers (queueing system). Given the filtering level $z_{\text{FL}}$, we use
the same number of reviewers $\Gamma(z_{\text{FL}})$ across all systems, where
$\Gamma(z_{\text{FL}})$ is a predetermined decision variable, fixed in advance
and not subject to randomness. We assume that for each system $n$, all
reviewers have the same service rate for class $k$ jobs, i.e.,
$\mu_{k,r}^{n}=\mu_{k}^{n},~{}\forall~{}k\in\\{1,2\\}$ for each reviewer
$r\in[\Gamma(z_{\text{FL}})]$. To ensure workload equality and fairness among
reviewers, we assume jobs passing through the filtering system are assigned to
one and only one human reviewer with equal probability
$1/\Gamma(z_{\text{FL}}),$ _independently_ of any other random objects. Each
human reviewer operates their own single-server queueing system. The jobs
allocated to the $r$th reviewer corresponds to their arrival processes,
denoted as $A_{\text{ps},r}^{n}(t)$, which are splited from the common arrival
process after filtering, denoted as $A_{\text{ps},0}^{n}(t)$. For the $j$th
job passing through the filtering system, let
$\mathbf{B}^{n}_{j}:=(B_{j1}^{n},\ldots,B_{j\Gamma(z_{\text{FL}})}^{n})$ be
the one-hot encoded representation of the reviewer it is assigned to. Then,
$A_{\text{ps},r}^{n}(t):=\sum_{j=1}^{A_{\text{ps},0}^{n}(t)}B_{jr},~{}\forall~{}t\in[0,n],r\in[\Gamma(z_{\text{FL}})]$.

For simplicity, we assume all reviewers utilize $f_{\theta}$ to predict the
class labels of incoming jobs. The system designer must decide another
threshold $z_{\text{TX}}\geq z_{\text{FL}}$ that affects the toxicity
classification. In particular, for the $s$th job assigned to reviewer $r$, it
is predicted to be toxic (class 1), i.e., $\underline{Y}^{n}_{s1,r}=1$, if and
only if $f_{\theta}(X^{n}_{s,r})\geq z_{\text{TX}}$. We assume all human
reviewers adopt the same scheduling policy. Similar to our model in Section 2,
reviewers use the predicted class $\underline{\mathbf{Y}}^{n}_{s,r}$ and
feasible scheduling policies must satisfy a variant of Definition 1.

Throughout this section, we use $i$ when counting jobs that arrive at the
triage system; $j$ for jobs that pass the filtering system and arrive at the
queueing system; $s$ for jobs assigned to a human reviewer; and $r$ for human
reviewers (servers). For a stochastic process $A_{\text{ps},0}^{n}(t)$, the
subscript ps indicates processes associated with jobs passing through the
filter and arriving at the queueing system. We use the subscript $0$ to
indicate the total arrival process and $r$ to indicate processes associated
with the reviewer $r$. We denote our decision variables
$(z_{\text{FL}},z_{\text{TX}})$ by $\mathbf{z}$. We summarize our assumptions
for the AI-based triage system below.

######  Assumption F (Data generating processes for the AI-based triage
system).

For any system $n\in\mathbb{N}$, (i)
$\\{(u_{i}^{n},v_{i}^{n},X_{i}^{n},Y_{i}^{n}):i\in\mathbb{N}\\}$ is a sequence
of i.i.d. random vectors; (ii) $\\{u_{i}^{n}:i\in\mathbb{N}\\}$ and
$\\{(v_{i}^{n},X_{i}^{n},Y_{i}^{n}):i\in\mathbb{N}\\}$ are independent; (iii)
for any $i\in\mathbb{N}$, $v^{n}_{i}$ and $X^{n}_{i}$ are conditionally
independent given $Y^{n}_{i}$; (iv) $\\{\mathbf{B}^{n}_{j}:j\in\mathbb{N}\\}$
is a sequence of i.i.d. random vectors; (v)
$\\{\mathbf{B}^{n}_{j}:j\in\mathbb{N}\\}$ is independent of
$\\{u_{i}^{n}:i\in\mathbb{N}\\}$ and
$\\{(v_{i}^{n},X_{i}^{n},Y_{i}^{n}):i\in\mathbb{N}\\}$.

The data generating process for the AI-based triage system is crucial to our
analysis, because it enables the reduction of the scheduling problem for all
reviewers to stochastically identical single-server scheduling problems across
the reviewers. Assumption F (i), (iv) and (v) ensure that each reviewer $r$
has a single stream of jobs with i.i.d. tuples
$\\{(v^{n}_{s,r},X^{n}_{s,r},Y^{n}_{s,r}):s\in\mathbb{N}\\}$. More
importantly, the tuples associated with reviewer $r$ become _independent_ of
those of any other reviewers. This leads to the joint convergence of the
diffusion-scaled processes defined by
$\\{(v^{n}_{s,r},X^{n}_{s,r},Y^{n}_{s,r}):s\in\mathbb{N}\\}$ across all
reviewers $r\in[\Gamma(z_{\text{FL}})]$. In addition, similar to Section 2,
Assumption F (i), (iv), and (v) allow us to disentangle the interarrival times
$\\{u^{n}_{s,r}:s\in\mathbb{N}\\}$ from the filtering process, service
processes, and the covariates, ensuring the joint convergence of the
diffusion-scaled processes defined by $\\{u^{n}_{s,r}:s\in\mathbb{N}\\}$
across the reviewers $r\in[\Gamma(z_{\text{FL}})]$. Since Assumption F (ii)
and (v) imply independence between
$\\{(v^{n}_{s,r},X^{n}_{s,r},Y^{n}_{s,r}):s\in\mathbb{N}\\}_{r\in[\Gamma(z_{\text{FL}})]}$
and $\\{u^{n}_{s,r}:s\in\mathbb{N}\\}_{r\in[\Gamma(z_{\text{FL}})]}$, we can
derive the desired joint convergence (Lemma 30) and apply our _sample path
analysis at the reviewer level_. For further discussion, see Appendix G.1.

####  7.2 Heavy traffic conditions for the AI-based triage system

In the sequel, we assume the triage system operates under heavy traffic
conditions and analyze the limiting system. Denote the conditional probability
of a class $k$ job passing through the level $z$ as
$g_{k}^{n}(z):=\mathbb{P}^{n}[f_{\theta}(X_{i}^{n})\geq z\mid
Y_{ik}^{n}=1],~{}\forall~{}z\in[0,1],~{}k\in\\{1,2\\}$. Similar to Assumption
B, we adopt the following heavy traffic conditions for the AI-based triage
system.

######  Assumption G (Heavy traffic conditions for AI-based triage system).

Given a classifier $f_{\theta}$ and a sequence of triage systems, we assume
that there exist $\Lambda$, $\mu_{k}$, and $g_{k}:[0,1]\rightarrow[0,1]$ such
that (i) for any filtering level $z_{\text{FL}}\in[0,1]$ and class
$k\in\\{1,2\\}$, we have that

$\displaystyle n^{1/2}(\Lambda^{n}-\Lambda)\rightarrow 0,\quad
n^{1/2}(\mu_{k}^{n}-\mu_{k})\rightarrow 0,\quad
n^{1/2}(g_{k}^{n}(z_{\text{FL}})-g_{k}(z_{\text{FL}}))\rightarrow 0;$

(ii) given the filtering level $z_{\text{FL}}$, the number of hired reviewers
satisfies
$\Gamma(z_{\text{FL}})=\Lambda\sum_{k=1}^{2}\frac{p_{k}g_{k}(z_{\text{FL}})}{\mu_{k}}.$

We adopt Assumption G to ensure that each reviewer aligns with Assumption B.
Specifically, according to Assumption G (i) and [68, Theorem 9.5.1], we can
show that for each reviewer $r$, their class prevalence
$p^{n}_{k,r}(z_{\text{FL}}):=\mathbb{P}^{n}[Y_{sk,r}^{n}=1\mid
f_{\theta}(X^{n}_{s,r})\geq z_{\text{FL}}]$ and confusion matrix
$\underline{q}^{n}_{kl,r}(\mathbf{z}):=\mathbb{P}^{n}[\underline{Y}^{n}_{sl,r}=1\mid
f_{\theta}(X^{n}_{s,r})\geq z_{\text{FL}},Y_{sk,r}^{n}=1]$ all converge to
their limits $p_{k}(z_{\text{FL}})$ and $\underline{q}_{kl}(\mathbf{z})$ at
the rate of $o(n^{-1/2})$ (Lemma 32). We use $Q^{n}(\mathbf{z})$ and
$Q(\mathbf{z})$ to denote the prelimit and limiting confusion matrix for each
reviewer. In addition, by Assumption G (ii), we have that

$\displaystyle
n^{1/2}\Big{[}\frac{\Lambda^{n}}{\Gamma(z_{\text{FL}})}\sum\limits_{k=1}^{2}\frac{p_{k}^{n}g_{k}^{n}(z_{\text{FL}})}{\mu_{k}^{n}}-1\Big{]}\rightarrow
0,$ (7.1)

which indicates that each reviewer operates under heavy traffic conditions and
matches (2.2). According to Assumption G (ii), when all reviewers operates
under heavy traffic conditions, the number of reviewers is solely determined
by limiting traffic indensity and the filtering level $z_{\text{FL}}$. Thus,
our decision variables are filtering level $z_{\text{FL}}$ and toxicity level
$z_{\text{TX}}$, with the number of reviewers determined accordingly.
Intuitively, as the filtering level $z_{\text{FL}}$ increases, the traffic
intensity decreases and the number of reviewers hired also decreases.

Starting from Assumptions F and G, we first establish the joint convergence
result in Lemma 30. As Assumptions F and G are compatible with Assumptions A
and B, we derive a common probability space $\mathbb{P}_{\text{copy}}$ in
Lemma 31 and apply the previous results on single-server queueing systems to
each reviewer. This allows us to establish the limiting total cost of the
triage system in Section 7.3.

####  7.3 Total Cost of the AI-based triage system

Motivated by content moderation problems, we divide the total cost into four
components: filtering cost, hiring cost, misclassification cost, and queueing
cost. Since the P$c\mu$-rule is optimal for each single-server queueing system
under heavy traffic conditions, we can explicitly quantify the best possible
queueing cost of the limiting system under quadratic cost assumption
(Assumption E). This enables us to determine the limiting total cost and
minimize it to find the optimal filtering and classification levels
$(z_{\text{FL}},z_{\text{TX}})$ for a fixed classifier $f_{\theta}$. In the
following, we first define each cost component and then establish the limiting
total cost in Theorem 5.

######  Definition 4 (Total cost of the AI-based triage system).

Given a classifier $f_{\theta}$, filtering level $z_{\text{FL}}$, toxicity
level $z_{\text{TX}}$, the number of hired reviewers $\Gamma(z_{\text{FL}})$,
and a sequence of AI-based triage system, for a sequence of feasible policies
$\\{\text{$\pi_{n}$}\\}$, define the cost incurred as the following.

  1. (i)

(Filtering cost) For each job that is filtered out, the unit costs for toxic
and non-toxic jobs are $c_{\text{FL},1}>0$ and $c_{\text{FL},2}<0$. The total
filtering cost up to time $t\in[0,n]$ is

$G^{n}(t;z_{\text{FL}}):=c_{\text{FL},1}\sum_{i=1}^{A_{0}^{n}(t)}\mathbb{I}(f_{\theta}(X^{n}_{i})<z_{\text{FL}})\cdot
Y^{n}_{i1}+c_{\text{FL},2}\sum_{i=1}^{A_{0}^{n}(t)}\mathbb{I}(f_{\theta}(X^{n}_{i})<z_{\text{FL}})\cdot
Y^{n}_{i2},$

and $\tilde{G}^{n}(t;z_{\text{FL}}):=n^{-1}G^{n}(nt;z_{\text{FL}})$ is the
scaled filtering cost.

  2. (ii)

(Hiring Cost) Each reviewer costs $c_{r}>0$ per unit of time.

  3. (iii)

(Misclassification Cost) The per-job cost of false positive, false negative,
true positive, or true negative are
$c_{\text{fp}},c_{\text{fn}},c_{\text{tp}},c_{\text{tn}}$, respectively. The
total misclassification cost up to time $t$ is $M^{n}(\mathbf{z},t)$, and its
scaled counterpart is
$\tilde{M}^{n}(t;\mathbf{z}):=n^{-1}M^{n}(nt;\mathbf{z})$.

  4. (iv)

(Queueing Cost) For each system $n$ and reviewer $r$,
$J^{n}_{\text{$\pi_{n}$},r}(t;Q^{n}(\mathbf{z}))$ is the cumulative queueing
cost as defined in Section 3.1, and
$\tilde{J}^{n}_{\text{$\pi_{n}$},r}(t;Q^{n}(\mathbf{z})):=n^{-1}J^{n}_{\text{$\pi_{n}$},r}(nt;Q^{n}(\mathbf{z}))$
is its scaled counterpart.

The total cost incurred up to time $t$ is defined by

$F_{\text{$\pi_{n}$}}^{n}(t;\mathbf{z})=\underbrace{G^{n}(t;z_{\text{FL}})}_{\text{filtering}}+\underbrace{c_{r}\Gamma(z_{\text{FL}})t}_{\text{hiring}}+\underbrace{M^{n}(t;\mathbf{z})}_{\text{misclassification}}+\underbrace{\sum_{r=1}^{\Gamma(z_{\text{FL}})}J^{n}_{\text{$\pi_{n}$},r}(t;Q^{n}(\mathbf{z}))}_{\text{queueing}},~{}\forall~{}t\in[0,n],$

and
$\tilde{F}_{\text{$\pi_{n}$}}^{n}(t;\mathbf{z}):=n^{-1}F_{\text{$\pi_{n}$}}^{n}(nt;\mathbf{z})$
is its scaled counterpart.

For any filtering level $z_{\text{FL}}$ and toxicity level $z_{\text{TX}}$, we
can easily establish the optimal total cost of the AI-based triage system
under heavy traffic limits by extending Proposition 6, Theorem 3, and
Proposition 4. Such optimal cost can be achieved by applying the P$c\mu$-rule
to all reviewers as shown in (7.2).

######  Theorem 5 (Total cost the AI-based triage system).

Given a classifier $f_{\theta}$, filtering level $z_{\text{FL}}$, toxicity
level $z_{\text{TX}}$, the number of hired reviewers $\Gamma(z_{\text{FL}})$,
and a sequence of AI-based triage system, suppose that Assumptions E, F, G,
and H hold. There exists a common probability space $\mathbb{P}_{\text{copy}}$
such that

  1. (i)

(Lower bound) under any feasible policies $\\{\text{$\pi_{n}$}\\}$, the
associated total cost $\tilde{F}_{\text{$\pi_{n}$}}^{n}(t;\mathbf{z})$
satisfies
$\liminf\limits_{n}\tilde{F}_{\text{$\pi_{n}$}}^{n}(t;\mathbf{z})\geq\tilde{F}^{*}(t;\mathbf{z})$,
$\forall~{}t\in[0,1]~{}\mathbb{P}_{\text{copy}}-a.s.$. For the original
processes under $\mathbb{P}^{n}$, under any feasible policies
$\\{\pi^{\prime}_{n}\\}$,

$\liminf\limits_{n}\mathbb{P}^{n}[\tilde{F}_{\pi^{\prime}_{n}}^{n}(t;\mathbf{z})>x]\geq\mathbb{P}_{\text{copy}}[\tilde{F}^{*}(t;\mathbf{z})>x],~{}\forall
x\in\mathbb{R},t\in[0,1];$

  2. (ii)

(Optimality) under the P$c\mu$-rule, we have that
$\tilde{F}^{n}_{\text{Pc$\mu$}}(\cdot;\mathbf{z})\rightarrow\tilde{F}^{*}(\cdot;\mathbf{z})$
$\text{in }(\mathcal{D},\|\cdot\|),~{}\mathbb{P}_{\text{copy}}-a.s.$. For the
original processes under $\mathbb{P}^{n}$,
$\tilde{F}^{n}_{\text{Pc$\mu$}}(\cdot;\mathbf{z})\Rightarrow\tilde{F}^{*}(\cdot;\mathbf{z})$
$\text{in }(\mathcal{D},J_{1})$, and in particular,
$\mathbb{P}^{n}[\tilde{F}^{n}_{\text{Pc$\mu$}}(t;\mathbf{z})>x]\rightarrow\mathbb{P}_{\text{copy}}[\tilde{F}^{*}(t;\mathbf{z})>x],~{}\forall~{}x\in\mathbb{R},t\in[0,1]$.

Here, the optimal total cost $\tilde{F}^{*}(t;\mathbf{z})$ is defined as

$\tilde{F}^{*}(t;\mathbf{z}):=\tilde{G}^{*}(t;z_{\text{FL}})+c_{r}\Gamma(z_{\text{FL}})t+\tilde{M}^{*}(t;\mathbf{z})+\sum_{r=1}^{\Gamma(z_{\text{FL}})}\tilde{J}_{r}^{*}(t;Q(\mathbf{z})),$
(7.2)

where

$\displaystyle\tilde{G}^{*}(t;z_{\text{FL}})=\Lambda
t\cdot[c_{\text{FL},1}p_{1}(1-g_{1}(z_{\text{FL}}))+c_{\text{FL},2}p_{2}(1-g_{2}(z_{\text{FL}}))],$
$\displaystyle\tilde{M}^{*}(t;\mathbf{z})=\Lambda
t\cdot\big{[}p_{1}g_{1}(z_{\text{FL}})[c_{\text{tp}}\underline{q}_{11}(\mathbf{z})+c_{\text{fn}}\underline{q}_{12}(\mathbf{z})]+p_{2}g_{2}(z_{\text{FL}})[c_{\text{fp}}\underline{q}_{21}(\mathbf{z})+c_{\text{tn}}\underline{q}_{22}(\mathbf{z})]\big{]}$
$\displaystyle\tilde{J}_{r}^{*}(t;Q(\mathbf{z}))=\frac{\beta_{1}(Q(\mathbf{z}))\beta_{2}(Q(\mathbf{z}))}{2\big{[}\beta_{1}(Q(\mathbf{z}))+\beta_{2}(Q(\mathbf{z}))\big{]}}\int_{0}^{t}\tilde{W}_{+}(s;\mathbf{z},r)^{2}\mathrm{d}s,$

for all $t\in[0,1]$, and $\tilde{W}_{+}(t;\mathbf{z},r)$ is the limiting
remaining total workload process of reviewer $r$ as defined in Lemma 33.

According to Theorem 5, we can minimize (7.2) to find the optimal filtering
and toxicity levels $(z_{\text{FL}},z_{\text{TX}})$ for a given classifier
$f_{\theta}$. In particular, (7.2) depends solely on limiting exogenous
quantities such as $\Lambda$, $p_{k}(z_{\text{FL}})$,
$\underline{q}_{kl}(z_{\text{FL}})$ that can be easily estimated given a small
set of validation data. $\tilde{W}_{+}^{n}(t;\mathbf{z},r)$ is a reflected
Brownian motion with a known drift and covariance (see further discussion in
Appendix G.3), so we can estimate the total cost using a simulated (reflected)
Brownian motion. The optimal level $\mathbf{z}^{*}$ can be then found through
a simple line search over $[0,1]$. Our approach avoids traditional queueing
simulations, which can be costly and time-consuming, making it practical and
scalable for real-world applications.

####  7.4 Numerical Experiments for the AI-based triage system

Our formulation trades off multiple desiderata, in contrast to the standard
industry practice that choose $\mathbf{z}$ solely based on prediction metrics,
such as maximizing recall subject to a fixed high precision level [11]. To
compare our proposed approach with such standard triage design approaches, we
consider the 2-class content moderation problem described in Section 6. We
assume the covariates for positive and negative classes are generated in the
same fasion as in the 2d logistic regression problem in Section 6, and
consider the logistic regression classifier $f_{\theta}$ developed by
minimizing the equally-weighted cross-entropy loss ($w_{1}=1$, $w_{2}=1$). For
simplicity, we fix the toxicity level $z_{\text{TX}}=0.5$ and only study how
filtering level $z_{\text{FL}}$ affects the total cost.

We examine the setting where the positive class has a relatively high arrival
rate to mimic the setting where only flagged content is sent to the triage
system, which results in a relatively high proportion of positive class;
recall Figure 1. In particular, we set
$[\Lambda_{1},\Lambda_{2}]=[10000,40000]$, $[\mu_{1},\mu_{2}]=[50,200]$, where
$[\Lambda_{1},\Lambda_{2}]$ is the arrival rate of positive and negative
classes to the triage system, and $[\mu_{1},\mu_{2}]$ is the common service
rate for the positive and negative classes across all reviewers. We consider
three cases: (i) filtering costs dominate, (ii) hiring costs dominate, and
(iii) a trade-off between filtering cost and hiring costs. The filtering costs
and hiring costs are set as follows: (i)
$[c_{\text{FL},1},c_{\text{FL},2}]=[200,-3]$, $c_{r}=500$, (ii)
$[c_{\text{FL},1},c_{\text{FL},2}]=[20,-3]$, $c_{r}=5000$, and (iii)
$[c_{\text{FL},1},c_{\text{FL},2}]=[20,-3]$, $c_{r}=500$. In all cases, the
misclassification costs are set as
$[c_{\text{fp}},c_{\text{fn}},c_{\text{tp}},c_{\text{tn}}]=[3,3,-3,-3]$, and
the delay costs are set as $C_{\cdot}(t)=c_{\cdot}t^{2}/2$ with
$c_{1}=15,c_{2}=1$.

Our goal is to find the best filtering level $z_{\text{FL}}$ that minimizes
the total cost. We compare our method that minimizes (7.2) to the following
classical method from Chandak [11], which finds the filtering level
$z_{\text{FL}}$ by maximizing recall subject to a high precision level lower
bound $z_{\text{prec}}\in[0,1]$. 222We follow notations used in Chandak [11].
For the filtering system, precision and recall are calculated by treating safe
content as the positive class. Both methods can be effectively implemented
using small set of validation data and a linear search. We set the search
range for $z_{\text{FL}}$ as $[0.05,0.48]$.

(i) Filtering costs dominate

(ii) Hiring costs dominate

(iii) Trade-off between

filtering and hiring costs

Figure 8: For different methods, we consider the selected filtering level
$z_{\text{FL}}$ and present the associated estimated total cost of the AI-
based triage system. The classical method maximizes recall subject to the
precision level $[0.93,0.94,0.95,0.96,0.97]$, positioned from left to right.
This method exhibits highly varying total cost even at high precision levels,
making it hard to determine the best filtering level. In contrast, our method
effectively minimizes the total cost by cheap simulations of (reflected)
Brownian motion.

In Figure 8, we present the average total cost over 10K sample paths of the
simulated (reflected) Brownian motion, with $2\times$ the standard error
encapsulated in the orange brackets. For the classical method, we set the
precision level as $[0.93,0.94,0.95,0.96,0.97]$, positioned from left to
right. To facilitate comparison with our method, we normalize the estimated
total cost by that of our method. We observe that the classical method
exhibits highly varying total cost (by $\sim 10\%-250\%$) even at high
precision levels in Figure 8. This demonstrates the importance of selecting
the right filtering level to minimize the total cost. In addition, for the
classical method, it also shows the total cost is highly sensitive to the
precision level. Therefore, the precision level serves as an important
hyperparameter, and it is challenging to determine the best precision level
that corresponds to optimal filtering level using the classical method.

Such challenge arises since our method takes a holistic view of the entire
triage system, yet the classical method only considers the prediction metrics.
In our toy example, a higher precision level leads to a lower selected
filtering level $z_{\text{FL}}$, which results in lower filtering costs and
higher hiring costs. Figure 8 (i)(ii) corresponds to simpler settings where
the total cost aligns with prediction metrics. That is, when filtering costs
or hiring costs dominate, the total cost is monotone with respect to the
filtering level and thus the precision level, as shown in Figure 8 (i)(ii).
Therefore, when adopting the classical method, we can simply choose the
precision level at the search boundary, which yields a filtering level near
the search boundary that minimizes the total cost. In contrast, in Figure 8
(iii), where there is a trade-off between filtering and hiring costs, the
total cost is non-monotone and “U”-shaped with respect to the
precision/filtering level. In this case, prediction metrics fails to capture
the total cost. While hyperparameter (precision) tuning based on total costs
is possible, the classical method merely shifts our search space to
hyperparameters (precision levels). In other words, hyperparameter tuning is
equivalently to a naive line search for the decision variable (filtering level
$z_{\text{FL}}$) based on simulated total cost and the classical method does
not serve as effective objectives/metrics. More importantly, without our
Theorem 5, the total cost can only be estimtaed through multiple costly
simulations of the entire triage system. Our method, in contrast, effectively
identifies the correct objective and finds the best filtering level through
cheap simulations of (reflected) Brownian motion.

Our numerical experiments demonstrate the the effectiveness of our method and
the importance of taking a holistic view of the entire content moderation
system. We hope our method paves the way for more advanced system designs for
complex AI-based triage systems in practical use.

###  8 Discussion

Our work builds on the large literature on queueing, as well as the more
nascent study of decision-making problems with prediction models [4, 41, 57,
33, 12, 60]. Unlike previous works that study relatively simple optimization
problems (e.g., linear programming [19]) that take as input predictions, our
scheduling setting requires modeling the endogenous impact of
misclassifications.

####  8.1 Related work

Heavy traffic analysis allows circumventing the complexity of state/policy
spaces via state-space collapse, thereby identifying asymptotically optimal
queueing decisions [28, 40, 50, 63, 68]. The $c\mu$-rule was shown to be
optimal among priority rules in [15], and Van Mieghem [63] proved heavy
traffic optimality of the G$c\mu$-rule with convex delay costs in single-
server systems with general distributions of interarrival and service times.
Under a heavy traffic regime defined with a complete resource pooling
condition [27], Mandelbaum and Stolyar [40] extended the result to multi-
server and multi-class queues. In the many server Halfin-Whitt heavy traffic
regime (where the server pool is also scaled [26]), Gurvich and Whitt [25]
showed their state-dependent policy that minimizes the holding cost reduces to
a simple index-rule with linear holding costs, and to the G$c\mu$-rule with
convex costs. When customers in queues can abandon systems, a similar index
rule that accounts for the customer abandonment rate was shown to minimize the
long-run average holding cost under the many-server fluid limit [5].

We focus on the single-server model and relax a common assumption that the
class of every job is known. We study the impact of AI models in queueing
jobs, and use the heavy traffic limit to analyze the downstream impacts of
miclassifications. Our results provide a unified framework for evaluating and
selecting AI models for optimal queueing. Along the way, we also provide
rigorous proofs for the classical setting with known classes by proving
unjustified steps in Van Mieghem [63] and qualifying conditions under which
they hold.

The challenge of unknown traffic parameters was identified as early as Cox
[14]. Using an off-policy ML model in queueing systems was also proposed for
classifying jobs into different types or priority classes [57, 60] and
predicting service times [12]. Argon and Ziya [4], Singh et al. [57] focus on
minimizing the mean _stationary_ waiting time with Poisson arrivals, while we
allow general distributions of arrival and service times in our heavy traffic
analysis. Although Argon and Ziya [4, Section 8] proposes a policy similar in
form to the P$c\mu$-rule, their policy is compared to the FCFS policies in
terms of the stationary waiting time, while our analysis shows the optimality
of P$c\mu$-rule over all feasible policies in terms of cumulative cost. Sun et
al. [60] consider a two-class setting (triage or not) where classes can be
inferred with additional time, and analyze when it is optimal to triage all
(or no) jobs. Importantly, they assume service times follow predicted classes.
Chen and Dong [12] develop a two-class priority rule using predicted service
times and show the convergence of the queue length process to the same limit
as in the perfect information case when estimation error is sufficiently
small. In contrast, we characterize the optimal queueing cost given a fixed
classifier instead of aiming to match the performance of the perfect
classifier. Our approach allows us to provide guidance on model selection for
classifiers as we illustrate in Section 6.

Going beyond simple index policies, deep reinforcement learning (DRL)
algorithms can be used for queueing systems with unknown parameters. Dai and
Gluzman [16] develop a policy optimization approach for multiclass Markovian
queueing networks and proposes several variance reduction techniques. Pavse et
al. [47] combine proximal and trust region-based policy optimization
algorithms [55] with a Lyapunov-inspired technique to ensure stability.
Developing further approaches to overcome the challenges of applying RL
algorithms in queueing (e.g., infinite state spaces, unbounded costs) is a
fertile direction of future research.

There is a growing body of work on learning in queueing systems that focus on
_online_ learning and analyze regret, the performance gap between the learning
algorithm and the best policy in hindsight with the complete knowledge of
system parameters [16, 21, 22, 23, 34, 35, 36, 56, 65, 66, 70]. Inspired by
the well-known static priority policies in queueing literature [5, 6, 40, 48,
49, 63], empirical versions of such policies were proposed where plug-in
estimates of unknown parameters are used to compute static priorities. When
service rates are unknown, Krishnasamy et al. [35] propose an empirical $c\mu$
rule for multi-server settings and show constant regret for linear cost
functions, and Zhong et al. [70] develop an algorithm for learning service and
abandonment rates in time-varying multiclass queues with many servers and show
the empirical $c\mu/\theta$ rule achieves optimal regret. In the machine
scheduling literature, where a finite set of jobs are given (with no external
arrivals), Lee and Vojnovic [37] studies settings where delay costs are
unknown, and show that a plug-in version of the $c\mu$-rule can achieve near-
optimal regret when coupled with an exploration strategy.

For more general queueing networks, Walton and Xu [66] present a connection
between the MaxWeight policy [61] and Blackwell approachability [9], relating
the waiting time regret to that of a policy for learning service rates.
Borrowing insights from the stochastic multi-armed bandit literature [58], a
body of work [13, 34, 36, 59, 65] develops learning algorithms to minimize
expected queue length, addressing challenges in the queueing bandit model such
as ensuring stability until the parameters are sufficiently learned [36].
Freund et al. [22] propose a new performance measure of time-averaged queue
length, and show near-optimality of the upper-confidence bound (UCB) algorithm
in a single-queue multi-server setting, as well as new UCB-type variants of
MaxWeight and BackPressure [61] in multi-queue systems and queueing networks,
respectively. For queueing systems with multi-server multiclass jobs, Yang et
al. [69] recently developed another UCB-type variant of the MaxWeight
algorithm. Learning service rates has also been studied in decentralized
queueing systems, where classes of jobs are considered as strategic agents
[21, 23, 56] and stability is a primary concern. Motivated by content
moderation, a concurrent work [38] studies the joint decision of content
classification, and admission and scheduling for human review in an online
learning framework.

####  8.2 Future directions

We discuss limitations of our framework and pose future directions of
research. First, implementing the P$c\mu$-rule needs more information than the
previous index-based policies. It necessitates arrival information, $\lambda$
and $\\{p_{k}\\}_{k\in[K]}$, as well as the misclassification probabilities
$Q^{n}=(\underline{q}_{kl}^{n})_{k,l\in[K]}$. In practice, such parameters
need to be estimated on a limited amount of data and estimation errors are
unavoidable.

###### Extension of the queueing model

We identify conceptual and analytical challenges in extending our framework to
the multiserver setting. Modeling the extension after Mandelbaum and Stolyar
[40] who consider known true classes, we can posit the complete resource
pooling (CRP) condition. This condition requires the limit of the arrival
rates to be located in the outer face of the stability region, and to be
uniquely represented as a maximal allocation of the servers’ service capacity.
For our setting in Section 2, the main challenge is that the CRP condition
will not necessarily hold on the arrival and service rates of the predicted
classes. Because the service rate of each predicted class in prelimit will be
a mixture of the original service rates as $\underline{\mu}_{l}^{n}$ in
Definition 10, the CRP condition on true classes may not be preserved for
predicted classes.

Understanding of how prediction error interacts with queueing performance
under general dynamics is an important direction of future research. For
example, when jobs exhibit abandonment behavior, a suitable adjustment to the
c$\mu$-rule minimizes the long-run holding cost under many-server fluid
scaling [5]. Policies that simultaneously account for predictive error and job
impatience may yield fruit.

###### Design of queueing systems under class uncertainty

While we focus on optimal scheduling, an even more important operational lever
is the _design_ of the queueing system [20, 30]. For example, designing
priority classes that account for predictive error is a promising research
direction [12]. In our model, if we keep the limiting distributions of the
interarrival and service times the same, class designs satisfying the heavy
traffic condition (2.2) should have an identical limiting total workload
$\tilde{W}_{+}$ by Proposition 1, implying similar forms of the lower bound in
(3.3). Given this observation, we may investigate how class design interacts
with the AI model’s predictive performance.

###### Combining the P$c\mu$-rule with AI-based approaches

The performance of RL algorithms degrade under distribution shift, and simple
index-based policies may offer robustness benefits. The two approaches may
provide synergies. For example, we can pre-train a policy to initially imitate
an index-based policy, and then fine-tune it to maximize performance in
specific environments.

For quadratic costs, we showed the effectiveness of using the relative regret
$\tilde{J}^{*}(\cdot;Q)$ to select the classification threshold.
Alternatively, we could directly fine-tune the classifier to minimize this
metric, which may further enhance downstream queueing performance, albeit at
the cost of increased engineering complexity.

### References

  * Fac [2020] How facebook uses super-efficient ai models to detect hate speech.  https://ai.meta.com/blog/how-facebook-uses-super-efficient-ai-models-to-detect-hate-speech, 2020.
  * Met [2021] Harmful content can evolve quickly. our new ai system adapts to tackle it.  https://ai.meta.com/blog/harmful-content-can-evolve-quickly-our-new-ai-system-adapts-to-tackle-it, 2021.
  * Allouah et al. [2023] A. Allouah, C. Kroer, X. Zhang, V. Avadhanula, N. Bohanon, A. Dania, C. Gocmen, S. Pupyrev, P. Shah, N. Stier-Moses, and K. R. Taarup.  Fair allocation over time, with applications to content moderation.  In _Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD)_ , pages 25––35, 2023.
  * Argon and Ziya [2009] N. T. Argon and S. Ziya.  Priority assignment under imperfect information on customer type identities.  _Manufacturing & Service Operations Management_, 11(4):674–693, 2009.
  * Atar et al. [2010] R. Atar, C. Giat, and N. Shimkin.  The $c\mu/\theta$ rule for many-server queues with abandonment.  _Operations Research_ , 58(5):1427–1439, 2010.
  * Atar et al. [2011] R. Atar, C. Giat, and N. Shimkin.  On the asymptotic optimality of the $c\mu/\theta$ rule under ergodic cost.  _Queueing Systems_ , 67:127–144, 2011.
  * Billingsley [1999] P. Billingsley.  _Convergence of Probability Measures_.  Wiley, Second edition, 1999.
  * Black et al. [2022] E. Black, M. Raghavan, and S. Barocas.  Model multiplicity: Opportunities, concerns, and solutions.  In _Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency_ , pages 850–863, 2022.
  * Blackwell [1956] D. Blackwell.  An analog of the minimax theorem for vector payoffs.  _Pacific Journal of Mathematics_ , 6(1):1–8, Spring 1956.
  * Borkan et al. [2019] D. Borkan, L. Dixon, J. Sorensen, N. Thain, and L. Vasserman.  Nuanced metrics for measuring unintended bias with real data for text classification.  In _Proceedings of the 2019 World Wide Web Conference_ , pages 491–500, 2019.
  * Chandak [2023] A. Chandak.  Augmenting our content moderation efforts through machine learning and dynamic content prioritization, 2023.  URL https://www.linkedin.com/blog/engineering/trust-and-safety/augmenting-our-content-moderation-efforts-through-machine-learni.  Accessed Mar 2024.
  * Chen and Dong [2021] Y. Chen and J. Dong.  Scheduling with service-time information: The power of two priority classes.  _arXiv:2105.10499 [math.OC]_ , 2021.
  * Choudhury et al. [2021] T. Choudhury, G. Joshi, W. Wang, and S. Shakkottai.  Job dispatching policies for queueing systems with unknown service rates.  In _22nd International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing_ , pages 181––190. Association for Computing Machinery, 2021.
  * Cox [1966] D. R. Cox.  Some problems of statistical analysis connected with congestion (with discussion).  In _Proceedings of the Symposium on Congestion Theory_ , pages 289–316. Chapel Hill, North Carolina: University of North Carolina Press, 1966.
  * Cox and Smith [1961] D. R. Cox and W. L. Smith.  _Queues_ , volume 2.  Methuen, 1961.
  * Dai and Gluzman [2021] J. G. Dai and M. Gluzman.  Queueing network controls via deep reinforcement learning.  _Stochastic Systems_ , pages 1–38, 2021.
  * D’Amour et al. [2022] A. D’Amour, K. Heller, D. Moldovan, B. Adlam, B. Alipanahi, A. Beutel, C. Chen, J. Deaton, J. Eisenstein, M. D. Hoffman, et al.  Underspecification presents challenges for credibility in modern machine learning.  _Journal of Machine Learning Research_ , 23(226):1–61, 2022.
  * Durrett [2010] R. Durrett.  _Probability: Theory and Examples_.  Cambridge University Press, 2010.
  * Elmachtoub and Grigas [2021] A. N. Elmachtoub and P. Grigas.  Smart ”predict, then optimize”.  _Management Science_ , 2021.
  * Feldman et al. [2008] Z. Feldman, A. Mandelbaum, W. A. Massey, and W. Whitt.  Staffing of time-varying queues to achieve time-stable performance.  _Management Science_ , 54(2):324–338, 2008.
  * Freund et al. [2022] D. Freund, T. Lykouris, and W. Weng.  Efficient decentralized multi-agent learning in asymmetric bipartite queueing systems.  _arXiv:2206.03324 [cs.LG]_ , 2022.
  * Freund et al. [2023] D. Freund, T. Lykouris, and W. Weng.  Quantifying the cost of learning in queueing systems.  _arXiv:2308.07817 [cs.LG]_ , 2023.
  * Gaitonde and Tardos [2023] J. Gaitonde and É. Tardos.  The price of anarchy of strategic queuing systems.  _Journal of the ACM_ , 70(20):1–63, May 2023.
  * Glynn [1990] P. W. Glynn.  Chapter 4 diffusion approximations.  In _Stochastic Models_ , volume 2 of _Handbooks in Operations Research and Management Science_ , pages 145–198. Elsevier, 1990.
  * Gurvich and Whitt [2008] I. Gurvich and W. Whitt.  Scheduling flexible servers with convex delay costs in many-server service systems.  _Manufacturing & Service Operations Management_, 11(2):237–253, 2008.
  * Halfin and Whitt [1981] S. Halfin and W. Whitt.  Heavy-traffic limits for queues with many exponential servers.  _Operations Research_ , 29(3):567–587, 1981.
  * Harrison and López [1999] J. M. Harrison and M. J. López.  Heavy traffic resource pooling in parallel‐server systems.  _Queueing Systems_ , 33:339–368, 1999.
  * Harrison and Zeevi [2004] J. M. Harrison and A. Zeevi.  Dynamic scheduling of a multiclass queue in the halfin-whitt heavy traffic regime.  _Operations Research_ , 52(2):243–257, 2004.
  * Henderson et al. [2018] P. Henderson, R. Islam, P. Bachman, J. Pineau, D. Precup, and D. Meger.  Deep reinforcement learning that matters.  In _Thirty-Second AAAI Conference on Artificial Intelligence_. AAAI Press, 2018.
  * Jennings et al. [1996] O. B. Jennings, A. Mandelbaum, W. A. Massey, and W. Whitt.  Server staffing to meet time-varying demand.  _Management Science_ , 42(10):1383–1394, 1996.
  * Kallenberg [1997] O. Kallenberg.  _Foundations of Modern Probability_.  Springer, 1997.
  * Koh et al. [2020] P. W. Koh, S. Sagawa, H. Marklund, S. M. Xie, M. Zhang, A. Balsubramani, W. Hu, M. Yasunaga, R. L. Phillips, S. Beery, et al.  Wilds: A benchmark of in-the-wild distribution shifts.  _arXiv:2012.07421 [cs.LG]_ , 2020.
  * Kotary et al. [2021] J. Kotary, F. Fioretto, P. Van Hentenryck, and B. Wilder.  End-to-end constrained optimization learning: A survey.  _arXiv:2103.16378 [cs.LG]_ , 2021.
  * Krishnasamy et al. [2016] S. Krishnasamy, R. Sen, R. Johari, and S. Shakkottai.  Regret of queueing bandits.  In _Advances in Neural Information Processing Systems 16_ , volume 29, 2016.
  * Krishnasamy et al. [2018] S. Krishnasamy, A. Arapostathis, R. Johari, and S. Shakkottai.  On learning the $c\mu$ rule in single and parallel server networks.  _arXiv:1802.06723 [cs.PF]_ , 2018.
  * Krishnasamy et al. [2021] S. Krishnasamy, R. Sen, R. Johari, and S. Shakkottai.  Learning unknown service rates in queues: A multiarmed bandit approach.  _Operations Research_ , 69(1):315–330, 2021.
  * Lee and Vojnovic [2021] D. Lee and M. Vojnovic.  Scheduling jobs with stochastic holding costs.  In _Advances in Neural Information Processing Systems 21_ , 2021.
  * Lykouris and Weng [2024] T. Lykouris and W. Weng.  Learning to defer in content moderation: The human-ai interplay.  _arXiv:2402.12237 [cs.LG]_ , 2024.
  * Makhijani et al. [2021] R. Makhijani, P. Shah, V. Avadhanula, C. Gocmen, N. E. Stier-Moses, and J. Mestre.  Quest: Queue simulation for content moderation at scale.  _arXiv:2103.16816_ , 2021.
  * Mandelbaum and Stolyar [2004] A. Mandelbaum and A. L. Stolyar.  Scheduling flexible servers with convex delay costs: Heavy-traffic optimality of the generalized c$\mu$-rule.  _Operations Research_ , 52(6):836–855, 2004.
  * Mišić and Perakis [2020] V. V. Mišić and G. Perakis.  Data analytics in operations management: A review.  _Manufacturing & Service Operations Management_, 22(1):158–169, 2020.
  * Mnih et al. [2013] V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller.  Playing Atari with deep reinforcement learning.  _arXiv:1312.5602 [cs.LG]_ , 2013.
  * Mörters and Peres [2010] P. Mörters and Y. Peres.  _Brownian Motion_.  Cambridge University Press, 2010.
  * Namkoong et al. [2022] H. Namkoong, Y. Ma, and P. W. Glynn.  Minimax optimal estimation of stability under distribution shift.  _arXiv:2212.06338 [stat.ML]_ , 2022.
  * Pang et al. [2007] G. Pang, R. Talreja, and W. Whitt.  Martingale proofs of many-server heavy-traffic limits for Markovian queues.  _Probability Surveys_ , 4:193–267, 2007.
  * Papadimitriou and Tsitsiklis [1994] C. H. Papadimitriou and J. N. Tsitsiklis.  The complexity of optimal queueing network control.  In _Proceedings of IEEE 9th Annual Conference on Structure in Complexity Theory_ , pages 318–322. IEEE, 1994.
  * Pavse et al. [2023] B. S. Pavse, Y. Chen, Q. Xie, and J. P. Hanna.  Tackling unbounded state spaces in continuing task reinforcement learning.  _arXiv:2306.01896 [cs.LG]_ , 2023.
  * Puha and Ward [2019] A. L. Puha and A. R. Ward.  Scheduling an overloaded multiclass many-server queue with impatient customers.  _INFORMS TutORials in Operations Research_ , pages 189–217, 2019.
  * Puha and Ward [2021] A. L. Puha and A. R. Ward.  Fluid limits for multiclass many-server queues with general reneging distributions and head-of-the-line scheduling.  _Mathematics of Operations Research_ , 47(2):1192–1228, 2021.
  * Reiman [1984] M. I. Reiman.  Some diffusion approximations with state space collapse.  In _Modelling and Performance Evaluation Methodology_ , pages 207–240. Springer, 1984.
  * Royden [1988] H. Royden.  _Real Analysis_.  Pearson, third edition, 1988.
  * Sagawa et al. [2019] S. Sagawa, P. W. Koh, T. B. Hashimoto, and P. Liang.  Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization.  In _Proceedings of the Seventh International Conference on Learning Representations_ , 2019.
  * Sanh et al. [2019] V. Sanh, L. Debut, J. Chaumond, and T. Wolf.  Distilbert, a distilled version of BERT: smaller, faster, cheaper and lighter.  _arXiv:1910.01108 [cs.CL]_ , 2019.
  * Schroepfer [2019] M. Schroepfer.  Community standards report, 2019.  URL https://ai.meta.com/blog/community-standards-report.  Accessed Apr 2024.
  * Schulman et al. [2015] J. Schulman, S. Levine, P. Abbeel, M. Jordan, and P. Moritz.  Trust region policy optimization.  In _Proceedings of the 32nd International Conference on Machine Learning_ , volume 37 of _Proceedings of Machine Learning Research_ , pages 1889–1897, Lille, France, 07–09 Jul 2015. PMLR.
  * Sentenac et al. [2021] F. Sentenac, E. Boursier, and V. Perchet.  Decentralized learning in online queuing systems.  In _Advances in Neural Information Processing Systems 34_ , volume 34, pages 18501–18512, 2021.
  * Singh et al. [2020] S. Singh, I. Gurvich, and J. A. Van Mieghem.  Feature-based design of priority queues: Digital triage in healthcare.  _SSRN3731865_ , 2020.  URL http://dx.doi.org/10.2139/ssrn.3731865.
  * Slivkins [2019] A. Slivkins.  Introduction to multi-armed bandits.  _arXiv:1904.07272 [cs.LG]_ , 2019.
  * Stahlbuhk et al. [2021] T. Stahlbuhk, B. Shrader, and E. Modiano.  Learning algorithms for minimizing queue length regret.  _IEEE Transactions on Information Theory_ , 67(3):1759–1781, 2021.
  * Sun et al. [2022] Z. Sun, N. T. Argon, and S. Ziya.  When to triage in service systems with hidden customer class identities?  _Production and Operations Management_ , 31(1):172–193, 2022.
  * Tassiulas and Ephremides [1992] L. Tassiulas and A. Ephremides.  Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks.  _IEEE Transactions on Automatic Control_ , 37:1936–1948, 1992.
  * [62] Tiktok Content Moderation.  Our approach to content moderation.  https://www.tiktok.com/transparency/en/content-moderation/.
  * Van Mieghem [1995] J. A. Van Mieghem.  Dynamic scheduling with convex delay costs: The generalized c-$\mu$ rule.  _Annals of Applied Probability_ , pages 809–833, 1995.
  * Vincent [2020] J. Vincent.  Facebook is now using ai to sort content for quicker moderation, 2020.  URL https://www.theverge.com/2020/11/13/21562596/facebook-ai-moderation.  Accessed Apr 2024.
  * Walton [2014] N. Walton.  Two queues with non-stochastic arrivals.  _Operations Research Letters_ , 42(1):53–57, 2014.
  * Walton and Xu [2021] N. Walton and K. Xu.  Learning and information in stochastic networks and queues.  In _Tutorials in Operations Research: Emerging Optimization Methods and Modeling Techniques with Applications_ , pages 161–198. INFORMS, 2021.
  * Wang et al. [2021] S. Wang, H. Fang, M. Khabsa, H. Mao, and H. Ma.  Entailment as few-shot learner.  _arXiv:2104.14690 [cs.CL]_ , 2021.
  * Whitt [2002] W. Whitt.  _Stochastic Process Limits: An Introduction to Stochastic Process Limits and Their Application to Queues_.  Springer Science & Business Media, 2002.
  * Yang et al. [2023] Z. Yang, R. Srikant, and L. Ying.  Learning while scheduling in multi-server systems with unknown statistics: Maxweight with discounted ucb.  In _Proceedings of the 26 International Conference on Artificial Intelligence and Statistics_ , volume 206 of _Proceedings of Machine Learning Research_ , pages 4275–4312. PMLR, 2023.
  * Zhong et al. [2022] Y. Zhong, J. R. Birge, and A. R. Ward.  Learning the scheduling policy in time-varying multiclass many server queues with abandonment.  _Available at SSRN_ , 2022.  URL http://dx.doi.org/10.2139/ssrn.4090021.

## Appendices

###  Appendix A Diffusion limits

We consider the following processes: partial sum process of interarrival time
$U_{0}^{n}(t)$ that depends solely on $\\{u_{i}^{n}:i\in\mathbb{N}\\}$,
partial sum process of service time $V_{0}^{n}$ and two other processes
$\underline{\mathbf{Z}}^{n}:=(\underline{Z}_{kl}^{n})_{k,l\in[K]},\underline{\mathbf{R}}^{n}:=(\underline{R}^{n}_{l})_{l\in[K]}$
that solely relies on $\\{(X_{i}^{n},Y_{i}^{n},v_{i}^{n}):i\in\mathbb{N}\\}$.
In particular, given system $n$, $\underline{Z}_{kl}^{n}(t)$ is the total
number of jobs from real class $k$ and predicted as class $l$ and
$\underline{R}_{l}^{n}(t)$ is the total service time requested by jobs
predicted as class $l$, among the first $\lfloor t\rfloor$ jobs arriving in
the system:

$\underline{Z}_{kl}^{n}(t):=\sum_{i=1}^{\lfloor
t\rfloor}Y_{ik}^{n}\underline{Y}_{il}^{n},\quad\underline{R}_{l}^{n}(t):=\sum_{i=1}^{\lfloor
t\rfloor}\underline{Y}_{il}^{n}v_{i}^{n},\quad t\in[0,n].$

For any $n\in\mathbb{N}$ and $t\in[0,1]$, let
$\tilde{U}_{0}^{n},\tilde{V}_{0}^{n},\underline{\tilde{\mathbf{Z}}}^{n}:=(\underline{\tilde{Z}}_{kl}^{n})_{k,l\in[K]},\underline{\tilde{\mathbf{R}}}^{n}:=(\underline{\tilde{R}}^{n}_{l})_{l\in[K]}$
be the diffusion-scaled process, where

$\tilde{U}_{0}^{n}(t)=n^{-1/2}[U_{0}^{n}(nt)-(\lambda^{n})^{-1}\cdot
nt],\quad\tilde{V}_{0}^{n}(t)=n^{-1/2}[V_{0}^{n}(nt)-\sum_{k=1}^{n}\frac{p^{n}_{k}}{\mu^{n}_{k}}\cdot
nt],\quad t\in[0,1];$ (A.1)

and formal definitions of $\underline{\tilde{\mathbf{Z}}}^{n}$ and
$\underline{\tilde{\mathbf{R}}}^{n}$ are deferred to Definition 8. In
Assumption H to come, we state basic moment conditions that allows the
application of the martingale FCLT.

######  Lemma 3 (Joint weak convergence).

Suppose that Assumptions A, B, and H hold. Then, there exist Brownian motions
$(\tilde{U}_{0},\underline{\tilde{\mathbf{Z}}},\underline{\tilde{\mathbf{R}}},\tilde{V}_{0})$
such that

$\displaystyle(\tilde{U}_{0}^{n},\underline{\tilde{\mathbf{Z}}}^{n},\underline{\tilde{\mathbf{R}}}^{n},\tilde{V}_{0}^{n})\Rightarrow(\tilde{U}_{0},\underline{\tilde{\mathbf{Z}}},\underline{\tilde{\mathbf{R}}},\tilde{V}_{0})\quad\text{\quad
in $(D^{K(K+1)+2},WJ_{1})$.}$

Deferring a detailed proof to Section A.2, we highlight the main ingredients
of the joint convergence result. Our main observation is that the diffusion-
scaled processes admit a martingale central limit result when
$\\{(u^{n}_{i},v^{n}_{i},X^{n}_{i},Y^{n}_{i}):i\in\mathbb{N}\\}$ are i.i.d.
(Assumption A (i)) and $v^{n}_{i}\perp X^{n}_{i}\mid Y^{n}_{i}$ (Assumption A
(iii)). This allows us to show the weak convergence
$\tilde{U}_{0}^{n}\Rightarrow\tilde{U}_{0}$ in $(\mathcal{D},J_{1})$ and
$(\underline{\tilde{\mathbf{Z}}}^{n},\underline{\tilde{\mathbf{R}}}^{n},\tilde{V}_{0}^{n})\Rightarrow(\underline{\tilde{\mathbf{Z}}},\underline{\tilde{\mathbf{R}}},\tilde{V}_{0})$
in $(\mathcal{D}^{K(K+1)+1},WJ_{1})$. Since $\\{u^{n}_{i}\\}$ and
$\\{(v_{i}^{n},X_{i}^{n},Y_{i}^{n})\\}$ are independent (Assumption A (ii)),
we can obtain the desired joint convergence (e.g., see Whitt [68, Theorem
11.4.4] which we give as Lemma 9).

Building off of our diffusion limit, we can strengthen the convergence to the
uniform topology using standard tools (e.g., see Lemma 6 and Lemma 7), and
conduct a sample path analysis where we construct _copies_ of
$(\tilde{U}_{0}^{n},\underline{\tilde{\mathbf{Z}}}^{n},\underline{\tilde{\mathbf{R}}}^{n},\tilde{V}_{0}^{n})$
and
$(\tilde{U}_{0},\underline{\tilde{\mathbf{Z}}},\underline{\tilde{\mathbf{R}}},\tilde{V}_{0})$
that are identical in distribution with their original counterparts and
converge almost surely under a common probability space. Abusing notation, we
use the same notation for the newly construced processes.

######  Lemma 4 (Uniform convergence).

Suppose that Assumptions A, B, and H hold. Then, there exist stochastic
processes
$(\tilde{U}_{0}^{n},\underline{\tilde{\mathbf{Z}}}^{n},\underline{\tilde{\mathbf{R}}}^{n},\tilde{V}_{0}^{n}),~{}\forall~{}n\geq
1$ and
$(\tilde{U}_{0},\underline{\tilde{\mathbf{Z}}},\underline{\tilde{\mathbf{R}}},\tilde{V}_{0})$
defined on a common probability space
$(\Omega_{\text{copy}},\mathcal{F}_{\text{copy}},\mathbb{P}_{\text{copy}})$
such that
$(\tilde{U}_{0}^{n},\underline{\tilde{\mathbf{Z}}}^{n},\underline{\tilde{\mathbf{R}}}^{n},\tilde{V}_{0}^{n}),~{}\forall~{}n\geq
1$ and
$(\tilde{U}_{0},\underline{\tilde{\mathbf{Z}}},\underline{\tilde{\mathbf{R}}},\tilde{V}_{0})$
are identical in distribution with their original counterparts and

$\displaystyle(\tilde{U}_{0}^{n},\underline{\tilde{\mathbf{Z}}}^{n},\underline{\tilde{\mathbf{R}}}^{n},\tilde{V}_{0}^{n})\rightarrow(\tilde{U}_{0},\underline{\tilde{\mathbf{Z}}},\underline{\tilde{\mathbf{R}}},\tilde{V}_{0})\quad\text{\quad
in
$(\mathcal{D}^{K(K+1)+2},\|\cdot\|)$,}\quad\mathbb{P}_{\text{copy}}\text{-a.s.}.$
(A.2)

We defer a detailed proof to Section A.3 since it is a basic consequence of
the Skorokhod representation theorem [7, Theorem 6.7]. Since the diffusion
limits
$(\tilde{U}_{0},\underline{\tilde{\mathbf{Z}}},\underline{\tilde{\mathbf{R}}},\underline{\tilde{V}}_{0})$
are multidimensional Brownian motions, the copied processes of
$(\tilde{U}_{0}^{n},\underline{\tilde{\mathbf{Z}}}^{n},\underline{\tilde{\mathbf{R}}}^{n},\underline{\tilde{V}}_{0}^{n})$
jointly converge to a continuous limit almost surely. We obtain the result by
noting that convergence in $J_{1}$ to a deterministic and continuous limit is
equivalent to uniform convergence on compact intervals (e.g., see Glynn [24,
Proposition 4] stated in Lemma 7).

Sample path analysis allows us to leverage properties of uniform convergence
and significantly simplifies our analysis. All subsequent results and their
proofs in the appendix, will be established on the copied processes in the
common probability space
$(\Omega_{\text{copy}},\mathcal{F}_{\text{copy}},\mathbb{P}_{\text{copy}})$
with probability one, i.e., $\mathbb{P}_{\text{copy}}\text{-}a.s.$, and all of
the convergence results will be understood to hold in the uniform norm
$\|\cdot\|$. Moreover, since these newly constructed processes are identical
in distribution with their original counterparts, all subsequent results
regarding almost sure convergence for the copied processes can be converted
into corresponding weak convergence results for the original processes; see
more discussion in Theorems 2 and 3.

To show the above result, we first introduce a uniform integrability condition
that allows us to apply the martigale FCLT.

######  Assumption H (Uniform integrability).

For any system $n\in\mathbb{N}$, we assume that

  1. (i)

$\mathbb{E}^{n}[(u_{1}^{n})^{2}]<\infty$,
$\mathbb{E}^{n}[(v_{1}^{n})^{2}]<\infty$,
$\mathbb{E}^{n}[(X_{1}^{n})^{2}]<\infty$, and there exists fuctions $g_{u}$
and $g_{v}$ such that $g_{u}(x)\rightarrow 0$, $g_{v}(x)\rightarrow 0$ as
$x\rightarrow\infty$ and for any $n\in\mathbb{N}$ and $x\in\mathbb{R}$,

$\displaystyle\mathbb{E}^{n}[(u_{1}^{n})^{2}\mathbf{1}\left\\{u_{1}^{n}>x\right\\}]\leq
g_{u}(x),\quad\mathbb{E}^{n}[(v_{1}^{n})^{2}\mathbf{1}\left\\{v_{1}^{n}>x\right\\}]\leq
g_{v}(x);$

  2. (ii)

There exist constants $\alpha_{u}\in(0,\infty)$ and
$\alpha_{v,k}\in(0,\infty)$ for any $k\in[K]$ such that

$\displaystyle\alpha_{u}^{n}:=\mathbb{E}^{n}[(u_{1}^{n})^{2}]\rightarrow\alpha_{u},\quad\alpha_{v,k}^{n}:=\mathbb{E}^{n}[(v_{1}^{n})^{2}|Y_{1k}^{n}=1]\rightarrow\alpha_{v,k}$

as $n\rightarrow\infty$.

For completeness, we review the martingale FCLT and Skorohod representation
result before proving the main results of Section 2.

####  A.1 Review of basic results

We review classical results on the martingale FCLT and the Skorohod
construction.

#####  A.1.1 Martigale Functional Central Limit Theorem

Our proof of Lemma 3 primarily relies on the martingale FCLT [45, Theorem
8.1]. We define the maximum jump and the optional quadratic variation of
processes and review the martingale FCLT in Lemma 5.

Let $\mathcal{D}_{[0,\infty)}:=\mathcal{D}([0,\infty),\mathbb{R})$ be the set
of right-continuous with left limits (RCLL) functions
$[0,\infty)\to\mathbb{R}$, and
$\mathcal{D}^{k}_{[0,\infty)}:=\mathcal{D}([0,\infty),\mathbb{R}^{k})$ be the
product space
$\mathcal{D}_{[0,\infty)}\times\cdots\times\mathcal{D}_{[0,\infty)}$ for
$k\in\mathbb{N}$. With a slight abuse of notations, we also use $J_{1}$ to
denote be the standard Skorohod $J_{1}$ topology on $\mathcal{D}_{[0,\infty)}$
and $WJ_{1}$ to denote the product $J_{1}$ topology on
$\mathcal{D}_{[0,\infty)}^{k}$.

######  Definition 5 (Maximum jump).

For any function $x\in\mathcal{D}_{[0,\infty)}$, the maximum jump of $x$ up to
time $t$ is represented as

$J(x,t):=\sup\\{|x(s)-x(s^{-})|:0<s\leq t\\},\quad t>0.$ (A.3)

######  Definition 6 (Optional quadratic variation).

Let $M_{1}$ and $M_{2}$ be two martingales in $\mathcal{D}_{[0,\infty)}$ with
respect to a filtration $\mathcal{F}\equiv\\{\mathcal{F}_{t}:t\geq 0\\}$
satisfying $M_{1}(0)=M_{2}(0)=0$. The optional quadratic variation between
$M_{1}$ and $M_{2}$ is defined as

$[M_{1},M_{2}](t)=\lim\limits_{m\rightarrow\infty}\sum\limits_{i=1}^{\infty}\big{(}M_{1}(t_{m,i})-M_{1}(t_{m,i-1})\big{)}\big{(}M_{2}(t_{m,i})-M_{2}(t_{m,i-1})\big{)},\quad
t>0,$ (A.4)

where $t_{m,i}=\min(t,i2^{-m})$.

Pang et al. [45, Theorem 3.2] shows that $[M_{1},M_{2}](t)$ is well-defined
for any martingales pairs $(M_{1},M_{2})$ satisfying conditions outlined in
Definition 6.

######  Lemma 5 (Multidimensional martingale FCLT).

For $n\geq 1$, let $\mathbf{M}^{n}\equiv(M^{n}_{1},\ldots,M^{n}_{k})$ be a
martingale in $(\mathcal{D}_{[0,\infty)}^{k},WJ_{1})$ with respect to a
filtration $\mathcal{F}_{n}\equiv\left\\{\mathcal{F}_{n,t}:t\geq 0\right\\}$
satisfying $\mathbf{M}^{n}(0)=$ $(0,\ldots,0)$. If both of the following
conditions hold

  1. (i)

the expected maximum jump is asymptotically negligible:
$\lim_{n\rightarrow\infty}\mathbb{E}[J(M^{n}_{i},T)]=0,~{}\forall~{}i\in[k],~{}\forall~{}T\geq
0;$

  2. (ii)

there exists a positive semidefinite symmetric matrix
$\mathbf{A}=\\{a_{ij}\\}_{i,j\in[k]}\in\mathbb{R}^{k\times k}$ such that for
any $1\leq i,j\leq k$ and $t>0$, $[M^{n}_{i},M^{n}_{j}](t)\Rightarrow a_{ij}t$
in $\mathbb{R}$ as $n\rightarrow\infty,$

then, we have that

$\mathbf{M}^{n}\Rightarrow\mathbf{M}\quad\text{ in
}(\mathcal{D}_{[0,\infty)}^{k},WJ_{1})\quad\text{ as }n\rightarrow\infty,$

where $\mathbf{M}$ is a $k$-dimensional Brownian motion with mean vector and
covariance matrix being

$\mathbb{E}[\mathbf{M}(t)]=(0,\ldots,0)\quad\text{ and
}\quad\mathbb{E}[\mathbf{M}(t)\mathbf{M}^{\top}(t)]=\mathbf{A}t,\quad t\geq
0.$

#####  A.1.2 Skorohod representation

Recall the definition of random elements on a metric space $(S,m)$ [68, Page
78].

######  Definition 7 (Random Element).

For a separable metric space $(S,m)$, we say that $\mathbf{X}$ is a random
element of $(S,m)$ if $\mathbf{X}$ is a measurable mapping from some
underlying probability space $(\Omega,\mathcal{F},\mathbb{P})$ to
$(S,\mathcal{B}(S))$, where $\mathcal{B}(s)$ is the Borel $\sigma$-field
induced by $(S,m)$.

The well-known Skorohod representation theorem [7, Theorem 6.7] gives the
following.

######  Lemma 6 (Skorohod representation).

Let $\\{\mathbf{X}^{n}\\}_{n\geq 1}$ and $\mathbf{X}$ be random elements of a
separable metric space $(S,m)$. If $\mathbf{X}^{n}\Rightarrow\mathbf{X}$ in
$(S,m)$, then there exists other random elements
$\\{\mathbf{X}^{n}_{\text{copy}}\\}_{n\geq 1}$ and $\mathbf{X}_{\text{copy}}$
of $(S,m)$, defined on a common probability space
$(\Omega,\mathcal{F},\mathbb{P})$, such that (i)
$\mathbf{X}^{n}_{\text{copy}}\stackrel{{\scriptstyle
d}}{{=}}\mathbf{X}^{n},~{}\forall~{}n\geq 1$ and
$\mathbf{X}_{\text{copy}}\stackrel{{\scriptstyle d}}{{=}}\mathbf{X}$; (ii)
$\lim_{n\rightarrow+\infty}m(\mathbf{X}^{n}_{\text{copy}},\mathbf{X}_{\text{copy}})=0$
$\mathbb{P}$-almost surely.

Let $d_{J_{1}}(\cdot,\cdot)$ be the $J_{1}$ metric (Skorohod metic) defined on
$\mathcal{D}:=\mathcal{D}([0,1],\mathbb{R})$, the set of RCLL functions
$[0,1]\rightarrow\mathbb{R}$ [68, Page 79]. Moreover, for the product space
$\mathcal{D}^{k}:=\mathcal{D}\times\cdots\times\mathcal{D}$, let
$d_{p}(\cdot,\cdot)$ be the product metric defined by
$d_{p}(\mathbf{x},\mathbf{y}):=\sum_{i=1}^{K}d_{J_{1}}(x_{i},y_{i}),~{}\forall~{}\mathbf{x},\mathbf{y}\in
D^{k}$ [68, Page 83]. It is known that both
$(\mathcal{D},d_{J_{1}}(\cdot,\cdot))$ and
$(\mathcal{D}^{k},d_{p}(\cdot,\cdot))$ are separable metric spaces with
$J_{1}$ topology and $WJ_{1}$ (weak $J_{1}$) topology respectively [68,
Sections 3.3, 11.4, and 11.5]. Then, according to Lemma 6, for weakly
converging random elements, we can obtain copies that converges almost surely.
This enables us to conduct sample path analysis. Specifically, if the limiting
random element is continuous almost surely, we can utilize the following
theorem from [24, Proposition 4] to conduct analysis under uniform norm