When Does the Gittins Policy Have Asymptotically Optimal Response Time Tail in the M/G/1?

Introduction

Scheduling to minimize response time (also known as sojourn time) of single-server queueing models is an important problem in queueing theory, with applications in computer systems, service systems, and beyond. In general, a queueing system will have a response time distribution, denoted T, and there are a variety of metrics that one might hope to minimize. There is significant work on minimizing mean response time E[T], which is the average response time of all jobs in a long arrival sequence (Schrage 1968, Gittins 1989, Aalto et al. 2009, Gittins et al. 2011).

Much less is known about minimizing the tail of response time P[T > t], which is the probability that a job has response time greater than a parameter t 0. In light of the difficulty of studying the tail directly, theorists have studied the asymptotic tail of response time, which is the asymptotic decay of P[T > t] in the t ! 1 limit (Stolyar and Ramanan 2001, N ú ñez-Queija 2002, Borst et al. 2003, Boxma and Zwart 2007, Scully et al. 2020b). In this work, we consider the preemptive M/G/1 queue and ask the following question.

Question 1.1. Does any scheduling policy simultaneously optimize the mean and asymptotic tail of response time in the M/G/1? Our focus on the M/G/1, a classic, single-server queueing model (Kendall 1953, Cox and Smith 1961, Kleinrock 1976, Harchol-Balter 2013), is motivated by its balance between modeling flexibility and analytical tractability. The fact that the distribution of job sizes (also known as service times) may be general is particularly important for modeling computer systems, where the distribution can be far from exponential (Peterson 1996, Crovella and Bestavros 1997, Harchol-Balter and Downey 1997).

Prior work answers Question 1.1 when job sizes are known to the scheduler. In this setting, the Shortest Remaining Processing Time (SRPT) policy, which preemptively serves the job of least remaining size, always minimizes mean response time (Schrage 1968).

However, SRPT's tail performance depends on the job size distribution. 1 • If the job size distribution is heavy-tailed (roughly, power-law; see Definition 4.1), then SRPT is tail-optimal, meaning that it has the best possible asymptotic tail decay (Definition 4.2).

• If the job size distribution is light-tailed (roughly, subexponential; see Definition 5.2), then SRPT is tailpessimal, meaning that it has the worst possible asymptotic tail decay (Definition 5.3).

This answers Question 1.1 for known job sizes: "yes, namely SRPT" in the heavy-tailed case, "no" in the light-tailed case.

Unfortunately, in practice, the scheduler often does not know job sizes, and, thus, one cannot implement SRPT. Instead, the scheduler often only knows the job size distribution. We study Question 1.1 in this unknownsize setting.

The question of minimizing mean response time with unknown job sizes was settled by Gittins (1989). He introduced a policy, now known as the Gittins policy, which leverages the job size distribution to minimize mean response time. Roughly speaking, Gittins uses each job's age-namely, the amount of time each job has been served so far-to figure out which job is most likely to complete after a small amount of service, then serves that job. For some job size distributions, Gittins reduces to a simpler policy, such as First-Come, First-Served (FCFS) or Foreground-Background (FB) (Aalto et al. 2009(Aalto et al. , 2011)).

In the unknown-size setting, given that Gittins minimizes mean response time, Question 1.1 reduces to the following.

Question 1.2. For which job size distributions is Gittins tail-optimal for response time?

Unfortunately, the asymptotic tail behavior of Gittins is understood in only a few special cases.

• In the heavy-tailed case, Gittins has been shown to be tail-optimal, but only under an assumption on the job size distribution's hazard rate (Scully et al. 2020b, corollary 3.5).

• In the light-tailed case, Gittins sometimes reduces to FCFS or FB (Aalto et al. 2009(Aalto et al. , 2011)). For light-tailed job sizes, FCFS is tail-optimal (Stolyar andRamanan 2001, Boxma andZwart 2007), but FB is tail-pessimal (Mandjes and Nuyens 2005).

This prior work leaves Question 1.2 largely open. We do not know whether Gittins is always tail-optimal in the heavy-tailed case, or whether it is sometimes suboptimal, or even tail-pessimal. Moreover, we do not understand Gittins's asymptotic tail at all in the lighttailed case, aside from when Gittins happens to reduce to a simpler policy.

The prior work above does tell us an important fact: Gittins can be tail-pessimal. This prompts another question.

Question 1.3. For job size distributions for which Gittins is tail-pessimal, is there another policy that has near-optimal mean response time while not being tailpessimal?

In this work, we answer Questions 1.1-1.3 for the M/G/1 with unknown job sizes, covering wide classes of heavy-and light-tailed job size distributions.

The key tool we use to analyze Gittins's asymptotic response time tail is the SOAP (Schedule Ordered by Age-based Priority) framework (Scully andHarchol-Balter 2018, Scully et al. 2020b). SOAP gives a universal M/G/1 response time analysis of all SOAP policies, which are scheduling policies where a job's priority level is a function of its age (Definition 3.1). Underlying our Gittins results is a general tail analysis of SOAP policies.

Our main contributions, which we describe in more detail later (Sections 4 and 5), are as follows:

• Heavy-tailed case: We give a sufficient condition under which an arbitrary SOAP policy is tail-optimal (Section 7).

• Heavy-tailed case: We show that the above condition always applies to Gittins, implying that it is always tail-optimal (Section 8).

• Light-tailed case: We characterize when an arbitrary SOAP policy is tail-optimal, tail-pessimal, or in between (Section 9).

• Light-tailed case: We spell out how the above characterization applies to Gittins and show how to modify Gittins to avoid tail pessimality (Section 10).

• General case: At the core of our modification of Gittins which avoids tail pessimality is a general result, which states that slightly perturbing the Gittins rank function only slightly affects its mean response time (Theorem 5.10 and Online Appendix EC.2). 2 The rest of the paper introduces definitions and notation (Sections 3 and 6) and concludes with some remarks about our motivating questions (Section 11).

Asymptotic Tail Analysis of Classic

Scheduling Policies Because of their frequent occurrence, light-tailed job size distributions have received a great amount of attention by queueing theorists. The performance of policies under light-tailed job sizes is generally measured in terms of the decay rate of the response time tail. In this sense, FCFS has proven to be optimal among all service policies (Stolyar and Ramanan 2001). Conversely, Foreground-Background Processor Sharing has the worst possible decay rate of the response time tail (Mandjes and Nuyens 2005).

On the other hand, it is shown that heavy-tailed job sizes can have a large impact on the performance characteristics of the queue. For this reason also, heavy-tailed job sizes have been thoroughly investigated in the literature. For example, researchers have made the striking observation that, contrary to the light-tailed case, FB is optimal where FCFS has the worst possible response time tail (Borst et al. 2003). This dichotomy between light and heavy tails is not limited to FCFS and FB (Boxma and Zwart 2007).

Other noteworthy literature highlighting both light and heavy tails includes delicate asymptotic results for a two-class priority policy (Abate and Whitt 1997) and robust optimization using a limited PS policy (Nair et al. 2010).

With one exception, discussed in Section 2.3, the literature on this subject concerns only a few relatively simple policies. This paper considers policies in which the priority of a job can vary essentially arbitrarily with its age. This generality is needed to analyze the Gittins policy, where a job's priority can be nonmonotonic (Aalto et al. 2011).

Model, SOAP Policies, and the Gittins Policy

We consider an M/G/1 queue with arrival rate λ, job size distribution X, and load ρ à λE[X]. For the tail of the job size distribution, we write F(t) à P[X > t]. We denote the maximum job size by x max à inf{t 0 |F(t) à 0}, allowing x max à 1. We write T π for the M/G/1's response time distribution under policy π. We allow policies to preempt jobs or share the processor without any overhead or loss of work (i.e., the model is preempt-resume). Special attention is given in this paper to the Gittins policy. It assigns each job a rank-namely, a prioritybased on the job's age-namely, the amount of time the job has been served so far. To analyze the Gittins policy, we make use of the SOAP framework (Scully and Harchol-Balter 2018, Scully et al. 2018, 2020b), which gives a response time analysis of the following broad class of policies. Definition 3.1. A SOAP policy is a policy π specified by a rank function r π : [0, x max ) ! R. Policy π assigns rank r π (a) to a job at age a. 4 When the policy being discussed is clear from context, we often omit the subscript and simply write r(a). At every moment in time, a SOAP policy serves the job of minimum rank, breaking ties in FCFS order. 5 Definition 3.2. The Gittins policy, denoted "Gtn" in subscripts for brevity, is the SOAP policy with rank function

Note that the Gittins rank function depends on the job size distribution X by way of F.

As is standard (Scully andHarchol-Balter 2018, Scully et al. 2018 appendix B), we assume that rank functions are piecewise-continuous and piecewise-monotonic, with finitely many pieces in any compact interval for both properties. This holds for Gittins under very mild conditions on the job size distribution X. For example, Aalto et al. (2011) show that the Gittins rank function is continuous and piecewise-monotonic, provided that X is a continuous distribution with continuous and piecewisemonotonic hazard rate. However, our results are not restricted to continuous job size distributions. Our generic SOAP results require no additional assumptions on X, and our Gittins results require only that X induces a piecewise-continuous and piecewise-monotonic Gittins rank function, which can occur even if X is not continuous.

Background on Heavy-Tailed Job Sizes

Roughly speaking, the heavy-tailed job size distributions we study are those that are asymptotically Pareto. The specific class that we study, described below, is slightly more general in that it also includes distributions whose tails oscillate between Pareto tails of different shape parameters.

Definition 4.1 (Heavy-Tailed Job Size Distribution). We say a job size distribution X is nicely heavy-tailed if x max à 1 and both of the following hold:

i. The tail F(•) is of intermediate regular variation (Cline 1994), meaning lim inf

ii. There exist β α > 1 such that the upper and lower Matuszewska indices of F(•) are in ( β, α) (Bingham et al. 1987, section 2.1). This implies that for all sufficiently large x 2 x 1 , 6

In informal discussion, we omit "nicely." Although the above definition includes all distributions with power-law-like tail decay, it is noted that we do not consider tails of a less heavy order, such as those of the lognormal and Weibull distributions. Consider an M/G/1 with nicely heavy-tailed job size distribution X. We call a scheduling policy π tail-optimal among preemptive work-conserving policies if

That is, tail optimality holds if large jobs have a response time of approximately 1=(1 ρ) times their size, which is the best possible asymptotic tail decay in the heavytailed case (Boxma andZwart 2007, Wierman andZwart 2012).

Results for Heavy-Tailed Case

Let us focus on a tagged job of size x. For determining whether it will be delayed by other jobs, it is important to know the worst (highest) ever rank that it will ever have, as well as the ages at which other jobs will have rank lower than that worst ever rank.

Definition 4.3. The worst ever rank of a job of size x is defined by w x à sup 0  a < x r(a). Definition 4.4. i. A w-interval is an interval (b, c) with 0  b < c  x max such that r(a)  w for all a 2 (b, c).

ii. A w-interval (b, c) is right-maximal if for all c 0 c, the interval (b, c 0 ) is not a w-interval. This is equivalent to c satisfying either r(c) w or c à x max . We define leftmaximal similarly, and we call a w-interval maximal if it is both left-and right-maximal.

Note that the tagged job of size x, no matter its age, always has priority over jobs that have rank higher than w x . Therefore, it can only be delayed by another job if that other job's age is in a w x -interval. See Figure 1 for an illustration. To ensure that the tagged job does not wait too long behind other jobs, the w x -intervals must be relatively short. We use the following condition to characterize the length of w x -intervals. ii. The w x -interval's endpoint is bounded by c  O(x η ). 7

Note that to check that (i) and (ii) hold, it suffices to consider only right-maximal w x -intervals.

At an intuitive level, we can think of Condition 4.5 as saying the following about how much other jobs delay the tagged job of size x:

• If ζ and θ are small enough, then w x -intervals are relatively short, so jobs of age greater than x cannot delay the tagged job for too long. Figure 2 illustrates the difference between the roles of ζ and θ (see also Section 4.3).

• If η is small enough, then there are no w x -intervals at sufficiently large ages, so jobs of sufficiently large age cannot delay the tagged job at all. Rank functions that satisfy Condition 4.5 do so for many possible parameter values. For instance, if Condition 4.5 is satisfied with parameters (ζ, θ, η), then it is also satisfied for (ζ + δ, θ δ + ✏, η + ✏) for all δ, ✏ > 0. But the idea is to find parameters that characterize a SOAP policy's rank function as tightly as possible because, as our main result below shows, if the parameters are small enough, then the policy is tail-optimal.

Theorem 4.6. Consider an M/G/1 with any nicely heavy-tailed job size distribution under a SOAP policy. Condition 4.5 implies the policy is tail-optimal if its parameters satisfy

We can apply Theorem 4.6 to show that Gittins is tailoptimal. Specifically, we will show that Gittins satisfies Condition 4.5 with ζ à 0, θ à 1, and η à 1. As such, it achieves a value of zero on the left-hand side of (4.1), so Gittins is tail-optimal, regardless of the values of β α > 1.

Theorem 4.7. The Gittins policy is tail-optimal for any nicely heavy-tailed job size distribution.

Comparing Our Tail Optimality Condition to That of Scully et al. (2020c)

Having formally stated our sufficient condition for tail optimality in the heavy-tailed case, we may now compare it in more detail to that of Scully et al. (2020b). Their condition (Scully et al. 2020b, assumption 3.2) and corresponding result (Scully et al. 2020b, theorem 3.3) are the same as our Condition 4.5 and Theorem 4.6, respectively, but restricted to the θ à 0 case. This means, roughly speaking, that Scully et al. (2020b) only look at the lengths between "peaks" of the rank

Figure 1. (Color online) Illustration of Worst Ever Rank w x (Purple Dotted Line) and Maximal w x -Intervals (Shaded Orange Regions) for a SOAP Policy Given by Rank Function r (Solid Cyan Curve) Note. A tagged job of size x always has rank w x or better, so if another job has priority over the tagged job, that other job's age must be in a w x -interval. Notes. (a) Rank function with ζ à 1 and θ à 0. (b) Rank function with ζ à 0 and θ à 1. Roughly speaking, one should think of ζ + θ as characterizing how far apart different "peaks" of the rank function are, and one should think of ζ=(ζ + θ) as characterizing how "steep" the rank function is between peaks. Both (a) and (b) have the same peaks, as reflected by (a) and (b) having the same value of ζ + θ. But the slopes are much steeper in (a) than in (b), as reflected by the larger value of ζ=(ζ + θ) in (a) than in (b). Unfortunately, looking only at distances between peaks of the rank function is not enough to prove Gittins's tail optimality in the heavy-tailed case. For Gittins, it turns out that we cannot, in general, do better than setting η à 1. If we had to set θ à 0, then to make Gittins satisfy Condition 4.5, it turns out that we would need to set ζ à 1, which is too large to satisfy (4.1). But the Gittins rank function looks less like Figure 2(a) and more like Figure 2(b): even though the peaks can be far apart, there are "gentle slopes" between them. Setting θ à 1 and ζ à 0 captures this behavior, and this satisfies (4.1). Thus, our refining of the sufficient condition of (Scully et al. 2020b, assumption 3.2) is necessary to prove Gittins's tail optimality in the heavy-tailed case, at least for this SOAP-based approach.

Underlying the tail optimality results of Scully et al. ( 2020b) is a busy period analysis combined with asymptotic response time bounds. We make use of their busy period analysis, which we distill into a simple statement (Lemma 7.4), but we replace their asymptotic response time bounds with a sharper analysis that accounts for the θ > 0 possibility (Sections 7.1 and 7.2).

Finally, we reiterate that whereas Scully et al. (2020b) study only heavy-tailed size distributions, we also study light-tailed job size distributions. Our results for the light-tailed case are based on very different techniques, reflecting fundamental differences between the heavy-and light-tailed settings.

Background on Light-Tailed Job Sizes

Definition 5.1. The decay rate of random variable V,

Higher decay rates thus correspond to asymptotically lighter tails.

Roughly speaking, the light-tailed job size distributions we study are those with positive decay rate. Our main tool for investigating the decay rate of a random variable V is via its Laplace-Stieltjes transform L[V], defined as

Under mild conditions on V (Nakagawa 2005(Nakagawa , 2007; Mimica 2016), we can determine its decay rate in terms of the convergence of its Laplace-Stieltjes transform:

(5.1)

The specific class of light-tailed job size distributions we consider, described below, are those that allow us to use (5.1) throughout this work (Online Appendix EC.3). The class includes essentially all light-tailed distributions of practical interest, such as finite-support, phase-type, and Gaussian-tailed distributions. In the terminology of Abate and Whitt (1997), we consider all "Class I" distributions. 8

Definition 5.2 (Light-Tailed Job Size Distribution). Given a job size distribution X, let

In informal discussion, we omit "nicely."

Definition 5.3 (Tail Optimality in Light-Tailed Case). Consider an M/G/1 with nicely light-tailed job size distribution X. We say a scheduling policy π is

In each case, we mean minimizing or maximizing over preemptive work-conserving policies. In informal discussion, we omit "log-."

Results for Light-Tailed Case

We have seen that a job's worst ever rank plays an important role in the heavy-tailed setting. When the job sizes are light-tailed, we are interested in the age at which the rank function's global maximum occurs.

Definition 5.4. The worst age, denoted a ⇤ , is the earliest age at which a job has the global maximum rank:

If the rank function has no maximum, we define a ⇤ à x max .

As an example, FCFS has a ⇤ à 0 because a job's priority is the worst before it starts service. In contrast, FB has a ⇤ à x max because a job's priority gets strictly worse with age.

We already know that FCFS and FB are tail-optimal and tail-pessimal, respectively. The theorem below fills in the gaps for all other SOAP policies, showing that the performance of the response time tail is completely determined by the worst age a ⇤ . Theorem 5.5. Consider an M/G/1 with any nicely lighttailed job size distribution under a SOAP policy. Let

To apply Theorem 5.5 to the Gittins policy, we need to characterize how the job size distribution X affects Gittins's worst age a ⇤ . Definition 5.6. We define two classes of distributions: NBUE and ENBUE.

• We say X is New Better than Used in Expectation, writing X 2 NBUE, if for all ages a 2 [0, x max ),

Remark 5.7. It is well known that the NBUE class includes all distributions with (weakly) increasing hazard rate. Similarly, one can show that the ENBUE class includes all distributions with "eventually increasing" hazard rate, meaning that the hazard rate is increasing at all ages greater than some threshold a 0 < x max .

Results of Aalto et al. (2009Aalto et al. ( , 2011) ) connect the classes NBUE and ENBUE to Gittins's worst age a ⇤ , implying the following characterization.

Theorem 5.8. Consider an M/G/1 with any nicely lighttailed job size distribution X. Gittins is

More generally, Theorem 5.5 can imply an analogue of Theorem 5.8 for other SOAP policies, whose rank at age a is related to the expected remaining size E[X a| X > a], such as the SERPT policy (Remark 10.1).

The fact that Gittins can be log-tail-pessimal is intriguing, considering that it is optimal for mean response time and tail-optimal under heavy-tailed job sizes. Fortunately, in most cases where Gittins is logtail-pessimal, slightly tweaking Gittins yields a log-tailintermediate policy without sacrificing much mean response time performance. Definition 5.9. A SOAP policy π is a q-approximate Gittins policy if there exists a constant m > 0 such that for all ages a 2 [0, x max ),

We may assume without loss of generality that m à 1 because the policy π 0 with rank function r π 0 (a) à r π (a)=m has identical behavior to policy π.

Theorem 5.10. Consider an M/G/1 with any job size distribution. For any q 1 and any q-approximate Gittins policy π, 9

An important observation is that a q-approximate Gittins policy has near-optimal mean response time for q close to one. At the same time, changing the Gittins rank function even within a small factor q can decrease the worst age, and therefore improve the tail performance.

Theorem 5.11. Consider an M/G/1 with nicely lighttailed job size distribution X ∉ ENBUE. Suppose that the expected remaining size of a job at all ages is uniformly bounded, meaning

Then, for all ✏ > 0, there exists a (1 + ✏)-approximate Gittins policy that is log-tail-optimal or log-tail-intermediate.

As an example in which log-tail-pessimality may be avoided, consider a hyperexponential job size X with two different rates. That is, for i à 1, 2, with probability p i , the job size is sampled from an exponential with rate µ i . Here, p 1 , p 2 > 0 such that p 1 + p 2 à 1, and we assume without loss of generality that µ 1 > µ 2 .

Because the hazard rate of a hyperexponential distribution is decreasing, r Gtn is increasing. Therefore, Gittins reduces to FB, so it is log-tail-pessimal. Fortunately, though, E[X a| X > a] < 1=µ 2 for all ages a; hence, Theorem 5.11 can be applied: for any q > 1, the policy with rank function

where ã is such that qr Gtn (ã) à 1=µ 2 is a q-approximate Gittins policy with a ⇤ à ã < 1. See Figure 3. Although Theorem 5.11 implies that any approximation factor q > 1 suffices to prevent log-tail-pessimality, there is a tradeoff to be made when choosing q. Higher values of q result in worse guarantees for the mean (Theorem 5.10). But higher values of q lead to lower values of a ⇤ , which, in turn, result in better tail decay (Lemma 9.8). We leave exploring this tradeoff quantitatively to future work.

E[X

Definition 6.4. For a job of size x, we define 11

See Figure 4. Intuitively, y x is the earliest age at which a job of size x attains its worst ever rank w x , and z x is the earliest age at which the rank function exceeds w x . Note that it may be that y x à x à z x . This occurs if the rank function is strictly increasing at x, and x is a "running maximum," meaning r(a) < r(x) for all ages a 2 [0, x).

Our final piece of notation is a generalization of a job's worst ever rank. Definition 6.5. The worst future rank of a job of size x at age a, written w x (a), is Notes. By Theorem 5.5, these have different tail asymptotics. The Gittins rank function attains its supremum of 1=µ 2 in the a ! 1 limit, so it is tail-pessimal. But the q-approximate Gittins rank function, described in (5.2), attains its supremum at a finite age ã, so it is tailintermediate. Note that the worst ever rank is simply the worst future rank at age zero-that is, w x à w x (0).

One can write a formula characterizing T(x), the response time distribution of jobs of size x, in terms of the notation from Definitions 6.2 and 6.5. We refer the reader to Scully and Harchol-Balter (2018) and Scully et al. (2018) for details, noting here one simple consequence of that formula. Lemma 6.6. Under any SOAP policy, the response time of jobs of size x is stochastically increasing in x. That is, for all x 1 x 0 > 0, we have T(x 0 )  st T(x 1 ).

Showing

Condition 7.3 Our goal in this section is to prove Proposition 7.8 below. It is applicable to proving Theorem 4.6 because (4.1) implies its precondition. Proposition 7.8. If ζ < 1 or η < 1, then Condition 4.5 implies Condition 7.3.

Proof. The η < 1 case follows from a result of (Scully et al. 2020b, lemma 7.3), so we address only the ζ < 1 case. We first observe that for all ρ 0 2 [0, ρ], we have

We can rewrite the integrand as

Of course, the integrand is also bounded above by

A job of size x attains its worst ever rank w x at age y x . This means that for all a < y x , we have w x (a) à w x , which by Definition 6.4 implies c 0 [w x (a) ] à y x . Splitting the integral in (7.7) at a à y x yields

Because y x  x and α > 1, it suffices to show that the integral in (7.8) is ǒ(x).

The main remaining obstacle is bounding c 0 [w x (a) ]. We do so in Lemma 7.9, which states

for some κ 2(α 1). Plugging this into (7.8) and substituting u à

Because ζ < 1 and (α 1)=κ 2 (0, 1=2], this is ǒ(x), as desired. w

The following lemma bounds c 0 [w x (a) ]. We defer its proof to Online Appendix EC.1.1. Lemma 7.9. Suppose Condition 4.5 holds, and let κ à 2 max{α 1, θ}. For all x 0 and a 2 (y x , x),

The Time-Per-Completion Function

To make further progress, we need to consider the specific form of the Gittins rank function. One useful way of thinking about the Gittins rank function uses the following definition (Aalto et al. 2009(Aalto et al. , 2011)).

Definition 8.1. The time-per-completion function for a given job size distribution S is defined for 0

The intuition is that if we serve a job from age b until either age c or its completion, whichever comes first, then we can interpret φ(b, c) as That is, under Gittins, a job's rank at age a is the best possible time-per-completion ratio achievable on any interval starting at age a.

How does using the time-per-completion function help us show (8.1)? The key observation is that for the Gittins rank function to be low over an interval (b, c), a job must be relatively likely to complete during (b, c), which would imply that φ(b, c) is also low. The following lemma, which we prove in Online Appendix EC.2.2, formalizes this intuition. Lemma 8.2. Under Gittins, for any right-maximal w-interval (b, c), we have φ(b, c)  w.

We note that although many results similar to Lemma 8.2 have been shown in prior work (Aalto et al. 2009(Aalto et al. , 2011;;Scully et al. 2020b), to the best of our knowledge, Lemma 8.2 itself is new.

With Lemma 8.2 in hand, showing (8.1) amounts to

• Proving an upper bound on w x , and • Proving a lower bound on φ(b, c) for all rightmaximal w x -intervals (b, c).

The first of these follows simply from prior work: Scully et al. (2020b, section 3.2) show that the Gittins rank function is bounded by r Gtn (a)  O(a), which implies

(8.3) Note. Any w x -interval (shaded orange regions)-namely, any interval where the Gittins rank function (solid cyan curve) is better than the worst ever rank w x of a job of size x-has length O(x).

Bounding Lengths of w x -Intervals

There is one more fact from prior work that we need to prove (8.4).

Lemma 8.4 (Scully et al. 2021, theorem 6.4). Under Gittins, y x à Θ(x) and z x à Θ(x).

In general, (y x , z x ) is a right-maximal w x -interval, but there can be plenty of other w x -intervals starting at values greater than z x . How can we use Lemma 8.4 to study such intervals? The key is to look not at y x and z x , but at y u and z u , where u is some point inside the w x -interval whose length we wish to bound.

Specifically, consider a right-maximal w x -interval (b, c) with b x and let u 2 (b, c) be an arbitrary size in the interval. Figure 6 illustrates the relationship between the interval (b, c), the worst ever rank w u of size u, and the ages y u and z u (Definition 6.4). The figure suggests the following lemma, which is a slight generalization of a result of Scully et al. (2020b, lemma 6.18). Lemma 8.5. Under any SOAP policy, for any w x -interval (b, c) with b x and any u 2 (b, c),

Proof. It is clear from Definition 6.4 that y u  u  z u . It thus suffices to show that y u ∉ (b, c) and z u ∉ (b, c). Both steps use the fact that x  b < u implies w x  w u (Definition 4.3).

We first show that z u ∉ (b, c). By Definition 4.4, the rank function does not exceed w x over the interval (b, c). But Definition 6.4 implies that every neighborhood of z u contains a point whose rank is greater than w u . Because w u w x , it must be that z u ∉ (b, c).

If w u > w x , then the argument that y u ∉ (b, c) is analogous to that for z u . The difference is that this time, Definition 6.4 implies that for all ✏ > 0, every neighborhood of y u contains a point whose rank is greater than w u ✏. Because w u ✏ > w x for small enough ✏, it must be that y u ∉ (b, c).

If, instead, w u à w x , then y u à y x , and we can reason more simply: Definition 6.4 implies y x  x, and we have assumed x  b, so y u  b. w Lemmas 8.4 and 8.5 combine to prove (8.4), from which Theorem 4.7 follows. The fact that c b  O(x) means that Gittins satisfies Condition 4.5 with ζ à 0, θ à 1, and η à 1. These obey (4.1), so by Theorem 4.6, Gittins is tail-optimal. w

Light-Tailed Job Sizes: Tail Asymptotics of SOAP Policies

In this section, we prove our main theorem for lighttailed job sizes.

Theorem 5.5. Consider an M/G/1 with any nicely lighttailed job size distribution under a SOAP policy. Let Operations Research, Articles in Advance, pp. 1-18, © 2024 INFORMS Downloaded from informs.org by [128.84.127.144] on 26 February 2024, at 08:14 . For personal use only, all rights reserved.

• Log-tail-intermediate if 0 < a ⇤ < x max , and • Log-tail-pessimal if a ⇤ à x max .

Proof. The result follows from Propositions 9.1, 9.2, and 9.9, which we prove in the rest of this section. w 9.1. Tail-Optimal Case Proposition 9.1. Consider an M/G/1 with any nicely light-tailed job size distribution under a SOAP policy. The policy is log-tail-optimal if a ⇤ à 0.

Proof. Suppose that a ⇤ à 0. In this case, because of the FCFS tiebreaking (Definition 3.1), the oldest job in the system always has priority over all other jobs. Therefore, the SOAP policy is exactly FCFS, which is known to be log-tail-optimal (Stolyar andRamanan 2001, Boxma andZwart 2007). w 9.2. Tail-Pessimal Case Mandjes and Nuyens (2005) show that the FB policy, which has rank function r(a) à a, is log-tail-pessimal.

Their argument focuses on analyzing the response time of very large jobs, showing that such jobs' response time tails have small decay rate. The fact that their argument focuses on just the very large jobs suggests that the essential property of FB is that it assigns the largest rank at the largest ages. Our tail pessimality result below shows this is indeed the case.

Proposition 9.2. Consider an M/G/1 with any nicely light-tailed job size distribution under a SOAP policy. The policy is log-tail-pessimal if a ⇤ à x max .

We prove Proposition 9.2 in Online Appendix EC.1.2 by generalizing the proof that Mandjes and Nuyens (2005) give for FB, making use of several of their intermediate results along the way. We describe the approach below, after which we present the proof.

Consider first the case where x max < 1, meaning we could have a job of size x max . Because a ⇤ à x max , jobs of size x max complete at the end of the busy period during which they arrive. This is the latest time a job can complete under a work-conserving policy, so d(T(x max )) à d min , where d min is the minimal, and thus pessimal, response time tail decay rate. If X has an atom at x max , meaning that X à x max occurs with positive probability, then d(T) à d(T(x max )) à d min .

Of course, for general job size distributions X, it may be that X à x max occurs with probability zero. This is certainly the case if x max à 1. Therefore, to generalize the argument above, instead of considering T(x max ), we consider T(x) in the x ! x max limit. Although d(T(x)) > d min for any fixed x < x max , we show that lim x!x max d (T(x)) à d min . This means that for any ✏ > 0, a positive fraction of jobs experience decay rate less than d min + ✏, implying d(T) à d min , as desired.

The last ingredient we need is notation for discussing the M/G/1 and, in particular, busy periods. This is because d min turns out to be a busy period's decay rate (Mandjes and Nuyens 2005, corollary 6). Definition 9.3.

i. We denote by B the distribution of an M/G/1 busy period length with arrival rate λ and job size distribution X. More generally, we write B(u) for a busy period with initial work u.

ii. We denote by B a the distribution of an M/G/1 busy period length with arrival rate λ and truncated job size distribution min{X, a}. More generally, we write B a (u) for a such busy period with initial work u.

iii. We denote by W the distribution of the total amount of work in an M/G/1.

It is known that d min à d(B) (Mandjes and Nuyens 2005, corollary 6), so proving Proposition 9.2 amounts to showing lim x!x max d(T(x)) à d(B). To show this, we first prove d(T(x))  d(B y x ), so it suffices to show lim x!x max d(B y x ) à d(B). This follows from the known fact that lim y!x max d(B y ) à d(B) (Mandjes and Nuyens 2005, proposition 8) and additional computation. See Online Appendix EC.1.2 for details.

Tail-Intermediate Case

We finally turn to the case where 0 < a ⇤ < x max , where we will show that the corresponding SOAP policy is log-tail-intermediate. We first simplify the problem of analyzing an arbitrary SOAP policy with 0 < a ⇤ < x max to the problem of analyzing two policies, called Step and Spike (Definition 9.4 and Figure 7), with similar rank functions. We then bound the decay rates of Step and Spike.

For brevity, we give only the key definitions and lemma structure of the proof, building up to Proposition 9.9, which states the main result for the tailintermediate case. The proofs of the individual steps are either largely computational or follow easily from prior work, so we defer the proofs to Online Appendix EC.1.2. Definition 9.4. For a given value of a ⇤ 2 (0, x max ) and r ⇤ > 0, the Step and Spike policies are the SOAP policies given by the following rank functions, which are illustrated in Figure 7:

r spike (a) à r ⇤ 1(a à a ⇤ ):

We will compare the response time tail of a SOAP policy with 0 < a ⇤ < x max and r(a ⇤ ) à r ⇤ to the response time tails of Step and Spike for those values of a ⇤ and r ⇤ . This comparison is possible because, as illustrated in Figure 7, all three policies have qualitatively similar rank functions. 14 For the remainder of this section, we consider SOAP policies π with 0 < a ⇤ < x max and r(a ⇤ ) à r ⇤ . We divide jobs in two classes:

• Class 1, jobs of size at most a ⇤ ; and

• Class 2, jobs of size greater than a ⇤ . For each class i 2 {1, 2}, let λ (i) be the arrival rate of class i jobs, and let T (i) π be the response time of class i jobs under policy π.

It turns out that only class 2 jobs affect the asymptotic decay rate of response time. Moreover, it turns out that the Step and Spike policies represent the worst-case and best-case scenarios for class 2 jobs. These facts, expressed in the following lemma, imply that it suffices to analyze the response time decay rate for class 2 jobs under Step and Spike. Lemma 9.5. Let π be a SOAP policy with 0 < a ⇤ < x max . We have

With Lemma 9.5 in hand, to show that π is tailintermediate, it suffices to show that both Step and Spike are tail-intermediate by bounding d(T (2) step ) and d(T (2) spike ). We begin by characterizing T (2) step and T (2) spike in terms of the M/G/1 concepts defined in Definition 9.3.

Lemma 9.6. The response time distributions of class 2 jobs under

Step and Spike are

) is the size distribution of class 2 jobs, and the random variables in each sum are mutually independent.

Combining Lemmas 9.5 and 9.6 reduces the question of analyzing the decay rate of π to analyzing the decay rate of the busy periods in Lemma 9.6. We will see soon that B a ⇤ (W) is the dominant term, so both Step and Spike have decay rate d(B a ⇤ (W)). In order to prove that B a ⇤ (W) is indeed the dominant term, and in order to bound its decay rate, we make heavy use of Laplace-Stieltjes transforms (Section 5.1).

Recall from (5.1) that one can determine a random variable's decay rate by determining when its Laplace-Stieltjes transform converges. 15 We therefore introduce notation to describe when a transform converges. For functions f : R ! R [ { 1, 1}, which diverge below a certain value and converge above it, define

to be the value at which f switches from diverging to converging. We can thus rewrite (5.1) as

Because we will be working with Laplace-Stieltjes transforms, we begin by recalling standard results for the transforms of the quantities defined in Definition 9.3. Let

letting σ(s) à 1 if there is no real solution. We define σ a similarly.

Standard M/G/1 results (Harchol-Balter 2013) express the Laplace-Stieltjes transforms of random variables in Definition 9.3 using σ and σ a . Specifically, for any nonnegative random variable U,

Therefore, to understand the decay rates of random variables in Definition 9.3, we need to understand σ 1 , σ, and σ a . Figure 8 illustrates σ and σ 1 and some key Notes. (a) Rank of Step. (b) Rank of Spike. (c) Rank of generic policy. As shown in Lemma 9.5, for a fixed job size distribution and value of a ⇤ , (a) the Step policy gives the worst possible tail decay, whereas (b) the Spike policy gives the best possible tail decay. This is because in (a), jobs of age a ⇤ or greater have the worst possible rank r ⇤ , whereas in (b), jobs of age a ⇤ or greater have the best possible rank zero. Under (c), a generic SOAP policy π, jobs of age a ⇤ or greater have rank somewhere in between.

values associated with them. We make frequent use of relationships between these values and other properties of σ and σ 1 , which are summarized below.

Lemma 9.7. Consider an M/G/1 with nicely light-tailed job size distribution X, and define

Then, as illustrated in Figure 8, the following hold: i. σ 1 is convex on (s 0 , 1), decreasing on (s 0 , s 2 ), and increasing on (s 2 , 1);

ii. s 0 < s 1 < s 2 < s 3 < 0.

Analogous statements hold for σ a for all a 2 (0, x max ].

Together, (9.2) and Lemma 9.7 give us the last ingredients we need to compute the decay rate of T π . We then show that this decay rate is neither optimal nor pessimal.

Lemma 9.8. Let π be a SOAP policy with 0 < a ⇤ < x max . Then, the decay rate of its response time is

Proposition 9.9. Consider an M/G/1 with any nicely light-tailed job size distribution under a SOAP policy. The policy is log-tail-intermediate if 0 < a ⇤ < x max .

Light-Tailed Job Sizes: Gittins Can Be

Tail-Optimal, Tail-Pessimal, or in Between Theorem 5.8. Consider an M/G/1 with any nicely lighttailed job size distribution X. Gittins is

Proof. By Theorem 5.5, it suffices to determine the worst age a ⇤ . Combining the following two prior results characterizes a ⇤ in terms of whether X is in each of NBUE and ENBUE.

• A result of Aalto et al. (2009, proposition 7) implies a ⇤ à 0 if and only if X 2 NBUE.

• A result of Aalto et al. (2011, proposition 9) implies a ⇤ < x max if and only if X 2 ENBUE w Theorem 5.11. Consider an M/G/1 with nicely lighttailed job size distribution X ∉ ENBUE. Suppose that the expected remaining size of a job at all ages is uniformly bounded, meaning

Then, for all ✏ > 0, there exists a (1 + ✏)-approximate Gittins policy that is log-tail-optimal or log-tail-intermediate.

so r Gtn (a) is also uniformly bounded. This means that for any ✏ > 0, there exists some sufficiently large age a(✏) such that increasing the rank at age a(✏) < x max from r Gtn (a(✏)) to (1 + ✏)r Gtn (a(✏)) and leaving all other ranks unchanged yields a new SOAP policy with worst age a ⇤ à a(✏). By construction, the new policy is a (1 + ✏)-approximate Gittins policy, and because its worst age is a ⇤ < x max , Theorem 5.5 implies it is logtail-optimal or log-tail-intermediate. w

Recall from Theorem 5.10 that a (1 + ✏)-approximate Gittins policy achieves mean response time within a factor of 1 + ✏ of optimal. We defer its proof to Online Appendix EC.2. This means that Theorem 5.11, whose precondition applies to nonpathological light-tailed job size distributions, gives a non-tail-pessimal policy with near-optimal mean response time. Notes. The partial inverse of σ 1 -namely, σ-corresponds to the branch going from the minimum of σ 1 to the right (orange highlight). As shown in Lemma 9.7, we have s 0 < s 1 < s 2 < s 3 .

Returning to the Motivating Questions

We conclude by returning to Questions 1.1-1.3, restated below for convenience.

Question 1.1. Does any scheduling policy simultaneously optimize the mean and asymptotic tail of response time in the M/G/1? Question 1.2. For which job size distributions is Gittins tail-optimal for response time? Question 1.3. For job size distributions for which Gittins is tail-pessimal, is there another policy that has near-optimal mean response time while not being tailpessimal?

Our characterization of Gittins's tail asymptotics (Theorems 4.7 and 5.8) answers Question 1.2, and our modification in the case where Gittins is tail-pessimal (Theorem 5.11) answers Question 1.3 affirmatively. This leaves only Question 1.1. In cases where we have shown that Gittins is tail-optimal, the answer is clearly affirmative. We might hope to conclude that the answer is negative in cases where we have shown that Gittins is tail-pessimal or tail-intermediate, but the situation is still slightly unclear. The remaining ambiguity is due to the fact that we have only considered FCFS tiebreaking when two jobs have the same rank (Definition 3.1), as we explain in more detail below.

The Gittins policy minimizes mean response time with arbitrary tiebreaking between jobs of the same rank (Gittins 1989, Gittins et al. 2011, Scully and Harchol-Balter 2021). Moreover, these proofs can be extended to show that any "non-Gittins" policy is strictly suboptimal for mean response time, where a "non-Gittins" policy is one that for a nonvanishing fraction of time serves a job other than one of minimal Gittins rank. Therefore, to fully answer Question 1.1, one would have to consider Gittins under arbitrary tiebreaking rules. We conjecture that using a different tiebreaking rule cannot improve the asymptotic decay rate of Gittins's response time in the light-tailed case.

Finally, we note that we have, of course, only answered Questions 1.1-1.3 for the classes of heavyand light-tailed job size distributions that we consider in this work (Definitions 4.1 and 5.2). Practically speaking, we believe the classes of distributions we consider are likely broad enough to draw useful conclusions. But it remains an open question whether we may extend our theory to broader classes of distributions. In particular, it seems likely that our proofs may hold mostly unchanged for additional light-tailed job size distributions, as discussed in Online Appendix EC.3.3.

Operations Research, Articles in Advance, pp. 1-18, © 2024 INFORMS Downloaded from informs.org by [128.84.127.144] on 26 February 2024, at 08:14 . For personal use only, all rights reserved. (i) For all p 0,

(ii) For all p 0,

Proof. We first show (i). Because (x, c 0 [w x ]) is a w x -interval, Condition 4.5 implies

We compute

[by Lemma 6.3]  Z O(x max{1,⇣+✓} ) 0 O(t p ↵ ) dt [by Definition 4.1 and (EC.1.1)] = 8 > < > :

thus proving (i).

We now show (ii), following a similar argument but with a more involved computation. Note that Definitions 6.1 and 6.5 together imply b k [w x ] x for all k 1. (EC.1.2)

We compute

O(t ↵ ) dt

[by Definition 4.1 and Condition 4.5] 

thus proving (ii).

LEMMA 7.9. Suppose Condition 4.5 holds, and let  = 2 max{↵ 1, ✓}. For all x 0 and a 2 (y x , x),

Proof. Because  > ✓ 0, by Condition 4.5 and (EC.1.2), for all u 0 and k 1,

We now plug in u = c 0 [w x (a) ] and make the following observations.

• By Definition 6.1, we know u = c 0 [w x (a) ] is the earliest age at which a job has rank at least w x (a), so w u = w x (a).

• By Definition 6.5, a job's rank is at most w x (a) between ages a and x, so there exists k 1 such that

In Recall that y x denotes the (first) age of the maximum rank in the interval [0, x]. Since T (x) is stochastically increasing in x (Lemma 6.6), it holds that P[T (x) > t] P[T (y x ) > t] for all t 0. Additionally we have that P[T (y x ) > t] P[T FB (y x ) > t] for all t, x 0, where T FB (x) is the response time for a job of size x under FB. The reason for this last inequality is that a job of size y x must wait for all other jobs to receive up to y x units of service before completing.foot_4 As a result, (Mandjes and Nuyens, 2005, Proposition 8) implies

Additionally, up to its last line the proof of (Mandjes and Nuyens, 2005, Lemma 9) is valid for arbitrary service policies. If x 0 > 0 is such that P[X x 0 ] > 0, we thus find ), so our task is to show that the limit still holds with y x instead of x.

Consider arbitrary

for all x > x 0 . Because a ⇤ = x max , there exists x 1 > x 0 such that y x 1 = x 1 , and thus |d(B yx 1 ) d(B)| < ".

But d(B yx ) is decreasing in x, because y x is increasing in x, and B x is stochastically increasing in x.

We conclude that for all x > x 1 , we have |d(B yx ) d(B)| < ". Our choice of " > 0 was arbitrary, so ), as desired.

LEMMA 9.5. Let ⇡ be a SOAP policy with 0 < a ⇤ < x max . We have

Proof. Clearly, T ⇡ is a mixture of T (1) ⇡ and T (2) ⇡ . Lemma 6.6 implies T (2)

. The same reasoning applies to Step and Spike. The lemma thus follows if we can show

step .

(EC.1.5)

The comparison in (EC.1.5) follows from a key fact from the SOAP analysis (Scully and Harchol-Balter, 2018) called the Pessimism Principle, which states that the response time of a particular job J is unaffected if, instead of following the usual rank function, job J follows its worst future rank function (Definition 6.5). The intuition is that any jobs that will get served ahead of job J in the future may as well be served ahead of it right now. Worst future rank functions (Definition 6.5, abbreviated w.f.r., dotted magenta curves) of the policies shown in Figure 9.1, with the original rank functions (translucent cyan curves) for reference. We show the worst future rank functions for a class 2 job of size x > a ⇤ .

We illustrate in Figure EC.1 the worst future rank under Step, Spike, and ⇡. Notice that, for any size

The Pessimism Principle says that we can compute a particular job J's response time by imagining that it always has its worst future rank. Increasing a job's rank can only increase its response time, so the above worst future rank comparisons imply that for all x > a ⇤ , T spike (x)  st T ⇡ (x)  st T step (x).

The desired (EC.1.5) follows because class 2 jobs are those of size greater than a ⇤ . LEMMA 9.6. The response time distributions of class 2 jobs under Step and Spike are

where X (2) = (X | X > a ⇤ ) is the size distribution of class 2 jobs, and the random variables in each sum are mutually independent.

Proof. This result follows easily from the SOAP analysis (Scully and Harchol-Balter, 2018). For completeness, we sketch the main ideas of how the SOAP analysis applies to Step and Spike. Consider a class 2 job J.

• Under Step, job J always has worst future rank r ⇤ (Figure EC.1(a)). Job J is thus delayed by any jobs present when it arrives, plus the pre-age-a ⇤ portion of any jobs that arrive while it is in the system.

• Under Spike, job J has worst future rank r ⇤ only until age a ⇤ (Figure EC.1(a)). Job J is thus delayed by any jobs present when it arrives, plus the pre-age-a ⇤ portion of any jobs that arrive before it reaches age a ⇤ . Once job J reaches age a ⇤ , its worst future rank is 0, so no further arrivals delay it.

The reason in both cases for looking at the pre-age-a ⇤ portion of new arrivals is because at age a ⇤ , those new arrivals reach rank r ⇤ , and thus job J has priority over them due to FCFS tiebreaking (Definition 3.1).

The delay due to jobs present when job J arrives corresponds to the W in each formula, and the delay due to new arrivals corresponds to the B a ⇤ (•) uses. The difference between the formulas is due to the fact that under Step, new arrivals delay job J until it completes, whereas under Spike, new arrivals delay job J only if they arrive before it reaches age a ⇤ , with the last X (2) a ⇤ portion of job J's service occurring uninterrupted.

LEMMA 9.7. Consider an M/G/1 with nicely light-tailed job size distribution X, and define

Then, as illustrated in Figure 9.2, the following hold:

(i) 1 is convex on (s 0 , 1), decreasing on (s 0 , s 2 ), and increasing on (s 2 , 1);

Analogous statements hold for a for all a 2 (0, x max ].

Proof. We prove the statement just for , as the argument for a is analogous. The illustration in Figure 9.2 may provide helpful intuition for the arguments that follow.

We begin by observing some general properties of 1 . Because L[X] is convex on (s 0 , 1), so is 1 .

This, along with the definition of s 2 , implies (a). The slope of 1 at zero is

and by Definition 5.2, we have 1 (s 0 ) = 1 > 0. Additionally, Definition 5.2 implies s 0 < 0. This means 1 is negative on a finite nonempty interval, namely (s 1 , 0), and nonnegative outside that interval.

We can now show the inequalities in (b).

• s 3 < 0: Because 1 is negative on some interval, its global minimum is negative.

• s 1 < s 2 : Because s 3 = 1 (s 2 ) < 0, we must have s 2 2 (s 1 , 0).

• s 2 < s 3 : Because 1 is convex with 1 (0) = 0 and ( 1 ) 0 (0) 2 (0, 1), we have s 2 < 1 (s 2 ).

In some of the proofs below, we use the fact that for sums of independent random variables U, V 0, (9.1) implies

There are two important implications of (EC.1.7). The first implication is that the global minimum of 1 a is less than that of 1 b . But these global minima are ( a ) and ( b ), respectively (see Figure 9.2), so

This means a (s) is finite whenever b (s) is. This contributes to the second implication of (EC.1.7): by Lemma 9.7(i),

Therefore, (EC.1.8) and (EC.1.9) together imply that there exists a value of s such that f ( b (s)) diverges while f ( a (s)) does not.

EC.2.1. The Gittins Game

The Gittins game is an optimization problem. Its inputs are a job at some age b and a penalty w. During the game, we serve the job for as long as we like. If the job completes, the game ends. At any moment before the job completes, we may choose to give up, in which case we pay the penalty w and the game immediately ends. The goal of the game is to minimize the expected sum of the time spent serving the job plus the penalty paid.

We can think of the Gittins game with penalty w as an optimal stopping problem whose state is the age b of the job. Standard optimal stopping theory (Peskir and Shiryaev, 2006;Shiryaev, 2008) implies that the optimal strategy thus has the following form: serve the job until it reaches some age c b, then give up. A possible policy here is never giving up, which is represented by c = 1. The (r Gtn , w)-relevant work of a job is related to the Gittins game via Lemma EC.2.3: it is the amount of time we would serve the job when optimally playing the Gittins game with penalty w. It turns out that mean (r Gtn , w)-relevant work directly translates into mean response time.

LEMMA EC.2.5 (Scully et al. (2020a, Theorem 6.3)). Under any nonclairvoyant scheduling policy ⇡, the mean response time can be written in terms of (r Gtn , w)-relevant work as

With Lemma EC.2.5 in hand, the proof of Theorem 5.10, restated below, reduces to bounding the mean amount of (r Gtn , w)-relevant work under q-approximate Gittins policies.

THEOREM 5.10. Consider an M/G/1 with any job size distribution. For any q 1 and any q-approximate Gittins policy ⇡,foot_10

Proof. Recall from Definition 5.9 that we may assume r ⇡ (a)/r Gtn (a) 2 [1, q] for all ages a without loss of generality. We will prove [by Lemma EC.2.5]

To show the left-hand inequality of (EC.2.2), it suffices to show that an arbitrary job's (r Gtn , w)-relevant work is upper bounded by its (r ⇡ , qw)-relevant work (Definition EC.2.4). This is indeed the case: r Gtn (a)  w implies r ⇡ (a)  qr Gtn (a)  qw, so the job will reach rank w under Gittins after at most as much service as it needs to reach rank qw under ⇡.

To show the right-hand inequality of (EC. We note that one can use the techniques of Scully et al. (2018b) to generalize the statement and proof of Theorem 5.10 beyond SOAP policies. It turns out that Theorem 5.10 still holds even if we allow q-approximate Gittins policies to adversarially assign ranks to jobs, provided that the assigned ranks are still within a factor-q window around the rank Gittins would assign.