Mean field optimal Core Allocation across Malleable jobs Zhouzi Li, Mor Harchol-Balter, Benjamin Berg Abstract . Modern data centers and cloud computing clusters are increasingly running workloads composed of malleable jobs. A malleable job can be parallelized across any number of cores, yet the job typically exhibits diminishing marginal returns for each additional core on which it runs. This can be seen in the concavity of a job’s speedup function, which describes the job’s processing speed as a function of the number of cores on which it runs. Examples of malleable jobs include machine learning tasks parallelized across multiple GPUs, and large-scale database queries parallelized across multiple servers. Given the prevalence of malleable jobs, several theoretical works have posed the problem of how to allocate a fixed number of cores across a stream of arriving malleable jobs so as to minimize the mean response time across jobs. We refer to this as the Core Allocation to Malleable jobs (CAM) problem. Previous theoretical work has only addressed the CAM problem under the assumption that either all jobs follow the same speedup function, or the speedup functions all follow a very unrealistic, simple form. By contrast, we solve the CAM problem under a highly general setting. We allow for multiple job classes, each with an arbitrary concave speedup function and holding costs (weight). Furthermore, unlike prior work, we allow for generally distributed inter-arrival times and job sizes. We analyze the CAM problem in the mean field asymptotic regime and derive two distinct mean field optimal policies, FW-CAM and WHAM. FW-CAM is interesting because it demonstrates a new intuition: in the mean field regime, job sizes are not relevant in finding an optimal policy. WHAM (Whittle Allocation for Malleable jobs) is interesting because it is asymptotically optimal and also serves as a good heuristic even outside of the asymptotic regime. Notably, none of the policies previously proposed in the literature are mean field optimal when jobs may follow different speedup functions. 1. Introduction Modern data centers and cloud computing clusters are increasingly tasked with hosting workloads composed of malleable jobs, such as machine learning training tasks ( Jayaram Subramanya et al. 2023 ; Qiao et al. 2021 ) , large-scale database queries ( Leis et al. 2014 ; Wagner et al. 2021 ) , and data center computing tasks ( Tumanov et al. 2016 ; Delgado et al. 2018 ) . Unlike traditional single-server jobs, malleable jobs can utilize multiple processor cores to accelerate their execution. Furthermore, unlike multi-server jobs that require a specific number of cores to run, malleable jobs do not have hard constraints on the degree of parallelism; a malleable job can execute on any number of cores, and can change its degree of parallelism as it runs. Given a stream of malleable jobs that arrive to a system over time, a system operator must allocate a fixed pool of n cores among the arriving jobs to optimize system performance (e.g., the mean response time, where a job’s response time is the time from when it arrives until it completes). Designing an efficient Core Allocation Policy for this setting remains a significant open challenge. Motivated by these applications, this paper studies the problem of Core Allocation to Malleable jobs (referred as CAM later in this paper). In this problem, we are given n cores and a stream of malleable jobs. The goal is to, at all times, determine how many cores to assign to each job – the number of cores assigned to a job can change over time. The objective is to minimize the (weighted) mean response time (i.e., time-average total holding cost, see Section 3 ). For ease of exposition, we refer to the objective as mean response time throughout the introduction. 1.1. Speedup functions and their effect on running time Figure 1 . Examples of speedup functions. A defining characteristic of this problem is the diminishing marginal returns associated with parallel execution. A job’s speedup function , s(k) , describes how much faster a job runs on k cores compared to a single core. Job speedup functions are typically concave and sublinear (see Figure 1 for some examples). Hence running a job on 4 cores may only increase its speed by a factor of 2. The CAM problem is complex because there are multiple classes of jobs, where every job class is associated with a different speedup function. Specifically, s_{i}(k) denotes the speedup function of a class- i (see Section 3 for the formal definition). Additionally, every class of job can have a different size distribution. The size of a job is the inherent work associated with the job, which we measure as the job’s running time on a single core. The running time of a job on k cores is determined by its size, speedup function, and the number of cores, k , as explained in Section 3 . 1.2. System Load vs. Effective Load In the CAM problem, as more cores are allocated to a single job, the overall system efficiency (defined as the total inherent work completed per unit of core time) decreases. To formalize this, we introduce a distinction between system load and effective load. For an m -class M/G/ n system ( n cores), the system load , \rho is defined as \rho=\frac{\sum_{i=1}^{m}\lambda_{i}\mathrm{\bf E}\left[X_{i}\right]}{n}, where \lambda_{i} is the arrival rate of class- i jobs, X_{i} is a random variable denoting the job size of a class- i job, and n is the number of cores. The system load is important in determining system performance. While the system load can be defined exactly the same way for the CAM problem, the system load alone is no longer sufficient to capture the queueing behavior of the system. This is because parallelization increases the "effective work" of a job due to sublinear speedup. For instance, if a job runs on 4 cores but achieves only a 2\times speedup, it consumes twice the core-seconds compared to the case when it is run on 1 core. In other words, the job’s “effective work” is double its inherent work. Consequently, the effective load on the system is strictly greater than the inherent system load, and the system may become unstable even when the system load is smaller than 1. Thus, essentially, the queueing behavior of a system is determined by the effective load , which depends on both the system load and the core allocation policy. This concept of effective load is central to our analysis in Section 5 and is further illustrated in Section 5.1 . 1.3. Asymptotic Regimes We are motivated to study the CAM problem in the realm of asymptotic regimes because of its complexity. Note that the CAM problem is strictly more challenging than the classical M/G/ n scheduling problem (where jobs are not parallelizable and each occupies a single server). The optimal scheduling policy for the M/G/ n remains open except under asymptotic regimes (see Section 2 for more discussion). Hence, in order to build intuition for a good allocation policy for CAM, we turn to asymptotic analysis. We limit our attention to the wide class of regimes where both the arrival rate and number of cores go to infinity while the job sizes stay fixed. In traditional M/G/ n systems, the regimes are differentiated by how the arrival rate scales compared to the number of cores. For example, in the mean field regime ( Dai et al. 2010 ; Gast and Van Houdt 2017 ; Gast et al. 2012 ; Gast and Bruno 2010 ) , the arrival rate scales proportionately to the number of cores; hence the system load \rho is held fixed. This is a good representation for real-world large-scale systems which operate under reasonable (not too high) loads. By contrast, in non-mean-field regimes, the arrival rate scales faster than the number of cores, causing the system load to approach 1 ( Halfin and Whitt 1981 ; Gupta and Walton 2019 ) . In the CAM problem, running jobs on more than 1 core causes the effective load to be higher than the system load. Hence for the CAM problem, regimes where the system load \rho approaches 1 are not interesting because they do not allow jobs to be parallelized. Specifically, given jobs that follow strictly sublinear speedup functions, if any constant fraction of jobs run on more than 1 core, the effective load is a constant factor larger than the system load (which is already approaching 1), resulting in an effective load greater than 1 and system instability. We formalize this intuition in Proposition A.1 . This observation compels us to focus on the mean field asymptotic regime (see Section 3 ), where the system load remains constant while the number of cores scales. 1.4. Our Approaches and Impacts We derive two distinct mean-field optimal policies, FW-CAM and WHAM , using fundamentally different methodologies. FW-CAM (Definition 5.1 ): The first policy, FW-CAM (Fixed-Width policy for CAM), leverages the effective load intuition. Recall that in the mean field regime, the system load \rho is fixed. The key idea of FW-CAM is to select a degree of parallelization that pushes the effective load towards 1 , in a Sub-Halfin-Whitt manner ( Halfin and Whitt 1981 ) , which, we will show, avoids queueing. Section 5.1 details this idea. While conceptually simple, FW-CAM reveals a critical insight: to achieve mean field optimality, a policy should treat all jobs in the same class (i.e., having the same speedup function) equally, allocating cores independently of the job’s remaining size. Any policy that fails to do this is not mean field optimal (see Proposition B.1 ). This contradicts the classical scheduling intuition of "prioritizing short jobs" (e.g., ( Berg et al. 2021 ; Berg et al. 2024 ) ). However, while FW-CAM is asymptotically optimal, we find that its performance degrades outside the asymptotic limit (if n is small). To address this, we derive a second policy based on the Whittle Index ( Whittle 1988 ) , which is mean field optimality and provides robust performance for small n . WHAM (Definition 6.9 ): Our second policy, WHAM (WHittle Allocation policy for Malleable jobs), applies the Whittle policy framework to the CAM problem. Whittle policies, introduced in the seminal work ( Whittle 1988 ) , are known for their asymptotic optimality and strong empirical performance for bandit problems (see Section 2 for prior work). However, to apply the Whittle policy to queueing problems, one must translate the queueing problem into a bandit problem. Then, deriving the Whittle policy for the corresponding bandit problem is usually intricate (e.g., ( Larrañaga et al. 2014 ; Aalto 2024 ) ). We provide background on the Whittle policy in Section 6 . A simplified definition of our WHAM policy for minimizing mean response time appears below. Definition 1.1 (Informal, WHAM for minimizing the mean response time). Given n cores, at every moment of time, • If the number of jobs is larger than n , allocate 1 core to each of the n jobs with smallest remaining size. • Otherwise, for each job j in the system, with job class i_{j} , find the largest possible allocation k_{j} such that the value of f_{i_{j}}(k_{j}):=\frac{s_{i_{j}}^{\prime}(k_{j})}{s_{i_{j}}(k_{j})-ks_{i_{j}}^{\prime}(k_{j})} is equal for every job and the total number of cores used across jobs is less than n . Notably, WHAM exhibits a "two-mode" structure. In the mean field regime, the first mode (number of jobs >n ) rarely occurs, aligning with the FW-CAM insight that job size information is not needed for a mean field optimal policy. However, outside of the asymptotic regime, both modes are essential. Simulations show that WHAM has strong performance even outside of the mean field regime, and its performance converges to the asymptotic optimum quickly (see Figure 2(a) ). 1.5. Our Contributions The contributions of this paper are as follows: • We derive two mean field optimal policies, FW-CAM and WHAM, for the CAM problem under extremely general settings. In particular, we allow for generally-distributed inter-arrival times, generally-distributed job sizes, multiple job classes with distinct speedup functions, and a different holding cost for each class. • (Section 5 ) Our first policy, FW-CAM, leverages the concept of effective load to derive a mean field optimal policy, where all jobs in the same class get the same allocation. • (Section 6 ) Our second policy, WHAM, serves as a bridge between theory and practice. It is not only mean field optimal (subject to some mild conditions) but also demonstrates superior empirical performance, converging rapidly to the optimal limit. It serves as a strong heuristic for general CAM settings. • Prior work on the CAM problem has been largely limited to only one speedup function or a narrow class of speedup functions (see Section 2 ). Even for the simple setting of just a single speedup function, our analysis provides novel insights challenging the conventional wisdom of prioritizing short jobs. • Finally, we believe the derivation of the Whittle policy for the CAM problem (WHAM) is of independent theoretical interest, particularly the emergence of the two-mode behavior. 2. Prior Work We review the prior work in three categories: work on relevant scheduling problems that differ from CAM, prior work on the CAM problem, and work applying bandit theory to queueing. Scheduling problems relevant to, but different from CAM Even under traditional multi-server scheduling, where jobs are not parallelizable and each job occupies only a single server, the optimal policy is still widely open. For M/G/ n systems, the only known optimality result is that SRPT- n is optimal in the conventional heavy traffic regime ( Grosof et al. 2019 ) . However, it has recently been shown that SRPT- n is not optimal under non-limiting load ( Grosof and Wang 2024 ) , and this line of work is still active. Another active line of work on multi-server scheduling involves multiserver jobs (e.g. ( Grosof et al. 2022 ; Chen et al. 2025 ) ). These jobs are parallelizable, but not malleable. Specifically, in ( Grosof et al. 2022 ; Chen et al. 2025 ) each job requires a fixed given number of cores specific to that job. It is hard to translate intuitions learned from the multiserver job setting to the CAM setting where jobs are malleable and can run on any number of cores. CAM: Core Allocation Policies for Malleable Jobs A variety of work from the system community considers scheduling malleable jobs ( Lin et al. 2018 ; Qiao et al. 2021 ; Jayaram Subramanya et al. 2023 ; Tumanov et al. 2016 ; Wagner et al. 2021 ) . However, all of these systems rely on simple heuristic policies with no theoretical guarantees. The CAM problem has been studied by the performance modeling community over the past decade, but most of this prior work on CAM ( Berg et al. 2017 ; Berg and Harchol-Balter 2021 ; Berg et al. 2021 ) assumes that all jobs follow a single speedup function. While some work considers multiple speedup functions ( Berg et al. 2020 ; Berg et al. 2022 ; Berg et al. 2024 ) , this work assumes that the speedup functions follow a rooftop shape: class- i jobs are perfectly parallelizable up to k_{i} cores, but get no further benefit from >k_{i} cores. Even within this restrictive setting of rooftop speedup functions, very few results are known. The closest work to ours is ( Berg et al. 2024 ) . However that work focuses on asymptotic regimes where \rho\to 1 , which are not meaningful when considering strictly sublinear speedup functions (See Proposition A.1 ). Finally, we note that all the prior work on the CAM problem assumes that job sizes are exponentially distributed and that the arrivals follow a Poisson process (the only exception is ( Berg et al. 2021 ) , which considers a clearing system). Our work allows for generally distributed, independently sampled (GI) job size distributions and inter-arrival times. Using Bandit Theory to solve Scheduling problems The latter half of the paper will leverage a bandit model. We do not consider a bandit problem in online learning sense; instead, we consider Markovian bandits, a special case of Markov Decision Processes (MDPs) (see Section 6.1 for more background on Markovian bandits). Throughout the rest of this paper, “bandits” refers to Markovian bandits. There is a subarea of queueing theory that first transforms various scheduling problems into bandit problems and then leverages bandit theory to solve the scheduling problem, e.g., ( Aalto et al. 2009 ; Scully and Harchol-Balter 2021 ; Larrañaga et al. 2014 ; Aalto 2024 ; Yu and Scully 2024 ) . While we aim to apply this technique, the translation of the CAM problem into a bandit problem introduces unique challenge: Unlike most scheduling problems, in CAM one not only needs to decide which job to run, but also needs to decide how many cores to run the job on. Thus, traditional bandits, which only support a binary action for each job (either "serve" or "queue"), cannot model the CAM problem. The CAM translates most cleanly to the recently-introduced “multi-gear” bandit framework ( Niño-Mora 2022 ) , which allows multiple actions allowed for each job. The Whittle policy for bandit problems The WHAM policy, which we will derive in Section 6 , is a Whittle policy ( Whittle 1988 ) . Variants of Whittle policies have been shown to be asymptotically optimal in various bandit settings (e.g. ( Whittle 1988 ; Weber and Weiss 1990 ; Ayesta et al. 2021 ) ); we provide background Whittle policies in Section 6.2 . Even outside of asymptotic regimes, the Whittle index is known to be a good heuristic for bandit problems ( Niño-Mora 2023 ) . Deriving the Whittle policy for a bandit problem is difficult in general, and deriving the Whittle policy for the CAM problem involves two particular challenges: First, because the CAM problem is a multi-gear bandit, it necessitates a more complex Whittle formulation ( Niño-Mora 2022 ) . Second, while our objective is to minimize the time-average total holding cost, the objective of the multi-gear bandit problem in ( Niño-Mora 2022 ) is to maximize total reward. This difference in objectives requires us to apply the “vanishing discount factor" technique ( Whittle 2005 ) , which adds greatly to the complexity of our analysis. 3. Core Allocation to Malleable jobs: Our Problem Setting We consider an m -class GI/GI/ n system with n homogeneous cores. 3.1. Job Classes There are m classes of jobs. Each class has its own arrival process, job size distribution, speedup function and holding cost, all to be defined below. Arrival process: The arrival process of class i is defined by i.i.d. inter-arrival times drawn from distribution A_{i} . We assume that A_{i} has mean \frac{1}{\lambda_{i}} and a finite second moment. Define \lambda:=\sum_{i=1}^{m}\lambda_{i} to be the total arrival rate of jobs. Job size distribution: The size of a job is defined as the time needed to complete a job on a single core. We can think of this as the inherent work associated with the job. The sizes of class i jobs are i.i.d. random variables, X_{i} , with \mathrm{\bf E}\left[X_{i}\right]=1/\mu_{i} . We assume that X_{i} has a finite third moment for each class, i . Throughout, we assume job sizes are known, but surprisingly, the exact size of each job turns out to be useless in the mean field regime. Speedup function: A job’s running time depends on the number of cores the job runs on and on its speedup function . We define s_{i}:\mathbb{R}^{+}\to\mathbb{R}^{+} to be the speedup function of class i jobs. If a class i job with size x runs on k cores, then its running time becomes \mbox{Running time on }k\mbox{ cores}=\frac{x}{s_{i}(k)}. Note that we assume that jobs can be assigned fractional cores, but a job cannot be assigned between 0 and 1 core. We make the following mild assumptions on the speedup functions: For any job class i , the speedup function s_{i}(\cdot) should fulfill the following properties: • s_{i}(1)=1 . • Sub-linearity: s_{i}(k)\leq k for k\geq 1 . • Not perfectly elastic: \exists k>1 such that s_{i}(k)1 . Although real-world speedup functions may not be perfectly concave, in practice, this is dealt with by using the monotonic, concave hull of an empirically measured speedup function ( Ghanbarian et al. 2024 ) . 3.2. Performance Metrics Holding Cost: Every class i job is associated with a holding cost c_{i} . The holding cost of a job specifies the rate that cost is incurred per second that the job is in the system, i.e., the job costs c_{i} dollars per second from when it arrives until it departs. Goal: The goal is to minimize the time-average total holding cost incurred, which we denote by \widebar{Cost} . Mathematically, let T_{i} be the stationary response time of class- i jobs. Then each class- i job contributes an expected total holding cost of c_{i}\cdot\mathrm{\bf E}\left[T_{i}\right] . Thus, the time-average total holding cost contributed by all class- i jobs is \lambda_{i}c_{i}\mathrm{\bf E}\left[T_{i}\right] . Hence the minimization objective of our CAM problem, the (normalized) time-average total holding cost, can be expressed as below 1 1 1 In this paper, we assume ergodicity and the existence of a stationary distribution of the system. : (1) \widebar{Cost}:=\frac{1}{\lambda}\sum_{i=1}^{m}\lambda_{i}c_{i}\mathrm{\bf E}\left[T_{i}\right]. Here the normalization (by \frac{1}{\lambda} ) does not change the optimal policy. It is only for convenience in the analysis of the asymptotic regime. No Preemption Overhead: We assume that there is no overhead when preempting or changing a job’s allocation. This simplification is also assumed in most prior theory works, e.g., ( Berg et al. 2020 ; Berg et al. 2024 ; Berg et al. 2022 ; Ghanbarian et al. 2024 ; Berg et al. 2021 ) ). Stability considerations: While we do not derive exact necessary and sufficient conditions for stability in the CAM problem, we will prove that both of our two policies, FW-CAM and WHAM stabilize the system in the mean field regime (see Lemma 5.5 and Lemma 6.10 ). 3.3. The Mean Field Regime The main results of this paper consider the mean field scaling regime . In the mean field regime, the number of classes, job size distributions and speedup functions are held fixed, and the arrival rate is scaled proportionally with the number of cores. Formally, a sequence of systems indexed by d are considered as d\to\infty . Let \lambda_{i}^{(d)} be the arrival rate of type- i jobs in the d^{th} system, and let n^{(d)} be the number of cores in the d^{th} system. Then in the mean field regime, \lambda_{i}^{(d)}=d\cdot\lambda_{i} and n^{(d)}=d\cdot n. More precisely, inter-arrival times in the d^{th} system are sampled from A_{i}^{(d)}:=\frac{A_{i}}{d} . In this way, the mean inter-arrival time scales, but the coefficient of variation of the inter-arrival time distribution stays constant. Importantly, in the mean field regime, the system load stays constant as d is increased. Mathematically, the system load in the d^{th} system is defined as \rho^{(d)}:=\frac{1}{n^{(d)}}\sum_{i=1}^{m}\lambda_{i}^{(d)}\cdot\mathrm{\bf E}\left[X_{i}\right], and is the same for all d. We refer to the CAM problem in the d^{th} system as CAM^{(d)} . A policy \pi with cost \widebar{Cost}^{\pi}_{CAM^{(d)}} (as defined in ( 1 )) is considered mean field optimal for the CAM problem if, for any other policy \pi^{\prime} with cost \widebar{Cost}^{\pi^{\prime}}_{CAM^{(d)}} we have \lim_{d\to\infty}\frac{\widebar{Cost}^{\pi}_{CAM^{(d)}}}{\widebar{Cost}^{\pi^{\prime}}_{CAM^{(d)}}}\leq 1. 4. Preliminaries: A relaxed version of the CAM problem In this section, we introduce a relaxed version of the CAM problem, which serves as a lower bound on \widebar{Cost} (Defined in ( 1 )) for the CAM problem. In the Relaxed problem, we drop the hard constraint that at every moment of time only n cores are available. Instead, we allow the total number of cores to fluctuate at our control, so long as the time-average number of cores is no more than n . This relaxation is commonly used in queueing/bandits theory to prove asymptotic optimality ( Verloop 2016 ; Weber and Weiss 1990 ; Whittle 1988 ) . Obviously, the cost for the Relaxed problem is a lower bound for the CAM problem cost, since the constraint of a fixed number of cores is relaxed. Mathematically, denote the optimal (normalized) time-average total holding cost of the CAM problem by \widebar{Cost}_{CAM}^{*} and the optimal (normalized) time-average total holding cost of the Relaxed problem by \widebar{Cost}_{Relaxed}^{*} . Then we have that (2) \widebar{Cost}_{CAM}^{*}\geq\widebar{Cost}_{Relaxed}^{*}. By relaxing the constraint on the number of cores used, the Relaxed problem becomes a simple convex optimization problem that can be solved using standard techniques. In fact, ( Li et al. 2024 ) has independently solved the Relaxed problem in a different context. For brevity, we restate their solution here and defer the reader to ( Li et al. 2024 ) for a full proof. Theorem 4.1 (Theorem 1 in ( Li et al. 2024 ) ). The optimal policy for the Relaxed problem is: Whenever a class- i job arrives in the system, k_{i} cores are immediately allocated to it until it completes, where k_{i} is the solution to the following convex optimization problem (3) \displaystyle\underset{k_{i}}{\text{minimize}} \displaystyle\sum_{i=1}^{m}\frac{\lambda_{i}}{\lambda}\frac{\mathrm{\bf E}\left[X_{i}\right]c_{i}}{s_{i}(k_{i})} \displaystyle\text{subject to} \displaystyle\sum_{i=1}^{m}\frac{\lambda_{i}\mathrm{\bf E}\left[X_{i}\right]k_{i}}{s_{i}(k_{i})}\leq n, \displaystyle k_{i}\geq 1. We refer to this optimal solution to the Relaxed problem as FW-Relax (where FW is short for Fixed-Width), because every job of class i gets the same finite number of cores, k_{i} 2 2 2 Here k_{i} must be finite because the speedup functions are not perfectly elastic. . Intuitively, ( 3 ) follows from the following observations: (1) Since each class i job gets k_{i} cores, we have that \mathrm{\bf E}\left[T_{i}\right]=\frac{\mathrm{\bf E}\left[X_{i}\right]}{s_{i}(k_{i})} . Thus the objective of ( 3 ) is just \frac{1}{\lambda}\sum_{i=1}^{m}\lambda_{i}c_{i}\mathrm{\bf E}\left[T_{i}\right] , which is the (normalized) time-average total holding cost, \widebar{Cost} . (2) Similarly, the expected total number of core-seconds that a class i job uses is k_{i}\mathrm{\bf E}\left[T_{i}\right]=\frac{\mathrm{\bf E}\left[X_{i}\right]k_{i}}{s_{i}(k_{i})} , thus \sum_{i=1}^{m}\frac{\lambda_{i}\mathrm{\bf E}\left[X_{i}\right]k_{i}}{s_{i}(k_{i})} represents the time-average number of cores used. Let \widebar{Cost}_{Relaxed}^{FW-Relax} denote the (normalized) time-average total holding cost of the Relaxed problem under policy FW-Relax. Then by Theorem 4.1 we have that (4) \widebar{Cost}_{Relaxed}^{*}=\widebar{Cost}_{Relaxed}^{FW-Relax}. We now apply Theorem 4.1 in the mean field regime. Here, we have that \lambda_{i}^{(d)}=d\cdot\lambda_{i} and n^{(d)}=d\cdot n. Thus for any d , ( 3 ) remains the same and provides a lower bound on the CAM. Formally, we define the following notation for the optimal solution to the optimization problem ( 3 ). Definition 4.2. Consider the convex optimization ( 3 ) parameterized by the set of arrival rates \{\lambda_{i}\} and number of cores n . Define its optimal solution to be k_{i}^{*}\left(\left\{\lambda_{i}\right\},n\right) and its optimal value of the objective to be V_{R}^{*}\left(\{\lambda_{i}\},n\right) . We observe that for all d , V_{R}^{*}\left(\{\lambda_{i}^{(d)}\},n^{(d)}\right)=V_{R}^{*}\left(\{\lambda_{i}\},n\right). Moreover, by Theorem 4.1 , we have that \widebar{Cost}_{Relaxed^{(d)}}^{*}=\widebar{Cost}_{Relaxed^{(d)}}^{FW-Relax}=V_{R}^{*}\left(\{\lambda_{i}^{(d)}\},n^{(d)}\right). Thus, together with ( 2 ), we can get the lower bound for the CAM problem in mean field: (5) \widebar{Cost}_{CAM^{(d)}}^{*}\geq\widebar{Cost}_{Relaxed^{(d)}}^{*}=V_{R}^{*}\left(\{\lambda_{i}^{(d)}\},n^{(d)}\right)=V_{R}^{*}\left(\{\lambda_{i}\},n\right). 5. The first Mean Field optimal policy: FW-CAM In this section, we present the first mean field optimal policy for the CAM problem, FW-CAM. In Section 5.1 we first develop the by intuition behind our policy. Next in Section 5.2 we present our FW-CAM policy. Finally in Section 5.3 we present the proof of its mean field optimality. 5.1. Intuition behind FW-CAM While the Relaxed problem has a simple optimal policy (FW-Relax), the optimal policy for the CAM problem is not clear at all. The main difficulty is that, in the CAM problem, we only have a fixed number of cores, and thus jobs may queue. By contrast, there is no queueing under the optimal policy in the Relaxed setting where we can occasionally use more than n cores. Fortunately, it is well-known that for many problems, queueing disappears in the mean field limit (e.g., ( Atar et al. 2010 ; Van Mieghem 1995 ; Stolyar 2004 ) ). We therefore hope to define a variant of the FW-Relax policy in the CAM setting which performs similarly to FW-Relax in the Relaxed setting as the probability of queueing vanishes. However, in the CAM problem, applying the FW-Relax policy directly will be a disaster — not only will queueing happen, but the system will even be unstable. The key intuition lies in the distinction between system load and effective load . System load and effective load: For a better understanding of the queueing behavior in the CAM problem, we need to distinguish between the system load and the effective load . Note that in the mean-field regime, the system load \rho^{(d)}:=\frac{1}{n^{(d)}}\sum_{i}^{m}\lambda_{i}^{(d)}\mathrm{\bf E}\left[X_{i}\right] stays constant as d\to\infty . However, when jobs are parallelized, because of the sub-linear nature of the speedup functions, the “inherent work” done by each core per unit time is smaller than the case when jobs are run on only one core. In other words, while a class- i job of size x requires x core-seconds to complete on a single core, the total number of core-seconds used to complete the job on k cores is k\cdot\frac{x}{s_{i}(k)} . We refer to the number of core-seconds a job consumes as the job’s effective work . We can then define effective load in terms of each job’s effective work rather than its inherent work (job size). Because the time-average number of cores demanded must be smaller than the number of cores, n , it is necessary for effective load to be smaller than 1 for the system to be stable. To derive the effective load under FW-Relax, note that each each class- i job gets k_{i}=k_{i}^{*}\left(\left\{\lambda_{i}\right\},n\right) cores. As a result, in expectation each class- i job contributes \frac{\mathrm{\bf E}\left[X_{i}\right]k_{i}}{s_{i}(k_{i})} to the total effective work. Hence the total effective load is \text{Total Effective Load}=\frac{1}{n}\sum_{i=1}^{m}\lambda_{i}\frac{\mathrm{\bf E}\left[X_{i}\right]k_{i}}{s_{i}(k_{i})} Note that k_{i} is defined by solving optimization problem ( 3 ). Moreover, by monotonicity of the speedup functions, the constraint inequality in ( 3 ) will be tight for the optimal solution k_{i} , giving \sum_{i=1}^{m}\lambda_{i}\frac{\mathrm{\bf E}\left[X_{i}\right]k_{i}}{s_{i}(k_{i})}=n. This means that the effective load under the FW-Relax policy becomes 1, the resulting queueing system is unstable, and the queueing time could blow up to infinity. Our solution: To find a mean field optimal policy, we want to mimic the FW-Relax policy in the CAM problem while keeping the effective load below 1. Our main insight is that, while FW-Relax sets the effective load to 1, a mean field optimal policy for the CAM problem can get similar performance by carefully letting the effective load approach 1 as the system scales. To accomplish this, we define the FW-CAM policy (see Definition 5.1 ). Roughly speaking, under FW-CAM, a class- i job is allocated k_{i}^{*}\left(\left\{\lambda_{i}\right\},n-n^{\beta}\right) cores, where \beta\in(0.75,1) . As a result, the effective load in the d^{th} system scales as 1-\omega(d^{-0.25}) . This scaling regime lies within the Sub-Halfin-Whitt regime 3 3 3 The Sub-Halfin-Whitt regime refers to systems where load scales as 1-\omega(d^{-0.5}) . We enforce a stronger scaling regime ( 1-\omega(d^{-0.25}) ) in order to apply the results in ( Li and Goldberg 2025 ) . . For a variety of queueing systems with non-parallelizable jobs, it is well-known that the mean queueing time goes to 0 in this regime ( Li and Goldberg 2025 ) . We will show that the mean queueing also goes to 0 in the CAM system. 5.2. Defining FW-CAM FW-CAM first divides the total number of cores n among the m classes, creating a pool of size n_{i} for the i th class to use. FW-CAM then chooses how to allocate these n_{i} cores to the stream of class- i jobs for each class. This two-stage design is not strictly necessary, but simplifies our analysis. We formally define FW-CAM as follows. Definition 5.1 (FW-CAM). Let k_{i}:=k_{i}^{*}\left(\left\{\lambda_{i}\right\},n-n^{\beta}\right) , where 0.75<\beta<1 (where k_{i}^{*} is defined in Defintion 4.2 ). For each class i , define the effective load to be r_{i}:=\lambda_{i}\cdot\frac{\mathrm{\bf E}\left[X_{i}\right]\cdot k_{i}}{s_{i}(k_{i})} , and let the number of cores used for class i be n_{i}:=n\cdot\frac{r_{i}}{\sum_{j=1}^{m}r_{j}}. Whenever a class i job arrives, if the total number of cores used by existing class i jobs is no more than n_{i}-k_{i} , the new job is allocated k_{i} cores until it completes; otherwise, the new job queues. Whenever a class i job completes, if there are queueing class i jobs, the released k_{i} cores are assigned to the class- i job that has waited the longest; otherwise, if there are no queueing class i jobs, the released cores idle even if there are queueing jobs from other classes. Observe that the policy FW-CAM is simple both to define and to compute numerically via a convex optimization problem. The following lemma shows that the value of k_{i} used in FW-CAM ( k_{i}^{*}\left(\left\{\lambda_{i}\right\},n-{n}^{\beta}\right) ) converges to that used in FW-Relax ( k_{i}^{*}\left(\left\{\lambda_{i}\right\},n\right) ) in the mean field limit. This lemma will be used in Lemma 5.5 and Theorem 5.6 . Lemma 5.2. For any class i , \lim_{d\to\infty}k_{i}^{*}\left(\left\{\lambda_{i}^{(d)}\right\},n^{(d)}-{\left(n^{(d)}\right)}^{\beta}\right)=k_{i}^{*}\left(\left\{\lambda_{i}\right\},n\right) . Proof Sketch. Note that both the left hand side and the right hand side of the equality are solutions to the optimization problem ( 3 ) (with different parameters). Moreover, we have k_{i}^{*}\left(\left\{\lambda_{i}^{(d)}\right\},n^{(d)}-{\left(n^{(d)}\right)}^{\beta}\right)=k_{i}^{*}\left(\left\{\frac{\lambda_{i}^{(d)}}{d}\right\},\frac{n^{(d)}-{\left(n^{(d)}\right)}^{\beta}}{d}\right)=k_{i}^{*}\left(\left\{\lambda_{i}\right\},n-n^{\beta}d^{\beta-1}\right). The lemma then follows from the continuity and convexity of ( 3 ). See Appendix C . ∎ 5.3. The mean field optimality of FW-CAM We now prove the mean field optimality of FW-CAM. We use Lemma 5.3 and Lemma 5.5 to show that the expected queueing time of all classes goes to 0 under FW-CAM. This leads to the proof of the main theorem, Theorem 5.6 . We begin with Lemma 5.3 , which shows that the system under FW-CAM can be viewed as m independent FCFS (first-come-first-serve) GI/GI/ n_{i}^{\prime} systems where n_{i}^{\prime}=\lfloor\frac{n_{i}}{k_{i}}\rfloor . Lemma 5.3. Let n_{i}^{\prime}=\lfloor\frac{n_{i}}{k_{i}}\rfloor . Then the response time of class i jobs under policy FW-CAM is the same as that in the following single-class GI/GI/ n_{i}^{\prime} system: Inter-arrival times are distributed as A_{i} , and job sizes are distributed as \frac{X_{i}}{s_{i}(k_{i})} . Proof. The proof is straightforward. Under policy FW-CAM, each job class sees and independent system and each class- i job occupies k_{i} cores. Thus, the running time of each class- i job follows the distribution \frac{X_{i}}{s_{i}(k_{i})} . The n_{i} nodes assigned to class i are divided into n^{\prime}_{i} chunks, creating a natural coupling between the system under FW-CAM and the GI/GI/ n_{i}^{\prime} system described above. ∎ We now borrow the following lemma (Lemma 5.4 ) from ( Li and Goldberg 2025 ) to prove that the queueing time under FW-CAM goes to 0 when d\to\infty (Lemma 5.5 ). Lemma 5.4 (Corollary 3 from ( Li and Goldberg 2025 ) ). For a GI/GI/ n queue with inter-arrival time A and job size distribution S , suppose: (i) \mathrm{\bf E}\left[A^{2}\right]<\infty , (ii) \mathrm{\bf E}\left[S^{3}\right]<\infty , (iii) \frac{1}{\mathrm{\bf E}\left[A\right]}0.75 , we have that \lim_{d\to\infty}\mathrm{\bf E}\left[N_{Q}^{(d)}\right]\to 0 . By Little’s Law, the expected queueing time of class- i jobs also goes to 0. ∎ Finally, we can prove our main theorem, which shows the mean field optimality of FW-CAM. Theorem 5.6. Our policy FW-CAM is mean field optimal. Proof. By Lemma 5.2 , as d\to\infty , the number of cores that a class i job is allocated converges to k_{i}^{*}\left(\left\{\lambda_{i}\right\},n\right) . Hence the expected service time of class- i jobs converges to \frac{\mathrm{\bf E}\left[X_{i}\right]}{s_{i}(k_{i}^{*})} . Moreover, by Lemma 5.5 , the expected queueing time of class- i jobs converges to 0. Thus, the expected response time of class- i jobs converges to \frac{\mathrm{\bf E}\left[X_{i}\right]}{s_{i}(k_{i}^{*})} , and the (normalized) time-average total holding cost under FW-CAM converges to \lim_{d\to\infty}\widebar{Cost}_{CAM^{(d)}}^{FW-CAM}=\frac{1}{\lambda}\sum_{i=1}^{m}\lambda_{i}c_{i}\frac{\mathrm{\bf E}\left[X_{i}\right]}{s_{i}(k_{i}^{*})}=V_{R}^{*}\left(\{\lambda_{i}\},n\right), which is the mean field lower bound for the CAM problem established in ( 5 ). ∎ 6. A “Better” Mean-Field Optimal policy: WHAM In Section 5 , we prove the mean field optimality of FW-CAM. However, outside the mean field regime, FW-CAM may make frequent mistakes. For example, if the number of jobs in the system is very small, FW-CAM may leave a lot of cores idle. On the other hand, if there are too many jobs in the system, FW-CAM allocates many cores to a subset of jobs, while forcing other jobs to queue. Intuitively, outside the mean field regime, a better policy should take the current number of jobs in the system into consideration. Hence, a natural question is: Is there a better policy that incorporates the current number of jobs in the system, while maintaining the mean field optimality? Our answer to this question is yes! We will derive a policy, called WHAM, which is both mean field optimal and also outperforms FW-CAM outside the mean field limit. Our results require one additional technical assumption on the speedup functions. 4 4 4 Assumption 1 is not necessary for the mean field optimality of FW-CAM. Assumption 1 (twice differentiable speedups). For any class i , assume that the speedup function is twice differentiable and s_{i}^{\prime\prime}(k)<0 for any k>1 . The remainder of the section is organized as follows: (1) (Section 6.1 to Section 6.5 ) The derivation of WHAM (Definition 6.9 ): We first provide the background on bandit problems in Section 6.1 and the background on the Whittle policy in Section 6.2 . Then, in Section 6.3 , we define the bandit formulation for the CAM problem. Our goal is to derive the Whittle policy for this bandit formulation. Then in Section 6.4 , we show how to set up the Whittle approach for our bandit formulation. Finally in Section 6.5 , we derive the Whittle policy, WHAM. (2) (Section 6.6 ) The proof of the mean field optimality of WHAM (Theorem 6.11 ) 6.1. Background on the (Markovian) Bandit theory A (Markovian) bandit problem is a special case of a Markov decision problem (MDP). A bandit problem has multiple arms , where each arm corresponds to a Markov process. At every moment of time, an agent selects an action for each arm, and a cost is incurred according to the states of the arms. The goal is to minimize the (discounted or time-average) cumulative cost (across all arms) over time. While there are many different versions of bandit problems, we choose to provide only the definition of the bandit formulation most relevant to us, i.e., the continuous-time multi-gear bandit. 5 5 5 Here we generalize the multi-gear bandits introduced in ( Niño-Mora 2022 ) to allow for continuous decision time, continuous state space, continuous action space and the arrival and departure of arms. The Arms (Markov Decision Processes): A bandit problem has multiple arms, where each arm i is associated with a continuous-time MDP. The MDP for arm i is defined by a state space \mathcal{S}_{i} and an action space \mathcal{A}_{i} . At any time t , the decision-maker selects an action a_{i}(t)\in\mathcal{A}_{i} (the “gear”), which determines the stochastic evolution of the state of arm i according to its MDP. The Resource Constraint: The defining feature of the “multi-gear” bandit problem is the coupling of these independent arms through a shared resource constraint at every moment of time. Each action a\in\mathcal{A}_{i} consumes a specific amount of resource, denoted by w_{i}(a) . The system is endowed with a total resource capacity of n at any moment of time. Mathematically, at every moment of time, t , the actions across all arms must satisfy the hard capacity constraint: (7) \sum_{\text{arm $i$ in system}}w_{i}(a_{i}(t))\leq n. The Objective: At any time, t , each arm i incurs cost at a rate C_{i}(x_{i}(t),a_{i}(t)) that depends on its current state x_{i}(t) and the chosen action a_{i}(t) . The goal is to find a policy which selects an action for each arm at every moment of time to minimize the total cost across all arms over time. We consider two standard objectives: • Discounted Cost: The cumulative cost is discounted by a factor \alpha>0 over an infinite horizon. The objective is to minimize: (8) \mathbb{E}\left[\int_{0}^{\infty}e^{-\alpha t}\sum_{\text{arm $i$ in system}}C_{i}(x_{i}(t),a_{i}(t))\,dt\right] • Time-Average Cost: The objective is to minimize the long-run time-average cost: (9) \lim_{T\to\infty}\frac{1}{T}\mathbb{E}\left[\int_{0}^{T}\sum_{\text{arm $i$ in system}}C_{i}(x_{i}(t),a_{i}(t))\,dt\right] While our primary goal in the CAM problem is minimizing the time-average total holding cost, the discounted framework is essential for the derivation of the Whittle index policy. We discuss this point in Section 6.3 . 6.2. Background on the Whittle policy In this section, we provide background on the Whittle policy ( Whittle 1988 ) . For the ease of illustration, we directly explain the (generalized) Whittle approach for discounted multi-gear bandits ( Niño-Mora 2022 ) . The Whittle approach consists of four steps: First , we relax the hard constraint that the total amount of resource used is no more than n at any moment of time. This hard constraint is relaxed to a total discounted usage constraint. Mathematically, suppose the total resource usage across all arms at time t is W(t) , then the hard constraint is W(t)\leq n . Whittle relaxes the hard constraint to the following constraint: \int_{0}^{\infty}e^{-\alpha t}W(t)dt\leq\frac{n}{\alpha}, where \alpha>0 is the discount factor. The bandit problem with this relaxed constraint (call this the "relaxed bandit") is then studied to obtain a heuristic for the original bandit. Second , Lagrange multipliers are used to solve the relaxed bandit. As a result, the relaxed bandit problem can be decomposed into independent single-arm bandit problems , where there is no constraint on the resource usage, but every unit of resource usage increases the service cost rate by \ell ( \ell serves as the Lagrange multiplier). This step puts a “price” on the resource usage, yielding a single-armed bandit problem parameterized by \ell for each arm. The hope is that, through controlling the “price”, the decision-maker can control the total resource usage across all the arms. Third , one solves each single-armed bandit problem for every value of service cost \ell . Intuitively, if the service cost \ell is very low, one would want to use a greater amount of resource for each arm; but if the service cost \ell is very high, one would want to use less resource. A property formalizing this intuition is called “indexability” ( ( Whittle 1988 ) ), which is a necessary condition for the Whittle policy to be well-defined. Intuitively, with indexability, the resource usage of any single arm is monotonically influenced by the service cost; this guarantees the existence of the “market-clearing” service cost defined below. Fourth , going back to the multi-armed bandit problem, the Whittle policy is defined as follows: at every moment of time, select a “market-clearing" service cost \ell such that if every single arm acts optimally under the service cost \ell (in the corresponding single-arm bandit problem), the total amount of resource used across all arms is exactly n . Remarks: The asymptotic optimality of the Whittle policy for bandit problems has been shown in prior work ( Whittle 1988 ; Weber and Weiss 1990 ) . In bandit theory, the asymptotic regime is typically defined in a way that the number of arms and the amount of resource capacity grow proportionally to infinity. Usually in traditional bandit problems where only binary actions are supported, the Whittle policy is described in the form of assigning each arm an index and always activating the arms with the highest index (e.g., ( Aalto 2024 ; Larrañaga et al. 2014 ) ). However, in our bandit formulation, the Whittle policy cannot be defined by an index function because each arm has multiple actions. Hence, we intentionally call our policy “the Whittle policy” instead of “the Whittle index policy.” 6.3. Our Multi-arm Bandit formulation In our bandit formulation, we model each job by an arm. The state of an arm is the remaining size of the corresponding job. The cost of an arm is the holding cost of the corresponding job. The action of an arm represents the number of cores assigned to the corresponding job; this is also the resource consumed by this action. The resource constraint is that we cannot assign more than n cores at any moment of time across the arms, and the objective is to minimize the time-average total holding cost across all jobs. Mathematically, we define the following continuous time bandit: Definition 6.1 (Our Time-average multi-armed bandit formulation). The CAM problem can be translated into the following bandit problem: Arm State: x\in\mathbb{R}\cup\bot . Each arm represents a job, and its state represents the remaining inherent work on the job. If x=\bot , the arm is marked as completed and leaves the system. Arrival and departure of arms: The inter-arrival time of class- i arms follows the distribution A_{i} ; Any class- i arm arrives with the state following distribution X_{i} , representing the inherent work of the job. Any arm in state \bot leaves the system. Cost: At every moment of time, for any class- i arm in the system, if its state is not \bot , it incurs cost at a rate of c_{i} per unit time (this corresponds to the holding cost of the job). Actions: k\geq 1 or k=0 . At every moment of time, the decision-maker has to choose an action for each arm. The action for an arm represents the number of cores allocated to the corresponding job. State transition: For any class- i arm, if its action is k=0 , its state stays the same. Otherwise, if its action is k>1 , its state decreases with rate s_{i}(k) . Resource Constraint: At every moment of time, the sum of the actions of all arms is no more than n . Objective: The goal is to minimize the time-average total holding cost ( 9 ). Let C(t) be the total cost across all arms in the system at time t . We also define a version of the above problem that optimizes discounted cost, ( 8 ). This discounted formulation does not correspond to the CAM problem, but is used to derive the Whittle policy. First, we will derive the Whittle policy for the discounted cost problem. Next, we will obtain the Whittle policy for the time-average bandit by taking the limit of the discounted cost problem as the discount factor \alpha goes to 0. 6 6 6 Roughly speaking, you can think about first multiplying equation ( 8 ) by \alpha and then taking the limit as \alpha\to 0 . That limit converges to the time-average cost given in ( 9 ). This “ vanishing discount factor ” approach is standard ( Li et al. 2025 ; Larrañaga et al. 2014 ; Whittle 2005 ) . Definition 6.2 (Our discounted multi-armed bandit formulation). The discounted bandit formulation (parameterized with the discount factor \alpha>0 ) is defined similarly to Definition 6.1 , except for the Cost and Objective: Cost: At every moment of time, for any class- i arm in the system, if its state is not \bot , it incurs cost at a rate of \alpha c_{i} per unit time. Objective: The goal is to minimize the total discounted holding cost, ( 8 ). Again, let C(t) be the total cost across all arms in the system at time t . 6.4. Setting up the Whittle approach for our bandit formulation We now set up the Whittle approach for our bandit formulation. We start by defining the single-armed bandit problem for our discounted bandit formulation (Definition 6.2 ). Definition 6.3 (Single-Armed Bandit). The single-armed bandit problem (parameterized with discount factor \alpha>0 and service cost \ell>0 ) corresponding to the discounted multi-armed bandit problem in Definition 6.2 is defined as follows. There is only one arm representing a single class- i job, where: • Arm State x\in\mathbb{R}\cup\bot , which represents the remaining inherent work on the corresponding job. If x=\bot , the job is marked as completed and leaves the system. • Cost: At every moment of time, if the arm state is not \bot , it incurs a cost rate of \alpha\cdot c_{i} . • Action k\geq 1 or k=0 : At every moment of time, an action is chosen for this arm, representing the number of cores ( k ) allocated to the corresponding job. A service cost rate of \ell\cdot k is incurred. • State transition: If the action is k=0 , the arm state stays the same (job is not served). Otherwise the state decreases with rate s_{i}(k) . • Objective: The goal is to minimize the discounted total cost \int_{0}^{\infty}\left(\alpha c_{i}\mathbf{1}[X(t)\neq\bot]+\ell\cdot k(t)\right)e^{-\alpha t}dt, where \mathbf{1}[X(t)\neq\bot] is an indicator variable which is 1 when the arm state at time t is not \bot , and k(t) is the action taken at time t . Based on the single-armed bandit problem above, the indexability (of the discounted multi-armed bandit problem) is defined as follows. Definition 6.4 (Indexability). Given a discount factor \alpha>0 , define the optimal action for state x in the single-armed bandit problem (parameterized by discount factor \alpha and service penalty \ell ) to be k^{*}(x,\ell) . The discounted multi-armed bandit problem parameterized by the discount factor \alpha is called indexable if for any state x , k^{*}(x,\ell) is decreasing with \ell and \lim_{\ell\to 0}k^{*}(x,\ell)\to\infty . That is, when the service cost is lower, the optimal number of cores allocated is higher. To derive the Whittle policy, we assume indexability holds (this assumption is made in other works as well, e.g., ( Ansell et al. 2003 ) ). We will only use the assumption of indexability in defining our Whittle policy – see Definition 6.5 . The mean field optimality of our Whittle policy does not rely on indexability – see Theorem 6.11 . Assuming indexability holds for any discount factor \alpha , the Whittle policy dynamically sets the service cost \ell to ensure that the total number of cores used at any moment of time is no more than n . Mathematically, the Whittle policy for the discounted problem is defined as follows: Definition 6.5 (The Whittle policy for discounted bandits). At every moment of time, given a set of jobs (arms) in the system, the Whittle policy calculates a “market-clearing" service cost \ell^{*} . Specifically, \ell^{*} is the smallest value such that if all arms act optimally with respect to \ell^{*} (i.e., each arm independently takes the optimal action in the corresponding single-arm bandit problem), the total number of cores used is no more than n . Then for each arm, the action selected by the Whittle policy is just its optimal action for the single-arm bandit problem with service penalty \ell^{*} . 6.5. Our policy WHAM We now derive WHAM (Definition 6.9 ), the closed form of the Whittle policy for our time-average multi-armed bandit formulation (Definition 6.1 ). Note that this involves first deriving the Whittle policy for the discounted bandit problem (Definition 6.5 and Definition 6.2 ), and then taking the vanishing discount factor limit ( \alpha\to 0 ) to obtain the Whittle policy for the time-average problem. The Whittle policy for the discounted bandit problem does not have a closed form expression. Fortunately, since we only care about the case when \alpha\to 0 to derive WHAM, we can simplify the problem by using little- o notation. 7 7 7 We say any term x\in o(\alpha) if \lim_{\alpha\to 0}\frac{x}{\alpha}=0 . Similarly, x\in o(1) if \lim_{\alpha\to 0}x=0 . Finally, we say x\in\Theta(\alpha) if \lim_{\alpha\to 0}\frac{x}{\alpha}=c for some constant c\neq 0 , and say x\in\Theta(1) if \lim_{\alpha\to 0}x=c for some constant c\neq 0 . In the remainder of this section, we first prove Lemma 6.7 to derive the optimal policy for the single-armed bandit problem when \alpha\to 0 . Lemma 6.7 is then used to derive the Whittle policy for the discounted bandit problems (Theorem 6.8 ). Our policy WHAM (Definition 6.9 ) comes from Theorem 6.8 . We first define the function, f_{i} , which crops up repeatedly in our analysis. Definition 6.6 ( f_{i} ). For any class i , define (10) f_{i}(k):=\frac{s_{i}^{\prime}(k)}{s_{i}(k)-ks_{i}^{\prime}(k)}. Here the derivative of s_{i} at 1 is defined as s_{i}^{\prime}(1):=\lim_{\epsilon\to 0^{+}}\frac{s_{i}(1+\epsilon)-1}{\epsilon} . Further we define f_{i}^{-1} to be the inverse function of f_{i} (the inverse exists because f_{i} is strictly decreasing, see Lemma E.2 ). We now derive the optimal solution of the single-armed bandit problem as \alpha\to 0 . Notably, the optimal policy behaves differently for different scalings of the service cost \ell . At this point it could be confusing why we focus on these scalings, but it will be clear in Theorem 6.8 . Lemma 6.7 (The optimal policy for the single-armed problem). When \alpha\to 0 and \ell\to\Theta(1) , the optimal policy for the single-armed bandit problem at arm state x is \begin{cases}\text{Choose action }k=1&\text{if }\ell<\frac{c_{i}}{x}+o(1)\\ \text{Choose action }k=0&\text{otherwise.}\end{cases} When \alpha\to 0 and \ell\to\Theta(\alpha) , the optimal policy for the single-armed bandit problem at arm state x is \begin{cases}\text{Choose action }k=1&\text{if }\frac{\ell}{\alpha c_{i}}\geq f_{i}(1)\\ \text{Choose action }k=f_{i}^{-1}\left(\frac{\ell}{\alpha c_{i}}\right)+o(1)&\text{otherwise.}\end{cases} Proof. By concavity of the speedup function, the optimal action should not change throughout the job’s life. Otherwise, picking the time-average number of cores leads to a better policy (see Lemma E.1 for a detailed proof). Hence, we only need to focus on the total cost of each action. The total discounted cost for action k=0 is just (11) \int_{0}^{\infty}\alpha e^{-\alpha s}c_{i}ds=c_{i}. For any action k\geq 1 , the total discounted cost is \displaystyle\int_{0}^{\frac{x}{s_{i}(k)}}e^{-\alpha s}(\alpha\cdot c_{i}+\ell\cdot k)ds=\left(c_{i}+\frac{\ell k}{\alpha}\right)\cdot\left(1-e^{-\alpha\frac{x}{s_{i}(k)}}\right) \displaystyle=\left(c_{i}+\frac{\ell k}{\alpha}\right)\left(\alpha\frac{x}{s_{i}(k)}+o(\alpha)\right) (12) \displaystyle=\frac{\ell kx}{s_{i}(k)}+\frac{c_{i}x}{s_{i}(k)}\alpha+o(\alpha)+o(\ell). Case 1: \alpha\to 0 , \ell=\Theta(1) . By ( 12 ), the optimal policy depends on the term \frac{\ell kx}{s_{i}(k)} . This term is increasing with k . Thus we only need to compare \ell x+o(1) (which is the total discounted cost of action k=1 ) with c_{i} (the total discounted cost of action k=0 ). Thus the optimal policy is \begin{cases}\text{Choose action }k=1&\text{if }\ell<\frac{c_{i}}{x}+o(1)\\ \text{Choose action }k=0&\text{otherwise.}\end{cases} Case 2: \alpha\to 0 , \ell=\Theta(\alpha) . In this case, by ( 12 ) the total discounted cost of any action k\geq 1 is of order \Theta(\alpha) , while the total discounted cost of action k=0 is c_{i} , which is of order \Theta(1) . Thus to minimize the cost, the optimal action should be some k\geq 1 . Note that by ( 12 ) the total discounted cost of action k\geq 1 is \left(\frac{kx}{s_{i}(k)}\cdot\frac{\ell}{\alpha}+\frac{c_{i}x}{s_{i}(k)}\right)\cdot\alpha+o(\alpha). Thus to minimize the total discounted cost, the optimal k minimizes \frac{k}{s_{i}(k)}\cdot\frac{\ell}{\alpha}+\frac{c_{i}}{s_{i}(k)}+o(1). The derivative of the expression above without the o(1) term is: \displaystyle\frac{\ell}{\alpha}\cdot\frac{s_{i}(k)-ks_{i}^{\prime}(k)}{(s_{i}(k))^{2}}+\frac{(-1)c_{i}s_{i}^{\prime}(k)}{(s_{i}(k))^{2}}=\frac{c_{i}}{(s_{i}(k))^{2}}\cdot(s_{i}(k)-ks_{i}^{\prime}(k))\cdot\left(\frac{\ell}{\alpha c_{i}}-f_{i}(k)\right). Note that the function f_{i}(k) is strictly decreasing with k (see Lemma E.2 ). Thus if \frac{\ell}{\alpha c_{i}}\geq f_{i}(1) , the total cost is minimized at k=1 ; otherwise it is minimized at k=f_{i}^{-1}(\frac{\ell}{\alpha c_{i}})+o(1) . ∎ Now we can derive the Whittle policy for our discounted multi-armed bandit. Note that a key step in deriving the Whittle policy (Definition 6.5 ) is to pick the “market-clearing” service cost \ell^{*} . Using Lemma 6.7 , we can now show that the market-clearing \ell^{*} scales differently with \alpha depending on the current number of jobs in the system. Theorem 6.8. Assuming indexability, the Whittle policy for the discounted multi-arm bandit (Definition 6.2 ) for \alpha\to 0 is: At every moment of time, • if the number of jobs is larger than the number of cores, allocate 1 core to each of the n jobs with the largest value of \left(\frac{\text{holding cost}}{\text{remaining job size}}+o(1)\right) . • otherwise, choose the smallest \ell^{*} such that if every class- i job gets g_{i}(\ell^{*}) cores, the total number of cores used is no more than n , where g_{i}(\ell) is defined as g_{i}(\ell):=\begin{cases}1&\text{if }\ell\geq f_{i}(1)+o(1),\\ f_{i}^{-1}\left(\frac{\ell}{c_{i}}\right)+o(1)&\text{otherwise,}\end{cases} where f_{i} and f_{i}^{-1} are defined in Definition 6.6 . Then, every class- i job gets g_{i}(\ell^{*}) cores. Proof. By Definition 6.5 , the Whittle policy is determined by selecting the value of \ell such that the total used cores is equal to n . Now we discuss two cases depending on the number of jobs. Case 1: number of jobs \mathbf{\geq n} . In this case, as \alpha\to 0 , if \ell^{*}\in\Theta(\alpha) , by Lemma 6.7 we know that each job wants at least 1 core, which will exceed our total limit n . Thus, we should make the service cost higher to decrease the total core usage. It turns out that the correct \ell^{*} should scale as \ell^{*}=\Theta(1) . By Lemma 6.7 , whether a job with holding cost c and remaining inherent work x wants 1 or 0 cores depends on whether \ell^{*}>\frac{c}{x}+o(1) . In this case, by selecting the market-clearing \ell^{*} , the resulting policy allocates 1 core to each of the first n jobs with the largest c/x+o(1) . x\in o(1) if \lim_{\alpha\to 0}\frac{x}{1}\to 0 Case 2: number of jobs \mathbf{1 , further define q^{(d)}(k_{0}) to be the time-average proportion of inherent work finished using more than k_{0} cores. Then \forall k_{0}>1,\lim_{d\to\infty}q^{(d)}(k_{0})\to 0. Proof. Recall that each type- i job brings X_{i} inherent work to the system. Thus we have that the time average inflowing rate of the inherent work is (16) \sum_{i=1}^{m}\lambda_{i}^{(d)}\cdot\mathrm{\bf E}\left[X_{i}\right]=\rho^{(d)}\cdot n^{(d)}. If a class- i job is running on k\geq k_{0} cores, then a unit inherent work is finished in \frac{1}{s_{i}(k)} units of time. Thus the core-second needed for a unit inherent work is k\cdot\frac{1}{s_{i}(k)}>\frac{k_{0}}{s_{i}(k_{0})} (because of the concavity of the speedup function s_{i} ). Thus, for the q^{(d)}(k_{0}) proportion of inherent work finished using more than k_{0} cores, the total core-second needed is at least q^{(d)}(k_{0})\cdot\rho^{(d)}n^{(d)}\cdot\frac{k_{0}}{\max_{i}s_{i}(k_{0})}. Moreover, for the rest 1-q^{(d)}(k_{0}) proportion of inherent work, by sub-linearity of the speedup functions, the total core-second needed is at least (1-q^{(d)}(k_{0}))\cdot\rho^{(d)}n^{(d)} . Note that for the system to be stable, the time average total core-second needed must be no more than n^{(d)} . Thus we have q^{(d)}(k_{0})\cdot\rho^{(d)}n^{(d)}\cdot\frac{k_{0}}{s_{i}(k_{0})}+(1-q^{(d)}(k_{0}))\cdot\rho^{(d)}n^{(d)}\leq n^{(d)}. This inequality gives that q^{(d)}(k_{0})\leq\left(\frac{1}{\rho^{(d)}}-1\right)\cdot\left(\frac{1}{\frac{k_{0}}{\max_{i}s_{i}(k_{0})}-1}\right). Since \lim_{d\to\infty}\rho^{(d)}\to 1 , we have that for any k_{0}>1 , \lim_{d\to\infty}q^{(d)}(k_{0})\to 0 . ∎ Appendix B Mean field optimal policies should not use exact job size information In this section, we prove that for any policy that is mean field optimal, it almost surely allocate the same number of cores to all class- i jobs, regardless of their exact job size. The proof uses results and notation from Section 4 . Proposition B.1. Assume the speedup function for any class i is strictly concave. Define k_{i}:=k_{i}^{*}\left(\left\{\lambda_{i}\right\},n\right) . For any policy \pi that is mean field optimal, and for any class i , we have that the fraction of class- i inherent work completed using k_{i} cores goes to 1 in mean field. Proof. We prove the proposition by contradiction. Suppose the statement does not hold, then either (1) fraction of class- i work completed using k^{\prime}\neq k_{i} goes to 1 in mean field, or (2) the fraction of class- i work is distributed among multiple values (or a range) of k , such that the fraction does not converge to 1 for any single core count. We first prove that (2) cannot hold for any class i . Suppose (2) holds for some class i . Let h_{i}(k) be the fraction of time that a class- i job is running on k cores ( \int_{1}^{\infty}h_{i}(k)dk=1 ). Now we create a policy \pi^{\prime} for the Relaxed problem, which always allocate k^{\prime}:=\int_{1}^{\infty}k\cdot h_{i}(k)dk cores to class- i jobs. By concavity of the speedup function, we have that the mean response time of class- i job under \pi^{\prime} is no worse than that under \pi (see Lemma 1 in ( Li et al. 2024 ) ). Moreover, the time-average number of cores used under \pi^{\prime} is strictly better than that under \pi : the time-average number of cores used under \pi^{\prime} is \frac{k^{\prime}\lambda_{i}\mathrm{\bf E}\left[X_{i}\right]}{s_{i}(k^{\prime})} , and that under \pi is \displaystyle\int_{0}^{k}\frac{k\lambda_{i}\mathrm{\bf E}\left[X_{i}\right]\cdot\frac{s_{i}(k)h_{i}(k)}{\int_{1}^{\infty}s_{i}(x)h_{i}(x)dx}}{s_{i}(k)}dk \displaystyle=\int_{0}^{k}k\lambda_{i}\mathrm{\bf E}\left[X_{i}\right]\cdot\frac{h_{i}(k)}{\int_{1}^{\infty}s_{i}(x)h_{i}(x)dx}dk \displaystyle=\frac{1}{\int_{1}^{\infty}s_{i}(x)h_{i}(x)dx}\lambda_{i}\mathrm{\bf E}\left[X_{i}\right]k^{\prime} \displaystyle>\frac{\lambda_{i}\mathrm{\bf E}\left[X_{i}\right]k^{\prime}}{s_{i}(k^{\prime})}. Define the reduced ratio of the time-average number of cores used to be some c>0 . Then, we have that \lim_{d\to\infty}\widebar{Cost}_{CAM^{(d)}}^{\pi}=\lim_{d\to\infty}\widebar{Cost}_{Relaxed^{(d)}}^{\pi}\geq\lim_{d\to\infty}\widebar{Cost}_{Relaxed^{(d)}}^{\pi^{\prime}}\geq V_{R}^{*}\left(\{\lambda_{i}\},n(1-c)\right)>V_{R}^{*}\left(\{\lambda_{i}\},n\right). Next, since (2) does not hold for any class i , under \pi each class i job only runs on a single number of cores in mean field, denoted by k_{i}^{\prime} . This means that k_{i}^{\prime} is a feasible solution of the optimization problem ( 3 ). Since the speedup functions are strictly concave, the optimization problem 3 can be translated into a strictly convex optimization and the optimal solution is unique. Thus, k_{i}^{\prime}=k_{i} . ∎ Appendix C Proof for Lemma 5.2 In this section, we prove Lemma 5.2 , which is listed below. Lemma C.1. For any class i , \lim_{d\to\infty}k_{i}^{*}\left(\left\{\lambda_{i}^{(d)}\right\},n^{(d)}-{\left(n^{(d)}\right)}^{\beta}\right)\to k_{i}^{*}\left(\left\{\lambda_{i}\right\},n\right) . Proof. By definition, k_{i}^{*}\left(\left\{\lambda_{i}^{(d)}\right\},n^{(d)}-{\left(n^{(d)}\right)}^{\beta}\right) is the optimal solution of the following optimization problem: (17) \displaystyle\underset{k_{i}}{\text{minimize}} \displaystyle\sum_{i=1}^{m}\frac{\lambda_{i}\cdot d}{\lambda\cdot d}\frac{\mathrm{\bf E}\left[X_{i}\right]c_{i}}{s_{i}(k_{i})} \displaystyle\text{subject to} \displaystyle\sum_{i=1}^{m}\frac{\lambda_{i}\cdot d\mathrm{\bf E}\left[X_{i}\right]k_{i}}{s_{i}(k_{i})}\leq n\cdot d-(n\cdot d)^{\beta}. Dividing by d on both sides of the constraint, we have that the optimization problem is equivalent to: (18) \displaystyle\underset{k_{i}}{\text{minimize}} \displaystyle\sum_{i=1}^{m}\frac{\lambda_{i}}{\lambda}\frac{\mathrm{\bf E}\left[X_{i}\right]c_{i}}{s_{i}(k_{i})} \displaystyle\text{subject to} \displaystyle\sum_{i=1}^{m}\frac{\lambda_{i}\mathrm{\bf E}\left[X_{i}\right]k_{i}}{s_{i}(k_{i})}\leq n-n^{\beta}\cdot d^{\beta-1}. Note that both the objective function and constraint function are continuous in k_{i} . Moreover, the optimization problem is a convex optimization problem (by applying changing of variables, as also stated in ( Li et al. 2024 ) ). Thus, since \lim_{d\to\infty}d^{\beta-1}\to 0 , we have that both the solution and the value of the optimization problem ( 18 ) converge to those of the optimization problem ( 3 ). ∎ Appendix D Verification of the conditions in ( Li and Goldberg 2025 ) As is also assumed in ( Li and Goldberg 2025 ) , we assume that the steady-state number of jobs in system exists (see ( Asmussen 2003 ) for detailed discussion on this condition). We now verify that all other conditions listed in Lemma 5.4 hold in mean field. (i) \mathrm{\bf E}\left[A_{i}^{2}\right]<\infty : In the d^{th} system, we have that \mathrm{\bf E}\left[(A_{i}^{(d)})^{2}\right]=\frac{\mathrm{\bf E}\left[A_{i}^{2}\right]}{d^{2}} , which is finite for any d . (ii) \mathrm{\bf E}\left[S^{3}\right]<\infty : In the d^{th} system, we have that \mathrm{\bf E}\left[\left(S_{i}^{(d)}\right)^{3}\right]=\mathrm{\bf E}\left[\left(\frac{X_{i}}{s_{i}(k_{i}^{(d)})}\right)^{3}\right] , which is finite for any d . (iii) \frac{1}{\mathrm{\bf E}\left[A\right]}0 , while the right hand side of ( 19 ) is of order \Theta(1) by definition. Hence the inequality always holds when d\to\infty . Appendix E Omitted proof for optimal policy of the single-arm bandit problem In this appendix we prove the following omitted lemma in the proof of Lemma 6.7 . Lemma E.1. For any discount factor \alpha\to 0 and service penalty \ell , the optimal policy for the single-arm bandit problem always chooses the same action throughout the arm’s lifetime. In other words, the optimal policy either always chooses action k=0 and leaves the arm forever incurring some cost, or keeps choosing some action k\geq 1 until the arm enters state \bot and completes. Proof. First, if the optimal action at state x is to choose k=0 , since the state will not change, we have that the optimal policy will choose k=0 forever. Otherwise, the lemma holds by concavity of the speedup function s_{i} . Mathematically, suppose the optimal policy \pi chooses action k(t)\geq 1 at time t for t\in[0,t^{\prime}] . One can create another policy \pi^{\prime} , which use the same action throughout this t^{\prime} time, incurring the same service penalty but does more work. Mathematically, define k^{\prime}=\frac{1}{1-e^{-\alpha t^{\prime}}}\int_{0}^{t^{\prime}}k(t)e^{-\alpha t}dt. The policy \pi^{\prime} allocates k^{\prime} cores to the job throughout time [0,t^{\prime}] . Compared with \pi , the two policies incur exactly the same total discounted service penalty for any \alpha and \ell . However, the total work \pi^{\prime} does is s_{i}(k^{\prime})t^{\prime} , while the total work \pi does is \int_{0}^{t^{\prime}}k(t)dt . Note that when \alpha\to 0 , k^{\prime} goes to the time-average value of k(t) within time [0,t^{\prime}] . Thus, by strict concavity of the speedup function, we have that \pi^{\prime} is strictly better than \pi when \alpha\to 0 . ∎ We also prove the following lemma. Lemma E.2. For any class i , the function f_{i}(k):=\frac{s_{i}^{\prime}(k)}{s_{i}(k)-ks_{i}^{\prime}(k)} is strictly decreasing with k . Proof. We only need to show that \frac{1}{f_{i}(k)} is increasing, which is \frac{s_{i}(k)}{s_{i}^{\prime}(k)}-k. We can take the derivative of this expression: \displaystyle\frac{d(\frac{1}{f_{i}(k)})}{dk} \displaystyle=\frac{s_{i}^{\prime}(k)^{2}-s_{i}(k)s_{i}^{\prime\prime}(k)}{s_{i}^{\prime}(k)^{2}}-1 \displaystyle=\frac{-s_{i}(k)s_{i}^{\prime\prime}(k)}{s_{i}^{\prime}(k)^{2}} \displaystyle>0. The last inequality holds because the speedup functions are (strictly) concave (Assumption 1 ). ∎ Appendix F Proof for job sizes that follow phase-type distribution In this appendix, we present the proof for the mean field optimality of WHAM under the assumption of phase-type distributed job sizes. The proof is similar to that presented in Section 6.6 . Assumption 2. Assume the job size distribution X_{i} is a phase-type distribution defined by the following Markov chain: There are K_{i} states. Let \textbf{p}_{i}=(p_{iu}) denote the vector of the initial probability to be in state u , and let \textbf{Q}_{i} be the sub-generator matrix of the Markov chain, i.e., \textbf{Q}_{i} is a K_{i}\times K_{i} matrix, and \textbf{Q}_{i}(u,v) is the transition rate from u to v u\neq v , \textbf{Q}_{i}(u,u):=-\sum_{v\neq u}\textbf{Q}_{i}(u,v)-q_{i}(u,0) where q_{i}(u,0) is the transition rate from state u to the absorbing state. Under the mean field regime, the limiting dynamics of the queueing system can be captured by an ODE ( Kurtz 1970 ; Gast and Van Houdt 2017 ) . Noticeably, even for a GI arrival process, the first-order drift is the same as a Poisson arrival, thus it can be treated as if it is a Poisson arrival in the ODE (Theorem 3 in ( Whittle 1988 ) ). Thus, the system under policy WHAM in mean field can be described by the following ODE: (23) \displaystyle\dot{\textbf{z}}_{i}=\lambda_{i}\textbf{p}_{i}+\textbf{z}_{i}\textbf{Q}_{i}\cdot s_{i}(g_{i}(\ell)), \displaystyle\text{where $\ell$ is determined by }\sum_{i=1}^{m}\textbf{z}_{i}\cdot\textbf{1}\cdot g_{i}(\ell)=n,\text{ and $g_{i}$ is defined in Definition~\ref{def:policytwo}.} Here \textbf{z}_{i} is the vector of the normalized number of class- i jobs, and \textbf{z}_{i}(u) is the normalized number of class- i jobs in state u . For a better understanding of the ODE ( 23 ), \lambda_{i}\textbf{p}_{i} is the arrival rate of class- i jobs, \textbf{z}_{i}\textbf{Q}_{i} represents the rate of transition between the states of class- i jobs (if running on 1 core), and s_{i}(g_{i}(\ell)) is the speedup that any class- i job gets. Finally, by the definition of WHAM, \ell is picked such that the total number of cores used reaches n , which is \sum_{i=1}^{m}\textbf{z}_{i}\cdot\textbf{1}\cdot g_{i}(\ell)=n . We can now state our main theorem. Note that the asymptotic optimality of WHAM relies on the assumption that ODE ( 23 ) has a global attractor. Similar assumptions of the existence of a global attractor are also made in prior works (e.g., ( Weber and Weiss 1990 ; Verloop 2016 ) , see ( Verloop 2016 ) for a detailed discussion). Theorem F.1 (mean field optimality of WHAM). If ODE ( 23 ) has a global attractor, then WHAM is mean field optimal. Proof. Suppose ODE ( 23 ) has a global attractor, then it must be a stationary point. We next prove that there exists a unique stationary point for ODE ( 23 ), and the resulting normalized time-average total holding cost is V_{R}^{*}\left(\{\lambda_{i}\},n\right) . Note that if this statement holds, we have that WHAM is mean field optimal because its time-average total holding cost converges to the lower bound ( 5 ). For the stationary point \textbf{z}_{i} , since \dot{\textbf{z}}_{i}=0 , we have that \textbf{z}_{i}\textbf{Q}_{i}\cdot s_{i}(g_{i}(\ell))=-\lambda_{i}\textbf{p}_{i}. Since matrix \textbf{Q}_{i} is inversible (Lemma 2.2.1 in ( Latouche and Ramaswami 1999 ) ), we have that (24) \textbf{z}_{i}=-\frac{\lambda_{i}}{s_{i}(g_{i}(\ell))}\textbf{p}_{i}\left(\textbf{Q}_{i}\right)^{-1}. Moreover, we have that \mathrm{\bf E}\left[X_{i}\right]=-\textbf{p}_{i}\left(\textbf{Q}_{i}\right)^{-1}\textbf{1} (Theorem 2.2.3 in ( Latouche and Ramaswami 1999 ) ). Thus, by multiplying 1 on both sides of ( 24 ), we have that \textbf{z}_{i}\textbf{1}=\frac{\lambda_{i}}{s_{i}(g_{i}(\ell))}\mathrm{\bf E}\left[X_{i}\right]. Now we can find the stationary point by solving the equation \sum_{i=1}^{m}\textbf{z}_{i}\textbf{1}\cdot g_{i}(\ell)=n, which is equivalently (25) \sum_{i=1}^{m}\frac{\lambda_{i}g_{i}(\ell)}{s_{i}(g_{i}(\ell))}\mathrm{\bf E}\left[X_{i}\right]=n. Note that g_{i} is strictly decreasing for any \ell