{'fraction_non_alphanumeric': 0.05675055134285973, 'fraction_numerical': 0.013171807498262892, 'mean_word_length': 3.5297981525829627, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 27, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 46, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Scheduling in the high uncertainty heavy traffic regime

We propose a model uncertainty approach to heavy traffic asymptotics that allows for a high level of uncertainty. That is, the uncertainty classes of underlying distributions accommodate disturbances that are of order 1 at the usual diffusion scale, as opposed to asymptotically vanishing disturbances studied previously in relation to heavy traffic. A main advantage of the approach is that the invariance principle underlying diffusion limits makes it possible to define uncertainty classes in terms of the first two moments only. The model we consider is a single server queue with multiple job types. The problem is formulated as a zero sum stochastic game played between the system controller, who determines scheduling and attempts to minimize an expected linear holding cost, and an adversary, who dynamically controls the service time distributions of arriving jobs, and attempts to maximize the cost. The heavy traffic asymptotics of the game are fully solved. It is shown that an asymptotically optimal policy for the system controller is to prioritize according to an index rule and for the adversary it is to select distributions based on the system's current workload. The workload-to-distribution feedback mapping is determined by an HJB equation, which also characterizes the game's limit value. Unlike in the vast majority of results in the heavy traffic theory, and as a direct consequence of the diffusive size disturbances, the limiting dynamics under asymptotically optimal play are captured by a stochastic differential equation where both the drift and the diffusion coefficients may be discontinuous.


Background, motivation and setting
The asymptotic analysis of queueing systems under heavy traffic and their non-asymptotic analysis under model uncertainty have both been subject to extensive research. There are very few papers on settings that combine the two; those that we are aware of are [10,11,12] and [25]. In this body of work, the effective size of uncertainty classes diminishes as the heavy traffic scaling parameter grows. The goal of this paper is to propose an approach that combines heavy traffic and model uncertainty in a way that keeps the disturbances associated with uncertainty at order one under the usual diffusion scale. As is well known, owing to the invariance principle governing diffusion limits, results in the heavy traffic regime enjoy the robustness property that the approximations they provide are based on only the first two moments of the underlying distributions. We shall argue that in the setting proposed here the same reasons make it possible to transform uncertainty classes in the space of distributions to classes defined by the first two moments, a desired property from model uncertainty viewpoint.
Although the approach is potentially applicable for a large variety of models, we focus here on one model where a single server caters to a number of streams of jobs of different types, and a system controller (SC) dynamically allocates the server's effort to the different streams. The system is subject to model uncertainty with respect to the service time distributions. The model is often referred to as a multiclass queue, but in this paper we reserve the term class to the context of uncertainty and instead use the term type to distinguish between streams of jobs, hence use multitype as substitute for multiclass. To capture uncertainty, a stochastic zero sum game is formulated in which an adversary can dynamically select the distributions of arriving job sizes from given uncertainty classes, one per job type. The cost consists of an expected discounted linear combination of queue lengths. The asymptotics of the game are fully solved. It is shown that it is asymptotically optimal (AO) for the SC to prioritize according to the cµ rule regardless of the adversary behavior. AO play for the adversary is derived in terms of an underlying ordinary differential equation of Hamilton-Jacobi-Bellman (HJB) type, which, moreover, characterizes the value function asymptotics.
The importance of accounting for uncertainty in queueing models is widely acknowledged. In what follows we mention a small sample of work in this area. An adversarial approach to questions regarding stability of queueing networks is proposed in [7]. It is developed in [14] by exploiting the relation between queueing models and their corresponding fluid models. In [5], a worst case approach based on techniques of robust optimization is proposed and used to obtain performance bounds on several queueing models. In [18], a queueing control problem is solved in which model uncertainty is characterized by relative entropy. The modeling of call centers has motivated much work on model uncertainty, including [6,9,16,20,27]. Among these, [6,16,27] model uncertainty via stochastic fluid models, where in particular, the fluid scale asymptotics are rigorously justified in [6]. A staffing problem is solved in [9] in the Halfin-Whitt heavy traffic regime, where a worst case approach is taken (among others) to uncertainty in the arrival process. Another control problem for a call center model is analyzed in [20], where uncertainty is modeled by stochastic arrival rates and diffusion-scale asymptotic optimality of a proposed control policy is proved. In [4,13], robust control problems associated with fluid queueing models are considered via differential games. A robust approach to queueing models at the large deviations regime is proposed in [1].
The work that is most relevant to ours is the aforementioned series [10,11,12]. It combines an adversarial and an asymptotic approach in the heavy traffic regime, and studies a queueing system similar to the one studied here. In [10,11] buffers are finite, cost is linear in queue length and rejection count, whereas in [12] buffers are infinite and cost is strictly convex in queue length. The uncertainty class of arrival and service time distributions is based on a reference model corresponding to the multitype M/M/1 queue, in which arrival and potential service processes are Poisson with given intensities. The adversary is allowed to perturb the law of these processes, but is subject to a penalty expressed in terms of a functional which is a generalization of the Kullback-Leibler divergence between the perturbed and reference measures. The results of [10,11] characterize the limiting value function in terms of an HJB equation and construct AO strategies, whereas the paper [12] proves that the generalized cµ rule is an AO strategy for the SC and provides an explicit solution to a differential game which governs the asymptotics of the problem. Similar setting and methodology appear also in the preprint [25].
Our treatment differs from that in [10,11,12] in a number of ways, two of which are crucial: The collection of distributions allowed in the uncertainty class, and the asymptotic size of this class. To explain the first aspect, note that because in [10,11,12] model uncertainty is quantified in terms of penalty for deviations measured by divergence, the uncertainty classes of the underlying counting processes are automatically restricted to absolutely continuous changes of measure with respect to Poisson processes. However, standard (non-game) heavy traffic limit theorems are typically concerned with much larger classes of distributions within the domain of applicability of CLT approximations, namely those restricted only by moment assumptions. We aim here at uncertainty classes defined only in terms of moments, and not restricted to absolutely continuous changes of measures of one another.
The second crucial aspect has to do with the scale of the uncertainty classes. In the setting of [10,11,12], the effective size of the uncertainty classes shrinks like n −1/2 as n grows, where we have denoted by n the usual heavy traffic scaling parameter. More precisely, it is shown in these references that there is no loss for the adversary to consider only changes of measures for which the stochastic intensities of the underlying counting processes are (1+O(n −1/2 ))-multiple of the reference model's Poissonian intensity (see Proposition 4.4 of [10] and Proposition 4.3 of [12]). For example, if the potential service process of type 1 jobs is Poisson of rate µ 1 under the reference measure then within the uncertainty class it has stochastic intensity bounded above and below by µ 1 (1 + O(n −1/2 )), and consequently the perturbed service time distributions are bounded between Exp(µ 1 + cn −1/2 ) and Exp(µ 1 − cn −1/2 ) in the sense of usual stochastic ordering (here, Exp(µ) denotes the exponential distribution with parameter µ). It is proposed to refer to this setting as the low uncertainty regime. Our aim is to address a different natural setting in which the perturbations are of order 1, in a sense to be made precise, to which we shall refer as the high uncertainty regime. One should not regard one regime superior to the other; rather, the two complement each other, each capturing realistic modeling assumptions under different scenarios.
We now give some more details on the setting in which we work. The model can be regarded as a multitype D/G/1 queue with uncertainty. The focus is on stochasticity associated only with sizes of jobs, not with their arrival times, that are deterministic by assumption. Although it is desired to model arrival stochasticity, avoiding it saves much notational burden, whereas mathematically this aspect is less difficult. However, because jobs of size zero are allowed to occur with positive probability, the setting automatically captures exponentially distributed interarrival times.
To fix some notation, consider for the moment the much simpler, single D/G/1 queue with fixed underlying law (i.e., no uncertainty), described as follows. For each n ∈ N, let {J n k } k∈N be IID nonnegative RVs. In the n-th system, an arrival occurs every unit of time, and the k-th job to arrive is of size J n k .
then under Lindberg-Feller conditions and convergence of initial conditions, the diffusion scaled workload of the n-th system converges, as n → ∞, to a reflected Brownian motion (BM) with infinitesimal drift and variance b and σ 2 . For this reason we shall refer to b n and σ 2 n as the prelimit drift and variance. Similarly, in a multitype setting, there is a pair of prelimit coefficients for each type.
We can now explain how the uncertainty classes are defined in this paper. For each n and type , an uncertainty class is a set in the space of measures on R + , representing probability laws of job sizes. For each such measure there corresponds a pair (b n , σ 2 n ) defined analogously to the above example. The collection of pairs (b n , σ 2 n ) corresponding to all measures in the uncertainty class is denoted by K n ⊂ R 2 . It is assumed that, as n → ∞, K n → K in the Hausdorff metric, where K is a compact (but otherwise arbitrary) subset of R × (0, ∞). A certain uniform integrability condition is also assumed.
According to this definition, an uncertainty class may contain distributions for which the second moment differs by O(1). The same is true, for example, for the absolute centered first moment. The only sense in which the distributions within the class must become close to each other is in the first moment, where they can differ by only O(n −1/2 ). This is necessary in order to not trivialize the problem: if the adversary is allowed to choose between prelimit drifts b n that are apart by more than O(n −1/2 ) then only those with greatest b n will be chosen, making the problem much simpler.

Results
A first key step in our analysis is to relate the workload process, whose limit provides the state process of the dynamics, to the queue length, in terms of which the cost is expressed. In non-game heavy traffic settings, these processes are asymptotically proportional to one another, a phenomenon known as Reiman's snapshot principle (RSP) [22]. In order to analyze the game one needs to develop, as we do, a version of RSP in which the asymptotic proportionality is attained uniformly in the actions of the SC.
The cµ rule is well known to be AO in the context of linear queue length cost. Our first main result is based on the aforementioned RSP and states that this rule defines an AO policy for the SC under arbitrary behavior of the adversary. Thanks to this result, we can, and do, analyze the game assuming that the cµ rule is always used by the SC. Thus, although the problem we are set to solve is concerned with game asymptotics, its limit is reduced to a stochastic control problem that involves only the adversary, which is considerably simpler than a stochastic differential game.
In this control problem, the state process is a one-dimensional controlled diffusion with reflection at the origin and controlled drift and diffusion coefficients. It is well known that solutions to a control problem of this kind are characterized in terms of viscosity solutions of an HJB equation, but classical solutions do not always exist. In our case we show by appealing to PDE theory on fully nonlinear uniformly elliptic equations that the HJB equation has a unique classical solution. The solution to the control problem is given by a diffusion with discontinuous drift and diffusion coefficients.
Our second main result provides a full solution to the game asymptotics. It states that the stochastic game's value converges to that of the diffusion control problem or, equivalently, to the solution of the HJB equation. It also specifies an AO policy for the adversary. It is established in its proof that any subsequential limit of the game dynamics is given by the aforementioned diffusion with discontinuous coefficients; in this respect the limit result resembles that in the recent work [2,3].
Finally we state a result that provides insight into the collection of distributions within the uncertainty classes from which the adversary selects. As we will explain, it is standard to deduce from the form of the HJB equation that an adversary that plays optimally will select distributions only from a part of the boundary of the set, specifically, the set that generates the convex hull of K. Our results reduces further the collection of potentially used points in the class, to what we call the set of dominating points. This is the collection of points on the boundary that are dominating the whole set w.r.t. the partial order 1.3 Organization of the paper §2 describes the queueing model, the game and the form of uncertainty classes, and introduces a martingale control problem (MCP) which is later proved to govern the game asymptotics. It then states Theorem 1 on the AO of the cµ-rule, Proposition 1, which relates the MCP value to an HJB equation, and Theorem 2, which establishes a relation between the game asymptotics, the MCP and the HJB equation. §3 contains remarks and examples. The remaining sections contain proofs. §4 provides the proof of Theorem 1. §5 studies the MCP and the HJB equation and proves Proposition 1. Finally, Theorem 2 is proved in § §6-7, where the former establishes a general upper bound on the game asymptotics in terms of the MCP value, and the latter identifies a sequence of controls for the adversary that asymptotically achieves this bound, thereby establishing the convergence of the game's value.

Notation
. For a, b ∈ R, a ∨ b and a ∧ b denote the maximum and, respectively, minimum of a and b, and a + = a ∨ 0. For a metric space (M, d), the Hausdorff metric between two nonempty sets U, V ⊂ M is defined by where d(x, U ) denotes the distance between a point x and a set U . For a subset K ⊂ R k , ch(K) denotes its closed convex hull. The symbol id : R + → R + denotes the identity map. For f : R + → R and t, δ > 0, For 0 ≤ s ≤ t, the notation f [s, t] stands for f (t) − f (s) and ∆f t = f (t) − f (t−) (when the left-limit exists). For real-valued functions and processes, the notation X(t) is used interchangeably with X t . Given a Polish space E, denote by C E [0, ∞) and D E [0, ∞) the spaces of E-valued, continuous and, respectively, càdlàg functions on [0, ∞). In the case E = R simply denote C and D respectively. Equip the former with the topology of convergence u.o.c. and the latter with the J 1 topology. Denote by ) of componentwise non-negative and nondecreasing functions. Write X n ⇒ X for convergence in law. A tight sequence of processes with sample paths in D E [0, ∞) is said to be C-tight if it is tight and the limit of every weakly convergent subsequence has sample paths in C E [0, ∞) a.s. The letter c denotes a deterministic constant whose value may change from one appearance to another.

Model and results
2.1 Queueing model and game setting

Queueing model
The queueing model is that of a multitype D/G/1 queue with L types of jobs, operating in continuous time, where each type has a dedicated unlimited buffer, and arrivals into each of these buffers occur at deterministic times. In the n-th system an arrival occurs every n −1 units of time (starting at time n −1 ), and the service rate is n. All random variables (RVs) and processes introduced below are defined on a probability space (Ω, F, P). For k ∈ N, at each time kn −1 , a type-job of size J n k arrives at the -th buffer of the n-th system. As a result, for each , the number of type-arrivals by time t, and the work associated with these arrivals are given, respectively, by nt , We note that we do not regard (1) as rescaling of time by factor n, rather nt is the number of jobs arriving by time t. Henceforth, a superscript 'tot' (for 'total') will denote summation over ∈ [L], e.g. A tot,n t = L =1 A n t , etc. Next we introduce the control process for the SC, denoted by B n t = (B n t ) ∈[L] . In the special case where the server's behavior is to devote all its effort to one type at a time, B n t is simply the time the server has devoted to type-jobs by time t. In general, resource sharing is allowed and therefore B n t represents the cumulative effort provided to -type jobs by time t. Because the server works at rate n, the work done by time t is given by nB n t , for each type . Denote the simplex in R L by Sim = {x ∈ [0, 1] L : x ≤ 1}. Then the sample paths of B n take values in It is assumed that within each type, jobs are served according to FIFO. It is also assumed that the system starts empty. Let W n t = (W n t ) ∈[L] denote the workload at the different buffers at time t. Then this process is uniquely determined by the workload arrival process A n t and the cumulative effort process Above, we have also expressed the nonnegativity of the workload, which we shall regard as a constraint imposed on the SC when selecting the process B n . The term nB n t reflects the fact that the service rate is given by n.
Next, the queue length Q ,n t can also be determined from A n and B n . To express it, let S n k = inf{t ≥ 0 : nB n t ≥ A n k/n }, D n t = sup{k ≥ 0 : S n k ≤ t}.
Then S n k represents the time the k-th -type job has left the system, and D n t , the departure process, represents the number of -type jobs that have left the system by time t. Then we have Note that by their construction, the processes A n , W n , Q n have sample paths in D R L The diffusion scale versions of W n , Q n and R n are given byŴ n = n −1/2 W n ,Q n = n −1/2 Q n and R n = n −1/2 R n . Several additional diffusion scaled processes are defined later along with conditions for heavy traffic.

Game formulation
We now describe a game, defined for each n, played between the SC that controls B n and an adversary that controls the laws from which J n are drawn. To introduce the cost, let a vector h ∈ (0, ∞) L be given, and let Above,Q n is the process determined by B n and J n . The SC's goal is to minimize this cost, whereas the adversary, whose goal is to disturb this effort as much as possible, attempts to maximize it. The precise details are as follows.
Adversary controls. Let P denote the space of probability measures on R + endowed with the topology of weak convergence. For each n and , a nonempty closed set Π n ⊂ P is given, playing the role of an uncertainty class for type-job size distributions. The product Π 1n × · · · × Π Ln is denoted by Π n . At each arrival time, n −1 k, the adversary selects the random vector of job sizes, J n k = (J n k ) ∈[L] , in two steps. First, it selects for each type a distribution from the corresponding uncertainty class, namely π n k ∈ Π n . Before doing so it may observe all past job sizes J n 1 , . . . , J n k−1 . This is expressed by requiring We also denote and note that F n k = G n k/n . In the second step, the adversary selects the random vector J n k so that it follows the product law corresponding to these newly selected distributions. More precisely, for C ∈ R + (Borel subsets of R + ), ∈ [L], (We assume without loss of generality that the probability space supports such RVs). An admissible control for the adversary is thus a sequence (a n k ) k∈N = (π n k , J n k ) k∈N of Π n × R L + -valued RVs, satisfying (5) and (7). The collection of all admissible controls for the adversary is denoted by A n . Remark 1. An alternative way to define the second step is to set A n = Π n and let J n k be selected arbitrarily according to (7) rather than letting the adversary select it. In this case one must show that the way in which it is selected always leads to the same game. This is true but requires some further arguments, which we have chosen to omit by letting the adversary select J n k (which also leads to the same game). Moreover, it may at first seem that when selecting the pair (π n k , J n k ), the adversary can compare outcomes of different pairs and select the best disturbance among these outcomes. However, this would violate the requirement (5) that π n k is selected based only on the past outcomes, J n 1 , . . . , J n k−1 .
SC strategies. In this paragraph we use underline to denote members of the space of sample paths of a corresponding stochastic processes. In particular, let A n = (Π n × R L + ) N . Then a n = (π n , J n ) ∈ A n is deterministic, and a n = (π n , J n ) ∈ A n defined above is a process that has sample paths in A n .
We topologize A n with the product topology and recall that B is equipped with the topology of u.o.c. convergence; we consider both spaces with their Borel σ-fields. A measurable map β n : A n → B is said to be a strategy for the SC in the n-th system. By selecting a strategy β n , the SC determines the control process B n as a response to the adversary's control a n via B n (ω) = β n (a n (ω)), ω ∈ Ω.
For a strategy β n to be admissible, it must satisfy several additional properties.
-Nonnegativity constraint. Given n, if a n = (π n , J n ) ∈ A n and B n = β n (a n ), then for the nonnegativity constraint (2) to hold we must require that -Work conservation. We will only consider work conserving strategies. For the precise details we need to introduce two pieces of notation. First, let R n t denote the idleness process R n t = nt − nB tot,n t . Work conservation is the property that the server works at full capacity whenever there is work in the system. This can be expressed mathematically as [0,∞) W tot,n t dR n t = 0. Second, enter the Skorohod map on the half line. This map, denoted throughout this paper by Γ : , sends a function ψ to a pair (ϕ, η), where The corresponding maps ψ → ϕ and ψ → η are denoted by Γ 1 and Γ 2 , respectively. Skorohod's lemma Putting together the last two comments, noting that by (2) Hence work conservation is expressed by requiring that the map β n satisfies the following. Given n, if a n = (π n , J n ) ∈ A n and B n = β n (a n ) then n id − nB n,tot = Γ 2 (A tot,n − n id), namely -Causality. We shall also require admissible strategies to be causal (or non-anticipating) in the following sense. For every n and a n ,ã n ∈ A n , denoting B n = β n (a n ),B n = β n (ã n ), if a n k =ã n k for all k ≤ K then B n t =B n t for all t ∈ [0, (K + 1)n −1 ).
A strategy β n is said to be admissible for the n-th system if (9), (12) and (13) hold. The collection of all admissible strategies for the n-th system is denoted by B n . The relation (8), that defines the process B n in terms of a n "omega-by-omega", will be written as B n = β n (a n ) in what follows.
By our definitions, the process a n k is {F n k }-adapted. As a consequence, the process A n t is {G n t }-adapted. For the adaptedness of B n we have the following. Lemma 1. If a n ∈ A n and β n ∈ B n then the process B n := β n (a n ) is {G n t }-adapted.
The proof of this result appears in the appendix.
Game's value. With a slight abuse of notation, for a given control process B n for the SC and a control process a n = (π n , J n ) for the adversary, we define the corresponding cost C n (B n , a n ) by identifying it with C n (B n , J n ) of (4). The value of the game is then defined by V n = inf β n ∈B n sup a n ∈A n C n (β n (a n ), a n ).
Remark 2. We have constructed the game in such a way that its whole history is measurable w.r.t. the job size history. Therefore, the requirement that the decisions of both players are adapted to the history of job sizes entails that the players are allowed to observe the complete game history (such as the past values of (W n t , B n t , D n t , Q n t )) when making their decisions.

Uncertainty classes and assumptions
For each π ∈ P, we denote by ξ π and (σ π ) 2 the mean and variance of π, i.e.
It will be convenient to work with the notation q π = 1 2 (σ π ) 2 . Further assumptions on the uncertainty classes Π n are as follows.
2. For each there exist a constant µ > 0 and a compact set K ⊂ R × (0, ∞) such that K n → K in d H , the Hausdorff distance corresponding to the Euclidean metric on R 2 , where Thus K n is the collection of prelimit drift and (half) variance of all measures that lie in Π n . It follows from the assumption that Π n are closed for each and n and Assumption 1(1) that K n are closed sets.
The assumption implies that all service time distributions allowed to be used by the adversary have the property that their mean converges to 1/µ as n → ∞. Thus µ represents the first order service rate for type . These parameters are assumed to satisfy the following. Assumptions 1 and 2 are our standing assumptions, that will be in force throughout this paper. Let us label the classes so that By scaling h we may and will assume without loss that h 1 µ 1 = 1.

Main results
A non-preemptive fixed priority policy is a strategy for the SC according to which service is noninterruptible and whenever the server becomes available (or the system is empty and a new arrival occurs) it admits into service a job of the type that has lowest index waiting in the queue (or arriving) at that moment. Because we have labeled the types as in (14), the corresponding policy obtained prioritizes according to the index hµ. This is often referred to in the literature as the nonpreemptive cµ policy. We will denote by β * n ∈ B n the strategy corresponding to the nonpreemptive cµ policy for the n-th system. Our first main result is that the sequence of strategies β * n is AO regardless of the behavior of the adversary.
Theorem 1. Consider an arbitrary sequence of controls for the adversary, a n ∈ A n . Then lim n { inf β n ∈B n C n (β n (a n ), a n ) − C n (β * n (a n ), a n )} = 0.
Theorem 1 allows us to reduce the asymptotic treatment of the game to that of a control problem in which the strategy for the SC has been fixed as β * n and one optimizes only over the adversary controls. We now introduce a problem that describes the limiting behavior of this control problem, hence of the game.
Martingale control problem (MCP). Given w ∈ R + , an admissible control system for w is a tuple where (Ω,F, {F t },P) is a filtered probability space, and Notice that Property 4 implies that both Y and [X ] have Lipschitz sample paths. The collection of all admissible control systems for w is denoted by S w . The cost for the problem is a function from ∪ w≥0 S w to R + , given by whereĒ denotes expectation underP, and the value is defined as In the MCP, the process W tot represents the limit of the processesŴ tot,n = Ŵ n and R the limit ofR n . The processes X and Y are related to the arrival processes A n in a slightly more complicated way, to be explained in §7. In terms of notation, X tot and Y tot stand for the sum over as per our convention, but note that as far as workload is concerned, the formulation above involves only one process, W tot (a notation W for the limit ofŴ n is not needed).
Then the value of the MCP can be characterized in terms of the following HJB equation that will always be considered with boundary conditions u (0) = 0 and lim sup w→∞ |u(w)|/w < ∞. We will be concerned with classical solutions, namely C 2 function that satisfy the equation classically.
Proposition 1. 1. There exists a unique classical solution to (HJB), denoted throughout by u. Moreover, V = u. 2. Given w there exists an admissible control system which is optimal for the MCP. Under this system, (W tot , R) form a weak solution (W, R) to the SDE with reflection at the origin where Z is a standard BM (SBM).
3. The function u is nonnegative, non-decreasing and convex.
Our second main result relates the stochastic game to the MCP and HJB equation.
There exists for each n and a measurable function ψ n : R + → Π n such that 3. If the SC uses the strategy β * n then it is AO for the adversary to select the control according to then the selection expressed by (15) can equivalently be stated as letting and then selecting a member π n k ∈ Π n k such that its prelimit drift and variance coefficients are given by (b π n , q π n ) = (b, q).

On the drift-variance tradeoff
Let us describe the simplest setting of our model for which the MCP is not trivial. This is the case when there is only one type of jobs, hence the SC has no freedom at all and the server simply works whenever there is work in the system. Moreover, the uncertainty class consists of only two members for each n. The adversary dynamically selects one of the two members for each arrival. This version of the model, although very simple, is meaningful, and can be used to explain the so called drift-variance tradeoff, which is present in a more complex fashion in the full model.
Consider a diffusion process W on R + with reflection at zero, for which the drift and diffusion coefficients can be dynamically controlled as follows. Two pairs of real numbers (b m , σ m ) ∈ R × (0, ∞), m = 1, 2, are given. A mode m ∈ {1, 2} can be dynamically chosen, and accordingly the instantaneous drift-diffusion pair of W is given by (b m , σ m ). One attempts to maximize the cost E ∞ 0 e −t W t dt. It is not hard to see that the MCP is equivalent to this problem in the special case under consideration. Now, if only the drift coefficient is subject to control (that is, σ 1 = σ 2 ) then it can be shown by a simple coupling that a control that always selects the larger value will maximize the cost. Similarly, if only the diffusion coefficient can be controlled, it is the one with larger value that is optimal to select. The situation is different when b 1 > b 2 and σ 1 < σ 2 . This problem was solved in [24], where it was called the tortoise-hare problem, and some extensions of it were studied in [3] where it was referred to as the drift-variance tradeoff. As shown in [24], the HJB equation can be fully solved, and its solution reveals an optimal tradeoff between the modes. Specifically, under the optimal control, mode 1 is selected at times when W t ≥ w * and mode 2 when W t < w * . Here, w * is a free boundary point characterized by an equation expressing the so called principle of smooth fit (see [24] and [3] for more details).
Thus, in the case where the uncertainty class has two members, the asymptotics of our model can be described by an explicit formula (i.e., the solution from [24] to the HJB equation), and moreover the asymptotic behavior of the adversary is fully understood.
We will have more to say about finite uncertainty classes. In any case, in its full generality, the MCP we study in this paper can be viewed as the problem of finding an optimal drift-variance tradeoff albeit in a more complex setting.

On the extremal and dominating subsets of ch(K n )
Our results show how the adversary behaves under an AO play. In particular, Theorem 2 asserts that the prelimit drift and variance coefficients are chosen dynamically so as to maximize the expression depending on the current state. A further insight on how the adversary acts can be gained by arguing that the maximization may be restricted to a smaller set. BecauseH is affine in (b, q), it is clear that the maximum is in the set, denoted ∂ ext K n , of extreme points of ch(K n ). We argue that one may restrict further the set where the maximum occurs. Consider the partial order ≤ on For a compact set K ⊂ R 2 let ∂ dom K denote the set of dominating points in K w.r.t. this partial order. That is, the smallest set of points (b , q ) such that for every (b, q) ∈ K there exists (b , q ) in this set such that (b, q) ≤ (b , q ). In follows from Proposition 1 that u and u are non-negative functions. As a result,H(u (w), u (w), b, q) is increasing in b and q. This implies that it is always advantageous for the adversary to choose points in the set ∂ dom K n . Combining the two observations, the maximum can be restricted a priori to An example is shown in Figure 1.  Figure 1: An example of a set K and its extremal and dominating sets. The set K is shown in gray. The boundary of ch(K) is in red. The set ∂ ext K consists of the two black points, three red points and the red dashed bold curve. The set ∂ dom K consists of the three red points, the red dashed and the red bold dashed curve. Thus the set ∂ ext K ∩ ∂ dom K is given by the three red points and the red bold dashed curve.
The simplification becomes much more significant in the special case of polygons. In this case the sets We arrive at a conclusion that uncertainty classes given by polygonal domains are no different than finite uncertainty classes as far as our setting is concerned. Beyond insight on the behavior of the adversary, this observation is relevant also for numerical solutions to the HJB equation, where it becomes much more manageable to numerically solve the equation when optimizing over a finite set.

Example: Gamma distribution
Gamma distributions are sometimes used to model service duration in the context of queueing systems; see for example [26] for an early such reference. Our goal here is to determine what collections of Gamma distributions give rise to a reasonable choice of an uncertainty class K n , and also what K n may look like for a natural choice of an uncertainty class defined in terms of the distribution parameters. Because there is no difference in our treatment between the various types ∈ [L], fix and let it be removed from all notation. For α > 0, β > 0, Gamma(α, β) is the distribution on R + that has a density f given by The mean and variance are given by α/β and α/β 2 , respectively. For the prelimit coefficients, consider a target set K n given as a rectangle, , and assume that b n 1 , b n 2 , q n 1 and q n 2 converge to b 1 , b 2 , q 1 and q 2 , respectively. Consider Π n to be a collection of Gamma(α, β) distributions of the form where G n ⊂ (0, ∞) 2 . What should G n be in order to achieve the above target set? To answer this, compute the prelimit coefficients for π ∈ Π n with parameters α, β. Then In addition, The last two equations imply This gives rise to The reverse direction is also of interest, namely for a given "reasonable" choice of G n we shall ask what K n and K look like. Consider first Π n given as in (16) In order for K n to converge to a compact set it is necessary (but not sufficient) that √ n(α n i /β n k −µ) = O(1) for all i, k ∈ {1, 2}. Hence one must have |β n which means For the set K n to converge, β n 1 and β n 2 must converge, and because of (18) and |β n 1 − β n 2 | → 0 they must have the same limit β * . There is only one choice of limiting variance given by µ/(2β * ). Although our results are not vacuous in this case, they do not give significant information.
We thus turn to a different definition of G n , which makes α/β nearly constant. A natural set that satisfies this requirement is Figure 2: The set K of (19). The extreme and dominating sets are shown according to the same convention as in Figure 1. Left: α 1 > 0 and α 2 > 0. Right: α 1 < 0 and α 2 > 0. (The case α 1 < 0 and α 2 < 0 is similar to the first one). In both cases, the set of extreme dominating points is given by the two red points.
. This gives rise to Taking the Hausdorff limit, using (18), K n converges to Possible sets K corresponding to the above are shown in Figure 2.

Example: Finite uncertainty class
Assume that for each , the uncertainty class Π n consists of finitely many measures. For simplicity, assume also that they all have the same cardinality, M . We label the members of each uncertainty class by m ∈ [M ], and, as in §3.1, refer to m as modes. Thus each Π n consists of {π mn : m ∈ [M ]}. In this case the game can be described in very simple terms. In the n-th system, for each ( , m) there is an IID sequence of π mn -distributed RVs, denoted J mn k , k ∈ N. These sequences are mutually independent. At each arrival time, k/n, for each type , there are M job candidates, namely J mn k , m ∈ [M ]. The adversary selects one of the M candidates and this will be the job to actually arrive at buffer . When making the selection, the adversary has access to the history of the system, as well as to the label m (thus the distribution) of each of the candidates, but it does not have access to the RVs J mn k themselves. As in our general setting, the SC's role is to split the server's effort among the types. See Figure 3.
It is assumed that all distributions alluded to above have a finite fourth moment, so as to satisfy our assumptions. Next, to meet our scaling assumptions, it is assumed that where q m > 0. By definition, for π = π mn , we have b π n = b m + o(1). As a consequence, K ,n → K in d H , where K consists of the pairs (b m , q m ). We now describe the choices made by the adversary. As argued in §3.2, among all points in K n , only those in ∆ n := ∂ ext K n ∩ ∂ n dom K n are taken into account. Let M n ⊂ [M ] denote the set of labels . . .

Server
Adversary SC Figure 3: Illustration of the case with finite uncertainty classes, specifically M = 2. With two streams of IID job sizes per type, the adversary dynamically controls which stream is admitted into the buffer, and the SC controls the server's effort allocation.
corresponding to points in ∆ n . An example of a finite set K n is shown in Figure 4(a). In this example there are three member of the set ∂ ext K n ∩ ∂ dom K n , shown in red. We argue that these three points define a finite partition of R 2 + according to which the adversary's choices are made. To this end, recall the notation v n k = (u (Ŵ tot,n (k−1)/n ), u (Ŵ tot,n (k−1)/n )).
By Proposition 1, this process takes values in R 2 + . By Theorem 2, the choice made at time k/n is to select mode Alternatively, this can be expressed as where θ m is the angle between (b m , q m ) and v n k . This rule corresponds to a partition of R 2 + into |M n | cone-shaped regions, as shown in Figure 4(b). Namely, the adversary chooses a mode at the k-th step according to the region to which v n k belongs. Note that if L = 1 and the set of points that are extremal and dominating consists of exactly two points, then we are back in the scenario described in §3.1. The above discussion shows that in this case the decision is according to whether

AO of the cµ policy
In this section we prove Theorem 1. The collection of all processes comprising the queueing model are uniquely defined once the players have selected their actions. Given n, a control a n ∈ A n chosen by the adversary and a strategy β n ∈ B n chosen by the SC, we shall always assume the collection of processes is the one determined by the pair (a n , β n ) and will not explicitly specify the dependence on this pair. In §2.1.3 we defined the tuple (ξ π , b π n , σ π , q π ) corresponding to a measure π. When one substitutes the measures π n k chosen by the adversary, this tuple becomes a stochastic process, for which we shall use the notation ξ n k = ξ π n k , b n k = b π n k , n , σ n k = σ π n k , q n k = q π n k .
We need the notion of convergence in probability uniformly in the strategy β n , and related notions.
Definition 1. Let {ψ n a n ,β n } and {ϕ n a n ,β n (·)} be a sequence of RVs and, respectively, stochastic processes, that depend on n ∈ N, a n ∈ A n and β n ∈ B n .
• Given a sequence a n ∈ A n , the sequence {ψ n a n ,β n } is said to converge to 0 in probability uniformly in β n ∈ B n if for any ε > 0, sup β n ∈B n P ψ n a n ,β n ≥ ε → 0 as n → ∞. Henceforth, this convergence will simply be called uniform in probability.
We now state several lemmas and provide the proof of Theorem 1 based on them. In §4.2, these lemmas are proved.

Proof of Theorem 1
The first states that the total workload process does not depend on the strategy. Lemma 2. For any n ∈ N, a n ∈ A n , β n ,β n ∈ B n , if W tot,n andW tot,n are the processes corresponding to (a n , β n ) and (a n ,β n ), respectively, then W tot,n =W tot,n .
Proof. Immediate from (11) and the definition of A tot,n .
Next is a polynomial in time estimate on the second moment of the workload and queue length. Lemma 3. There exists a constant c < ∞ such that for all n ∈ N, t ≥ 0, a n ∈ A n and β n ∈ B n , The following result is a version of the RSP, by which the queue length and workload processes are asymptotically proportional to one another. Lemma 4. Given any a n ∈ A n , for all t 0 > 0 and ∈ [L], Q n − µ Ŵ n t 0 → 0 uniformly in probability as n → ∞.
Whereas the above three lemmas are concerned with general behavior of the SC, our next result is about a certain property of the specific strategy β * n . It states that when the server operates under the fixed nonpreemptive priority rule, the workload is asymptotically concentrated on the lowest-priority type.
Lemma 5. Assume that the SC applies the strategy β * n . Then for any a n ∈ A n , L =2Ŵ n → 0 in probability as n → ∞.
We are now ready to prove Theorem 1.
Proof of Theorem 1. It suffices to prove that lim inf n ∆ n ≥ 0 where ∆ n = inf β∈B n C n (β n (a n ), a n ) − C n (β * n (a n ), a n ).
To this end, we observe that for any strategy β n ∈ B n and t 0 > 0, C n (β n (a n ), a where the last inequality is due to the nonnegativity ofŴ n t and the fact h µ ≥ h 1 µ 1 = 1. Upon denoting ε t 0 (a n , β n ) = E L =1 h Q n − µ Ŵ n t 0 ,ε t 0 (a n ) = sup β n ∈B n ε t 0 (a n , β n ), and recalling that by Lemma 2,Ŵ tot,n does not depend on the strategy, we have inf β n ∈B n C n (β n (a n ), a n ) ≥ E t 0 0 e −tŴ tot,n t dt −ε t 0 (a n ).
Again using the fact thatŴ tot,n is independent of β n , combining with (23) we obtain ∆ n ≥ −ε t 0 (a n ) −ε t 0 (a n ).
In view of Lemma 3, the uniform (in β n ) convergence stated in Lemma 4 shows that lim nε t 0 (a n ) = 0 for every t 0 . For the same reason, lim nε t 0 1 (a n ) = 0. Similarly, by Lemmas 3 and 5, lim nε t 0 3 (a n ) = 0. This shows that lim inf where Lemma 3 is used again. The result follows on taking t 0 → ∞.

Proof of the Lemmas
The proofs require some preparation. Denote the centered version of job size byJ n k = J n k − ξ n k . Recalling the definition of b n from Assumption 1.2 and (21), we can write where we defined By compactness of K and the convergence K n → K in d H , the sets K n are uniformly bounded. Hence so are the processes b n , q n . Recalling that by our conventionŶ n = n −1/2 Y n , we have Second, with e n t = nt − nt, by (11) we write W tot,n t = X tot,n t + Y tot,n t + e n t + R tot,n t and obtain (Ŵ tot,n ,R n ) = Γ (X tot,n +Ŷ tot,n +ê n ).
Lemma 6. There exists a constant c such that for all n ∈ N, ∈ [L], a n ∈ A n and β n ∈ B n , 1. The processesX n are martingales with respect to {G n t }, of quadratic covariation [X n ,X n ] t = 1 n nt k=1J n kJ n k , 2. E X n 2 t ≤ ct and E [X n ] t ≤ ct.
Proof. As the index does not play any role in the proof, it is fixed and omitted to simplify notation. Note that {X n t } t≥0 is adapted to {G n t } t≥0 by the definition ofX n and of G n . Consider s < t. If nt = ns then the increment ofX n is zero. If nt = ns + 1 then For general t > s the martingale property follows by the tower property. The expression for the quadratic covariation follows directly from its definition. This proves part 1.
To prove part 2, abbreviateX n t toX t andJ n toJ k in the next display to get where the boundedness of the second moment ofJ n k follows from the boundedness of q n k . The claim regarding E[ X 2 t ] now follows from Doob's inequality. Next, E [X n ] t is equal to the first term in (28), and thus the required estimate follows from (29).
Hence by Lemma 6, E Ŵ n 2 t ≤ c(t + 1) 2 . Next, by the definition of D n t we have W n t = nt k=D n t +1 J n k , where clearly D n t ≤ nt. By the definition Hence,Q n t = µ (Ŵ n t −X n t −Ŷ n t +X n D n t /n +Ŷ n D n t /n ). (31) By the bound just obtained on the second moment ofŴ n and the bounds used in the previous paragraph onX n andŶ n , E Q n 2 t ≤ c(t + 1) 2 .
Lemma 7. For any control a n ∈ A n , the sequence {X n , [X n ],Ŷ n ,Ŵ tot,n ,R n } n∈N is uniformly C-tight.
C-tightness is not stated, and in general does not hold, for each componentŴ n .
Proof. It suffices to prove uniform C-tightness for each component. We prove first for each ∈ [L] that the first three components of the tuple are uniformly C-tight, omitting the index in the proof. By (26), the processŶ n is bounded by the function ct, and w t 0 (Ŷ n , δ) ≤ c(δ + n −1 ). Because both bounds are uniform in β n ∈ B n , uniform C-tightness follows. Turning toX n , given t 0 , the uniform bound needed on P( X n t 0 > x) follows from Lemma 6. Next, for any δ of the form 3t 0 /N , some N ∈ N, consider the N = 3t 0 /δ closed intervals 4 .
SinceX n t is a martingale, Burkholder's inequality yields where the last ineqaulity combines Cauchy-Schwarz inequality, Assumption 1.1 and the fact that |nt−nt i | ≤ nδ. Note that c does not depend on β n . Combining the above estimates gives This converges to 0 when taking n → ∞ and then δ → 0, proving uniform C-tightness of {X n } n . As for [X n ], recalling that this process is nondecreasing, we have by Lemma 6 the estimate needed on P([X n ] t 0 > x). To estimate its modulus of continuity, a similar consideration as forX n gives Using (32) to bound the terms in the above sum as we did forX n yields uniform C-tightness of [X n ] as in the argument forX n . Next, by (11) we have (Ŵ tot,n ,R n ) = Γ (X tot,n +Ŷ tot,n +ê n ). Hence the continuity of Γ implies uniform C-tightness of {Ŵ tot,n ,R n } n .
Proof of Lemma 4. All the processes in the proof are associated with a fixed , omitted from the notation. Write where j n t = j n t is the work that the server has completed by time t of the job served at that time, if it is of type (0 otherwise). Denotingψ n =X n +Ŷ n , where on the last line we used (3). The last display readily gives two bounds, namely and, using again the identity (3), We show that the RHS of (34) converges to 0 uniformly in probability, as n → ∞. To this end, bound the second term as for any δ > 0. The uniform C-tightness ofX n stated in Lemma 7 implies that the above expression converges to 0 uniformly in probability as n → ∞ and then δ → 0. As for the first term in (34), note that for ε > 0, Lemma 7 implies that lim δ→0 lim sup n→∞ sup β∈B n P(w t 0 (ψ n , δ) > ε) = 0. Also, by (33) and uniform Ctightness ofŴ tot,n andψ n , it follows that n −1 Q n t 0 → 0 uniformly in probability. Altogether, these estimates show that Ŵ n −Q n µ t 0 → 0 uniformly in probability, as n → ∞. Proof of Lemma 5. Let the strategy β * n be used by the SC. Fix ε, t 0 > 0 and denote by E n the event { L =2Ŵ n t 0 > ε}. Denote byψ n the procesŝ Then, by (24), By Lemma 7 and the convergeceê n → 0, {ψ n } n is C-tight. Let Let j n t denote the residual work of the job in service at time t. On E n , τ and θ take values in [0, t 0 ]. In addition, L =2 (nB n τ − nB n θ ) ≥ n(τ − θ) − j n θ on E n because there is work to serve throughout this time interval (thus the server is not idle), and moreover, there is work of high-priority (≥ 2) types so the cumulative effort of serving type 1 jobs is bounded by j n θ (in case the job in service at time θ is of type 1). Therefore by (35) and the heavy-traffic condition L =1 (µ ) −1 = 1, on E n one has To show that the second term converges to 0, note that it is bounded by n −1/2 max k∈[nt], ∈[L] J n k . Hence the argument given in the proof of Lemma 4 applies here. As for the first term, ≤ P ψ n t 0 > cn 1/4 + P w t 0 ψ n , n −1/4 > ε 4 .
Both terms converge to 0 by the C-tightness of {ψ n } n . This shows that P(E n ) → 0 and completes the proof.
Theorem 1 justifies the choice of the strategy β * n by the SC, and this will be assumed for the rest of the paper.

The MCP
In this section we prove Proposition 1. The proof is based on existence of classical solutions to fully nonlinear uniformly elliptic equations with Dirichlet boundary conditions. Specifically, consider the following version of the HJB equation, set on a finite interval, namely with the boundary conditions u(0) = ϕ 0 , u(x) = ϕ 1 . Let us show that the assumptions of [15,Theorem 17.18] hold. To this end, the infimum in the formulation given in [15] can be translated to supremum by the transformation u → −u in an obvious way. Moreover, as indicated in the paragraph that follows the statement of [15,Theorem 17.18], it suffices to verify the conditions in [15, (17.62)]. To verify these conditions, note that uniform ellipticity holds in our case by the assumption that K is compact and contained in R × (0, ∞). The boundedness of the coefficients and their derivatives is trivial in our case, as these coefficients are given, in the notation of [15], as follows: the coefficients a ij ν , b i ν and c ν are constants for each ν (the role of ν is played in our setting by the point (b , q ) ∈ R 2 ), and f ν (w) = w. We thus deduce that there exists a unique classical solution to (HJB-x), for any (ϕ 0 , ϕ 1 ) ∈ R 2 . The proof now proceeds in several steps.
For the boundary condition at infinity, note that by Burkholder's inequality and property 4 of the MCP one hasĒ[ X tot t ] ≤ c(Ē[X tot ] t ]) 1/2 < ct 1/2 . Also by property 4, Y tot t ≤ ct. By property 3, Hence, for every w and S ∈ S w , Since the constant c does not depend on S, it follows that Next, to show V (0) = 0, note that We shall use the following property of the map Γ 1 , which can be easily checked directly by its definition. Let w ≥ 0, ϕ ∈ C R [0, ∞), ψ 1 = Γ 1 (ϕ) and ψ 2 = Γ 1 (w + ϕ). Denote the hitting time τ = τ (w + ϕ) = inf{t ≥ 0 : w + ϕ t ≤ 0}. Then for all t, ψ 1 t ≤ ψ 2 t , whereas for all t ≥ τ , Next, using the Lipschitz property of Γ 1 , we bound further Because for all w and all S ∈ S w , the processes Y tot are uniformly Lipschitz, denoting by c 0 the Lipschitz constant, we have To proceed, note that by Property 4 of the MCP and the fact that K ⊂ R×(0, ∞), the mapping s → [X tot ] s has the property for all 0 ≤ s 1 < s 2 , where 0 < c 1 < c 2 are constants. Consequently, this mapping admits a Lipschitz, strictly increasing inverse, denoted T . By the time-change theorem for martingales [19,Theorem 3.4.6], the process Z t = X tot T (t) is a SBM. Thus The RHS above does not depend on S, and, for every t > 0, converges to zero as w → 0. This shows that the RHS of (37) converges to zero as w → 0, which shows that V (0) = 0.
For 0 ≤ t ≤ τ x , property 3 of the MCP reduces to W tot = w + X tot + Y tot and R = 0. The goal of this step is to prove the identity Abbreviating W tot to W, applying Itô's lemma and denoting τ = τ (x, t) := τ x ∧ t, Substitute dW s = dX tot s + dY tot s and d[X tot ] s = L =1 d[X ] s (since, by property 4 of the MCP, [X , X ] = 0 for = ) and take expectation. Using the fact that X tot is a martingale gives Using this in (39) gives where the last equality holds because f solves (HJB-x). On the event {τ x < t}, we have W τx ∈ {0, x}, hence the boundary conditions of (HJB-x) yield We now take the limit t → ∞. Note that for s ≤ τ x ∧ t, W s is bounded by x, and the function u x is also bounded. Using the bounded convergence theorem for the first and last terms, and, noticing that the almost sure limit of e −τx 1 {τx<t} V (W τx ) is e −τx 1 {τx<∞} V (W τx ) and using Fatou's lemma for this term, and finally taking supremum over all admissible systems, we obtain that f (w) is bounded below by the RHS of (38). For the reverse inequality, we invoke a measurable selection theorem, according to which for each there exists a function (b , * , q , * ) : [0, x] → ch(K ) such that for every y ∈ [0, x], q , * (y)f (y) + b , * (y)f (y) = max{qf (y) + bf (y) : (b, q) ∈ ch(K )}.
This follows directly from [8,Lemma 8.10]. Denote σ , * (y) = 2 q , * (y). The argument requires the construction of an admissible system for the MCP, S * . The first step in this construction will be to argue that there exists a weak solution (W, R, Z, {F t }) to the SDE where w ≥ 0, {F t } is a filtration Z = (Z ) is a standard L-dimensional {F t }-BM, R the reflection term at 0, and (W, R) are adapted. Denoteσ(y) = ( L =1 (σ , * (y)) 2 ) 1/2 , y ≥ 0. Consider the SDE on R whereZ is a 1d BM, and sign(y) = 1 for y > 0 and = −1 for y ≤ 0. By [19,Theorem 5.5.15] and the fact thatσ is bounded away from zero, this SDE admits a weak solution (Ψ,Z, {F t }). Denote W t = |Ψ t | and Z t = t 0 sign(Ψ s )dZ s . Then clearlyẐ is an SBM, and, by Tanaka's formula [21, Propositions 9.2 and 9.3], there exists a process R with sample paths in C + such that and [0,∞) W t dR t = 0 a.s. Notice that the term b , * (W s )ds of (SDE1) agrees with the term b tot, * (W s )ds of (43). Hence the proof that (SDE1) possesses a weak solution will be complete once we construct an L-dimensional SBM (Z ) that satisfies To this end we look for a measurable map U : (0, ∞) L → R L×L that sends any v ∈ R L + \ {0} to a matrix whose columns comprise an orthonormal basis of R L . Denote by {e } the standard basis of R L . Given a column vector v ∈ (0, ∞) L , the collection {v, e 1 , ..., e L−1 } spans R L . Denote by U (v) the matrix obtained by the Gram-Schmidt procedure, applied on the collection {v, e 1 , ..., e L−1 }. Then the first column of the In addition, the map U is measurable by the Gram-Schmidt construction. Assume WLOG that the probability space supports L − 1 independent SBMs, independent ofẐ; denote the resulting L-dimensional SBM by (Ž ) whereŽ 1 =Ẑ. Denote by σ * (W t ) the column-vector valued process (σ 1, * (W t ), ..., σ L, * (W t )) T . Define the R L×L -valued process η t = U (σ * (W t )). Finally, let Because η t is an orthonormal matrix for every t, it follows by [19,Proposition 3.2.17] that Z is an Ldimensional SBM. It remains to show (44). Note that the LHS of (44) is σ * (W s ) T dZ s . By construction, where the third equality follows from (45) and the last one by the identitiesσ(·) = σ * (·) andŽ 1 =Ẑ. This completes the proof that the tuple (W, R, Z) solves (SDE1). The next step in the construction of S * is to let It remains to prove that S satisfies Properties 1-4 of the MCP. Properties 1-2 follow by construction. For Property 3, by construction, (SDE1) reads W t = w + X tot t + Y tot t + R t . Moreover, W t is R + -valued and [0,∞) W t dR t = 0 a.s. Hence, by Skorohod's lemma, (W, R) = Γ (w + X tot + Y tot ) a.s. As for Property 4, note first that for = , one has [Z , Z ] = 0, hence [X , X ] = 0, using [19,Proposition 3.2.17]. Moreover, by definition, (b , * (y), (σ , * (y)) 2 ) ∈ ch(K ) for all y ∈ R + and We now go back to the argument leading to (41), and show that, with the system S * just constructed, (41) holds with equality. To this end, note by the construction of X and Y, and the definition of b * and σ * , that Reviewing the proof of (41) we see that it holds as equality in this case. We finally take t → ∞ as before, except that this time we apply the bounded convergence theorem for the second term, appealing to (36). This proves the identity (38).
Step 3. By the dynamic programming principle, the function f = f (x) defined on [0, x] and the function V are related as V(w) = f (x) (w), 0 ≤ w ≤ x. As this is true for all x ∈ R + , it follows that the function V is a classical solution to (HJB) on R + , and by Step 1 it satisfies the boundary conditions attached to it.
To complete the proof of part 1 of the Proposition, one must show that if u is any classical solution then u = V. This can be shown by a calculation very similar to that carried out in Step 2; we omit the details.
Step 4. We next prove Part 2. We consider a system constructed exactly as S * from Step 2 except that the function u is used instead of f (x) , and with a slight abuse of notation denote it again by S * . Then the relation of this system to the SDE (43) is as claimed, and it remains to prove that it is optimal for the MCP (which is different than the statement already proved, that it is optimal for the control problem (38)). A calculation similar to that given in Step 2, replacing τ by t and using the boundary condition V (0) = 0, gives a version of (40) with equality, namely Thus optimality follows once it is shown that the LHS above converges to 0 as t → ∞. It is easy to see by (43) that E[W t ] ≤ c(1 + t) (where c may depend on w but not on t). Combined with (36) this shows E[|V(W t )|] ≤ c(1+t). Thus the LHS above converges to 0, and optimality is proved. The statement relating b and σ toH, H follows by the construction in Step 2. Specifically, this statement is exactly equations (42) and (43).

The upper bound
The goal of this section and the next is to prove Theorem 2, where this section is devoted to establishing lim sup To prove it, note that V n ≤ sup a n C n (β * n (a n ), a n ). Therefore it suffices to show that for every sequence a n of admissible controls for the adversary, one has lim sup n C n (β * n (a n ), a n ) ≤ V(0).
To prove (47), fix a n . Lemma 7 establishes the C-tightness of the tuple {X n , [X n ],Ŷ n ,Ŵ tot,n ,R n } n∈N . Thus to prove (47), it suffices to show that (47) holds along any subsequence where the tuple converges. In what follows we fix a subsequence where the tuple converges, and denote its limit by {X , U , Y , W tot , R}.
(We later prove that U = [X ]). WLOG, the limit processes are defined on the original probability space. The main step toward proving this upper bound will be to show that the limit tuple defines an admissible system for the MCP, as we state below in Proposition 2. We first need to establish the following.
1. Let ψ be defined by ψ n t = 1 n nt k=1 1 2 (J n k ) 2 − q n k , and let γ n t = [X n ,X n ] t . Then ψ n and γ n are martingales w.r.t. {G n t } for = .
Proof. Part 1. The proof is based on (σ n k ) 2 /2 = q n k and on the fact that for m ≤ k − 1 where the second identity follows from the conditional independence of J n k and J n k stated in (7). Part 2. The main tool for estimating the two martingales is Burkholder's inequality. Starting with ψ n , by the identity (σ n k ) 2 /2 = q n k , as n → ∞, where we used (7) and the measurability of σ 2 k with respect to F n k−1 , and the last inequality is due to Assumption 1.1. Finally for γ n , = , by (7), as n → ∞.
Recall that we have denoted the subsequential limit by ((X , Y , U ) , W tot , R). Denotē Proof. Property 2 of the MCP follows directly from the definition of the filtration. For Property 3, recall (27). By the weak convergence of (X n ,Ŷ n ) , along the subsequence that has been fixed, the continuity of the sample paths of (X , Y ) , and the convergence ofê n to zero, we have that w +X tot,n +Ŷ tot,n +ê n ⇒ Z := w + X tot + Y tot . Since Γ is a continuous mapping, we obtain (W tot , R) = Γ (Z).
For Property 4, first we shall prove the following statement: To this end we invoke [17, Corollary VI.6.30]. To do this, note that where c does not depend on n. Hence the assumptions of [17, Corollary VI. 6.30] are verified and it follows that (X n , [X n ]) ⇒ (X, [X]). Hence we obtain the identity [X ] = U . By Lemma 8.2, [X n ,X n ] → 0 in probability for = . Therefore we have [X , X ] = 0, = . This shows (49).
The first part of Property 4 of the MCP follows. As for its second part, recall the definition of the processes b n k and σ n k from (21) and the definition of Y n t in (25). Then The RHS converges to 0 in probability by Lemma 8.2. It follows from (49) that (Ŷ n , [X n ]) ⇒ (Y , [X ]). Therefore the sequence (nt − ns) −1 nt k= ns +1 (b n k , q n k ) has a limit, and it remains to show that this limit is in ch(K ). To show this, note that (b n k , q n k ) ∈ K n . Therefore, for n > (t − s) −1 , as a convex combination of members of K ,n . We have assumed that K n → K in d H . By the definition of d H , it is elementary to show that this implies ch(K n ) → ch(K ) in d H . It is also elementary that the limit of a convergent sequence of members of ch(K n ) must lie in ch(K ). We omit the details. As a result, for every s < t, the limit of (50), given by (t To this end we first show that for any k ∈ N and any continuous bounded function g k : R 2k → R, where ρ t 1 ...t k is the natural projection from D 2 [0, ∞) to R 2k at 0 ≤ t 1 ≤ · · · ≤ t k ≤ t. Indeed, by the martingale property ofX n , E X n t+u g k (ρ t 1 ...t k (X n ,Ŷ n )) = E X n t g k (ρ t 1 ...t k (X n ,Ŷ n )) .
Hence by the normalization h 1 µ 1 = 1, we have h ·Q n ⇒ W tot . To deduce from this convergence of the expected integrals, we appeal to uniform integrability. Consider the probability measure dP × e −t dt on the product space (Ω × R + , F ⊗ R + ). W.r.t. this measure, h ·Q n are uniformly integrable as RVs on the product space, as follows directly from Lemma 3. As a result, along the subsequence, lim n C(β * n (a n ), a n ) = lim This completes the proof of (47). The upper bound (46) follows.

The lower bound
The objective here is to prove and then complete the proof of Theorem 2. To this end, we construct a sequence {a * n } that satisfies This suffices in order to prove that lim n V n = V(0) because by Theorem 1, Toward showing (55), recall that by Lemmas 4 and 5 and the choice h 1 µ 1 = 1, when the SC uses strategy β * n , one has thatQ n → 0 for 2 ≤ ≤ L and h ·Q n −Ŵ tot,n → 0 in probability. Using this along with a uniform integrability argument as in (53) yields that, under {β * n } and any control sequence {a n }, lim inf n→∞ C(β * n (a n ), a n ) = lim inf Therefore, in order to prove (55) (hence (54)) it suffices to find a control sequence {a * n } such that under (a * n , β * n ) one has We will now show that (56) holds under a suitable {a * n }; in particular, we will assume throughout what follows that the strategy β * n is used. Again, in this proof, the label 'tot' is suppressed. Recall the expression given in (27) for (Ŵ n ,R n ). Here it is more convenient to work with pure jump processes and define (W n ,R n ) = Γ (X n +Ŷ n ). Because of the Lipschitz property of Γ , we have only a small error between (W n ,R n ) and (Ŵ n ,R n ). Specifically, for all t, W n −Ŵ n t + R n −R n t ≤ c ê n t ≤ cn −1/2 .
ThusW n ,R n ,X n ,Ŷ n are pure jump processes starting at 0, andW n =X n +Ŷ n +R n . Moreover, the jump sizes are given by e.g., ∆W n k/n =W n k/n −W n (k−1)/n , k ≥ 1. Denote W n k =W k/n and R n k =R n k/n . We shall use the fact that, by the definition of (W n ,R n ), (and withJ tot,n k , b tot,n k abbreviated asJ n k , b n k ), ∆W n k = ∆X n k/n + ∆Ŷ n k/n + ∆R n k = n −1/2J n k + n −1 b n k + ∆R n k .
Once π n k is selected as above for all , the tuple (J n k ) ∈[L] is selected according to (7), and this defines a control process that we shall denote a * n . The proof of the first part of the theorem will be complete once we show that this control satisfies (55).
SinceW n is piecewise constant with jumps at times that are multiples of n −1 , nτ takes values in N ∪ {∞}. In addition, nτ is an {F n k } stopping time since {nτ ≤ k} = {τ ≤ k n } ∈ G n k/n = F n k . Applying Taylor expansion with the Lagrange remainder, there exists ζ n k taking a value between W n k and W n k−1 such that Consider the kth term in the first sum in (63). Denote H k = 1 {k−1<nτ } . Note that b n k and W n k−1 are F n k−1 -measurable and that E[(J n k ) 2 |F n k−1 ] = q tot,n k =: q k due to the independence of (J n k ) conditioned on F n k−1 . Hence by (62) and (HJB), Toward using the HJB equation we need to address the discrepancy between the maximization over K n and over K . To this end we use the following fact, which follows directly from the assumption that K n → K in d H and the compactness of K n and K . Namely, for any compact C ⊂ R 2 , lim n sup x∈C | max y∈K n y · x − max y∈K y · x| = 0.
Moreover, by [23, Theorem 32.2] max y∈K y · x = max y∈ch(K ) y · x. We apply these two facts with where |ε n 4,k | ≤ε n 4 andε n 4 is a deterministic sequence (which depends on x but not on k or ) converging to zero as n → ∞. The above, together with the fact that u solves (HJB), results in The next step is to show that E[ε n i ] → 0 for 1 ≤ i ≤ 6, where the case i = 4 has already been addressed. For ε n 2 , let K 1 = K n 1 = {k ∈ [nt] : ∆R n k > 0} and sum separately over k ∈ K 1 and over k ∈ K c 1 . For k ∈ K c 1 , we have |ρ n k | ≤ c/n. For k ∈ K 1 , recall the definition of ξ n and observe that since ∆R n k > 0 only if W n k = 0, one has by (58), where the last equality follows from the relation between ξ n k and b n k expressed in Assumption 1(2) and Assumption 2 by which 1/µ sum to 1. Therefore, in these times, 0 ≤ J n k ≤ 1 and ∆R n k ≤ n −1/2 .
This implies |ρ n k | = ∆R n k + b n k n ≤ 2 √ n ,