arXiv:1404.1957v3 [math.PR] 29 Oct 2015

The Annals of Applied Probability
2015, Vol. 25, No. 6, 3511–3570
DOI: 10.1214/14-AAP1081
c Institute of Mathematical Statistics, 2015

ERGODIC CONTROL OF MULTI-CLASS M/M/N + M QUEUES
IN THE HALFIN–WHITT REGIME
By Ari Arapostathis∗,1, Anup Biswas∗,2 and Guodong Pang†,3
The University of Texas at Austin∗ and Pennsylvania State University†
We study a dynamic scheduling problem for a multi-class queueing network with a large pool of statistically identical servers. The
arrival processes are Poisson, and service times and patience times
are assumed to be exponentially distributed and class dependent. The
optimization criterion is the expected long time average (ergodic) of
a general (nonlinear) running cost function of the queue lengths. We
consider this control problem in the Halfin–Whitt (QED) regime,
that is, the number of servers n and the total offered load r scale
√
like n ≈ r + ρ̂ r for some constant ρ̂. This problem was proposed in
[Ann. Appl. Probab. 14 (2004) 1084–1134, Section 5.2].
The optimal solution of this control problem can be approximated
by that of the corresponding ergodic diffusion control problem in the
limit. We introduce a broad class of ergodic control problems for controlled diffusions, which includes a large class of queueing models in
the diffusion approximation, and establish a complete characterization of optimality via the study of the associated HJB equation. We
also prove the asymptotic convergence of the values for the multi-class
queueing control problem to the value of the associated ergodic diffusion control problem. The proof relies on an approximation method
by spatial truncation for the ergodic control of diffusion processes,
where the Markov policies follow a fixed priority policy outside a
fixed compact set.

Received April 2014; revised November 2014.
Supported in part by the Office of Naval Research Grant N00014-14-1-0196.
2
Supported in part by an award from the Simons Foundation (# 197982) to The University of Texas at Austin and in part by the Office of Naval Research through the Electric
Ship Research and Development Consortium.
3
Supported in part by the Marcus Endowment Grant at the Harold and Inge Marcus
Department of Industrial and Manufacturing Engineering at Penn State.
AMS 2000 subject classifications. Primary 60K25; secondary 68M20, 90B22, 90B36.
Key words and phrases. Multi-class Markovian queues, reneging/abandonment,
Halfin–Whitt (QED) regime, diffusion scaling, long time-average control, ergodic control,
stable Markov optimal control, spatial truncation, asymptotic optimality.
1

This is an electronic reprint of the original article published by the
Institute of Mathematical Statistics in The Annals of Applied Probability,
2015, Vol. 25, No. 6, 3511–3570. This reprint differs from the original in
pagination and typographic detail.
1

2

A. ARAPOSTATHIS, A. BISWAS AND G. PANG

CONTENTS
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1. Contributions and comparisons . . . . . . . . . . . . . . .
1.2. Organization . . . . . . . . . . . . . . . . . . . . . . . . .
1.3. Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2. The controlled system in the Halfin–Whitt regime . . . . . .
2.1. The multi-class Markovian many-server model . . . . . .
2.2. The ergodic control problem in the Halfin–Whitt regime
3. A broad class of ergodic control problems for diffusions . . .
3.1. The controlled diffusion model . . . . . . . . . . . . . . .
3.2. Structural assumptions . . . . . . . . . . . . . . . . . . .
3.3. Piecewise linear controlled diffusions . . . . . . . . . . . .
3.4. Existence of optimal controls . . . . . . . . . . . . . . . .
3.5. The HJB equation . . . . . . . . . . . . . . . . . . . . . .
3.6. Technical proofs . . . . . . . . . . . . . . . . . . . . . . .
4. Approximation via spatial truncations . . . . . . . . . . . . .
5. Asymptotic convergence . . . . . . . . . . . . . . . . . . . . . .
5.1. The lower bound . . . . . . . . . . . . . . . . . . . . . . .
5.2. The upper bound . . . . . . . . . . . . . . . . . . . . . . .
6. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . .
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

2
4
6
6
8
8
10
14
14
17
18
22
26
31
42
48
49
53
61
61
61

1. Introduction. One of the classical problems in queueing theory is to
schedule the customers/jobs in a network in an optimal way. These problems are known as the scheduling problems which arise in a wide variety
of applications, in particular, whenever there are different customer classes
present in the network and competing for the same resources. The optimal
scheduling problem has a long history in the literature. One of the appealing
scheduling rules is the well-known cµ rule. This is a static priority policy
in which it is assumed that each class-i customer has a marginal delay cost
ci and an average service time 1/µi , and the classes are prioritized in the
decreasing order of ci µi . This static priority rule has proven asymptotically
optimal in many settings [4, 28, 32]. In [11], a single-server Markov modulated queueing network is considered and an averaged cµ-rule is shown
asymptotically optimal for the discounted control problem.
An important aspect of queueing networks is abandonment/reneging, that
is, customers/jobs may choose to leave the system while being in the queue
before their service. Therefore, it is important to include customer abandonment in modeling queueing systems. In [5, 6], Atar et al. considered a
multi-class M/M/N +M queueing network with customer abandonment and
proved that a modified priority policy, referred to as cµ/θ rule, is asymptotically optimal for the long run average cost in the fluid scale. Dai and Tezcan
[13] showed the asymptotic optimality of a static priority policy on a finite

ERGODIC CONTROL IN THE HALFIN–WHITT REGIME

3

time interval for a parallel server model under the assumed conditions on
the ordering of the abandonment rates and running costs. Although static
priority policies are easy to implement, it may not be optimal for control
problems of many multi-server queueing systems. For the same multi-class
M/M/N + M queueing network, discounted cost control problems are studied in [3, 7, 22], and asymptotically optimal controls for these problems are
constructed from the minimizer of a Hamilton–Jacobi–Bellman (HJB) equation associated with the controlled diffusions in the Halfin–Whitt regime.
In this article, we are interested in an ergodic control problem for a
multi-class M/M/N + M queueing network in the Halfin–Whitt regime.
The network consists of a single pool of n statistically identical servers and
a buffer of infinite capacity. There are d customer classes and arrivals of
jobs/customers are d independent Poisson processes with parameters λni ,
i = 1, . . . , d. The service rate for class-i customers is µni , i = 1, . . . , d. Customers may renege from the queue if they have not started to receive service
before their patience times. Class-i customers renege from the queue at rates
γin > 0, i = 1, . . . , d. The scheduling policies are work-conserving, that is, no
server stays idle if any of the queues is nonempty. We assume the system
operates in the Halfin–Whitt regime, where the arrival rates and the number
of servers are scaled appropriately in a manner that the traffic intensity of
the system satisfies
!
d
X
√
λni
−→ ρ̂ ∈ R.
n 1−
nµni n→∞
i=1

In this regime, the system operations achieve both high quality (high server
levels) and high efficiency (high servers’ utilization), and hence it is also
referred to as the Quality-and-Efficiency-Driven (QED) regime; see, for example, [7, 16, 17, 19, 21] on the many-server regimes. We consider an ergodic
cost function given by

Z T
1
n
r(Q̂ (s)) ds ,
lim sup E
T →∞ T
0

where the running cost r is a nonnegative, convex function with polynomial
growth and Q̂n = (Q̂n1 , . . . , Q̂nd )T is the diffusion-scaled queue length process.
It is worth mentioning that in addition to the running cost above which is
based on the queue-length, we can add an idle-server cost provided that it
has at most polynomial growth. For such, a running cost structure the same
analysis goes through. The control is the allocation of servers to different
classes of customers at the service completion times. The value function is
defined to be the infimum of the above cost over all admissible controls
(among all work-conserving scheduling policies). In this article, we are interested in the existence and uniqueness of asymptotically optimal stable

4

A. ARAPOSTATHIS, A. BISWAS AND G. PANG

stationary Markov controls for the ergodic control problem, and the asymptotic behavior of the value functions as n tends to infinity. In [7], Section 5.2,
it is stated that analysis of this type of problems is important for modeling
call centers.
1.1. Contributions and comparisons. The usual methodology for studying these problems is to consider the associated continuum model, which
is the controlled diffusion limit in a heavy-traffic regime, and to study the
ergodic control problem for the controlled diffusion. Ergodic control problems governed by controlled diffusions have been well studied in literature
[1, 9] for models that fall in these two categories: (a) the running cost is
near-monotone, which is defined by the requirement that its value outside a
compact set exceeds the optimal average cost, thus penalizing unstable behavior (see Assumption 3.4.2 in [1] for details), or (b) the controlled diffusion
is uniformly stable, that is, every stationary Markov control is stable and the
collection of invariant probability measures corresponding to the stationary
Markov controls is tight. However, the ergodic control problem at hand does
not fall under any of these frameworks. First, the running cost we consider
here is not near-monotone because the total queue length can be 0 when
the total number of customers in the system are O(n). On the other hand,
it is not at all clear that the controlled diffusion is uniformly stable (unless
one imposes nontrivial hypotheses on the parameters), and this remains an
open problem. One of our main contributions in this article is that we solve
the ergodic control problem for a broad class of nondegenerate controlled
diffusions, that in a certain way can be viewed as a mixture of the two categories mentioned above. As we show in Section 3, stability of the diffusion
under any optimal stationary Markov control occurs due to certain interplay
between the drift and the running cost. The model studied in Section 3 is
far more general than the queueing problem described, and thus it is of separate interest for ergodic control. We present a comprehensive study of this
broad class of ergodic control problems that includes existence of a solution
to the ergodic HJB equation, its stochastic representation and verification
of optimality (Theorem 3.4), uniqueness of the solution in a certain class
(Theorem 3.5), and convergence of the vanishing discount method (Theorem 3.6). These results extend the well-known results for near-monotone
running costs. The assumptions in these theorems are verified for the multiclass queueing model and the corresponding characterization of optimality
is obtained (Corollary 3.1), which includes growth estimates for the solution
of the HJB.
We also introduce a new approximation technique, spatial truncation, for
the controlled diffusion processes; see Section 4. It is shown that if we freeze
the Markov controls to a fixed stable Markov control outside a compact
set, then we can still obtain nearly optimal controls in this class of Markov

ERGODIC CONTROL IN THE HALFIN–WHITT REGIME

5

controls for large compact sets. We should keep in mind that this property is
not true in general. This method can also be thought of as an approximation
by a class of controlled diffusions that are uniformly stable.
We remark that for a fixed control, the controlled diffusions for the queueing model can be regarded as a special case of the piecewise linear diffusions
considered in [14]. It is shown in [14] that these diffusions are stable under
constant Markov controls. The proof is via a suitable Lyapunov function.
We conjecture that uniform stability holds for the controlled diffusions associated with the queueing model. For the same multi-class Markovian model,
Gamarnik and Stolyar show that the stationary distributions of the queue
lengths are tight under any work-conserving policy [15], Theorem 2. We also
wish to remark here that we allow ρ̂ to be negative, assuming abandonment
rates are strictly positive, while in [15], ρ̂ > 0 and abandonment rates can
be zero.
Another important contribution of this work is the convergence of the
value functions associated with the sequence of multi-class queueing models to the value of the ergodic control problem, say ̺∗ , corresponding to the
controlled diffusion model. It is not obvious that one can have asymptotic optimality from the existence of optimal stable controls for the HJB equations
of controlled diffusions. This fact is relatively straightforward when the cost
under consideration is discounted. In that situation, the tightness of paths
on a finite time horizon is sufficient to prove asymptotic optimality [7]. But
we are in a situation where any finite time behavior of the stochastic process
plays no role in the cost. In particular, we need to establish the convergence
of the controlled steady states. Although uniform stability of stationary distributions for this multi-class queueing model in the case where ρ̂ > 0 and
abandonment rates can be zero is established in [15], it is not obvious that
the stochastic model considered here has the property of uniform stability.
Therefore, we use a different method to establish the asymptotic optimality.
First, we show that the value functions are asymptotically bounded below by
̺∗ . To study the upper bound, we construct a sequence of Markov scheduling policies that are uniformly stable (see Lemma 5.1). The key idea used
in establishing such stability results is a spatial truncation technique, under which the Markov policies follow a fixed priority policy outside a given
compact set. We believe these techniques can also be used to study ergodic
control problems for other many-server queueing models.
The scheduling policies we consider in this paper allow preemption, that
is, a customer in service can be interrupted for the server to serve a customer
of a different class and her service will be resumed later. In fact, the asymptotic optimality is shown within the class of the work-conserving preemptive
policies. In [7], both preemptive and nonpreemptive policies are studied,
where a nonpreemptive scheduling control policy is constructed from the
HJB equation associated with preemptive policies and thus is shown to be

6

A. ARAPOSTATHIS, A. BISWAS AND G. PANG

asymptotically optimal. However, as far as we know, the optimal nonpreemptive scheduling problem under the ergodic cost remains open.
For a similar line of work in uncontrolled settings, we refer the reader
to [16, 19]. Admission control of the single class M/M/N + M model with
an ergodic cost criterion in the Halfin–Whitt regime is studied in [26]. For
controlled problems and for finite server models, asymptotic optimality is
obtained in [12] in the conventional heavy-traffic regime. The main advantage in [12] is the uniform exponential stability of the stochastic processes,
which is obtained by using properties of the Skorohod reflection map. A
recent work studying ergodic control of a multi-class single-server queueing
network is [25].
To summarize our main contributions in this paper:
– We introduce a new class of ergodic control problems and a framework to
solve them.
– We establish an approximation technique by spatial truncation.
– We provide, to the best of our knowledge, the first treatment of ergodic
control problems at the diffusion scale for many server models.
– We establish asymptotic optimality results.
1.2. Organization. In Section 1.3, we summarize the notation used in
the paper. In Section 2, we introduce the multi-class many server queueing
model and describe the Halfin–Whitt regime. The ergodic control problem
under the heavy-traffic setting is introduced in Section 2.2, and the main
results on asymptotic convergence are stated as Theorems 2.1 and 2.2. Section 3 introduces a class of controlled diffusions and associated ergodic control problems, which contains the queueing models in the diffusion scale.
The key structural assumptions are in Section 3.2 and these are verified for
a generic class of queueing models in Section 3.3, which are characterized
by piecewise linear controlled diffusions. Section 3.4 concerns the existence
of optimal controls under the general hypotheses, while Section 3.5 contains
a comprehensive study of the HJB equation. Section 3.6 is devoted to the
proofs of the results in Section 3.5. The spatial truncation technique is introduced and studied in Section 4. Finally, in Section 5 we prove the results
of asymptotic optimality.
1.3. Notation. The standard Euclidean norm in Rd is denoted by |·|. The
set of nonnegative real numbers is denoted by R+ , N stands for the set of
natural numbers, and I denotes the indicator function. By Zd+ we denote the
set of d-vectors of nonnegative integers. The closure, the boundary and the
complement of a set A ⊂ Rd are denoted by A, ∂A and Ac , respectively. The
open ball of radius R around 0 is denoted by BR . Given two real numbers
a and b, the minimum (maximum) is denoted by a ∧ b (a ∨ b), respectively.

ERGODIC CONTROL IN THE HALFIN–WHITT REGIME

7

Define a+ := a ∨ 0 and a− := −(a ∧ 0). The integer part of a real number
a is denoted by ⌊a⌋. We use the notation ei , i = 1, . . . , d, to denote the
vector with ith entry equal to 1 and all other entries equal to 0. We also let
e := (1, . . . , 1)T . Given any two vectors x, y ∈ Rd the inner product is denoted
by x · y. By δx we denote the Dirac mass at x. For any function f : Rd → R
and domain D ⊂ R we define the oscillation of f on D as follows:
osc(f ) := sup{f (x) − f (y) : x, y ∈ D}.
D

For a nonnegative function g ∈ C(Rd ), we let O(g) denote the space of
|f (x)|
< ∞. This is a Banach space
functions f ∈ C(Rd ) satisfying supx∈Rd 1+g(x)
under the norm
|f (x)|
kf kg := sup
.
x∈Rd 1 + g(x)
We also let o(g) denote the subspace of O(g) consisting of those functions f
satisfying
lim sup
|x|→∞

|f (x)|
= 0.
1 + g(x)

By a slight abuse of notation, we also denote by O(g) and o(g) a generic
member of these spaces. For two nonnegative functions f and g, we use the
notation f ∼ g to indicate that f ∈ O(g) and g ∈ O(f ).
We denote by Lploc (Rd ), p ≥ 1, the set of real-valued functions that are
p
d
d
locally p-integrable and by Wk,p
loc (R ) the set of functions in Lloc (R ) whose
p
ith weak derivatives, i = 1, . . . , k, are in Lloc (Rd ). The set of all bounded
k,α
continuous functions is denoted by Cb (Rd ). By Cloc
(Rd ) we denote the set of
functions that are k-times continuously differentiable and whose kth derivatives are locally Hölder continuous with exponent α. We define Cbk (Rd ), k ≥ 0,
as the set of functions whose ith derivatives, i = 1, . . . , k, are continuous and
bounded in Rd and denote by Cck (Rd ) the subset of Cbk (Rd ) with compact
support. For any path X(·), we use the notation ∆X(t) to denote the jump
at time t. Given any Polish space X , we denote by P(X ) the set of probability measures on X and we endow P(X ) with the Prokhorov metric. For
ν ∈ P(X ) and a Borel measurable map f : X → R, we often use the abbreviated notation
Z
f dν.
ν(f ) :=
X

The quadratic variation of a square integrable martingale is denoted by
h·, ·i and the optional quadratic variation by [·, ·]. For presentation purposes
we use the time variable as the subscript for the diffusion processes. Also
κ1 , κ2 , . . . and C1 , C2 , . . . are used as generic constants whose values might
vary from place to place.

8

A. ARAPOSTATHIS, A. BISWAS AND G. PANG

Fig. 1.

A schematic model of the system.

2. The controlled system in the Halfin–Whitt regime.
2.1. The multi-class Markovian many-server model. Let (Ω, F, P) be a
given complete probability space and all the stochastic variables introduced
below are defined on it. The expectation w.r.t. P is denoted by E. We consider a multi-class Markovian many-server queueing system which consists
of d customer classes and n parallel servers capable of serving all customers
(see Figure 1).
The system buffer is assumed to have infinite capacity. Customers of class
i ∈ {1, . . . , d} arrive according to a Poisson process with rate λni > 0. Customers enter the queue of their respective classes upon arrival if not being
processed. Customers of each class are served in the first-come-first-serve
(FCFS) service discipline. While waiting in queue, customers can abandon
the system. The service times and patience times of customers are classdependent and both are assumed to be exponentially distributed, that is,
class i customers are served at rate µni and renege at rate γin . We assume
that customer arrivals, service and abandonment of all classes are mutually
independent.
The Halfin–Whitt regime. We study this queueing model in the Halfin–
Whitt regime [or the Quality-and-Efficiency-Driven (QED) regime]. Consider a sequence of such systems indexed by n, in which the arrival rates λni
and the number of servers n both increase appropriately. Let rni := λni /µni
be the mean offered load of classPi customers. The traffic intensity of the
nth system is given by ρn = n−1 di=1 rni . In the Halfin–Whitt regime, the

ERGODIC CONTROL IN THE HALFIN–WHITT REGIME

9

parameters are assumed to satisfy the following: as n → ∞,

(2.1)

λni
→ λi > 0,
µni → µi > 0,
n
√
λni − nλi
√
n(µni − µi ) → µ̂i ,
→ λ̂i ,
n
λi
rni
→ ρi :=
< 1,
n
µi

This implies that
√

n(1 − ρn ) → ρ̂ :=

d
X

γin → γi > 0,

ρi = 1.

i=1

d
X
ρi µ̂i − λ̂i
i=1

µi

∈ R.

The above scaling is common in multi-class multi-server models [7, 22]. Note
that we do not make any assumption on the sign of ρ̂.
State descriptors. Let Xin = {Xin (t) : t ≥ 0} be the total number of class i
customers in the system, Qni = {Qni (t) : t ≥ 0} the number of class i customers
in the queue and Zin = {Zin (t) : t ≥ 0} the number of class i customers in
service. The following basic relationships hold for these processes: for each
t ≥ 0 and i = 1, . . . , d,
(2.2)

Xin (t) = Qni (t) + Zin (t),
Qni (t) ≥ 0,

Zin (t) ≥ 0 and

e · Z n (t) ≤ n.

We can describe these processes using a collection {Ani , Sin , Rin , i = 1, . . . , d}
of independent rate-1 Poisson processes. Define
Ãni (t) := Ani (λni t),
 Z t

S̃in (t) := Sin µni
Zin (s) ds ,
0

 Z t

n
n
n
n
R̃i (t) := Ri γi
Qi (s) ds .
0

Then the dynamics take the form
(2.3) Xin (t) = Xin (0) + Ãni (t) − S̃in (t) − R̃in (t),

t ≥ 0, i = 1, . . . , d.

Scheduling control. Following [7, 22], we only consider work-conserving
policies that are nonanticipative and allow preemption. When a server becomes free and there are no customers waiting in any queue, the server stays
idle, but if there are customers of multiple classes waiting in the queue, the

10

A. ARAPOSTATHIS, A. BISWAS AND G. PANG

server has to make a decision on the customer class to serve. Service preemption is allowed, that is, service of a customer class can be interrupted at
any time to serve some other class of customers and the original service is resumed at a later time. A scheduling control policy determines the processes
Z n , which must satisfy the constraints in (2.2) and the work-conserving
constraint, that is,
e · Z n (t) = (e · X n (t)) ∧ n,

t ≥ 0.

Define the action set An (x) as
An (x) := {a ∈ Zd+ : a ≤ x and e · a = (e · x) ∧ n}.
Thus, we can write Z n (t) ∈ An (X n (t)) for each t ≥ 0. We also assume that
all controls are nonanticipative. Define the σ-fields
Ftn := σ{X n (0), Ãni (t), S̃in (t), R̃in (t) : i = 1, . . . , d, 0 ≤ s ≤ t} ∨ N
and
Gtn := σ{δÃni (t, r), δS̃in (t, r), δR̃in (t, r) : i = 1, . . . , d, r ≥ 0},
where
δÃni (t, r) := Ãni (t + r) − Ãni (t),
 Z t

n
n
n
n
n
δS̃i (t, r) := Si µi
Zi (s) ds + µi r − S̃in (t),
0

δR̃in (t, r) :=

Rin



γin

Z

0

t

Qni (s) ds + γin r



− R̃in (t),

and N is the collection of all P-null sets. The filtration {Ftn , t ≥ 0} represents
the information available up to time t while Gtn contains the information
about future increments of the processes.
We say that a working-conserving control policy is admissible if:
(i) Z n (t) is adapted to Ftn ,
(ii) Ftn is independent of Gtn at each time t ≥ 0,
(iii) for each i = 1, . . . , d, and t ≥ 0, the process δS̃in (t, ·) agrees in law
with Sin (µni ·), and the process δR̃in (t, ·) agrees in law with Rin (γin ·).

We denote the set of all admissible control policies (Z n , F n , G n ) by Un .

2.2. The ergodic control problem in the Halfin–Whitt regime. Define the
diffusion-scaled processes
X̂ n = (X̂1n , . . . , X̂dn )T ,

Q̂n = (Q̂n1 , . . . , Q̂nd )T

and

Ẑ n = (Ẑ1n , . . . , Ẑdn )T ,

ERGODIC CONTROL IN THE HALFIN–WHITT REGIME

11

by

(2.4)

1
X̂in (t) := √ (Xin (t) − ρi nt),
n
1
Q̂ni (t) := √ Qni (t),
n
1
Ẑin (t) := √ (Zin (t) − ρi nt)
n

for t ≥ 0. By (2.3), we can express X̂in as
Z t
Z t
n
n
n
n
n
n
X̂i (t) = X̂i (0) + ℓi t − µi
Ẑi (s) ds − γi
Q̂ni (s) ds
0
0
(2.5)
n
n
n
+ M̂A,i
(t) − M̂S,i
(t) − M̂R,i
(t),
where ℓn = (ℓn1 , . . . , ℓnd )T is defined as
1
ℓni := √ (λni − µni ρi n),
n

and

(2.6)

1
n
M̂A,i
(t) := √ (Ani (λni t) − λni t),
n
  Z t


Z t
1
n
n
n
n
n
n
M̂S,i (t) := √ Si µi
Zi (s) ds − µi
Zi (s) ds ,
n
0
0
  Z t


Z t
1
n
n
n
n
n
n
M̂R,i (t) := √ Ri γi
Qi (s) ds − γi
Qi (s) ds
n
0
0

are square integrable martingales w.r.t. the filtration {Ftn }.
Note that
√
1
(λ̂i − ρi µ̂i )
.
ℓni = √ (λni − λi n) − ρi n(µni − µi ) −→ ℓi :=
n→∞
n
µi
Define
S := {u ∈ Rd+ : e · u = 1}.

For Z n ∈ Un we define, for t ≥ 0 and for adapted Û n (t) ∈ S,
(2.7)

Q̂n (t) := (e · X̂ n (t))+ Û n (t),

Ẑ n (t) := X̂ n (t) − (e · X̂ n (t))+ Û n (t).

If Q̂n (t) = 0, we define Û n (t) := ed = (0, . . . , 0, 1)T . Thus, Ûin represents the
fraction of class-i customers in the queue when the total queue size is positive. As we show later, it is convenient to view Û n (t) as the control. Note
that the controls are nonanticipative and preemption is allowed.

12

A. ARAPOSTATHIS, A. BISWAS AND G. PANG

2.2.1. The cost minimization problem. We next introduce the running
cost function for the control problem. Let r : Rd+ → R+ be a given function
satisfying
(2.8)

c1 |x|m ≤ r(x) ≤ c2 (1 + |x|m )

for some m ≥ 1,

and some positive constants ci , i = 1, 2. We also assume that r is locally Lipschitz. This assumption includes linear and convex running cost functions.
For example, if we let hi be the holding cost rate for class i customers, then
some of the typical running cost functions are the following:
r(x) =

d
X

hi xm
i ,

m ≥ 1.

i=1

These running cost functions evidently satisfy the condition in (2.8).
Given the initial state X n (0) and a work-conserving scheduling policy
n
Z ∈ Un , we define the diffusion-scaled cost function as

Z T
1
n
n
n
(2.9)
r(Q̂ (s)) ds ,
J(X̂ (0), Ẑ ) := lim sup E
T →∞ T
0
where the running cost function r satisfies (2.8). Note that the running
cost is defined using the scaled version of Z n . Then the associated cost
minimization problem becomes
(2.10)

V̂ n (X̂ n (0)) := ninf n J(X̂ n (0), Ẑ n ).
Z ∈U

We refer to V̂ n (X̂ n (0)) as the diffusion-scaled value function given the
initial state X̂ n (0) in the nth system.
From (2.7), it is easy to see that by redefining r as r(x, u) = r((e · x)+ u)
we can rewrite the control problem as
˜ X̂ n (0), Û n ),
V̂ n (X̂ n (0)) = inf J(
where
(2.11)

˜ X̂ n (0), Û n ) := lim sup 1 E
J(
T →∞ T

Z

T
0


r(X̂ n (s), Û n (s)) ds ,

and the infimum is taken over all admissible pairs (X̂ n , Û n ) satisfying (2.7).
For simplicity, we assume that the initial condition X̂ n (0) is deterministic
and X̂ n (0) → x as n → ∞ for some x ∈ Rd .

ERGODIC CONTROL IN THE HALFIN–WHITT REGIME

13

2.2.2. The limiting controlled diffusion process. As in [7, 22], one formally deduces that, provided X̂ n (0) → x, there exists a limit X for X̂ n on
every finite time interval, and the limit process X is a d-dimensional diffusion
process with independent components, that is,
(2.12)

dXt = b(Xt , Ut ) dt + Σ dWt,

with initial condition X0 = x. In (2.12), the drift b(x, u) : Rd × S → Rd takes
the form
(2.13)
with

b(x, u) = ℓ − R(x − (e · x)+ u) − (e · x)+ Γu,
ℓ := (ℓ1 , . . . , ℓd )T ,
R := diag(µ1 , . . . , µd ),
Γ := diag(γ1 , . . . , γd ).

The control Ut lives in S and is nonanticipative, W (t) is a d-dimensional
standard Wiener process independent of the initial condition X0 = x, and
the covariance matrix is given by
ΣΣT = diag(2λ1 , . . . , 2λd ).
A formal derivation of the drift in (2.13) can be obtained from (2.5) and
(2.7). A detailed description of equation (2.12) and related results are given
in Section 3. Let U be the set of all admissible controls for the diffusion
model (for a definition see Section 3).
2.2.3. The ergodic control problem in the diffusion scale. Define r̃ : Rd+ ×
Rd+ → R+ by
r̃(x, u) := r((e · x)+ u),

where r is the same function as in (2.9). In analogy with (2.11) we define
the ergodic cost associated with the controlled diffusion process X and the
running cost function r̃(x, u) as

Z T
1 U
J(x, U ) := lim sup Ex
r̃(Xt , Ut ) dt ,
U ∈ U.
T →∞ T
0
We consider the ergodic control problem
(2.14)

̺∗ (x) = inf J(x, U ).
U ∈U

We call ̺∗ (x) the optimal value at the initial state x for the controlled
diffusion process X. It is shown later that ̺∗ (x) is independent of x. A
detailed treatment and related results corresponding to the ergodic control
problem are given in Section 3.
We next state the main results of this section, the proof of which can be
found in Section 5.

14

A. ARAPOSTATHIS, A. BISWAS AND G. PANG

Theorem 2.1. Let X̂ n (0) → x ∈ Rd as n → ∞. Also assume that (2.1)
and (2.8) hold. Then
lim inf V̂ n (X̂ n (0)) ≥ ̺∗ (x),
n→∞

where ̺∗ (x) is given by (2.14).
Theorem 2.2. Suppose the assumptions of Theorem 2.1 hold. In addition, assume that r in (2.9) is convex. Then
lim sup V̂ n (X̂ n (0)) ≤ ̺∗ (x).
n→∞

Thus, we conclude that for any convex running cost function r, Theorems 2.1 and 2.2 establish the asymptotic convergence of the ergodic control
problem for the queueing model.
3. A broad class of ergodic control problems for diffusions.
3.1. The controlled diffusion model. The dynamics are modeled by a controlled diffusion process X = {Xt , t ≥ 0} taking values in the d-dimensional
Euclidean space Rd , and governed by the Itô stochastic differential equation
(3.1)

dXt = b(Xt , Ut ) dt + σ(Xt ) dWt .

All random processes in (3.1) live in a complete probability space (Ω, F, P).
The process W is a d-dimensional standard Wiener process independent of
the initial condition X0 . The control process U takes values in a compact,
metrizable set U, and Ut (ω) is jointly measurable in (t, ω) ∈ [0, ∞) × Ω.
Moreover, it is nonanticipative: for s < t, Wt − Ws is independent of
Fs := the completion of σ{X0 , Ur , Wr , r ≤ s} relative to (F, P).
Such a process U is called an admissible control, and we let U denote the set
of all admissible controls.
We impose the following standard assumptions on the drift b and the
diffusion matrix σ to guarantee existence and uniqueness of solutions to
equation (3.1).
(A1) Local Lipschitz continuity: The functions
b = [b1 , . . . , bd ]T : Rd × U → Rd

and σ = [σ ij ] : Rd → Rd×d

are locally Lipschitz in x with a Lipschitz constant CR > 0 depending on
R > 0. In other words, for all x, y ∈ BR and u ∈ U,
|b(x, u) − b(y, u)| + kσ(x) − σ(y)k ≤ CR |x − y|.
We also assume that b is continuous in (x, u).

ERGODIC CONTROL IN THE HALFIN–WHITT REGIME

15

(A2) Affine growth condition: b and σ satisfy a global growth condition
of the form
|b(x, u)|2 + kσ(x)k2 ≤ C1 (1 + |x|2 )

∀(x, u) ∈ Rd × U,

where kσk2 := trace(σσ T ).
(A3) Local nondegeneracy: For each R > 0, it holds that
d
X

i,j=1

−1 2
|ξ|
aij (x)ξi ξj ≥ CR

∀x ∈ BR ,

for all ξ = (ξ1 , . . . , ξd )T ∈ Rd , where a := σσ T .
In integral form, (3.1) is written as
Z t
Z t
(3.2)
σ(Xs ) dWs .
b(Xs , Us ) ds +
Xt = X0 +
0

0

The third term on the right-hand side of (3.2) is an Itô stochastic integral.
We say that a process X = {Xt (ω)} is a solution of (3.1), if it is Ft -adapted,
continuous in t, defined for all ω ∈ Ω and t ∈ [0, ∞), and satisfies (3.2) for
all t ∈ [0, ∞) a.s. It is well known that under (A1)–(A3), for any admissible
control there exists a unique solution of (3.1) [1], Theorem 2.2.4.
We define the family of operators Lu : C 2 (Rd ) → C(Rd ), where u ∈ U plays
the role of a parameter, by
(3.3)

Lu f (x) := 12 aij (x)∂ij f (x) + bi (x, u)∂i f (x),

u ∈ U.

We refer to Lu as the controlled extended generator of the diffusion. In
∂
(3.3) and elsewhere in this paper, we have adopted the notation ∂i := ∂x
i
2

and ∂ij := ∂x∂i ∂xj . We also use the standard summation rule that repeated
subscripts and superscripts are summed from 1 through d. In other words,
the right-hand side of (3.3) stands for
d
d
X
1 X ij
∂f
∂2f
bi (x, u)
a (x)
(x) +
(x).
2
∂xi ∂xj
∂xi
i=1

i,j=1

Of fundamental importance in the study of functionals of X is Itô’s formula. For f ∈ C 2 (Rd ) and with Lu as defined in (3.3), it holds that
Z t
LUs f (Xs ) ds + Mt ,
(3.4)
a.s.,
f (Xt ) = f (X0 ) +
0

where

Mt :=

Z

0

t

h∇f (Xs ), σ(Xs ) dWs i

16

A. ARAPOSTATHIS, A. BISWAS AND G. PANG

is a local martingale. Krylov’s extension of Itô’s formula [27], page 122,
d
extends (3.4) to functions f in the local Sobolev space W2,p
loc (R ), p ≥ d.
Recall that a control is called Markov if Ut = v(t, Xt ) for a measurable map
v : R+ × Rd → U, and it is called stationary Markov if v does not depend on
t, that is, v : Rd → U. Correspondingly, (3.1) is said to have a strong solution
if given a Wiener process (Wt , Ft ) on a complete probability space (Ω, F, P),
there exists a process X on (Ω, F, P), with X0 = x0 ∈ Rd , which is continuous,
Ft -adapted, and satisfies (3.2) for all t a.s. A strong solution is called unique,
if any two such solutions X and X ′ agree P-a.s., when viewed as elements of
C([0, ∞), Rd ). It is well known that under assumptions (A1)–(A3), for any
Markov control v, (3.1) has a unique strong solution [20].
Let USM denote the set of stationary Markov controls. Under v ∈ USM , the
process X is strong Markov, and we denote its transition function by Pvt (x, ·).
It also follows from the work of [8, 31] that under v ∈ USM , the transition
probabilities of X have densities which are locally Hölder continuous. Thus,
Lv defined by
Lv f (x) := 12 aij (x)∂ij f (x) + bi (x, v(x))∂i f (x),

v ∈ USM ,

for f ∈ C 2 (Rd ), is the generator of a strongly-continuous semi-group on
Cb (Rd ), which is strong Feller. We let Pvx denote the probability measure
and Evx the expectation operator on the canonical space of the process under the control v ∈ USM , conditioned on the process X starting from x ∈ Rd
at t = 0.
We need the following definition.
Definition 3.1. A function h : Rd × U → R is called inf-compact on a
set A ⊂ Rd if the set Ā ∩ {x : minu∈U h(x, u) ≤ β} is compact (or empty) in
Rd for all β ∈ R. When this property holds for A ≡ Rd , then we simply say
that h is inf-compact.
Recall that control v ∈ USM is called stable if the associated diffusion
is positive recurrent. We denote the set of such controls by USSM , and let
µv denote the unique invariant probability measure on Rd for the diffusion
under the control v ∈ USSM . We also let M := {µv : v ∈ USSM }. Recall that
v ∈ USSM if and only if there exists an inf-compact function V ∈ C 2 (Rd ), a
bounded domain D ⊂ Rd , and a constant ε > 0 satisfying
Lv V(x) ≤ −ε

∀x ∈ D c .

We denote by τ (A) the first exit time of a process {Xt , t ∈ R+ } from a set
A ⊂ Rd , defined by
τ (A) := inf{t > 0 : Xt ∈
/ A}.

ERGODIC CONTROL IN THE HALFIN–WHITT REGIME

17

The open ball of radius R in Rd , centered at the origin, is denoted by BR ,
c ).
and we let τR := τ (BR ), and τ̆R := τ (BR
We assume that the running cost function r(x, u) is nonnegative, continuous and locally Lipschitz in its first argument uniformly in u ∈ U. Without
loss of generality, we let κR be a Lipschitz constant of r(·, u) over BR . In
summary, we assume that
(A4) r : Rd ×U → R+ is continuous and satisfies, for some constant CR > 0
|r(x, u) − r(y, u)| ≤ CR |x − y|

∀x, y ∈ BR , ∀u ∈ U,

and all R > 0.

In general, U may not be a convex set. It is therefore often useful to
enlarge the control set to P(U). For any v(du) ∈ P(U) we can redefine the
drift and the running cost as
Z
Z
(3.5)
b̄(x, v) := b(x, u)v(du) and r̄(x, v) := r(x, u)v(du).
U

U

It is easy to see that the drift and running cost defined in (3.5) satisfy all
the aforementioned conditions (A1)–(A4). In what follows, we assume that
all the controls take values in P(U). These controls are generally referred to
as relaxed controls. We endow the set of relaxed stationary Markov controls
with the following topology: vn → v in USM if and only if
Z
Z
Z
Z
f (x) g(x, u)v(du|x) dx
f (x) g(x, u)vn (du|x) dx −→
Rd

n→∞ Rd

U

L1 (Rd )

L2 (Rd )

U

(Rd

for all f ∈
∩
and g ∈ Cb
× U). Then USM is a compact
metric space under this topology [1], Section 2.4. We refer to this topology
as the topology of Markov controls. A control is said to be precise if it takes
value in U. It is easy to see that any precise control Ut can also be understood
as a relaxed control by Ut (du) = δUt . Abusing the notation, we denote the
drift and running cost by b and r, respectively, and the action of a relaxed
control on them is understood as in (3.5).
3.2. Structural assumptions. Assumptions 3.1 and 3.2, described below,
are in effect throughout the analysis, unless otherwise stated.
Assumption 3.1.

For some open set K ⊂ Rd , the following hold:

(i) The running cost r is inf-compact on K.
(ii) There exist inf-compact functions V ∈ C 2 (Rd ) and h ∈ C(Rd × U), such
that
(3.6)

Lu V(x) ≤ 1 − h(x, u)

∀(x, u) ∈ Kc × U,

Lu V(x) ≤ 1 + r(x, u)

∀(x, u) ∈ K × U.

18

A. ARAPOSTATHIS, A. BISWAS AND G. PANG

Without loss of generality, we assume that V and h are nonnegative.
Remark 3.1. In the statement of Assumption 3.1, we refrain from using
any constants in the interest of notational economy. There is no loss of
generality in doing so, since the functions V and h can always be scaled to
eliminate unnecessary constants.
The next assumption is not a structural one, but rather the necessary requirement that the value of the ergodic control problem is finite. Otherwise,
the problem is vacuous. For U ∈ U, define

Z T
1 U
̺U (x) := lim sup Ex
(3.7)
r(Xs , Us ) ds .
T →∞ T
0
Assumption 3.2.
x ∈ Rd .

There exists U ∈ U such that ̺U (x) < ∞ for some

Assumption 3.2 alone does not imply that ̺v < ∞ for some v ∈ USSM .
However, when combined with Assumption 3.1, this is the case as the following lemma asserts.
Lemma 3.1. Let Assumptions 3.1 and 3.2 hold. Then there exists u0 ∈
USSM such that ̺u0 < ∞. Moreover, there exists a nonnegative inf-compact
function V0 ∈ C 2 (Rd ), and a positive constant η such that
(3.8)

Lu0 V0 (x) ≤ η − r(x, u0 (x))

∀x ∈ Rd .

Conversely, if (3.8) holds, then Assumption 3.2 holds.
Proof. The first part of the result follows from Theorem 3.1(e) and
(3.23) whereas the converse part follows from Lemma 3.2. These proofs are
stated later in the paper. 
Remark 3.2. There is no loss of generality in using only the constant
η in Assumption 3.2, since V0 can always be scaled to achieve this.
We also observe that for K = Rd the problem reduces to an ergodic control problem with near-monotone cost, and for K = ∅ we obtain an ergodic
control problem under a uniformly stable controlled diffusion.
3.3. Piecewise linear controlled diffusions. The controlled diffusion process in (2.12) belongs to a large class of controlled diffusion processes, called
piecewise linear controlled diffusions [14]. We describe this class of controlled
diffusions and show that it satisfies the assumptions in Section 3.2.

ERGODIC CONTROL IN THE HALFIN–WHITT REGIME

19

Definition 3.2. A square matrix R is said to be an M -matrix if it can
be written as R = sI − N for some s > 0 and nonnegative matrix N with
property that ρ(N ) ≤ s, where ρ(N ) denotes the spectral radius of N .
Let Γ = [γ ij ] be a given matrix whose diagonal elements are positive,
= 0 for i = 1, . . . , d − 1, and the remaining elements are in R. (Note that
for the queueing model, Γ is a positive diagonal matrix. Our results below
hold for the more general Γ.) Let ℓ ∈ Rd and R be a nonsingular M -matrix.
Define
γ id

(3.9)

b(x, u) := ℓ − R(x − (e · x)+ u) − (e · x)+ Γu,

with u ∈ S := {u ∈ Rd+ : e · u = 1}. Assume that
eT R ≥ 0T .

We consider the following controlled diffusion in Rd :
(3.10)

dXt = b(Xt , Ut ) dt + Σ dWt,

where Σ is a constant matrix such that ΣΣT is invertible. It is easy to see
that (3.10) satisfies conditions (A1)–(A3).
Analysis of these types of diffusion approximations is an established tradition in queueing systems. It is often easy to deal with the limiting object and
it also helps to obtain information on the behavior of the actual queueing
model.
We next introduce the running cost function. Let r : Rd × S → [0, ∞) be
locally Lipschitz with polynomial growth and
(3.11)

c1 [(e · x)+ ]m ≤ r(x, u) ≤ c2 (1 + [(e · x)+ ]m ),

for some m ≥ 1 and positive constants c1 and c2 that do not depend on u.
Some typical examples of such running costs are
+ m

r(x, u) = [(e · x) ]

d
X
i=1

hi um
i

with m ≥ 1,

for some positive vector (h1 , . . . , hd )T .
Remark 3.3. The controlled dynamics in (3.9) and running cost in
(3.11) are clearly more general than the model described in Section 2.2. In
(3.10), X denotes the diffusion approximation for the number customers in
the system in the Halfin–Whitt regime and its ith component X i denotes
the diffusion approximation of the number of class i customers. Therefore,
(e · X)+ denotes the total number of customers in the queue. For R and
Γ diagonal as in (2.13), the diagonal entries of R and Γ denote the service

20

A. ARAPOSTATHIS, A. BISWAS AND G. PANG

and abandonment rates, respectively, of the customer classes. The ith coordinate of U denotes the fraction of class-i customers waiting in the queue.
Therefore, the vector-valued process Xt − (e · Xt )+ Ut denotes the diffusion
approximation of the numbers of customers in service from different customer classes.
Proposition 3.1. Let b and r be given by (3.9) and (3.11), respectively.
Then (3.10) satisfies Assumptions 3.1 and 3.2, with h(x) = c0 |x|m and

(3.12)

K := {x : δ|x| < (e · x)+ }

for appropriate positive constants c0 and δ.

Proof. We recall that if R is a nonsingular M -matrix, then there exists
a positive definite matrix Q such that QR + RT Q is strictly positive definite
[14]. Therefore, for some positive constant κ0 it holds that
2
κ0 |y|2 ≤ y T [QR + RT Q]y ≤ κ−1
0 |y|

∀y ∈ Rd .

The set K in (3.12), where δ > 0 is chosen later, is an open convex cone,
and the running cost function r is inf-compact on K. Let V be a nonnegative function in C 2 (Rd ) such that V(x) = [xT Qx]m/2 for |x| ≥ 1, where the
constant m is as in (3.11).
Let |x| ≥ 1 and u ∈ S. Then
m[xT Qx]m/2−1 T
x [QR + RT Q]x
2
+ m[xT Qx]m/2−1 Qx · (R − Γ)(e · x)+ u


m/2−1 κ0
T
2
+
≤ ℓ · ∇V(x) − m[x Qx]
|x| − C|x|(e · x)
2

∇V(x) · b(x, u) = ℓ · ∇V(x) −

κ0
, then on Kc ∩ {|x| ≥ 1}
for some positive constant C. If we choose δ = 4C
we have the estimate
mκ0 T
(3.13)
[x Qx]m/2−1 |x|2 .
∇V(x) · b(x, u) ≤ ℓ · ∇V(x) −
4
Note that ℓ · V is globally bounded for m = 1. For any m ∈ (1, ∞), it follows
by (3.13) that
mκ0 T
∇V(x) · b(x, u) ≤ m(ℓT Qx)[xT Qx]m/2−1 −
[x Qx]m/2−1 |x|2
4
(3.14)
m/2
T
mκ0 (λ(Q))m/2 m
m|ℓ Q|(λ(Q))
|x|m−1 −
|x|
≤
λ(Q)
4λ(Q)

for x ∈ Kc ∩ {|x| ≥ 1}, where λ(Q) and λ(Q) are the smallest and largest
eigenvalues of Q, respectively. We use Young’s inequality
|a|m m − 1 m/(m−1)
+
|b|
,
a, b ≥ 0,
|ab| ≤
m
m

ERGODIC CONTROL IN THE HALFIN–WHITT REGIME

21

in (3.14) to obtain the bound
(3.15)

∇V(x) · b(x, u) ≤ κ1 −

mκ0
(λ(Q))m/2 |x|m
8λ(Q)

for some constant κ1 > 0. A similar calculation shows for some constant
κ2 > 0 it holds that
(3.16)

∇V(x) · b(x, u) ≤ κ2 (1 + [(e · x)+ ]m )

∀x ∈ K ∩ {|x| ≥ 1}.

Also note that we can select κ3 > 0 large enough such that
(3.17)

1
mκ0
|trace(ΣΣT ∇2 V(x))| ≤ κ3 +
(λ(Q))m/2 |x|m .
2
16λ(Q)

Hence, by (3.13)–(3.17) there exists κ4 > 0 such that
mκ0
(λ(Q))m/2 |x|m IKc (x) + κ2 [(e · x)+ ]m IK (x)
(3.18) Lu V(x) ≤ κ4 −
16λ(Q)
for all x ∈ Rd . It is evident that we can scale V, by multiplying it with a
constant, so that (3.18) takes the form
(3.19) Lu V(x) ≤ 1 − c0 |x|m IKc (x) + c1 [(e · x)+ ]m IK (x)

∀x ∈ Rd .

By (3.11), the running cost r is inf-compact on K. It then follows from (3.11)
and (3.19) that (3.6) is satisfied with h(x) := c0 |x|m .
We next show that (3.10) satisfies Assumption 3.2. Let
u0 (·) ≡ ed = (0, . . . , 0, 1)T .
Then we can write (3.10) as
(3.20)

dXt = (ℓ − R(Xt − (e · Xt )+ u0 ) − (e · x)+ Γu0 ) dt + Σ dWt.

It is shown in [14] that the solution Xt in (3.20) is positive recurrent and,
therefore, u0 is a stable Markov control. This is done by finding a suitable
Lyapunov function. In particular, in [14], Theorem 3, it is shown that there
exists a positive definite matrix Q̃ such that if we define
(3.21)

ψ(x) := (e · x)2 + κ̃[x − ed φ(e · x)]T Q̃[x − ed φ(e · x)],

for some suitably chosen constant κ̃ and

 y,
φ(y) = − 21 δ̃,

smooth,

a function φ ∈ C 2 (R), given by
if y ≥ 0,
if y ≤ −δ̃,

if − δ̃ < y < 0,

where δ̃ > 0 is a suitable constant and 0 ≤ φ′ (y) ≤ 1, then it holds that
(3.22)

Lu0 ψ(x) ≤ −κ̃1 |x|2 ,

22

A. ARAPOSTATHIS, A. BISWAS AND G. PANG

for |x| large enough and positive constant κ̃1 . We define V0 := eaψ where a
is to be determined later. Note that |∇ψ(x)| ≤ κ̃2 (1 + |x|) for some constant
κ̃2 > 0. Hence, a straightforward calculation shows that if we choose a small
enough, then for some constant κ̃3 > 0 it holds that
Lu0 V0 (x) ≤ (−κ̃1 a|x|2 + a2 kΣk2 κ̃2 (1 + |x|)2 )V0 (x)
≤ −κ̃3 |x|2 V0 (x),

for all |x| large enough. Since V0 (x) > [(e · x)+ ]m , m ≥ 1, for all large enough
|x| we see that V0 satisfies (3.8) with control u0 . Hence, Assumption 3.2
holds by Lemma 3.1. 
3.4. Existence of optimal controls.
Definition 3.3.

Recall the definition of ̺U in (3.7). For β > 0, we define

Uβ := {U ∈ U : ̺U (x) ≤ β for some x ∈ Rd }.
We also let UβSM := Uβ ∩ USM , and
̺ˆ∗ := inf{β > 0 : Uβ 6= ∅},

̺∗ := inf{β > 0 : UβSM 6= ∅},

̺˜∗ := inf{π(r) : π ∈ G},
where

Z
d
G := π ∈ P(R × U) :

Rd ×U

u

L f (x)π(dx, du) = 0 ∀f

∈ Cc∞ (Rd )


,

and Lu f (x) is given by (3.3). It is well known that G is the set of ergodic
occupation measures of the controlled process in (3.1), and that G is a closed
and convex subset of P(Rd × U) [1], Lemmas 3.2.2 and 3.2.3. We use the
notation πv when we want to indicate the ergodic occupation measure associated with the control v ∈ USSM . In other words,
πv (dx, du) := µv (dx)v(du|x).
Lemma 3.2. If (3.8) holds for some V0 and u0 , then we have πu0 (r) ≤ η.
Therefore, ̺ˆ∗ < ∞.
Proof. Let (Xt , u0 (Xt )) be the solution of (3.1). Recall that τR is the
first exit time from BR for R > 0. Then by Itô’s formula

Z T ∧τR
u0
u0
Ex [V0 (XT ∧τR )] − V0 (x) ≤ ηT − Ex
r(Xs , u0 (Xs )) ds .
0

ERGODIC CONTROL IN THE HALFIN–WHITT REGIME

23

Therefore, letting R → ∞ and using Fatou’s lemma, we obtain the bound

Z T
u0
Ex
r(Xs , u0 (Xs )) ds ≤ ηT + V0 (x) − min V0 ,
Rd

0

and thus
1
lim sup Eux0
T →∞ T

Z

T
0



r(Xs , u0 (Xs )) ds ≤ η.



In the analysis, we use a function h̃ ∈ C(Rd × U) which, roughly speaking,
is of the same order as r in K × U and lies between r and a multiple of r + h
on Kc × U, with K as in Assumption 3.1. The existence of such a function
is guaranteed by Assumption 3.1 as the following lemma shows.
Lemma 3.3.

Define

H := (K × U) ∪ {(x, u) ∈ Rd × U : r(x, u) > h(x, u)},
where K is the open set in Assumption 3.1. Then there exists an inf-compact
function h̃ ∈ C(Rd × U) which is locally Lipschitz in its first argument uniformly w.r.t. its second argument, and satisfies
(3.23) r(x, u) ≤ h̃(x, u) ≤

k0
(1 + h(x, u)IHc (x, u) + r(x, u)IH (x, u))
2

for all (x, u) ∈ Rd × U, and for some positive constant k0 ≥ 2. Moreover,
(3.24)

Lu V(x) ≤ 1 − h(x, u)IHc (x, u) + r(x, u)IH (x, u)

for all (x, u) ∈ Rd × U, where V is the function in Assumption 3.1.
Proof. If f (x, u) denotes the right-hand side of (3.23), with k0 = 4,
then
f (x, u) − r(x, u) > h(x, u)IHc (x, u) + r(x, u)IH (x, u)
≥ h(x, u)IKc (x) + r(x, u)IK (x),
since r(x, u) > h(x, u) on H \ (K × U). Therefore, by Assumption 3.1, the
set {(x, u) : f (x, u) − r(x, u) ≤ n} is bounded in Rd × U for every n ∈ N.
Hence, there exists an increasing sequence of open balls Dn , n = 1, 2, . . . ,
centered at 0 in Rd such that f (x, u) − r(x, u) ≥ n for all (x, u) ∈ Dnc × U. Let
g : Rd → R be any nonnegative smooth function such that n − 1 ≤ g(x) ≤ n
for x ∈ Dn+1 \ Dn , n = 1, 2, . . . , and g(x) = 0 on D1 . Clearly, h̃ := r + g is
continuous, inf-compact, locally Lipschitz in its first argument, and satisfies
(3.23). That (3.24) holds is clear from (3.6) and the fact that H ⊇ K × U.


24

A. ARAPOSTATHIS, A. BISWAS AND G. PANG

Remark 3.4. It is clear from the proof of Lemma 3.3 that we could
fix the value of the constant k0 in (3.23), say k0 = 4. However, we keep the
variable k0 because this provides some flexibility in the choice of h̃, and also
in order to be able to trace it along the different calculations.
Remark 3.5. Note that if h ≥ r and r is inf-compact, then H = K × U
and h̃ := r satisfies (3.23). Note also, that in view of (3.11) and Proposition 3.1, for the multi-class queueing model we have
r(x, u) ≤ c2 (1 + [(e · x)+ ]m )

c2 dm−1
(1 + (1 ∧ c0 )|x|m )
1 ∧ c0


c2 dm−1
1
+ m
m c
≤
1 + c0 |x| IK (x) + m [(e · x) ] IK (x)
1 ∧ c0
δ


m−1
1
c2 d
r(x, u)IK (x)
1 + h(x)IKc (x) +
≤
1 ∧ c0
c1 δm

≤

≤
≤

c2 dm−1
(1 + h(x)IKc (x) + r(x, u)IK (x))
1 ∧ c0 ∧ c1 δm

c2 dm−1
(1 + h(x)IHc (x, u) + r(x, u)IH (x, u)).
1 ∧ c0 ∧ c1 δm

Therefore, h̃(x, u) := c2 + c2 dm−1 |x|m satisfies (3.23).

Remark 3.6. We often use the fact that if g ∈ C(Rd × U) is bounded
below, then the map P(Rd × U) ∋ ν 7→ ν(g) is lower semi-continuous. This
easily follows from two facts: (a) g can be expressed as an increasing limit
of bounded continuous functions, and (b) if g is bounded and continuous,
then π 7→ π(g) is continuous.
Theorem 3.1.

Let β ∈ (ˆ
̺∗ , ∞). Then:

(a) For all U ∈ Uβ and x ∈ Rd such that ̺U (x) ≤ β, then
Z T

1 U
lim sup Ex
(3.25)
h̃(Xs , Us ) ds ≤ k0 (1 + β).
t→∞ T
0

(b) ̺ˆ∗ = ̺∗ = ̺˜∗ .
(c) For any β ∈ (̺∗ , ∞), we have UβSM ⊂ USSM .
(d) The set of invariant probability measures Mβ corresponding to controls in UβSM satisfies
Z
h̃(x, v(x))µv (dx) ≤ k0 (1 + β)
∀µv ∈ Mβ .
Rd

ERGODIC CONTROL IN THE HALFIN–WHITT REGIME

25

In particular, UβSM is tight in P(Rd ).
(e) There exists (Ṽ , ̺˜) ∈ C 2 (Rd ) × R+ , with Ṽ inf-compact, such that
(3.26)

min[Lu Ṽ (x) + h̃(x, u)] = ̺˜.
u∈U

Proof. Using Itô’s formula, it follows by (3.24) that

(3.27)

1 U
(E [V(XT ∧τR )] − V(x))
T x
Z T ∧τR

1 U
h(Xs , Us )IHc (Xs , Us ) ds
≤ 1 − Ex
T
0

Z T ∧τR
1 U
+ Ex
r(Xs , Us )IH (Xs , Us ) ds .
T
0

Since V is inf-compact, (3.27) together with (3.23) implies that

Z T
1 U
2
lim sup E
h̃(Xs , Us ) ds
k0 T →∞ T x 0
(3.28)

Z T
1 U
≤ 2 + 2 lim sup Ex
r(Xs , Us ) ds .
T →∞ T
0
Part (a) then follows from (3.28).
Now fix U ∈ Uβ and x ∈ Rd such that ̺U (x) ≤ β. The inequality in (3.25)
U : t ≥ 1}, defined by
implies that the set of mean empirical measures {ζx,t

Z t
1 U
U
IA×B (Xs , Us ) ds
ζx,t(A × B) := Ex
t
0

for any Borel sets A ⊂ Rd and B ⊂ U, is tight. It is the case that any limit
point of the mean empirical measures in P(Rd × U) is an ergodic occupation
measure [1], Lemma 3.4.6. Then in view of Remark 3.6 we obtain
(3.29)

U
π(r) ≤ lim sup ζx,t
(r) ≤ β
t→∞

for some ergodic occupation measure π. Therefore, ̺˜∗ ≤ ̺ˆ∗ . Disintegrating
the measure π as π(dx, du) = v(du|x)µv (dx), we obtain the associated control v ∈ USSM . From ergodic theory [33], we also know that

Z T
1
lim sup Evx
r(Xs , v(Xs )) ds = πv (r)
for almost every x.
T →∞ T
0

It follows that ̺∗ ≤ ̺˜∗ , and since it is clear that ̺ˆ∗ ≤ ̺∗ , equality must hold
among the three quantities.
If v ∈ UβSM , then (3.28) implies that (3.29) holds with U ≡ v and π ≡ πv .
Therefore, parts (c) and (d) follow.

26

A. ARAPOSTATHIS, A. BISWAS AND G. PANG

Existence of (Ṽ , ̺˜), satisfying (3.26), follows from Assumption 3.2 and
[1], Theorem 3.6.6. The inf-compactness of Ṽ follows from the stochastic
representation of Ṽ in [1], Lemma 3.6.9. This proves (e). 
Existence of a stationary Markov control that is optimal is asserted by
the following theorem.
Theorem 3.2. Let G denote the set of ergodic occupation measures corresponding to controls in USSM , and Gβ those corresponding to controls in
UβSM , for β > ̺∗ . Then:
(a) The set Gβ is compact in P(Rd ) for any β > ̺∗ .
(b) There exists v ∈ USM such that ̺v = ̺∗ .

Proof. By Theorem 3.1(d), the set Gβ is tight for any β > ̺∗ . Let
{πn } ⊂ Gβ , for some β > ̺∗ , be any convergent sequence in P(Rd ) such that
πn (r) → ̺∗ as n → ∞ and denote its limit by π∗ . Since G is closed, π∗ ∈ G, and
since the map π → π(r) is lower semi-continuous, it follows that π∗ (r) ≤ ̺∗ .
Therefore, Gβ is closed, and hence compact. Since π(r) ≥ ̺∗ for all π ∈ G,
the equality π∗ (r) = ̺∗ follows. Also v is obtained by disintegrating π∗ . 
Remark 3.7. The reader might have noticed at this point that Assumption 3.1 may be weakened significantly. What is really required is the
existence of an open set Ĥ ⊂ Rd × U and inf-compact functions V ∈ C 2 (Rd )
and h ∈ C(Rd × U), satisfying
(H1) inf {u : (x,u)∈Ĥ} r(x, u) −→ ∞.
(H2)

|x|→∞
u
L V(x) ≤ 1 − h(x, u)IĤc (x, u) + r(x, u)IĤ (x, u)

∀(x, u) ∈ Rd × U.

In (H1), we use the convention that the ‘inf’ of the empty set is +∞. Also
note that (H1) is equivalent to the statement that {(x, u) : r(x, u) ≤ c} ∩ Ĥ is
bounded in Rd × U for all c ∈ R+ . If (H1)–(H2) are met, we define H := Ĥ ∪
{(x, u) ∈ Rd × U : r(x, u) > h(x, u)}, and following the proof of Lemma 3.3, we
assert the existence of an inf-compact h̃ ∈ C(Rd × U) satisfying (3.23). In fact,
throughout the rest of the paper, Assumption 3.1 is not really invoked. We
only use (3.24), the inf-compact function h̃ satisfying (3.23), and, naturally,
Assumption 3.2.
3.5. The HJB equation. For ε > 0, let
rε (x, u) := r(x, u) + εh̃(x, u).
By Theorem 3.1(d), for any π ∈ Gβ , β > ̺∗ , we have the bound
(3.30)

π(rε ) ≤ β + εk0 (1 + β).

ERGODIC CONTROL IN THE HALFIN–WHITT REGIME

27

Therefore, since rε is near-monotone, that is,
lim inf min rε (x, u) > inf π(rε ),
|x|→∞ u∈U

π∈G

there exists πε ∈ arg minπ∈G π(rε ). Let π∗ ∈ G be as in the proof of Theorem 3.2. The sub-optimality of π∗ relative to the running cost rε and (3.30)
imply that
πε (r) ≤ πε (rε )
(3.31)

≤ π∗ (rε )
≤ ̺∗ + εk0 (1 + ̺∗ )

∀ε > 0.

It follows from (3.31) and Theorem 3.1(d) that {πε : ε ∈ (0, 1)} is tight. Since
πε 7→ πε (r) is lower semi-continuous, if π̄ is any limit point of πε as ε ց 0,
then taking limits in (3.31), we obtain
(3.32)

π̄(r) ≤ lim sup πε (r) ≤ ̺∗ .
εց0

Since G is closed, π̄ ∈ G, which implies that π̄(r) ≥ ̺∗ . Therefore, equality
must hold in (3.32), or in other words, π̄ is an optimal ergodic occupation
measure.
Theorem 3.3. There exists a unique function V ε ∈ C 2 (Rd ) with V ε (0) =
0, which is bounded below in Rd , and solves the HJB
(3.33)

min[Lu V ε (x) + rε (x, u)] = ̺ε ,
u∈U

where ̺ε := inf π∈G π(rε ), or in other words, ̺ε is the optimal value of the
ergodic control problem with running cost rε . Also a stationary Markov control vε is optimal for the ergodic control problem relative to rε if and only if
it satisfies
(3.34) Hε (x, ∇V ε (x)) = b(x, vε (x)) · ∇V ε (x) + rε (x, vε (x))
where
(3.35)

Hε (x, p) := min[b(x, u) · p + rε (x, u)].
u∈U

Moreover:
(a) for every R > 0, there exists kR such that
(3.36)

osc V ε ≤ kR ;
BR

a.e. in Rd ,

28

A. ARAPOSTATHIS, A. BISWAS AND G. PANG

(b) if vε is a measurable a.e. selector from the minimizer of the Hamiltonian in (3.35), that is, if it satisfies (3.33), then for any δ > 0,

Z τ̆δ
V ε (x) ≥ Evxε
(rε (Xs , vε (Xs )) − ̺ε ) ds + inf V ε ;
Bδ

0

(c) for any stationary control v ∈ USSM and for any δ > 0,

Z τ̆δ
ε
v
ε
V (x) ≤ Ex
(rε (Xs , v(Xs )) − ̺ε ) ds + V (Xτ̆δ ) ,
0

where τ̆δ is hitting time to the ball Bδ .
Theorem 3.4.
following hold:

Let V ε , ̺ε , and vε , for ε > 0, be as in Theorem 3.3. The

(a) The function V ε converges to some V∗ ∈ C 2 (Rd ), uniformly on compact sets, and ̺ε → ̺∗ , as ε ց 0, and V∗ satisfies
min[Lu V∗ (x) + r(x, u)] = ̺∗ .

(3.37)

u∈U

Also, any limit point v∗ (in the topology of Markov controls) as ε ց 0 of the
set {vε } satisfies
Lv∗ V∗ (x) + r(x, v∗ (x)) = ̺∗

a.e. in Rd .

(b) A stationary Markov control v is optimal for the ergodic control problem relative to r if and only if it satisfies
a.e. in Rd ,

(3.38) H(x, ∇V∗ (x)) = b(x, v(x)) · ∇V∗ (x) + r(x, v(x))
where
H(x, p) := min[b(x, u) · p + r(x, u)].
u∈U

Moreover, for an optimal v ∈ USM , we have

Z T
1 v
r(Xs , v(Xs )) ds = ̺∗
lim Ex
T →∞ T
0

∀x ∈ Rd .

(c) The function V∗ has the stochastic representation
Z τ̆δ

v
Ex
V∗ (x) = lim S inf
(r(Xs , v(Xs )) − ̺∗ ) ds
δց0 v∈

(3.39)

= lim

δց0

Ev̄x

β
β>0 USM

Z

0

τ̆δ
0

(r(Xs , v∗ (Xs )) − ̺∗ ) ds

for any v̄ ∈ USM that satisfies (3.38).



ERGODIC CONTROL IN THE HALFIN–WHITT REGIME

29

(d) If U is a convex set, u 7→ {b(x, u) · p + r(x, u)} is strictly convex whenever it is not constant, and u 7→ h̃(x, u) is strictly convex for all x, then any
measurable minimizer of (3.33) converges pointwise, and thus in USM , to the
minimizer of (3.37).
Theorem 3.4 guarantees the existence of an optimal stable control, which
is made precise by (3.38), for the ergodic diffusion control problem with the
running cost function r. Moreover, under the convexity property in part (d),
the optimal stable control can be obtained as a pointwise limit from the
minimizing selector of (3.33). For instance, if we let
+

r(x, u) = (e · x)

d
X

hi um
i ,

m > 1,

i=1

then by choosing h and h̃ + |u|2 as in Proposition 3.1, we see that the
approximate value function V ε and approximate control vε converge to the
desired optimal value function V∗ and optimal control v∗ , respectively.
Concerning the uniqueness of the solution to the HJB equation in (3.37),
recall that in the near-monotone case the existing uniqueness results are as
follows: there exists a unique solution pair (V, ̺) of (3.37) with V in the class
of functions C 2 (Rd ) which are bounded below in Rd . Moreover, it satisfies
V (0) = 0 and ̺ ≤ ̺∗ . If the restriction ̺ ≤ ̺∗ is removed, then in general,
there are multiple solutions. Since in our model r is not near-monotone in
Rd , the function V∗ is not, in general, bounded below. However, as we show
later in Lemma 3.10 the negative part of V∗ grows slower than V, that is,
it holds that V∗− ∈ o(V), with o(·) as defined in Section 1.3. Therefore, the
second part of the theorem that follows may be viewed as an extension of the
well-known uniqueness results that apply to ergodic control problems with
near-monotone running cost. The third part of the theorem resembles the
hypotheses of uniqueness that apply to problems under a blanket stability
hypothesis.
Theorem 3.5.
(3.40)

Let (V̂ , ̺ˆ) be a solution of
min[Lu V̂ (x) + r(x, u)] = ̺ˆ,
u∈U

such that V̂ − ∈ o(V) and V̂ (0) = 0. Then the following hold:
(a) Any measurable selector v̂ from the minimizer of the associated Hamiltonian in (3.38) is in USSM and ̺v̂ < ∞.
(b) If ̺ˆ ≤ ̺∗ then necessarily ̺ˆ = ̺∗ and V̂ = V∗ .
(c) If V̂ ∈ O(minu∈U h̃(·, u)), then ̺ˆ = ̺∗ and V̂ = V∗ .

30

A. ARAPOSTATHIS, A. BISWAS AND G. PANG

Applying these results to the multi-class queueing diffusion model, we
have the following corollary.
Corollary 3.1. For the queueing diffusion model with controlled dynamics given by (3.10), drift given by (3.9), and running cost as in (3.11),
there exists a unique solution V , satisfying V (0) = 0, to the associated HJB
in the class of functions C 2 (Rd ) ∩ O(|x|m ), whose negative part is in o(|x|m ).
This solution agrees with V∗ in Theorem 3.4.
Proof. Existence of a solution V follows by Theorem 3.4. Select V ∼
|x|m as in the proof of Proposition 3.1. That the solution V is in the stated
class then follows by Lemma 3.10 and Corollary 4.1 that appear later in
Sections 3.6 and 4, respectively. With h ∼ |x|m as in the proof of Proposition 3.1, it follows that minu∈U h̃(x, u) ∈ O(|x|m ). Therefore, uniqueness
follows by Theorem 3.5. 
We can also obtain the HJB equation in (3.37) via the traditional vanishing discount approach as the following theorem asserts. Similar results
are shown for a one-dimensional degenerate ergodic diffusion control problem in [29] and certain multi-dimensional ergodic diffusion control problems
(allowing degeneracy and spatial periodicity) in [2].
Theorem 3.6.

Let V∗ and ̺∗ be as in Theorem 3.4. For α > 0, we define

Z ∞
−αt
U
e r(Xt , Ut ) dt .
Vα (x) := inf Ex
U ∈U

0

The function Vα − Vα (0) converges, as α ց 0, to V∗ , uniformly on compact
subsets of Rd . Moreover, αVα (0) → ̺∗ , as α ց 0.
The proofs of the Theorems 3.3–3.6 are given in Section 3.6. The following
result, which follows directly from (3.31), provides a way to find ε-optimal
controls.
Proposition 3.2. Let {vε } be the minimizing selector from Theorem 3.3
and {µvε } be the corresponding invariant probability measures. Then almost
surely for all x ∈ Rd ,
 Z
Z T
1 vε
lim Ex
r(x, vε (x))µvε (dx)
r(Xs , vε (Xs )) ds =
T →∞ T
Rd
0
≤ ̺∗ + εk0 (1 + ̺∗ ).

ERGODIC CONTROL IN THE HALFIN–WHITT REGIME

31

3.6. Technical proofs. Recall that rε (x, u) = r(x, u) + εh̃(x, u), with h̃ as
in Lemma 3.3. We need the following lemma.
For α > 0 and ε ≥ 0, we define

Z ∞
ε
U
−αt
Vα (x) := inf Ex
(3.41)
e rε (Xt , Ut ) dt ,
U ∈U

0

where we set r0 ≡ r. Clearly, when ε = 0, we have Vα0 ≡ Vα .
We quote the following result from [1], Theorem 3.5.6, Remark 3.5.8.

Lemma 3.4. Provided ε > 0, then Vαε defined above is in C 2 (Rd ) and is
the minimal nonnegative solution of
min[Lu Vαε (x) + rε (x, u)] = αVαε (x).
u∈U

The HJB in Lemma 3.4 is similar to the equation in [7], Theorem 3, which
concerns the characterization of the discounted control problem.
Lemma 3.5. Let u be any precise Markov control and Lu be the corresponding generator. Let ϕ ∈ C 2 (Rd ) be a nonnegative solution of
Lu ϕ − αϕ = g,

d
where g ∈ L∞
loc (R ). Let κ : R+ → R+ be any nondecreasing function such that
kgkL∞ (BR ) ≤ κ(R) for all R > 0. Then for any R > 0 there exists a constant
D(R) which depends on κ(4R), but not on u, or ϕ, such that


osc ϕ ≤ D(R) 1 + α inf ϕ .
BR

B4R

Proof. Define g̃ := α(g − 2κ(4R)) and ϕ̃ := 2κ(4R) + αϕ. Then g̃ ≤ 0
in B4R and ϕ̃ solves
Lu ϕ̃ − αϕ̃ = g̃

in B4R .

Also
kg̃kL∞ (B4R ) ≤ α(2κ(4R) + kgkL∞ (B4R ) )
≤ 3α(2κ(4R) − kgkL∞ (B4R ) )
= 3 inf |g̃|
B4R

≤ 3|B4R |−1 kg̃kL1 (B4R ) .
Hence by [1], Theorem A.2.13, there exists a positive constant C̃H such that
sup ϕ̃(x) ≤ C̃H inf ϕ̃(x),

x∈B3R

x∈B3R

32

A. ARAPOSTATHIS, A. BISWAS AND G. PANG

implying that


α sup ϕ(x) ≤ C̃H 2κ(4R) + inf αϕ(x) .

(3.42)

x∈B3R

x∈B3R

We next consider the solution of
Lu ψ = 0

in B3R ,

ψ=ϕ

on ∂B3R .

Then
Lu (ϕ − ψ) = αϕ + g

in B3R .

If ϕ(x̂) = inf x∈B3R ϕ(x), then applying the maximum principle ([1], Theorem A.2.1, [18]) it follows from (3.42) that
sup |ϕ − ψ| ≤ Ĉ(1 + αϕ(x̂)).

(3.43)

x∈B3R

Again ψ attains its minimum at the boundary ([1], Theorem A.2.3, [18]).
Therefore, ψ − ϕ(x̂) is a nonnegative function, and hence by the Harnack
inequality, there exists a constant CH > 0 such that
ψ(x) − ϕ(x̂) ≤ CH (ψ(x̂) − ϕ(x̂)) ≤ CH Ĉ(1 + αϕ(x̂))

∀x ∈ B2R .

Thus, combining the above display with (3.43) we obtain
osc ϕ ≤ sup(ϕ − ψ) + sup ψ − ϕ(x̂) ≤ Ĉ(1 + CH )(1 + αϕ(x̂)).

B2R

B2R

B2R

This completes the proof. 
Lemma 3.6. Let Vαε be as in Lemma 3.4. Then for any R > 0, there
exists a constant kR > 0 such that
osc Vαε ≤ kR

for all α ∈ (0, 1] and ε ∈ [0, 1].

BR

Proof. Recall that µu0 is the stationary probability distribution for the
process under the control u0 ∈ USSM in Lemma 3.1. Since u0 is sub-optimal
for the α-discounted criterion in (3.41), and Vαε is nonnegative, then for any
ball BR , using Fubini’s theorem, we obtain
Z
ε
Vαε (x)µu0 (dx)
µu0 (BR ) inf Vα ≤
BR

Rd

≤

Z

Rd

Eux0

Z

∞

0

−αt

e


rε (Xt , u0 (Xt )) dt µu0 (dx)

1
µu (rε )
α 0
1
≤ (η + εk0 (1 + η)),
α
=

ERGODIC CONTROL IN THE HALFIN–WHITT REGIME

33

where for the last inequality we used Lemma 3.2 and Theorem 3.1(a).
Therefore, we have the estimate
α inf Vαε ≤
BR

η + εk0 (1 + η)
.
µu0 (BR )

The result then follows by Lemma 3.5. 
We continue with the proof of Theorem 3.3.
Proof of Theorem 3.3. Consider the function V̄αε := Vαε − Vαε (0). In
view of Lemma 3.5 and Lemma 3.6, we see that V̄αε is locally bounded uniformly in α ∈ (0, 1] and ε ∈ (0, 1]. Therefore, by standard elliptic theory, V̄αε
and its first- and second-order partial derivatives are uniformly bounded in
Lp (B), for any p > 1, in any bounded ball B ⊂ Rd , that is, for some constant
CB depending on B and p, kV̄αε kW2,p (B) ≤ CB ([18], Theorem 9.11, page 117).
Therefore, we can extract a subsequence along which V̄αε converges. Then
the result follows from Theorems 3.6.6, Lemma 3.6.9 and Theorem 3.6.10 in
[1]. The proof of (3.36) follows from Lemma 3.5 and Lemma 3.6. 
Remark 3.8. In the proof of the following lemma, and elsewhere in the
paper, we use the fact that if U ⊂ USSM is a any set of controls such that
the corresponding set {µv : v ∈ U } ⊂ M of invariant probability measures is
tight then the map v 7→ πv from the closure of U to P(Rd × U) is continuous,
and so is the map v 7→ µv . In fact, the latter is continuous under the total
variation norm topology [1], Lemma 3.2.6. We also recall that G and M are
closed and convex subsets of P(Rd × U) and P(Rd ). Therefore,{πv : v ∈ Ū } is
compact in G. Note also that since U is compact, tightness of a set of invariant
probability measures is equivalent to tightness of the corresponding set of
ergodic occupation measures.
Lemma 3.7. If {vε : ε ∈ (0, 1]} is a collection of measurable selectors from
the minimizer of (3.33), then the corresponding invariant probability measures {µε : ε ∈ (0, 1]} are tight. Moreover, if vεn → v∗ along some subsequence
εn ց 0, then the following hold:
(a) µεn → µv∗ as εn ց 0,
(b) Rv∗ is a stable Markov control,
(c) Rd r(x, v∗ (x))µv∗ (dx) = limεց0 ̺ε = ̺∗ .

Proof. By (3.25) and (3.31), the set of ergodic occupation measures
corresponding to {vε : ε ∈ (0, 1]} is tight. By Remark 3.8, the same applies
to the set {µε : ε ∈ (0, 1]}, and also part (a) holds. Part (b) follows from
the equivalence of the existence of an invariant probability measure for a

34

A. ARAPOSTATHIS, A. BISWAS AND G. PANG

controlled diffusion and the stability of the associated stationary Markov
control (see [1], Theorem 2.6.10). Part (c) then follows since equality holds
in (3.32). 
We continue with the following lemma that asserts the continuity of the
mean hitting time of a ball with respect to the stable Markov controls.
Lemma 3.8. Let {vn : n ∈ N} ⊂ UβSM , for some β > 0, be a collection
of Markov controls such that vn → v̂ in the topology of Markov controls as
n → ∞. Let µn , µ̂ be the invariant probability measures corresponding to the
controls vn , v̂, respectively. Then for any δ > 0, it holds that
Evxn [τ̆δ ] −→ Ev̂x [τ̆δ ]

∀x ∈ Bδc .

n→∞

Proof. Define H(x) := minu∈U h̃(x, u). It is easy to see that H is infcompact and locally Lipschitz. Therefore, by Theorem 3.1(d) we have
sup µn (H) ≤ k0 (1 + β),

n∈N

and since µn → µ̂, we also have µ̂(H) ≤ k0 (1 + β). Then by [1], Lemma 3.3.4,
we obtain

Z τ̆δ

Z τ̆δ
sup Evxn
H(Xs ) ds + Ev̂x
(3.44)
H(Xs ) ds < ∞.
n∈N

0

0

Let R be a positive number greater than |x|. Then by (3.44), there exists a
positive k such that

Z τ̆δ

Z τ̆δ
1
k
Evx
I{H>R} (Xs ) ds ≤ Evx
H(Xs )I{H>R} (Xs ) ds ≤
R
R
0
0
for v ∈ {{vn }, v̂}. From this assertion and (3.44), we see that

Z τ̆δ
v
sup Ex
I{H>R} (Xs ) ds −→ 0.
v∈{{vn },v̂}

R→∞

0

Therefore, in order to prove the lemma it is enough to show that, for any
R > 0, we have
Z τ̆δ

Z τ̆δ

vn
v̂
Ex
I{H≤R} (Xs ) ds −→ Ex
I{H≤R} (Xs ) ds .
0

n→∞

0

But this follows from [1], Lemma 2.6.13(iii). 

ERGODIC CONTROL IN THE HALFIN–WHITT REGIME

35

Lemma 3.9. Let (V ε , ̺ε ) be as in Theorem 3.3, and vε satisfy (3.35).
There exists a subsequence εn ց 0, such that V εn converges to some V∗ ∈
C 2 (Rd ), uniformly on compact sets, and V∗ satisfies
min[Lu V∗ (x) + r(x, u)] = ̺∗ .

(3.45)

u∈U

Also, any limit point v∗ (in the topology of Markov controls) of the set {vε },
as ε ց 0, satisfies
(3.46)

Lv∗ V∗ (x) + r(x, v∗ (x)) = ̺∗

a.e. in Rd .

Moreover, V∗ admits the stochastic representation

Z τ̆δ
v
V∗ (x) = S inf
Ex
(r(Xs , v(Xs )) − ̺∗ ) ds + V∗ (Xτ̆δ )
v∈

(3.47)

= Evx∗

β
β>0 USM

Z

0

τ̆δ

0


(r(Xs , v∗ (Xs )) − ̺∗ ) ds + V∗ (Xτ̆δ ) .

It follows that V∗ is the unique limit point of V ε as ε ց 0.

Proof. From (3.36), we see that the family {V ε : ε ∈ (0, 1]} is uniformly
locally bounded. Hence, applying the theory of elliptic PDE, it follows that
d
{V ε : ε ∈ (0, 1]} is uniformly bounded in W2,p
loc (R ) for p > d. Consequently,
1,γ
ε
{V : ε ∈ (0, 1]} is uniformly bounded in Cloc for some γ > 0. Therefore, along
some subsequence εn ց 0, V εn → V∗ ∈ W2,p ∩ C 1,γ , as n → ∞, uniformly on
compact sets. Also, limεց0 ̺ε = ̺∗ by Lemma 3.6(c). Therefore, passing to
the limit we obtain the HJB equation in (3.45). It is straightforward to verify
that (3.46) holds [1], Lemma 2.4.3.
By Theorem 3.3(c), taking limits as ε ց 0, we obtain

Z τ̆δ
Evx
(3.48) V∗ (x) ≤ S inf
(r(Xs , v(Xs )) − ̺∗ ) ds + V∗ (Xτ̆δ ) .
v∈

β
β>0 USM

0

Also by Theorem 3.3(b) we have the bound
V ε (x) ≥ −̺ε Evxε [τ̆δ ] + inf V ε .
Bδ

Using Lemma 3.8 and taking limits as εn ց 0, we obtain the lower bound
(3.49)

V∗ (x) ≥ −̺∗ Evx∗ [τ̆δ ] + inf V∗ .
Bδ

By Lemma 3.7(c) and Theorem 3.1(d), v∗ ∈ USSM , and πv∗ (h̃) ≤ k0 (1 + ̺∗ ).
Define
Z τ̆δ

v∗
ϕ(x) := Ex
(3.50)
h̃(Xs , v∗ (Xs )) ds .
0

36

A. ARAPOSTATHIS, A. BISWAS AND G. PANG

For |x| > δ, we have
Evx∗ [I{τR <τ̆δ } ϕ(XτR )] = Evx∗



I{τR <τ̆δ }

Z

τ̆δ
τR ∧τ̆δ


h̃(Xs , v∗ (Xs )) ds .

Therefore, by the dominated convergence theorem and the fact that ϕ(x) <
∞ we obtain
Evx∗ [ϕ(XτR )I{τR <τ̆δ } ] −→ 0.
Rր∞

By (3.48) and (3.49), we have |V∗ | ∈ O(ϕ). Thus (3.49) and (3.50) imply that
lim inf Evx∗ [V∗ (XτR )I{τR <τ̆δ } ] = 0,
Rր∞

and thus
lim inf Evx∗ [V∗ (XτR ∧τ̆δ )] = Evx∗ [V∗ (Xτ̆δ )].

(3.51)

Rր∞

Applying Itô’s formula to (3.46), we obtain
Z τ̆δ ∧τR

v∗
(3.52) V∗ (x) = Ex
(r(Xs , v∗ (Xs )) − ̺∗ ) ds + V∗ (Xτ̆δ ∧τR ) .
0

Taking limits as R → ∞, and using the dominated convergence theorem, we
obtain (3.47) from (3.48). 
Recall the definition of o(·) from Section 1.3. We need the following
lemma.
Lemma 3.10.

Let V∗ be as in Lemma 3.9. It holds that V∗− ∈ o(V).

Proof. Let v∗ be as in Lemma 3.9. Applying Itô’s formula to (3.24)
with u ≡ v∗ we obtain

Z τ̆δ
v∗
Ex
h(Xs , v∗ (Xs ))IHc (Xs , v∗ (Xs )) ds

(3.53)

0

≤ Evx∗

Z

τ̆δ
0



r(Xs , v∗ (Xs ))IH (Xs , v∗ (Xs )) ds + Evx∗ [τ̆δ ] + V(x).

Therefore, adding the term

Z τ̆δ
v∗
Ex
r(Xs , v∗ (Xs ))IH (Xs , v∗ (Xs )) ds − (1 + 2̺∗ )Evx∗ [τ̆δ ]
0

ERGODIC CONTROL IN THE HALFIN–WHITT REGIME

37

to both sides of (3.53) and using the stochastic representation of V∗ we
obtain
Z τ̆δ

−1 v∗
F (x) := 2k0 Ex
h̃(Xs , v∗ (Xs )) ds − 2(1 + ̺∗ )Evx∗ [τ̆δ ]

(3.54)

0

≤ 2V∗ (x) + V(x) − 2 inf V∗ .
Bδ

From the stochastic representation of V∗ we have V∗− (x) ≤ ̺∗ Evx∗ [τ̆δ ]−inf Bδ V∗ .
For any R > δ, we have
Z τ̆δ
 

v∗
c
(3.55) Ex
h̃
Ex [τ̆R ]
∀x ∈ BR
.
h̃(Xs , v∗ (Xs )) ds ≥ inf
c
BR ×U

0

It is also straightforward to show that lim|x|→∞ EExx[τ̆[τ̆Rδ ]] = 1. Therefore, since

h̃ is inf-compact, it follows by (3.54) and (3.55) that the map x 7→ Evx∗ [τ̆δ ]
is in o(F ), which implies that V∗− ∈ o(F ). On the other hand, by (3.54) we
obtain F (x) ≤ V(x) − 2 supBδ V∗ for all x such that V∗ (x) ≤ 0, which implies
that the restriction of F to the support of V∗− is in O(V). It follows that
V∗− ∈ o(V). 
We next prove Theorem 3.4.
Proof of Theorem 3.4. Part (a) is contained in Lemma 3.9.
To prove part (b), let v̄ be any control satisfying (3.38). By Lemma 3.10
the map V + 2V∗ is inf-compact and by Theorem 3.4 and (3.24) it satisfies
Lv̄ (V + 2V∗ )(x) ≤ 1 + 2̺∗ − r(x, v̄(x)) − h(x, v̄(x))IHc (x, v̄(x))
≤ 2 + 2̺∗ − 2k0−1 h̃(x, v̄(x))

∀x ∈ Rd .

This implies that v̄ ∈ USSM . Applying Itô’s formula, we obtain

Z T
1 v̄
lim sup Ex
(3.56)
h̃(Xs , v̄(Xs )) ds ≤ k0 (1 + ̺∗ ).
T →∞ T
0
Therefore, πv̄ (h̃) < ∞. By (3.24), we have

Z t
v̄
v̄
Ex [V(Xt )] ≤ V(x) + t + Ex
r(Xs , v̄(Xs )) ds ,
0

and since r ≤ h̃, this implies by (3.56) that
1
(3.57)
lim sup Ev̄x [V(XT )] ≤ 1 + k0 (1 + ̺∗ ).
T →∞ T
Since V∗− ∈ o(V), it follows by (3.57) that
1
lim sup Ev̄x [V∗− (XT )] = 0.
T →∞ T

38

A. ARAPOSTATHIS, A. BISWAS AND G. PANG

Therefore, by Itô’s formula, we deduce from (3.37) that

Z T
1 v̄
(3.58)
r(Xs , v̄(Xs )) ds ≤ ̺∗ .
lim sup Ex
T →∞ T
0
On the other hand, since the only limit point of the mean empirical measures
v̄ , as t → ∞, is π , and π (r) = ̺ , then in view of Remark 3.6, we obtain
ζx,t
v̄
v̄
∗
v̄ (r) ≥ ̺ . This proves that equality holds in (3.58) and that
lim inf t→∞ ζx,t
∗
the “lim sup” may be replaced with “lim.”
Conversely, suppose v ∈ USM is optimal but does not satisfy (3.38). Then
there exists R > 0 and a nontrivial nonnegative f ∈ L∞ (BR ) such that
fε (x) := IBR (x)(Lv V ε (x) + rε (x, v(x)) − ̺ε )

converges to f , weakly in L1 (BR ), along some subsequence ε ց 0. By applying Itô’s formula to (3.33), we obtain

Z T ∧τR
1 v
1 v ε
ε
(E [V (XT ∧τR )] − V (x)) + Ex
rε (Xs , v(Xs )) ds
T x
T
0
(3.59)
Z T ∧τR

1 v
fε (Xs , v(Xs )) ds .
≥ ̺ε + Ex
T
0
Define, for some δ > 0,
G(x) := Evx

Z

0

τ̆δ


rε (Xs , v(Xs )) ds .

Since V is bounded from below, by Theorem 3.3(c) we have V ε ∈ O(G).
Invoking [1], Corollary 3.7.3, we obtain
ε

1 v ε
Ex [V (XT )] = 0,
T →∞ T
lim

and
lim Evx [V ε (XT ∧τR )] = Evx [V ε (XT )].

R→∞

Therefore, taking limits in (3.59), first as R ր ∞, and then as T → ∞, we
obtain
(3.60)

πv (rε ) ≥ ̺ε + πv (fε ).

Taking limits as ε ց 0 in (3.60), since µv has a strictly positive density in
BR , we obtain
πv (r) ≥ ̺∗ + πv (f ) > ̺∗ ,
which is a contradiction. This completes the proof of part (b).

ERGODIC CONTROL IN THE HALFIN–WHITT REGIME

39

The first equality (3.39) follows by Lemma 3.9, taking limits as δ ց 0.
To show that the second equality holds for any optimal control, suppose v̄
satisfies (3.38). By (3.24) we have, for δ > 0 and |x| > δ,

Z τR ∧τ̆δ
(1 + r(Xs , v̄(Xs ))) ds .
Ev̄x [V(XτR )I{τR <τ̆δ } ] ≤ V(x) + sup V − + Ev̄x
Bδ

0

It follows that (see [1], Lemma 3.3.4)
lim sup Ev̄x [V(XτR )I{τR <τ̆δ } ] < ∞,
R→∞

and since V∗− ∈ o(V) we must have

lim sup Ev̄x [V∗− (XτR )I{τR <τ̆δ } ] = 0.
R→∞

By the first equality in (3.47), we obtain V∗+ ∈ O(ϕ), with ϕ as defined in
(3.50) with v∗ replaced by v̄. Thus, in analogy to (3.51), we obtain
lim inf Ev̄x [V∗ (XτR ∧τ̆δ )] = Ev̄x [V∗ (Xτ̆δ )].
Rր∞

The rest follows as in the proof of Lemma 3.9 via (3.52).
We next prove part (d). We assume that U is a convex set and that
c(x, u, p) := {b(x, u) · p + r(x, u)}
is strictly convex in u if it is not identically a constant for fixed x and p. We
fix some point ū ∈ U. Define
B := {x ∈ Rd : c(x, ·, p) = c(x, ū, p) for all p}.

It is easy to see that on B both b and r do not depend on u. It is also easy
to check that B is a closed set. Let (V∗ , v∗ ) be the limit of (V ε , vε ), where
V∗ is the solution to (3.37) and v∗ is the corresponding limit of vε . We have
already shown that v∗ is a stable Markov control. We next show that it
is, in fact, a precise Markov control. By our assumption, vε is the unique
minimizing selector in (3.34) and, moreover, vε is continuous in x. By the
definition of rε it is clear that the restriction of vε to B does not depend on
ε. Let vε (x) = v ′ (x) on B. Using the strict convexity property of c(x, ·, ∇V∗ )
it is easy to verify that vε converges to the unique minimizer of (3.37) on
B c . In fact, since B c is open, then for any sequence xε → x ∈ B c it holds that
vε (xε ) → v∗ (x). This follows from the definition of the minimizer and the
uniform convergence of ∇V ε to ∇V∗ . Therefore, we see that v∗ is a precise
Markov control, v∗ = v ′ on B, and vε → v∗ pointwise as ε → 0. It is also easy
to check that pointwise convergence implies convergence in the topology of
Markov controls. 
We now embark on the proof of Theorem 3.5.

40

A. ARAPOSTATHIS, A. BISWAS AND G. PANG

Proof of Theorem 3.5. The hypothesis that V̂ − ∈ o(V) implies that
the map V + 2V̂ is inf-compact. Also by (3.24) and (3.40), it satisfies
Lv̂ (V + 2V̂ )(x) ≤ 1 + 2ˆ
̺ − r(x, v̂(x)) − h(x, v̂(x))IHc (x, v̂(x))
≤ 2 + 2ˆ
̺ − 2k0−1 h̃(x, v̂(x))

∀x ∈ Rd .

R
Therefore, h̃(x, v̂(x)) dπv̂ < ∞ from which it follows that ̺v̂ < ∞. This
proves part (a).
By (3.24), we have

Z t
v̂
v̂
r(Xs , v̂(Xs )) ds ,
Ex [V(Xt )] ≤ V(x) + t + Ex
0

and since ̺v̂ < ∞, this implies that
1
lim sup Ev̂x [V(XT )] ≤ 1 + ̺v̂ .
(3.61)
T →∞ T
Since V̂ − ∈ o(V), it follows by (3.61) that
lim sup
T →∞

1 v̂ −
E [V̂ (XT )] = 0.
T x

Therefore, by Itô’s formula, we deduce from (3.40) that

Z T

1 v̂
1 v̂ +
E [V̂ (XT )] + Ex
r(Xs , v̂(Xs )) ds = ̺ˆ.
lim sup
T x
T
T →∞
0

This implies that ̺v̂ ≤ ̺ˆ and since by hypothesis ̺ˆ ≤ ̺∗ we must have ̺ˆ = ̺∗ .
Again by (3.24), we have
Z τR ∧τ̆δ

v̂
−
v̂
Ex [V(XτR )I{τR <τ̆δ } ] ≤ V(x) + sup V + Ex
(1 + r(Xs , v̂(Xs ))) ds .
Bδ

0

It follows by [1], Lemma 3.3.4, that
lim sup Ev̂x [V(XτR )I{τR <τ̆δ } ] < ∞,
R→∞

and since V̂ − ∈ o(V) we must have
(3.62)

lim sup Ev̂x [V̂ − (XτR )I{τR <τ̆δ } ] = 0.
R→∞

Using (3.62) and following the steps in the proof of the second equality in
(3.47), we obtain
Z τ̆δ

v̂
V̂ (x) ≥ Ex
(r(Xs , v̂(Xs )) − ̺∗ ) ds + inf V̂
Bδ

0

≥ V∗ (x) − sup V∗ + inf V̂ .
Bδ

Bδ

41

ERGODIC CONTROL IN THE HALFIN–WHITT REGIME

Taking limits as δ ց 0, we have V∗ ≤ V̂ . Since Lv̂ (V∗ − V̂ ) ≥ 0 and V∗ (0) =
V̂ (0), we must have V̂ = V∗ on Rd , and the proof of part (b) is complete.
R To prove part (c) note that by part (a) we haveR ̺v̂ < ∞. Therefore,
h̃ dπv̂ ≤ ∞ by Theorem 3.1(a), which implies that |V̂ | dµv̂ ≤ ∞ by the
hypothesis. Therefore, Ev̂x (|V̂ (Xt )|) converges as t → ∞ by [23], Proposition 2.6, which of course implies that 1t Ev̂x (|V̂ (Xt )|) tends to 0 as t → ∞.
Similarly, we deduce that 1t Evx∗ (|V̂ (Xt )|) as t → ∞. Applying Itô’s formula
to (3.40), with u ≡ v∗ , we obtain ̺ˆ ≤ ̺∗ . Another application with u ≡ v̂
results in ̺ˆ = ̺v̂ . Therefore, ̺ˆ = ̺∗ . The result then follows by part (b). 
We finish this section with the proof of Theorem 3.6.
Proof of Theorem 3.6. We first show that limαց0 αVα (0) = ̺∗ . Let
Ṽ(t, x) := e−αt V(x), and τn (t) := τn ∧ t. Applying Itô’s formula to (3.24), we
obtain

Z τn (t)
U
U
Ex [Ṽ(τn (t), Xτn (t) )] ≤ V(x) − Ex
αṼ(s, Xs ) ds
0

It follows that
Z
U
Ex

(3.63)

τn (t)

−αs

e
0

≤

+ EU
x

Z

+ EU
x

Z

τn (t)

−αs

e

0
τn (t)

−αs

e

0

(1 − h(Xs , Us ))IHc (Xs , Us ) ds


(1 + r(Xs , Us ))IH (Xs , Us ) ds .

h(Xs , Us )IHc (Xs , Us ) ds

1
+ V(x) + EU
x
α

Z

τn (t)
0






e−αs r(Xs , Us )IH (Xs , Us ) ds .

Taking limits first as n ր ∞ and then as t ր ∞ in (3.63), and evaluating U
at an optimal α-discounted control vα∗ , relative to r we obtain the estimate,
using also (3.23),

Z ∞
2
∗
e−αs h̃(Xs , vα∗ (Xs )) ds ≤ + V(x) + 2Vα (x).
(3.64) 2k0−1 Exvα
α
0
By (3.23) and (3.64), it follows that
Z
∗
ε
vα
Vα (x) ≤ Vα (x) ≤ Ex

0

∞

−αs

e

rε (Xs , vα∗ (Xs )) ds

≤ Vα (x) + εk0 (α−1 + V(x) + Vα (x)).



42

A. ARAPOSTATHIS, A. BISWAS AND G. PANG

Multiplying by α and taking limits as α ց 0 we obtain
lim sup αVα (0) ≤ ̺ε ≤ (1 + εk0 ) lim sup αVα (0) + εk0 .
αց0

αց0

The same inequalities hold for the “lim inf.” Therefore, limαց0 αVα (0) = ̺∗ .
Let
Ṽ := lim (Vα − Vα (0)).
αց0

(Note that a similar result as Lemma 3.5 holds.) Then Ṽ satisfies

Z τ̆δ
[ β
v
Ṽ (x) ≤ lim Ex
(r(Xs , v(Xs )) − ̺∗ ) ds
∀v ∈
USM .
δց0

0

β>0

This can be obtained without the near-monotone assumption on the running
cost; see, for example, [1], Lemma 3.6.9 or Lemma 3.7.8. It follows from
(3.39) that Ṽ ≤ V∗ . On the other hand, since Lv∗ (Ṽ − V∗ ) ≥ 0, and Ṽ (0) =
V∗ (0), we must have Ṽ = V∗ by the strong maximum principle. 
4. Approximation via spatial truncations. We introduce an approximation technique which is in turn used to prove the asymptotic convergence
results in Section 5.
Let v0 ∈ USSM be any control such that πv0 (r) < ∞. We fix the control v0
on the complement of the ball B̄l and leave the parameter u free inside. In
other words, for each l ∈ N we define

b(x, u),
if (x, u) ∈ B̄l × U,
bl (x, u) :=
b(x, v0 (x)),
otherwise,

r(x, u),
if (x, u) ∈ B̄l × U,
rl (x, u) :=
r(x, v0 (x)),
otherwise.

We consider the family of controlled diffusions, parameterized by l ∈ N, given
by
(4.1)

dXt = bl (Xt , Ut ) dt + σ(Xt ) dWt ,

with associated running costs rl (x, u). We denote by USM (l, v0 ) the subset of USM consisting of those controls v which agree with v0 on B̄lc . Let
η0 := πv0 (r). It is well known that there exists a nonnegative solution ϕ0 ∈
d
W2,p
loc (R ), for any p > d, to the Poisson equation (see [1], Lemma 3.7.8(ii))
Lv0 ϕ0 (x) = η0 − h̃(x, v0 (x))

x ∈ Rd ,

which is inf-compact, and satisfies, for all δ > 0,

Z τ̆δ
v0
ϕ0 (x) = Ex
(h̃(Xs , v0 (Xs )) − η0 ) ds + ϕ0 (Xτ̆δ )
0

∀x ∈ Rd .

ERGODIC CONTROL IN THE HALFIN–WHITT REGIME

43

We recall the Lyapunov function V from Assumption 3.1. We have the
following theorem.
Theorem 4.1. Let Assumptions 3.1 and 3.2 hold. Then for each l ∈ N
d
l
there exists a solution V l in W2,p
loc (R ), for any p > d, with V (0) = 0, of the
HJB equation
min[Lul V l (x) + rl (x, u)] = ̺l ,

(4.2)

u∈U

Lul

where
is the elliptic differential operator corresponding to the diffusion
in (4.1). Moreover, the following hold:
(i)
(ii)
2ϕ0 (x)
(iii)
(iv)

̺l is nonincreasing in l;
there exists a constant C0 , independent of l, such that V l (x) ≤ C0 +
for all l ∈ N;
(V l )− ∈ o(V + ϕ0 ) uniformly over l ∈ N;
the restriction of V l on Bl is in C 2 .

Proof. As earlier, we can show that

Z ∞
l
U
−αs
Vα (x) := inf Ex
e
rl (Xs , Us ) ds
U ∈U

0

is the minimal nonnegative solution to
(4.3)

min[Lul Vαl (x) + rl (x, u)] = αVαl (x),
u∈U

d
and Vαl ∈ W2,p
loc (R ), p > d. Moreover, any measurable selector from the minimizer in (4.3) is an optimal control. A similar estimate as in Lemma 3.5 holds
and, therefore, there exists a subsequence {αn }, along which Vαl n (x) − Vαl n (0)
d
l
converges to V l in W2,p
loc (R ), p > d, and αn Vαn (0) → ̺l as αn ց 0, and
(V l , ̺l ) satisfies (4.2) (see also [1], Lemma 3.7.8).
To show that πvl (r) = ̺l , v l is a minimizing selector in (4.2), we use the
following argument. Since πv0 (r) < ∞, we claim that there exists a nonnegative, inf-compact function g ∈ C(Rd ) such that πv0 (g · (1 + r)) < ∞. Indeed,
this is true since integrability and uniform integrability of a function under
any given measure are equivalent (see also the proof of [1], Lemma 3.7.2).
Since every control in USM (l, v0 ) agrees with v0 on Blc , then for any x0 ∈ B̄lc
the map

Z τ̆l
v
v 7→ Ex0
g(Xs )(1 + r(Xs , v(Xs ))) ds
0

is constant on USM (l, v0 ). By the equivalence of (i) and (iii) in Lemma 3.3.4
of [1], this implies that
sup
v∈USM (l,v0 )

πv (g · (1 + r)) < ∞

∀l ∈ N,

44

A. ARAPOSTATHIS, A. BISWAS AND G. PANG

and thus r is uniformly integrable with respect to the family {πv :
v ∈ USM (l, v0 )} for any l ∈ N. It then follows by [1], Theorem 3.7.11, that
(4.4)

̺l =

inf

v∈USM (l,v0 )

πv (r),

l ∈ N.

This yields part (i). Moreover, in view of Lemmas 3.5 and 3.6, we deduce
that for any δ > 0 it holds that supBδ |V l | ≤ κδ , where κδ is a constant
independent of l ∈ N. It is also evident by (4.4) that ̺l is decreasing in l and
̺l ≤ η0 for all l ∈ N. Fix δ such that minu∈U h̃(x, u) ≥ 2η0 on Bδc . Since ϕ0 is
nonnegative, we obtain

Z τ̆δ
v0
(4.5)
∀x ∈ Rd .
(h̃(Xs , v0 (Xs )) − η0 ) ds ≤ ϕ0 (x)
Ex
0

Using an analogous argument as the one used in the proof of [1], Lemma 3.7.8,
we have
Z τ̆δ

l
v
(4.6) V (x) ≤ Ex
(rl (Xs , v(Xs )) − ̺l ) ds + κδ
∀v ∈ USM (l, v0 ).
0

Thus, by (4.5) and (4.6), and since by the choice of δ > 0, it holds that
r ≤ h̃ ≤ 2(h̃ − η0 ) on Bδc , we obtain
Z τ̆δ

V l (x) ≤ Evx0
2(h̃(Xs , v0 (Xs )) − η0 ) ds + κδ
0

(4.7)

≤ κδ + 2ϕ0 (x)

∀x ∈ Rd .

This proves part (ii).
Now fix l ∈ N. Let vαl be a minimizing selector of (4.3). Note then that
l
vα ∈ USM (l, v0 ). Therefore, vαl is a stable Markov control. Let vαl n → v l in
the topology of Markov controls along the same subsequence as above. Then
it is evident that v l ∈ USM (l, v0 ). Also from Lemma 3.8, we have
vl

l

Exαn [τ̆δ ] −→ Evx [τ̆δ ]

∀x ∈ Bδc , ∀δ > 0.

αn ց0

Using [1], Lemma 3.7.8, we obtain the lower bound
l

V l (x) ≥ −̺l Evx [τ̆δ ] − κδ .

(4.8)

By [1], Theorem 3.7.12(i) (see also (3.7.50) in [1]), it holds that

Z τ̆δ
l
vl
l
l
V (x) = Ex
(rl (Xs , v (Xs )) − ̺l ) ds + V (Xτ̆δ )
0

(4.9)

≥

l
Evx

Z

0

τ̆δ

l



l

rl (Xs , v (Xs )) ds − ̺l Evx [τ̆δ ] − κδ

∀x ∈ Blc .

ERGODIC CONTROL IN THE HALFIN–WHITT REGIME

45

By (3.23), we have
2k0−1 h̃(x, u)IH (x, u) ≤ 1 + r(x, u)IH (x, u).
Therefore, using the preceding inequality and (4.9), we obtain
l

(4.10)

V l (x) + (1 + ̺l )Evx [τ̆δ ] + κδ
Z τ̆δ

2 vl
l
l
≥ Ex
h̃(Xs , v (Xs ))IH (Xs , v (Xs )) ds .
k0
0

By (3.24), (4.9) and the fact that V is nonnegative, we have
Z τ̆δ

2 vl
l
Ex
h̃(Xs , v l (Xs ))IHc (Xs , v l (Xs )) ds − V(x) − Evx [τ̆δ ]
k0
0
Z τ̆δ

vl
l
l
≤ Ex
(4.11)
r(Xs , v (Xs ))IH (Xs , v (Xs )) ds
0

l

l

≤ V (x) + ̺l Evx [τ̆δ ] + κδ .
Combining (4.7), (4.10) and (4.11), we obtain

Z τ̆δ
l
l
h̃(Xs , v l (Xs )) ds ≤ k0 (1 + ̺l )Evx [τ̆δ ]
Evx
0

+

k0
V(x) + 2k0 (ϕ0 (x) + κδ )
2

for all l ∈ N. As earlier, using the inf-compact property of h̃ and the fact
that ̺l ≤ η0 is bounded, we can choose δ large enough such that
Z τ̆δ

vl
vl
l
(4.12) η0 Ex [τ̆δ ] ≤ Ex
h̃(Xs , v (Xs )) ds ≤ k0 V(x) + 4k0 (ϕ0 (x) + κδ )
0

for all l ∈ N. Since h̃ is inf-compact, part (iii) follows by (4.8) and (4.12).
Part (iv) is clear from regularity theory of elliptic PDE [18], Theorem 9.19,
page 243. 
Similar to Theorem 3.3, we can show that oscillations of {V l } are uniformly bounded on compacts. Therefore, if we let l → ∞ we obtain a HJB
equation
(4.13)

min[Lu V̂ (x) + r(x, u)] = ̺ˆ,
u∈U

with V̂ ∈ C 2 (Rd ) and liml→∞ ̺l = ̺ˆ. By Theorem 4.1, we have the bound
(4.14)

V̂ (x) ≤ C0 + 2ϕ0 (x),

46

A. ARAPOSTATHIS, A. BISWAS AND G. PANG

for some positive constant C0 . This of course, implies that V̂ + (x) ≤ C0 +
2ϕ0 (x). Moreover, it is straightforward to show that for any v ∈ USSM with
̺v < ∞, we have
1
lim sup Evx [V(Xt )] < ∞.
t→∞ t

Therefore, if in addition, we have
1
lim sup Evx [ϕ0 (Xt )] < ∞,
t→∞ t
then it follows by Theorem 4.1(iii) that
(4.15)

1
lim sup V̂ − (Xt ) −→ 0.
t→∞
t→∞ t

Theorem 4.2. Suppose that ϕ0 ∈ O(minu∈U h̃(·, u)). Then, under the
assumptions of Theorem 4.1, we have liml→∞ ̺l = ̺ˆ = ̺∗ , and V̂ = V∗ . Moreover, V∗ ∈ O(ϕ0 ).
Proof. Let {v̂l } be any sequence of measurable selectors from the minimizer of (4.2) and {πl } the corresponding sequence of ergodic occupation
measures. Since by Theorem 3.1 {πl } is tight, then by Remark 3.8 if v̂ is
a limit point of a subsequence {v̂l }, which we also denote by {v̂l }, then
π̂ = πv̂ is the corresponding limit point of {πl }. Therefore, by the lower
semi-continuity of π → π(r) we have
̺ˆ = lim πl (r) ≥ π̂(r) = ̺v̂ .
l→∞

It also holds that
(4.16)

Lv̂ V̂ (x) + r(x, v̂(x)) = ̺ˆ,

a.s.

By (4.15), we have
lim inf
T →∞

1 v̂
E [V̂ (XT )] = 0,
T x

and hence applying Itô’s rule on (4.16) we obtain ̺v̂ ≤ ̺ˆ. On the other hand,
if v∗ is an optimal stationary Markov control, then by the hypothesis ϕ0 ∈
O(h̃), the fact that πv∗ (h̃) < ∞, (4.14) and [23], Proposition 2.6, we deduce
that Evx∗ [V̂ + (Xt )] converges as t → ∞, which of course together with (4.15)
implies that 1t Ev̂x [V̂ (Xt )] tends to 0 as t → ∞. Therefore, evaluating (4.13) at
v∗ and applying Itô’s rule we obtain ̺v∗ ≥ ̺ˆ. Combining the two estimates,
we have ̺v̂ ≤ ̺ˆ ≤ ̺∗ , and thus equality must hold. Here, we have used the
fact that there exists an optimal Markov control for r by Theorem 3.4.

ERGODIC CONTROL IN THE HALFIN–WHITT REGIME

Next, we use the stochastic representation in (4.9)

Z τ̆δ
l
v̂l
l
(4.17) V (x) = Ex
(r(Xs , v̂l (Xs )) − ̺l ) ds + V (Xτ̆δ ) ,
0

47

x ∈ Bδc .

̺v

Fix any x ∈ Bδc . Since USM0 is compact, it follows that for each δ and R with
̺v
0 < δ < R, the map Fδ,R (v) : USM0 → R+ defined by

Z τ̆δ ∧τR
v
Fδ,R (v) := Ex
r(Xs , v(Xs )) ds
0

is continuous. Therefore, the map F̄δ := limRր∞ Fδ,R is lower semi-continuous.
It follows that

Z τ̆δ

Z τ̆δ
v̂
v̂l
r(Xs , v̂(Xs )) ds ≤ lim Ex
(4.18) Ex
r(Xs , v̂l (Xs )) ds .
l→∞

0

0

On the other hand, since h̃ is inf-compact, it follows by (4.12) that τ̆δ is
uniformly integrable with respect to the measures {Pv̂xl }. Therefore, as also
shown in Lemma 3.8, we have
lim Ev̂xl [τ̆δ ] = Ev̂x [τ̆δ ].

(4.19)

l→∞

Since V l → V̂ , uniformly on compact sets, and ̺l → ̺∗ , as l → ∞, it follows
by (4.17)–(4.19) that
Z τ̆δ

V̂ (x) ≥ Ev̂x
(r(Xs , v̂(Xs )) − ̺∗ ) ds + V̂ (Xτ̆δ ) ,
x ∈ Bδc .
0

Therefore, by Theorem 3.4(b), for any δ > 0 and x ∈ Bδc we obtain
Z τ̆δ

v̂
V∗ (x) ≤ Ex
(r(Xs , v̂(Xs )) − ̺∗ ) ds + V∗ (Xτ̆δ )
0

≤ V̂ (x) + Ev̂x [V ∗ (Xτ̆δ )] − Ev̂x [V̂ (Xτ̆δ )],

and taking limits as δ ց 0, using the fact that V̂ (0) = V∗ (0) = 0, we obtain V∗ ≤ V̂ on Rd . Since Lv̂ (V∗ − V̂ ) ≥ 0, we must have V∗ = V̂ . By Theorem 4.1(ii), we have V∗ ∈ O(ϕ0 ). 
Remark 4.1. It can be seen from the proof of Theorem 4.2 that the assumption ϕ0 ∈ O(h̃) can be replaced by the weaker hypothesis that
1 v∗
T Ex [ϕ0 (XT )] → 0 as T → ∞.
It is easy to see that if one replaces rl by

1

 r(x, u) + f (u),
for x ∈ B̄l ,
l
rl (x, u) =

 r(x, v0 (x)) + 1 f (v0 (x)),
otherwise,
l

Remark 4.2.

48

A. ARAPOSTATHIS, A. BISWAS AND G. PANG

for some positive valued continuous function f , the same conclusion of Theorem 4.2 holds.
If we consider the controlled dynamics given by (3.20), with running cost
as in (3.11), then there exists a function V ∼ |x|m satisfying (3.6). This fact
is proved in Proposition 3.1. There also exists a Lyapunov function V0 ∈
O(|x|m ), satisfying the assumption in Theorem 4.2, relative to any control
v0 with πv0 (h̃) < ∞, where h̃ is selected as in Remark 3.5. Indeed, in order
to construct V0 we recall the function ψ in (3.21). Let V0 ∈ C 2 (Rd ) be any
function such that V0 = ψ m/2 on the complement of the unit ball centered
at the origin. Observe that for some positive constants κ1 and κ2 it holds
that
κ1 |x|2 ≤ ψ(x) ≤ κ2 |x|2 .
Then a straightforward calculation from (3.22) shows that (3.8) holds with
the above choice of V0 . By the stochastic representation of ϕ0 , it follows that
ϕ0 ∈ O(V0 ). We have proved the following corollary.
Corollary 4.1. For the queueing diffusion model with controlled dynamics given by (3.20), and running cost given by (3.11), there exists a
solution (up to an additive constant) to the associated HJB in the class of
functions in C 2 (Rd ) whose positive part grows no faster than |x|m and whose
negative part is in o(|x|m ).
We conclude this section with the following remark.
Remark 4.3. Comparing the approximation technique introduced in
this section with that in Section 3, we see that the spatial truncation technique relies on more restrictive assumption on the Lyapunov function V0
and the running cost function (Theorem 4.2). In fact, the growth of h̃ also
restricts the growth of r by (3.23). Therefore, the class of ergodic diffusion
control problems considered in this section is more restrictive. For example,
if the running cost r satisfies (3.11) and h̃ ∼ |x|m , then it is not obvious that
one can obtain a Lyapunov function V0 with growth at most of order |x|m .
For instance, if the drift has strictly sub-linear growth, then it is expected
that the Lyapunov function should have growth larger than |x|m . Therefore,
the class of problems considered in Section 3 is larger than those considered
in this section.
5. Asymptotic convergence. In this section, we prove that the value of
the ergodic control problem corresponding to the multi-class M/M/N + M
queueing network asymptotically converges to ̺∗ , the value of the ergodic
control for the controlled diffusion.

ERGODIC CONTROL IN THE HALFIN–WHITT REGIME

49

Recall the diffusion-scaled processes X̂ n , Q̂n and Ẑ n defined in (2.4), and
from (2.5) and (2.6) that
Z t
Z t
n
n
n
n
n
n
X̂i (t) = X̂i (0) + ℓi t − µi
Ẑi (s) ds − γi
Q̂ni (s) ds
(5.1)

0

0

n
n
n
+ M̂A,i
(t) − M̂S,i
(t) − M̂R,i
(t),

n (t), M̂ n (t) and M̂ n (t), i = 1, . . . , d, as defined in (2.6), are
where M̂A,i
S,i
R,i
square integrable martingales w.r.t. the filtration {Ftn } with quadratic variations

λni
t,
n
Z
µni t n
n
hM̂S,i i(t) =
Z (s) ds,
n 0 i
Z
γin t n
n
Q (s) ds.
hM̂R,i i(t) =
n 0 i

n
hM̂A,i
i(t) =

5.1. The lower bound. In this section, we prove Theorem 2.1.
Proof of Theorem 2.1. Recall the definition of V̂ n in (2.10), and
consider a sequence such that supn V̂ n (X̂ n (0)) < ∞. Let ϕ ∈ C 2 (Rd ) be any
function satisfying ϕ(x) := |x|m for |x| ≥ 1. As defined in Section 1.3, ∆X(t)
denotes the jump of the process X at time t. Applying Itô’s formula on ϕ
(see, e.g., [24], Theorem 26.7), we obtain from (5.1) that

Z t
Θn1 (X̂1n (s), Ẑ1n (s))ϕ′ (X̂1n (s)) ds
E[ϕ(X̂1n (t))] = E[ϕ(X̂1n (0))] + E
0

+E

Z

0

+E

t

Θn2 (X̂1n (s), Ẑ1n (s))ϕ′′ (X̂1n (s)) ds

X
s≤t



∆ϕ(X̂1n (s)) − ϕ′ (X̂1n (s−)) · ∆X̂1n (s)

1 ′′ n
n
n
− ϕ (X̂ (s−))∆X̂1 (s)∆X̂1 (s) ,
2

where
Θn1 (x, z) := ℓn1 − µn1 z − γ1n (x − z),


µn1 z + γ1n (x − z)
λn1
1 n
n
√
+
µ ρ1 +
.
Θ2 (x, z) :=
2 1
n
n

50

A. ARAPOSTATHIS, A. BISWAS AND G. PANG

Since {ℓn1 } is a bounded sequence, it is easy to show that for all n there exist
positive constants κi , i = 1, 2, independent of n, such that
Θn1 (x, z)ϕ′ (x) ≤ κ1 (1 + |(e · x)+ |m ) − κ2 |x|m ,
κ2
Θn2 (x, z)ϕ′′ (x) ≤ κ1 (1 + |(e · x)+ |m ) + |x|m ,
4
provided that x − z ≤ (e · x)+ and √zn ≤ 1. We next compute the terms
corresponding to the jumps. For that, first we see that the jump size is of
order √1n . We can also find a positive constant κ3 such that
sup |ϕ′′ (y)| ≤ κ3 (1 + |x|m−2 )

∀x ∈ Rd .

|y−x|≤1

Using Taylor’s approximation, we obtain the inequality
∆ϕ(X̂1n (s)) − ϕ′ (X̂1n (s−)) · ∆X̂1n (s) ≤

1
sup
|ϕ′′ (y)|[∆(X̂1n (s))]2 .
2 |y−X̂ n (s−)|≤1
1

Hence, combining the above facts we obtain
X
E
∆ϕ(X̂1n (s)) − ϕ′ (X̂1n (s−)) · ∆X̂1n (s)
s≤t

(5.2)


1 ′′ n
n
n
− ϕ (X̂1 (s−))∆X̂1 (s)∆X̂1 (s)
2
X
≤E
κ3 (1 + |X̂1n (s−)|m−2 )(∆(X̂1n (s)))2
s≤t

t

 
λn1
µn1 Z1n (s) γ1n Qn1 (s)
= κ3 E
+
+
ds
n
n
n
0
Z t 
 
κ2
≤E
κ4 + |X̂1n (s)|m + κ5 ((e · X̂ n (s))+ )m ds ,
4
0
Z



(1 + |X̂1n (s)|m−2 )

for some suitable positive constants κ4 and κ5 , independent of n, where in
the second inequality we use the fact that the optional martingale [X̂1n ] is
the sum of the squares of the jumps, and that [X̂1n ] − hX̂1n i is a martingale.
Therefore, for some positive constants C1 and C2 it holds that
0 ≤ E[ϕ(X̂1n (t))]
(5.3)

≤ E[ϕ(X̂1n (0))] + C1 t −
+ C2 E

Z

t
0

κ2
E
2

Z

0

t

|X̂1n (s)|m ds


((e · X̂ (s)) ) ds .
n

+ m



ERGODIC CONTROL IN THE HALFIN–WHITT REGIME

51

By (2.8), we have
r(Q̂n (s)) ≥

c1
((e · X̂ n (s))+ )m ,
dm

which, combined with the assumption that supn V̂ n (X̂ n (0)) < ∞, implies
that

Z T
1
+ m
n
((e · X̂ (s)) ) ds < ∞.
sup lim sup E
n
T →∞ T
0
In turn, from (5.3) we obtain
sup lim sup
n

T →∞

1
E
T

Z

T

0


|X̂1n (s)|m ds < ∞.

Repeating the same argument for coordinates i = 2, . . . , d, we obtain

Z T
1
(5.4)
|X̂ n (s)|m ds < ∞.
sup lim sup E
n
T →∞ T
0
We introduce the process
 n
 X̂i (t) − Ẑin (t)
,
n
n
+
Ui (t) :=
 (e · X̂ (t))
ed ,

i = 1, . . . , d,

if (e · X̂ n (t))+ > 0,
otherwise.

Since Z n is work-conserving, it follows that U n takes values in S, and Uin (t)
represents the fraction of class i customers in queue. Define the mean empirical measures

Z T
1
n
n
n
ΦT (A × B) := E
IA×B (X̂ (s), U (s)) ds
T
0

for Borel sets A ⊂ Rd and B ⊂ S.
From (5.4), we see that the family {ΦnT : T > 0, n ≥ 1} is tight. Hence, for
any sequence Tk → ∞, there exists a subsequence, also denoted by Tk , such
that ΦnTk → π n , as k → ∞. It is evident that {π n : n ≥ 1} is tight. Let π n → π
along some subsequence, with π ∈ P(Rd × S). Therefore, it is not hard to
show that
Z
n
n
r̃(x, u)π(dx, du),
lim V̂ (X̂ (0)) ≥
n→∞

Rd ×U

where, as defined earlier, r̃(x, u) = r((e · x)+ u). To complete the proof of the
theorem, we only need to show that π is an ergodic occupation measure
for the diffusion. For that, consider f ∈ Cc∞ (Rd ). Recall that [X̂in , X̂jn ] = 0

52

A. ARAPOSTATHIS, A. BISWAS AND G. PANG

for i 6= j [30], Lemmas 9.2 and 9.3. Therefore, using Itô’s formula and the
definition of ΦnT , we obtain
1
E[f (X̂ n (T ))]
T
1
= E[f (X̂ n (0))]
T
!
Z
d
X
(5.5)
Ani (x, u) · fxi (x) + Bin (x, u)fxi xi (x) ΦnT (dx, du)
+
Rd ×U

+

i=1

d

"

X
1 X
fxi (X̂ n (s−)) · ∆X̂in (s)
E
∆f (X̂ n (s)) −
T
s≤T

i=1

#
d
1 X
n
n
n
fxi xj (X̂ (s−))∆X̂i (s)∆X̂j (s) ,
−
2
i,j=1

where

Ani (x, u) := ℓni − µni (xi − (e · x)+ ui ) − γin (e · x)+ ui ,


λn µn xi + (γin − µni )(e · x)+ ui
1 n
√
µi ρi + i + i
.
Bin (x, u) :=
2
n
n

We first bound the last term in (5.5). Using Taylor’s formula, we see that
n

∆f (X̂ (s)) −
−

d
X
i=1

∇f (X̂ n (s−)) · ∆X̂ n (s)

d
1 X
fxi xj (X̂ n (s−))∆X̂in (s)∆X̂jn (s)
2
i,j=1

=

d
kkf kC 3 X
√
|∆X̂in (s)∆X̂jn (s)|
n
i,j=1

for some positive constant k, where we use the fact that the jump size is
√1 . Hence, using the fact that independent Poisson processes do not have
n
simultaneous jumps w.p.1, using the identity Q̂ni = X̂in − Ẑin , we obtain
"
d
X
1 X
∇f (X̂ n (s−)) · ∆X̂ n (s)
E
∆f (X̂ n (s)) −
T
i=1

s≤T

(5.6)

#
d
1 X
−
fxi xj (X̂ n (s−))∆X̂in (s)∆X̂jn (s)
2
i,j=1

ERGODIC CONTROL IN THE HALFIN–WHITT REGIME

kkf k 3
≤ √C E
T n

"Z

T

0

53

d  n
X
λ
i=1

 #
n Z n (s)
n Qn (s)
µ
γ
i
+ i i
+ i i
ds .
n
n
n

Therefore, first letting T → ∞ and using (5.2) and (5.4) we see that the
expectation on the right-hand side of (5.6) is bounded above. Therefore, as
n → ∞, the left-hand side of (5.6) tends to 0. Thus, by (5.5) and the fact
that f is compactly supported, we obtain
Z
Lu f (x)π(dx, du) = 0,
Rd ×U

where

Lu f (x) = λi ∂ii f (x) + (ℓi − µi (xi − (e · x)+ ui ) − γi (e · x)+ ui )∂i f (x).
Therefore, π ∈ G. 
5.2. The upper bound. The proof of the upper bound in Theorem 2.2 is
a little more involved than that of the lower bound. Generally, it is very
helpful if one has uniform stability across n ∈ N (see, e.g., [12]). In [12],
uniform stability is obtained from the reflected dynamics with the Skorohod
mapping. However, here we establish the asymptotic upper bound by using
the technique of spatial truncation that we have introduced in Section 4.
Let vδ be any precise continuous control in USSM satisfying vδ (x) = u0 =
(0, . . . , 0, 1) for |x| > K > 1.
First, we construct a work-conserving admissible policy for each n ∈ N
(see [7]). Define a measurable map ̟ : {z ∈ Rd+ : e · z ∈ Z} → Zd+ as follows:
for z = (z1 , . . . , zd ) ∈ Rd , let
!
d
X
(zi − ⌊zi ⌋) .
̟(z) := ⌊z1 ⌋, . . . , ⌊zd−1 ⌋, ⌊zd ⌋ +
i=1

Note that |̟(z) − z| ≤ 2d. Define

uh (x) := ̟((e · x − n)+ vδ (x̂n )),
x ∈ Rd ,


x1 − ρ1 n
xd − ρd n
n
√
x̂ :=
,..., √
,
n
n
n
√ o
An := x ∈ Rd+ : sup |xi − ρi n| ≤ K n .
i

We define a state-dependent, work-conserving policy as follows:
 n
X − uh (X n ),
if X n ∈ An ,


 i
!
+
i−1
X
Zin [X n ] :=
(5.7)
n
n

,
otherwise.
Xj
X ∧ n−

 i
j=1

54

A. ARAPOSTATHIS, A. BISWAS AND G. PANG

Therefore, whenever the state of the system is in Acn , the system works under
the fixed priority policy with the least priority given to class-d jobs. First,
we show that this is a well-defined policy for all large n. It is enough to
show that Xin − uh (X n ) ≥ 0 for all i when X n ∈ An . If not, then for some
i, 1 ≤ i ≤ d, we must have Xin − uh (X n ) < 0 and so Xin < (e · X n − n)+ + d.
Since X n ∈ An , we obtain
√
−K n + ρi n ≤ Xin
< (e · X n − n)+ + d
!+
d
X
n
(Xi − ρi n)
=
+d
i=1

√
≤ dK n + d.

But this cannot hold for large n. Hence, this policy is well defined for all
large n. Under the policy defined in (5.7), X n is a Markov process and its
generator given by
Ln f (x) =

d
X
i=1

+

λni (f (x + ei ) − f (x)) +

d
X
i=1

d
X
i=1

µni Zin [x](f (x − ei ) − f (x))

γin Qni [x](f (x − ei ) − f (x)),

x ∈ Zd+ ,

where Z n [x] is as above and Qn [x] := x − Z n [x]. It is easy to see that, for
x∈
/ An ,
! + #+
"
i−1
X
n
xj
.
Qi [x] = xi − n −
j=1

Lemma 5.1. Let X n be the Markov process corresponding to the above
control. Let q be an even positive integer. Then there exists n0 ∈ N such that

Z T
1
q
n
sup lim sup E
|X̂ (s)| ds < ∞,
n≥n0 T →∞ T
0
where X̂ n = (X̂1n , . . . , X̂dn )T is the diffusion-scaled process corresponding to
the process X n , as defined in (2.4).
Proof. The proof technique is inspired by [6], Lemma 3.1. Define
fn (x) :=

d
X
i=1

βi (xi − ρi n)q ,

ERGODIC CONTROL IN THE HALFIN–WHITT REGIME

55

where βi , i = 1, . . . , d, are positive constants to be determined later. We first
show that for a suitable choice of βi , i = 1, . . . , d, there exist constants Ci ,
i = 1, 2, independent of n ≥ n0 , such that
Ln fn (x) ≤ C1 nq/2 − C2 fn (x),

(5.8)

x ∈ Zd+ .

Choose n large enough so that the policy is well defined. We define Yin :=
xi − ρi n. Note that
Also,

(a ± 1)q − aq = ±qa · aq−2 + O(aq−2 ),

µni Zin [x] = µni xi
Ln fn (x) =

d
X
i=1

−
−
≤

(5.9)

i=1

d
X
i=1

i=1

d
X

d
X
i=1

+

βi µni xi [qYin |Yin |q−2 + O(|Yin |q−2 )]
βi (γin − µni )Qni [x][qYin |Yin |q−2 + O(|Yin |q−2 )]

βi (λni + µni xi + |γin − µni |Qin [x])O(|Yin |q−2 )

i=1

≤

Then

a ∈ R.

βi λni [qYin |Yin |q−2 + O(|Yin |q−2 )]

d
X

d
X

+

− µni Qni [x].

βi qYin |Yin |q−2 (λni − µni xi − (γin − µni )Qni [x])

βi (λni + (µni + |γin − µni |)(Yin + ρi n))O(|Yin |q−2 )

d
X
i=1

βi qYin |Yin |q−2 (λni − µni xi − (γin − µni )Qni [x]),

where in the last inequality we use the fact that Qni [x] ≤ xi for x ∈ Zd+ . Let
√
δin := λni − µni ρi n = O( n).

The last estimate is due to the assumptions in (2.1) concerning the parameters in the Halfin–Whitt regime. Then

(5.10)

d
X
i=1

βi qYin |Yin |q−2 (λni − µni xi − (γin − µni )Qni [x])
= −q

d
X
i=1

βi µni |Yin |q +

d
X
i=1

βi qYin |Yin |q−2 (δin − (γin − µni )Qni [x]).

56

A. ARAPOSTATHIS, A. BISWAS AND G. PANG

If x ∈ An and n is large, then

Qni [x] = uh (x) = ̟((e · x − n)+ vδ (x̂n ))
√
≤ (e · x − n)+ + d ≤ 2dK n.

Let x ∈ Acn . We use the fact that for any a, b ∈ R it holds that a+ − b+ =
ξ[a − b] for some ξ ∈ [0, 1]. Also,
!+ #+
"
i−1
X
nρj
= 0,
i = 1, . . . , d.
nρi − n −
j=1

Thus, we obtain maps ξ, ξ̃ : Rd → [0, 1]d such that
!+ #+
"
i−1
X
nρj
− Qni [x]
−Qni [x] = nρi − n −
j=1

= ξi (x)(nρi − xi ) − ξ˜i (x)

i−1
X
(xj − nρj ),

x ∈ Acn .

j=1

Hence, from (5.10) we obtain
d
X
i=1

βi qYin |Yin |q−2 (λni − µni xi − (γin − µni )Qni [x])
d
d
X
X
√
βi ((1 − ξi (x))µni + ξi (x)γin )|Yin |q
βi |Yin |q−1 − q
≤ O( n)q
i=1

i=1

+q

d
X
i=1

βi Yin |Yin |q−2

δin

− (γin

− µni )ξ̃i (x)

where we used the fact that on An we have
!+ #+
"
i−1
X
√
= O( n)
xj
xi − n −
j=1

i−1
X

Yjn

j=1

!

,

∀i.

Observe that there exists ϑ > 0, independent of n due to (2.1), such that
(1 − ξi (x))µni + ξi (x)γin ≥ min(µni , γin ) ≥ ϑ
for all n ∈ N, all x ∈ Rd , and all i = 1, . . . , d. As a result, we obtain
d
X
i=1

βi qYin |Yin |q−2 (λni − µni xi − (γin − µni )Qni [x])

57

ERGODIC CONTROL IN THE HALFIN–WHITT REGIME
d
d
X
X
√
n q−1
βi |Yin |q
βi |Yi |
− qϑ
≤ O( n)q

(5.11)

i=1

i=1

+q

d
X
i=1

βi Yin |Yin |q−2 δin − (γin − µni )ξ̃i (x)

i−1
X
j=1

!

Ynj .

We next estimate the last term on the right-hand side of (5.11). Let κ :=
ϑ
. Using Young’s inequality, we obtain the estisupn,i |γin − µni |, and ε1 := 8κ
mate
q
i−1
i−1
X
1 X n
n q−1
j
n q
Yj .
|Yi |
Yn ≤ ε1 |Yi | + q−1
ε
1
j=1
j=1
Therefore,

q

d
X
i=1

βi Yin |Yin |q−2 −(γin − µni )ξ̃i (x)

≤ qκ

d
X

ε1 βi |Yin |q

≤ qκ

d
X

ε1 βi |Yin |q

i=1

i=1

+

+

i−1
βi X

ε1q−1

j=1

βi

q−1

ε1q−1

i−1
X

Yjn

j=1

Yjn

d

!

q!

i−1
X
|Yjn |q
j=1

!

!
d
i−1
qϑ X
βi q−1 X n q
n q
=
βi |Yi | + q d
|Yj | .
8
ε1
i=1

j=1

We choose β1 = 1 and for i ≥ 2, we define βi by

εq1
βi := q min βj .
d j≤i−1
With this choice of βi it follows from above that
q

d
X
i=1

βi Yin |Yin |q−2

−(γin

− µni )ξ̃i (x)

i−1
X
j=1

Ynj

!

Using the preceding inequality in (5.11), we obtain

(5.12)

d
X
i=1

d

qϑ X
≤
βi |Yin |q .
4
i=1

βi qYin |Yin |q−2 (λni − µni xi − (γin − µni )Qni [x])
d
d
X
√
3 X
βi |Yin |q .
≤ O( n)q
βi |Yin |q−1 − qϑ
4
i=1

i=1

58

A. ARAPOSTATHIS, A. BISWAS AND G. PANG

Combining (5.9) and (5.12), we obtain
Ln fn (x) ≤
(5.13)

d
X
i=1

d
X
√
O(n)O(|Yin |q−2 )
O( n)O(|Yin |q−1 ) +
i=1

d

3 X
βi |Yin |q .
− qϑ
4
i=1

By Young’s inequality, for any ε > 0, we have the bounds
√
√
O( n)O(|Yin |q−1 ) ≤ ε[O(|Yin |q−1 )]q/(q−1) + ε(1−q) [O( n)]q ,

O(n)O(|Yin |q−2 ) ≤ ε[O(|Yin |q−2 )]q/(q−2) + ε(1−q/2) [O(n)]q/2 .

Thus, choosing ε properly in (5.13) we obtain (5.8).
We proceed to complete the proof of the lemma by applying (5.8). First,
we observe that E[sups∈[0,T ] |X n (s)|p ] is finite for any p ≥ 1 as this quantity
is dominated by the Poisson arrival process. Therefore, from (5.8) we see
that

Z T
n
n
n
Ln fn (X (s)) ds
E[fn (X (T ))] − fn (X (0)) = E
0

≤ C1 n

q/2

T − C2 E

Z

T

0


fn (X (s)) ds ,
n

which implies that
#
"Z
d
d
T X
X
βi (X̂in (0))q .
C2 E
βi (X̂in (s))q ds ≤ C1 T +
0

i=1

i=1

Hence, the proof follows by dividing both sides by T and letting T → ∞.

Proof of Theorem 2.2. Let r be the given running cost with polynomial growth with exponent m in (2.8). Let q = 2(m + 1). Recall that
r̃(x, u) = r((e · x)+ u) for (x, u) ∈ Rd × S. Then r̃ is convex in u and satisfies
(3.11) with the same exponent m. For any δ > 0, we choose vδ ∈ USSM such
that vδ is a continuous precise control with invariant probability measure µδ
and
Z
(5.14)
r̃(x, vδ (x))µδ (dx) ≤ ̺∗ + δ.
Rd

We also want the control vδ to have the property that vδ (x) = (0, . . . , 0, 1)
outside a large ball. To obtain such vδ , we see that by Theorems 4.1, 4.2 and

ERGODIC CONTROL IN THE HALFIN–WHITT REGIME

59

Remark 4.2 we can find vδ′ and a ball Bl for l large, such that vδ′ ∈ USSM ,
vδ′ (x) = ed for |x| > l, vδ′ is continuous in Bl , and
Z
δ
r̃(x, vδ′ (x))µ′δ (dx) − ̺∗ < ,
2
d
R
where µ′δ is the invariant probability measure corresponding to vδ′ . We note
that vδ′ might not be continuous on ∂Bl . Let {χn : n ∈ N} be a sequence
c
of cut-off functions such that χn ∈ [0, 1], it vanishes on Bl−(1/n)
, and it
n
n
takes the value 1 on Bl−(2/n) . Define the sequence vδ (x) := χ (x)vδ′ (x) +
(1 − χn (x))ed . Then vδn → vδ′ , as n → ∞, and the convergence is uniform
on the complement of any neighborhood of ∂Bl . Also by Proposition 3.1
the corresponding invariant probability measures µnδ are exponentially tight.
Thus,
Z
Z
′
′
r̃(x, vδn (x))µnδ (dx) −→ 0.
r̃(x, vδ (x))µδ (dx) −
Rd

Rd

n→∞

Combining the above two expressions, we can easily find vδ which satisfies
(5.14). We construct a scheduling policy as in Lemma 5.1. By Lemma 5.1,
we see that for some constant K1 it holds that

Z T
1
q
n
(5.15)
|X̂ (s)| ds < K1 ,
q = 2(m + 1).
sup lim sup E
n≥n0 T →∞ T
0
Define
vh (x) := ̟((e · x − n)+ vδ (x̂n )),
√
v̂h (x̂n ) := ̟( n(e · x̂n )+ vδ (x̂n )).
Since vδ (x̂n ) = (0, . . . , 0, 1) when |x̂n | ≥ K, it follows that
Qn [X n ] = X n − Z n [X n ] = vh (X n )
P
n
for large n, provided that d−1
i=1 Xi ≤ n. Define
( d−1
)
X
√
x̂ni > ρd n .
Dn := x :
i=1

Then



1
n
r(Q̂ (t)) = r √ v̂h (X̂ (t)) + r(X̂ n (t) − Ẑ n (t))I{X̂ n (t)∈Dn }
n


1
n
− r √ v̂h (X̂ (t)) I{X̂ n (t)∈Dn } .
n
n

60

A. ARAPOSTATHIS, A. BISWAS AND G. PANG

Define, for each n, the mean empirical measure ΨnT by

Z T
1
IA (X̂ n (t)) dt .
ΨnT (A) := E
T
0
By (5.15), the family {ΨnT : T > 0, n ≥ 1} is tight. We next show that
 Z
Z T
1
n
(5.16) lim lim sup E
r((e · x)+ vδ (x))µδ (dx).
r(Q̂ (t)) dt =
n→∞ T →∞ T
Rd
0
For each n, select a sequence {Tkn : k ∈ N} along which the “lim sup” in (5.16)
is attained. By tightness, there exists a limit point Ψn of ΨnT n . Since Ψn has
k
support on a discrete lattice, we have




Z
Z
1
1
n
r √ v̂h (x) Ψn (dx).
r √ v̂h (x) ΨT n (dx) −→
k
k→∞
d
n
n
d
R
R
Therefore,
1
lim sup E
T →∞ T

Z

T
0






1
r √ v̂h (x) Ψn (dx) ± E n ,
r(Q̂ (t)) dt ≶
n
d
R
n

Z

where
E n = lim sup
T →∞

1
E
T

Z

0

T




1
r(Q̂n (t)) + r √ v̂h (X̂ n (t)) I{X̂ n (t)∈Dn } dt .
n

By (5.15), the family {Ψn : n ≥ 1} is tight. Hence, it has a limit Ψ. By
definition, we have
1
2d
√ v̂h (x) − (e · x)+ vδ (x) ≤ √ .
n
n
Thus, using the continuity property of r and (2.8) it follows that


Z
Z
1
n
r √ v̂h (x) Ψ (dx) −→
r((e · x)+ vδ (x))Ψ(dx),
n→∞
n
d
d
R
R
along some subsequence. Therefore, in order to complete the proof of (5.16)
we need to show that
lim sup E n = 0.
n→∞

Since the policies are work-conserving, we observe that 0 ≤ X̂ n − Ẑ n ≤ (e ·
X̂ n )+ , and therefore for some positive constants κ1 and κ2 , we have


1
n
r √ v̂h (X̂ (t)) ∨ r(X̂ n (t) − Ẑ n (t)) ≤ κ1 + κ2 [(e · X̂ n )+ ]m .
n

ERGODIC CONTROL IN THE HALFIN–WHITT REGIME

61

Given ε > 0 we can choose n1 so that for all n ≥ n1 ,

Z T
1
+ m
n
√
√
[(e · X̂ (s)) ] I{|X̂ n (s)|>(ρd / d) n} ds ≤ ε,
lim sup E
T →∞ T
0
p
where we use (5.15). We observe that Dn ⊂ {|x̂n | > ρd d/n}. Thus, (5.16)
holds. In order to complete the proof, we only need to show that Ψ is the
invariant probability measure corresponding to vδ . This can be shown using
the convergence of generators as in the proof of Theorem 2.1. 
6. Conclusion. We have answered some of the most interesting questions
for the ergodic control problem of the Markovian multi-class many-server
queueing model. This current study has raised some more questions for future research. One of the interesting questions is to consider nonpreemptive
policies and try to establish asymptotic optimality in the class of nonpreemptive admissible polices [7]. It will also be interesting to study a similar
control problem when the system has multiple heterogeneous agent pools
with skill-based routing.
It has been observed that customers’ service requirements and patience
times are nonexponential [10] in some situations. It is therefore important
and interesting to address similar control problems under general assumptions on the service and patience time distributions.
Acknowledgements. We thank the anonymous referee for many helpful
comments that have led to significant improvements in our paper. Ari Arapostathis acknowledges the hospitality the Department of Industrial and
Manufacturing Engineering in Penn State while he was visiting at the early
stages of this work. Guodong Pang acknowledges the hospitality of the Department of Electrical and Computer Engineering at University of Texas at
Austin while he was visiting for this work. Part of this work was done while
Anup Biswas was visiting the Department of Industrial and Manufacturing
Engineering in Penn State. Hospitality of the department is acknowledged.
REFERENCES
[1] Arapostathis, A., Borkar, V. S. and Ghosh, M. K. (2012). Ergodic Control
of Diffusion Processes. Encyclopedia of Mathematics and Its Applications 143.
Cambridge Univ. Press, Cambridge. MR2884272
[2] Arisawa, M. and Lions, P.-L. (1998). On ergodic stochastic control. Comm. Partial
Differential Equations 23 2187–2217. MR1662180
[3] Atar, R. (2005). Scheduling control for queueing systems with many servers: Asymptotic optimality in heavy traffic. Ann. Appl. Probab. 15 2606–2650. MR2187306
[4] Atar, R. and Biswas, A. (2014). Control of the multiclass G/G/1 queue in the
moderate deviation regime. Ann. Appl. Probab. 24 2033–2069. MR3226171
[5] Atar, R., Giat, C. and Shimkin, N. (2010). The cµ/θ rule for many-server queues
with abandonment. Oper. Res. 58 1427–1439. MR2560545

62

A. ARAPOSTATHIS, A. BISWAS AND G. PANG

[6] Atar, R., Giat, C. and Shimkin, N. (2011). On the asymptotic optimality of the
cµ/θ rule under ergodic cost. Queueing Syst. 67 127–144. MR2771197
[7] Atar, R., Mandelbaum, A. and Reiman, M. I. (2004). Scheduling a multi class
queue with many exponential servers: Asymptotic optimality in heavy traffic.
Ann. Appl. Probab. 14 1084–1134. MR2071417
[8] Bogachev, V. I., Krylov, N. V. and Röckner, M. (2001). On regularity of transition probabilities and invariant measures of singular diffusions under minimal
conditions. Comm. Partial Differential Equations 26 2037–2080. MR1876411
[9] Borkar, V. S. (1989). Optimal Control of Diffusion Processes. Pitman Research
Notes in Mathematics Series 203. Longman, Harlow. MR1005532
[10] Brown, L., Gans, N., Mandelbaum, A., Sakov, A., Shen, H., Zeltyn, S. and
Zhao, L. (2005). Statistical analysis of a telephone call center: A queueingscience perspective. J. Amer. Statist. Assoc. 100 36–50. MR2166068
[11] Budhiraja, A., Ghosh, A. and Liu, X. (2014). Scheduling control for Markovmodulated single-server multiclass queueing systems in heavy traffic. Queueing
Syst. 78 57–97. MR3238008
[12] Budhiraja, A., Ghosh, A. P. and Lee, C. (2011). Ergodic rate control problem for single class queueing networks. SIAM J. Control Optim. 49 1570–1606.
MR2817491
[13] Dai, J. G. and Tezcan, T. (2008). Optimal control of parallel server systems with
many servers in heavy traffic. Queueing Syst. 59 95–134. MR2430811
[14] Dieker, A. B. and Gao, X. (2013). Positive recurrence of piecewise Ornstein–
Uhlenbeck processes and common quadratic Lyapunov functions. Ann. Appl.
Probab. 23 1291–1317. MR3098433
[15] Gamarnik, D. and Stolyar, A. L. (2012). Multiclass multiserver queueing system
in the Halfin-Whitt heavy traffic regime: Asymptotics of the stationary distribution. Queueing Syst. 71 25–51. MR2925789
[16] Gamarnik, D. and Zeevi, A. (2006). Validity of heavy traffic steady-state approximation in generalized Jackson networks. Ann. Appl. Probab. 16 56–90.
MR2209336
[17] Garnett, O., Mandelbaum, A. and Reiman, M. I. (2002). Designing a call center
with impatient customers. Manuf. Serv. Oper. Manag. 4 208–227.
[18] Gilbarg, D. and Trudinger, N. S. (1983). Elliptic Partial Differential Equations of
Second Order, 2nd ed. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 224. Springer, Berlin. MR0737190
[19] Gurvich, I. (2014). Diffusion models and steady-state approximations for exponentially ergodic Markovian queues. Ann. Appl. Probab. 24 2527–2559. MR3262510
[20] Gyöngy, I. and Krylov, N. (1996). Existence of strong solutions for Itô’s stochastic equations via approximations. Probab. Theory Related Fields 105 143–158.
MR1392450
[21] Halfin, S. and Whitt, W. (1981). Heavy-traffic limits for queues with many exponential servers. Oper. Res. 29 567–588. MR0629195
[22] Harrison, J. M. and Zeevi, A. (2004). Dynamic scheduling of a multiclass queue
in the Halfin–Whitt heavy traffic regime. Oper. Res. 52 243–257. MR2066399
[23] Ichihara, N. and Sheu, S.-J. (2013). Large time behavior of solutions of Hamilton–
Jacobi–Bellman equations with quadratic nonlinearity in gradients. SIAM J.
Math. Anal. 45 279–306. MR3032978
[24] Kallenberg, O. (2002). Foundations of Modern Probability, 2nd ed. Springer, New
York. MR1876169

ERGODIC CONTROL IN THE HALFIN–WHITT REGIME

63

[25] Kim, J. and Ward, A. R. (2013). Dynamic scheduling of a GI/GI/1 + GI queue
with multiple customer classes. Queueing Syst. 75 339–384. MR3110643
[26] Koçağa, Y. L. and Ward, A. R. (2010). Admission control for a multi-server queue
with abandonment. Queueing Syst. 65 275–323. MR2652045
[27] Krylov, N. V. (1980). Controlled Diffusion Processes. Applications of Mathematics
14. Springer, New York. Translated from the Russian by A. B. Aries. MR0601776
[28] Mandelbaum, A. and Stolyar, A. L. (2004). Scheduling flexible servers with convex delay costs: Heavy-traffic optimality of the generalized cµ-rule. Oper. Res.
52 836–855. MR2104141
[29] Ocone, D. and Weerasinghe, A. (2003). Degenerate variance control in the onedimensional stationary case. Electron. J. Probab. 8 no. 24, 27 pp. (electronic).
MR2041825
[30] Pang, G., Talreja, R. and Whitt, W. (2007). Martingale proofs of many-server
heavy-traffic limits for Markovian queues. Probab. Surv. 4 193–267. MR2368951
[31] Stannat, W. (1999). (Nonsymmetric) Dirichlet operators on L1 : Existence, uniqueness and associated Markov processes. Ann. Scuola Norm. Sup. Pisa Cl. Sci.
(4) 28 99–140. MR1679079
[32] van Mieghem, J. A. (1995). Dynamic scheduling with convex delay costs: The generalized cµ rule. Ann. Appl. Probab. 5 809–833. MR1359830
[33] Yosida, K. (1980). Functional Analysis, 6th ed. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 123.
Springer, Berlin. MR0617913
A. Arapostathis
A. Biswas
Department of Electrical
and Computer Engineering
The University of Texas at Austin
1616 Guadalupe St., UTA 7.508
Austin, Texas 78701
USA
E-mail: ari@ece.utexas.edu
anupbiswas@utexas.edu

G. Pang
The Harold and Inge Marcus Department
of Industrial and Manufacturing Engineering
College of Engineering
Pennsylvania State University
University Park, Pennsylvania 16802
USA
E-mail: gup3@psu.edu

