1

Learning-aided Stochastic Network Optimization
with Imperfect State Prediction

arXiv:1705.05058v1 [math.OC] 15 May 2017

Longbo Huang∗ , Minghua Chen+ , Yunxin Liu†
∗longbohuang@tsinghua.edu.cn, IIIS@Tsinghua University
+minghua@ie.cuhk.edu.hk, IE@CUHK
†yunxin.liu@microsoft.com, Microsoft Research Asia

Abstract—We investigate the problem of stochastic network
optimization in the presence of imperfect state prediction and
non-stationarity. Based on a novel distribution-accuracy curve
prediction model, we develop the predictive learning-aided control
(PLC) algorithm, which jointly utilizes historic and predicted
network state information for decision making. PLC is an online
algorithm that requires zero a-prior system statistical information, and consists of three key components, namely sequential
distribution estimation and change detection, dual learning, and
online queue-based control.
Specifically, we show that PLC simultaneously achieves good
long-term performance, short-term queue size reduction, accurate change detection, and fast algorithm convergence. In particular, for stationary networks, PLC achieves a near-optimal [O(),
O(log(1/)2 )] utility-delay tradeoff. For non-stationary networks,
PLC obtains an [O(), O(log2 (1/) + min(c/2−1 , ew /))] utilitymax(−c ,e−2
w )
backlog tradeoff for distributions that last Θ(
) time,
1+a
where ew is the prediction accuracy and a = Θ(1) > 0 is
a constant (the Backpressue algorithm [1] requires an O(−2 )
length for the same utility performance with a larger backlog).
Moreover, PLC detects distribution change O(w) slots faster
with high probability (w is the prediction size) and achieves
an O(min(−1+c/2 , ew /) + log2 (1/)) convergence time, which
is faster than Backpressure and other algorithms. Our results
demonstrate that state prediction (even imperfect) can help
(i) achieve faster detection and convergence, and (ii) obtain
better utility-delay tradeoffs. They also quantify the benefits of
prediction in four important performance metrics, i.e., utility
(efficiency), delay (quality-of-service), detection (robustness), and
convergence (adaptability), and provide new insight for joint
prediction, learning and optimization in stochastic networks.

I. I NTRODUCTION
Enabled by recent developments in sensing, monitoring,
and machine learning methods, utilizing prediction for performance improvement in networked systems has received a
growing attention in both industry and research. For instance,
recent research works [2], [3], and [4] investigate the benefits
of utilizing prediction in energy saving, job migration in cloud
computing, and video streaming in cellular networks. On the
industry side, various companies have implemented different
ways to take advantage of prediction, e.g., Amazon utilizes
prediction for better package delivery [5] and Facebook enables prefetching for faster webpage loading [6]. However,
despite the continuing success in these attempts, most existing
results in network control and analysis do not investigate
This paper will be presented in part at the 18th ACM International
Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), India,
July 2017.

the impact of prediction. Therefore, we still lack a thorough theoretical understanding about the value-of-prediction in
stochastic network control. Fundamental questions regarding
how prediction should be integrated in network algorithms, the
ultimate prediction gains, and how prediction error impacts
performance, remain largely unanswered.
To contribute to developing a theoretical foundation for
utilizing prediction in networks, in this paper, we consider a
general constrained stochastic network optimization formulation, and aim to rigorously quantify the benefits of system state
prediction and the impact of prediction error. Specifically, we
are given a discrete-time stochastic network with a dynamic
state that evolves according to some potentially non-stationary
probability law. Under each system state, a control action is
chosen and implemented. The action generates traffic into network queues but also serves workload from them. The action
also results in a system utility (cost) due to service completion
(resource expenditure). The traffic, service, and cost are jointly
determined by the action and the system state. The objective
is to maximize the expected utility (or equivalently, minimize
the cost) subject to traffic/service constraints, given imperfect
system state prediction information.
This is a general framework that models various practical
scenarios, for instance, mobile networks, computer networks,
supply chains, and smart grids. However, understanding the
impact of prediction in this framework is challenging. First,
statistical information of network dynamics is often unknown
a-priori. Hence, in order to achieve good performance, algorithms must be able to quickly learn certain sufficient
statistics of the dynamics, and make efficient use of prediction
while carefully handling prediction error. Second, system
states appear randomly in every time slot. Thus, algorithms
must perform well under such incremental realizations of
the randomness. Third, quantifying system service quality
often involves handling queueing in the system. As a result,
explicit connections between control actions and queues must
be established.
There has been a recent effort in developing algorithms
that can achieve good utility and delay performance for this
general problem without prediction in various settings, for
instance, wireless networks, [7], [8], [9], [10], processing
networks, [11], [12], cognitive radio, [13], and the smart grid,
[14], [15]. However, existing results mostly focus on networks
with stationary distributions. They either assume full system
statistical information beforehand, or rely on stochastic ap-

2

proximation techniques to avoid the need of such information.
Works [16] and [17] propose schemes to incorporate historic
system information into control, but they do not consider
prediction. Recent results in [18], [19], [20], [21] and [22]
consider problems with traffic demand prediction, and [23]
jointly considers demand and channel prediction. However,
they focus either on M/M/1-type models, or do not consider
queueing, or do not consider the impact of prediction error. In
a different line of work, [24], [25], [26] and [27] investigate
the benefit of prediction from the online algorithm design
perspective. Although the results provide novel understanding
about the effect of prediction, they do not apply to the
general constrained network optimization problems, where
action outcomes are general functions of time-varying network
states, queues evolve in a controlled manner, i.e., arrival and
departure rates depend on the control policy, and prediction
can contain error.
In this paper, we develop a novel control algorithm for
the general framework called predictive learning-aided control
(PLC). PLC is an online algorithm that consists of three
components, sequential distribution estimation and change
detection, dual learning, and online control (see Fig. 1).
Prediction

Distribution

& History

Estimate

Network

Learning

Queue-based
Control

Fig. 1. The PLC algorithm contains (i) a distribution estimator that utilizes
both historic and predicted information to simultaneously form a distribution
estimate and detect distribution change, (ii) a learning component that computes an empirical Lagrange multiplier based on the distribution estimate,
and (iii) a queue-based controller whose decision-making information is
augmented by the multiplier.

The distribution estimator conducts sequential statistical
comparisons based on prediction and historic network state
records. Doing so efficiently detects changes of the underlying
probability distribution and guides us in selecting the right
state samples to form distribution estimates. The estimated
distribution is then fed into the dual learning component to
compute an empirical multiplier of an underlying optimization
formulation. This multiplier is further incorporated into the
Backpressure (BP) network controller [1] to perform realtime network operation. Compared to the commonly adopted
receding-horizon-control approach (RHC), e.g., [28], PLC provides another way to utilize future state information, which
focuses on using the predicted distribution for guiding action
selection in the present slot and can be viewed as performing
steady-state control under the predicted future distribution.
We summarize our main contributions as follows.
i. We propose a general state prediction model featured with
a distribution-accuracy curve. Our model captures key factors
of several existing prediction models, including window-based
[22], distribution-based [29], and filter-based [26] models.
ii. We propose a general constrained network control algorithm called predictive learning-aided control (PLC), which is

an online algorithm that requires zero a-prior system statistical
information. PLC jointly performs sequential distribution estimation and change detection, dual learning, and queue-based
online control.
iii. We show that for stationary networks, PLC achieves
an [O(), O(log2 (1/))] utility-delay tradeoff. For nonstationary networks, PLC obtains an [O(), O(log2 (1/)
+ min(c/2−1 , ew /))] utility-backlog tradeoff for distribumax(−c ,e−2
w )
) time, where ew is the prediction
tions that last Θ(
1+a
accuracy, c ∈ (0, 1) and a > 0 is an Θ(1) constant (the
Backpressue algorithm [1] requires an O(−2 ) length for the
same utility performance with a larger backlog).1
iv. We show that for both stationary and non-stationary
system dynamics, PLC detects distribution change O(w) slots
(w is prediction window size) faster with high probability and
achieves a fast O(min(−1+c/2 , ew /) + log2 (1/)) convergence time, which is faster than the O(−1+c/2 + −c ) time of
the OLAC scheme [16], and the O(1/) time of Backpressure.
v. Our results show that state prediction (even imperfect)
can help performance in two ways (a) achieve faster detection,
i.e., detect change w slots faster, and (b) obtain a better
utility-delay tradeoff, i.e., reduce delay to O(ew /+log2 (1/))
for the same utility. They rigorously quantify the benefits of
prediction in four important performance metrics, i.e., utility
(efficiency), delay (quality-of-service), detection (robustness),
and convergence (adaptability).
The rest of the paper is organized as follows. In Section II,
we discuss a few motivating examples in different application
scenarios. We set up the notations in Section III, and present
the problem formulation in Section IV. Background information is provided in Section V. Then, we present PLC in Section
VI, and prove its performance in Section VII. Simulation
results are presented in Section VIII, followed by conclusions
in Section IX. To facilitate reading, all the proofs are placed
in the appendices.
II. M OTIVATING E XAMPLES
In this section, we present a few interesting practical scenarios that fall into our general framework.
Matching in sharing platforms: Consider a Uber-like company that provides ride service to customers. At every time,
customer requests enter the system and available cars join
to provide service. Depending on the environment condition
(state), e.g., traffic condition or customer status, matching
customers to drivers can result in different user satisfaction,
and affect the revenue of the company (utility). The company
gets access to future customer demand and car availability, and
system condition information (prediction), e.g., through reservation or machine learning tools. The objective is to optimally
match customers to cars so that the utility is maximized, e.g.,
[30] and [31].
Energy optimization in mobile networks: Consider a
base-station (BS) sending traffic to a set of mobile users.
The channel conditions (state) between users and the BS
are time-varying. Thus, the BS needs different amounts of
1 Note that when there is no prediction, i.e., w = 0 and e
w = ∞, we
recover previous results of OLAC [16].

3

power for packet transmission (cost) at different times. Due
to higher layer application requirements, the BS is required
to deliver packets to users at pre-specified rates. On the other
hand, the BS can predict future user locations in some short
period of time, from which it can estimate future channel
conditions (prediction). The objective of the BS is to jointly
optimize power allocation and scheduling among users, so
as to minimize energy consumption, while meeting the rate
requirements, e.g., [8], [13]. Other factors such as energy harvesting, e.g., [32], can also be incorporated in the formulation.
Resource allocation in cloud computing: Consider an
operator, e.g., a dispatcher, assigning computing jobs to servers
for processing. The job arrival process is time-varying (state),
and available processing capacities at servers are also dynamic
(state), e.g., due to background processing. Completing users’
job requests brings the operator reward (utility). The operator
may also have information regarding future job arrivals and
service capacities (prediction). The goal is to allocate resources
and balance the loads properly, so as to maximize system
utility. This example can be extended to capture other factors
such as rate scaling [33] and data locality constraints [34].
In these examples and related works, not only can the state
statistics be potentially non-stationary, but the system often
gets access to certain (possibly imperfect) future state information through various prediction techniques. These features
make the problems different from existing settings considered,
e.g., [8] and [15], and require different approaches for both
algorithm design and analysis.
III. N OTATIONS
R denotes the n-dimensional Euclidean space. Rn+ (Rn− )
denotes the non-negative (non-positive) orthant. Bold symbols
x = (x1 , ..., xn ) denote vectors in Rn . w.p.1 denotes “with
probability 1.” k·k denotes P
the Euclidean
norm. For a sequence
t−1 
1
E
y(τ
)
denotes its average
{y(t)}∞
t=0 , y = limt→∞ t
τ =0
(when exists). x  y means xP
j ≥ yj for all j. For distributions
π 1 and π 2 , kπ 1 − π 2 ktv = i |π1i − π2i | denotes the total
variation distance.
n


Pr S(t) = si the probability of being in state si at time t and
denote π(t) = (π1 (t), ..., πM (t)) the state distribution at time
t. The network controller can observe S(t) at the beginning
of every slot t, but the πi (t) probabilities are unknown. To
simplify notations, we divide time into intervals that have the
same distributions and denote {tk , k = 0, 1, ...} the starting
point of the k-th interval Ik , i.e., π(t) = π k for all t ∈ Ik ,
{tk , tk+1 −1}. The length of Ik is denoted by dk , tk+1 −tk .
B. State prediction
At every time slot, the operator gets access to a prediction
module, e.g., a machine learning algorithm, which provides
prediction of future network states. Different from recent
works, e.g., [25], [26] and [35], which assume prediction
models on individual states, we assume that the prediction
module outputs a sequence of predicted distributions Ww (t) ,
{π̂(t), π̂(t + 1), ..., π̂(t + w)}, where w + 1 is the prediction
window size. Moreover, the prediction quality is characterized
by a distribution-accuracy curve {e(0), ..., e(w)} as follows.
For every 0 ≤ k ≤ w, π̂(t + k) satisfies:
||π̂(t + k) − π(t + k)||tv ≤ e(k), ∀ k.

That is, the predicted distribution at time k has a total-variation
error bounded by some e(k) ≥ 0.3 Note that e(k) = 0 for
all 0 ≤ k ≤ w corresponds to a perfect predictor, in that it
predicts the exact distribution in every slot. We assume the
{e(0), ..., e(w)}
Pw curve is known to the operator and denote
1
ew , w+1
k=0 e(k) the average prediction error.
Our prediction model (1) is general and captures key characteristics of several existing prediction models. For instance, it
captures the exact demand statistics prediction model in [29],
where the future demand distribution is known (e(k) = 0 for
all 0 ≤ k ≤ w). It can also capture the window-based predictor
model, e.g., [22], if each π̂(t + k) corresponds to the indicator
value for the true state. Moreover, our model captures the
error-convolution prediction model proposed in [35], [25] and
[26], which captures features of the Wiener filter and Kalman
filter. Specifically, under the convolution model, the predicted
state Ŝ(t + k) at time t satisfies:4

IV. S YSTEM M ODEL
Consider a controller that operates a network with the goal
of minimizing the time average cost, subject to the queue
stability constraint. The network is assumed to operate in
slotted time, i.e., t ∈ {0, 1, 2, ...}, and there are r ≥ 1 queues
in the network.

(1)

kŜ(t + k) − S(t + k)k =

t+k
X
s=t+1

g(t + k − s)a(s),

(2)

where g(s) is the impulse function that captures how error
propagates over time in prediction, and a(s) is assumed to be
a zero mean i.i.d. random variable [25]. Thus, we can compute
the corresponding e(k) once g(s) and a(s) are given.

A. Network state
In every slot t, we use S(t) to denote the current network
state, which indicates the current network parameters, such as
a vector of conditions for each network link, or a collection of
other relevant information about the current network channels
and arrivals. S(t) is independently distributed across time, and
each realization is drawn from a state space of M distinct
states denoted as S = {s1 , s2 , . . . , sM }.2 We denote πi (t) =
2 The independent assumption is made to facilitate presentation and understanding. The results in this paper can likely be generalized to systems where
S(t) evolves according to general time inhomogeneous Markovian dynamics.

C. The cost, traffic, and service
At each time t, after observing S(t) = si , the controller
chooses an action x(t) from a set Xi , i.e., x(t) = xi for some
xi ∈ Xi . The set Xi is called the feasible action set for network
state si and is assumed to be time-invariant and compact for all
si ∈ S. The cost, traffic, and service generated by the chosen
action x(t) = xi are as follows:
3 It makes sense to assume a deterministic upper bound of the difference
here because we are dealing with distributions.
4 In [25] and [26], the state space is a metric space.

4

(a) The chosen action has an associated cost given by the
cost function f (t) = f (si , xi ) : Xi 7→ R+ (or Xi 7→ R−
in reward maximization problems).5
(b) The amount of traffic generated by the action to
queue j is determined by the traffic function Aj (t) =
Aj (si , xi ) : Xi 7→ R+ , in units of packets.
(c) The amount of service allocated to queue j is given
by the rate function µj (t) = µj (si , xi ) : Xi 7→ R+ , in
units of packets.
Here Aj (t) can include both exogenous arrivals from outside
the network to queue j, and endogenous arrivals from other
queues, i.e., transmitted packets from other queues to queue j.
We assume the functions −f (si , ·), µj (si , ·) and Aj (si , ·) are
time-invariant, their magnitudes are uniformly upper bounded
by some constant δmax ∈ (0, ∞) for all si , j, and they are
known to the operator. Note that this formulation is general
and models many network problems, e.g., [8], [15], and [36].
D. Problem formulation
Let q(t) = (q1 (t), ..., qr (t))T ∈ Rr+ , t = 0, 1, 2, ... be
the queue backlog vector process of the network, in units of
packets. We assume the following queueing dynamics:


qj (t + 1) = max qj (t) − µj (t) + Aj (t), 0 , ∀j,
(3)
and q(0) = 0. By using (3), we assume that when a queue does
not have enough packets to send, null packets are transmitted,
so that the number of packets entering qj (t) is equal to Aj (t).
We adopt the following notion of queue stability [1]:
q av , lim sup
t→∞

t−1 r
1 XX 
E qj (τ ) < ∞.
t τ =0 j=1

(4)

0
distribution π 0 = (π10 , ..., πM
) with kπ 0 − π k ktv ≤ k , there
(si ) z=1,2,...,∞
(s )
exist a set of actions {xz }i=1,...,M with xz i ∈ Xi and
P (si )
(si )
variables ϑz ≥ 0 for all si and z with z ϑz = 1 for all
si (possibly depending on π 0 ), such that:
X X
(si )
(si )
i)
πi0
ϑ(s
z [Aj (si , xz ) − µj (si , xz )] ≤ −η0 , ∀ j, (6)
si

Assumption 1 corresponds to the “slack” condition commonly assumed in the literature with k = 0, e.g., [36] and
[37].7 With k > 0, we assume that when two systems are
relatively close to each other (in terms of π), they can both
be stabilized by some (possibly different) randomized control
policy that results in the same slack.
E. Discussion of the model
Two key differences between our model and previous ones
include (i) π(t) itself can be time-varying and (ii) the operator
gets access to a prediction window Ww (t) that contains
imperfect prediction. These two extensions are important to the
current network control literature. First, practical systems are
often non-stationary. Thus, system dynamics can have timevarying distributions. Thus, it is important to have efficient algorithms to automatically adapt to the changing environment.
Second, prediction has recently been made increasingly accurate in various contexts, e.g., user mobility in cellular network
and harvestable energy availability in wireless systems, by data
collection and machine learning tools. Thus, it is critical to
understand the fundamental benefits and limits of prediction,
and its optimal usage.

Π
to
We use Π to denote an action-choosing policy, and use fav
denote its time average cost, i.e.,
Π
fav
, lim sup
t→∞

t−1
1X  Π
E f (τ ) ,
t τ =0

(5)

Π

where f (τ ) is the cost incurred at time τ under policy Π.
We call an action-choosing policy feasible if at every time
slot t it only chooses actions from the feasible action set Xi
when S(t) = si . We then call a feasible action-choosing policy
under which (4) holds a stable policy.
In every slot, the network controller observes the current
network state and prediction, and chooses a control action,
with the goal of minimizing the time average cost subject to
network stability. This goal can be mathematically stated as:6
Π
(P1) min : fav
, s.t. (4).

In the following, we call (P1) the stochastic problem, and we
π
to denote its optimal solution given a fixed distribution
use fav
π. It can be seen that the examples in Section II can all be
modeled by our stochastic problem framework.
Throughout our paper, we make the following assumption.

V. T HE D ETERMINISTIC P ROBLEM
For our later algorithm design and analysis, here we define
the deterministic problem and its dual problem [38]. Specifically, the deterministic problem for a given distribution π is
defined as follows [38]:
X
min : V
πi f (si , x(si ) )
(7)
s

Xi
s.t.
πi [Aj (si , x(si ) ) − µj (si , x(si ) )] ≤ 0, ∀ j,
si

x(si ) ∈ Xi

∀ i = 1, 2, ..., M.

Q
Here the minimization is taken over x ∈
i Xi , where
x = (x(s1 ) , ..., x(sM ) )T , and V ≥ 1 is a positive constant
introduced for later analysis. The dual problem of (7) can be
obtained as follows:
max : g(γ, π),

s.t. γ  0,

(8)

where g(γ, π) is the dual function for problem (7) and is
defined as:
X 
g(γ, π) = inf
πi V f (si , x(si ) )
(9)
x(si ) ∈Xi

Assumption 1. For every system distribution π k , there exists
a constant k = Θ(1) > 0 such that for any valid state

si

+

X
j

5 We

use cost and utility interchangeably in this paper.
6 When π(t) is time-varying, the optimal system utility needs to be defined
carefully. We will specify it when discussing the corresponding results.

z

where η0 = Θ(1) > 0 is independent of π 0 . ♦

7 Note




(si )
(si )
γj Aj (si , x ) − µj (si , x ) .

that η0 ≥ 0 is a necessary condition for network stability [1].

5

γ = (γ1 , ..., γr )T is the Lagrange multiplier of (7). It is well
known that g(γ, π) in (9) is concave in the vector γ for all γ ∈
Rr . Hence, the problem (8) can usually be solved efficiently,
particularly when the cost functions and rate functions are
separable over different network components [39]. We use γ ∗π
to denote the optimal multiplier corresponding to a given π
∗
and sometimes omit the subscript when it is clear. Denote gπ
the optimal value of (8) under a fixed distribution π. It was
shown in [40] that:
π
∗
fav
= gπ
.

(10)

∗
gπ

That is,
characterizes the optimal time average cost of the
stochastic problem. For our analysis, we make the following
assumption on the g(γ, π k ) function.
Assumption 2. For every system distribution π k , g(γ, π k )
has a unique optimal solution γ ∗πk 6= 0 in Rr . ♦
Assumption 2 is also commonly assumed and holds for
many network utility optimization problems, e.g., [8] and [38].
VI. P REDICTIVE L EARNING - AIDED C ONTROL
In this section, we present the predictive learning-aided control algorithm (PLC). PLC contains three main components:
a distribution estimator, a learning component, and an online
queue-based controller. Below, we first present the estimation
part. Then, we present the PLC algorithm.

Wm (t)

=

{bsd (t), ..., bed (t)},

(11)

{bm (t), ..., min[bsd (t), bm (t) + Tl ]}.

(12)

Here bsd (t) and bm (t) mark the beginning slots of Wd (t) and
Wm (t), respectively, and bed (t) marks the end of Wd (t). Ideally, Wd (t) contains the most recent d samples (including the
prediction) and Wm (t) contains Tl subsequent samples (where
Tl is a pre-specified number). We denote Wm (t) = |Wm (t)|
and Wd (t) = |Wd (t)|. Without loss of generality, we assume
that d ≥ w+1. This is a reasonable assumption, as we see later
that d grows with our control parameter V while prediction
power is often limited in practice.
We use π̂ d (t) and π̂ m (t) to denote the empirical distributions of Wd (t) and Wm (t), i.e.,8


t−1
X
X
1
d
π̂i (t) =
1[S(τ )=si ] +
π̂i (τ )
d
τ ∈Ww (t)

τ =(t+w−d)+

π̂im (t)
8 Note

=

1
Wm (t)

X

Wm (t)

1[S(τ )=si ] .

τ ∈Wm (t)

that this is only one way to utilize the samples. Other methods such
as EWMA can also be applied when appropriate.

Wd (t)

t

bm (t)

bm (t + 1)

Here we specify the distribution estimator. The idea is
to first combine the prediction in Ww (t) with historic state
information to form an average distribution, and then perform
statistical comparisons for change detection. We call the
module the average distribution estimate (ADE).
Specifically, ADE maintains two windows Wm (t) and
Wd (t) to store network state samples, i.e.,
=

The idea of ADE is shown in Fig. 4.

Wm (t + 1)

A. Distribution estimation and change detection

Wd (t)

That is, π̂ d (t) is the average of the empirical distribution of the
“observed” samples in Wd (t) and the predicted distribution,
whereas π̂ m (t) is the empirical distribution.
The formal procedure of ADE is as follows (parameters
Tl , d, d will be specified later).
Average Distribution Estimate (ADE(Tl , d, d )): Initialize
bsd (0) = 0, bed (0) = t + w and bm (0) = 0, i.e.,
Wd (t) = {0, ..., t + w} and Wm (t) = φ. At every
time t, update bsd (t), bed (t) and bm (t) as follows:
(i) If Wm (t) ≥ d and ||π̂ d (t)− π̂ m (t)||tv > d , set bm (t) =
t + w + 1 and bsd (t) = bed (t) = t + w + 1.
(ii) If Wm (t) = Tl and there exists k such that ||π̂(t + k) −
l)
, set bm (t) = t + w + 1
π̂ m (t)||tv > e(k) + 2M√log(T
Tl
s
e
and bd (t) = bd (t) = t + w + 1. Mark t + w + 1 a reset
point.
(iii) Else if t ≤ bsd (t − 1), bm (t) = bm (t − 1), bsd (t) =
bsd (t − 1), and bed (t) = bed (t − 1).9
(iv) Else set bm (t) = bm (t − 1), bsd (t) = (t + w − d)+ and
bed (t) = t + w.
Output an estimate at time t as follow:

m
if Wm (t) ≥ Tl
Pπ̂w (t)
♦ (13)
π a (t) =
1
π̂(t
+
k)
else
k=0
w+1
Wm (t)

t+w

Wd (t)

t

t+w
bm (t + 1)

Wd (t + 1)

t+1

bm (t)

t+w+1

t+1

bsd (t + 1)

bed (t + 1)

Fig. 2. Evolution of Wm (t) and Wd (t). (Left) No change detected: Wd (t)
advances by one slot and Wm (t) increases its size by one. (Right) Change
detected: both windows set their start and end points to t + w + 1.

The intuition of ADE is that if the environment is changing
over time, we should rely on prediction for control. Else
if the environment is stationary, then one should use the
average distribution learned over time to combat the potential
prediction error that may affect performance. Tl is introduced
to ensure the accuracy of the empirical distribution and can
be regarded as the confidence-level given to the distribution
stationarity. A couple of√technical remarks are also ready. (a)
The term 2M log(Tl )/ Tl is to compensate the inevitable
deviation of π̂ m (t) from the true value due to randomness. (b)
In Wm (t), we only use the first Tl historic samples. Doing so
avoids random oscillation in estimation and facilitates analysis.
Note that prediction is used in two ways in ADE. First, it is
used in step (i) to decide whether the empirical distributions
match (average prediction). Second, it is used to check whether
prediction is consistent with the history (individual prediction).
The reason for having this two-way utilization is to accommodate general prediction types. For example, suppose each
π̂(t + k) denotes the indicator for state S(t + k), e.g., as in the
look-ahead window model [22]. Then, step (ii) is loose since
e(k) is large, but step (i) will be useful. On the other hand,
when π̂(t + k) gets closer to the true distribution, both steps
will be useful.
9 This step is evoked after we set b (t0 ) = bs (t0 ) = t0 + w + 1 ≥ t for
m
d
some time t0 , in which case we the two windows remain unchanged until t
0
is larger than t + w + 1.

6

VII. P ERFORMANCE A NALYSIS

B. Predictive learning-aided control
We are now ready to present the PLC algorithm. Our
algorithm is shown in Fig. 1, and the formal description is
given below.
Predictive Learning-aided Control (PLC): At time t, do:
• (Estimation) Update π a (t) with ADE(Tl , d, d ).
• (Learning) Solve the following empirical problem and
compute the optimal Lagrange multiplier γ ∗ (t), i.e.,
max : g(γ, π a (t)),

s.t. γ  0,

(14)

If γ ∗ (t) = ∞, set γ ∗ (t) = V log(V ) · 1. If Wm (t − 1) =
Tl and π a (t) 6= π a (t − 1), set q(t + w + 1) = 0.
• (Control) At every time slot t, observe the current
network state S(t) and the backlog q(t). If S(t) = si ,
choose x(si ) ∈ Xi that solves the following:
r
X


max : −V f (si , x) +
Qj (t) µj (si , x) − Aj (si , x)
j=1

s.t.

x ∈ Xi ,

(15)
(γj∗ (t)

+

where Qj (t) , qj (t) +
− θ) . Then, update the
queues according to (3) with Last-In-First-Out. ♦
For readers who are familiar with the Backpressure (BP)
algorithm, e.g., [1] and [41], the control component of PLC
is the BP algorithm with its queue vector augmented by the
empirical multiplier γ ∗ (t). Also note that packet dropping is
introduced to enable quick adaptation to new dynamics if there
is a distribution change. It occurs only when a long-lasting
distribution ends, which avoids dropping packets frequently
in a fast-changing environment.
We have the following remarks. (i) Prediction usage:
Prediction is explicitly incorporated into control by forming
an average distribution and converting the distribution estimate into a Lagrange multiplier. The intuition for having
Tl = max(V c , e−2
w ) is that when ew is small, we should rely
on prediction as much as possible, and only switch to learned
statistics when it is sufficiently accurate. (ii) Connection
with RHC: It is interesting to see that when Wm (t) < Tl ,
PLC mimics the commonly adopted receding-horizon-control
method (RHC), e.g., [28]. The main difference is that, in
RHC, future states are predicted and are directly fed into a
predictive optimization formulation for computing the current
action. Under PLC, distribution prediction is combined with
historic state information to compute an empirical multiplier
for augmenting the controller. In this regard, PLC can be
viewed as exploring the benefits of statistics whenever it finds
the system stationary (and does it automatically). (iii) Parameter selection: The parameters in PLC can be conveniently
chosen as follows. First, fix a detection error probability
δ = V − log(V ) . Then, choose a small d and a d that satisfies
d ≥ 4 log(V )2 /2d +w+1. Finally, choose Tl = max(V c , e−2
w )
and θ according to (17).
While recent works [16] and [17] also design learningbased algorithms that utilize historic information, they do not
consider prediction and do not provide insight on its benefits
and the impact of prediction error. Moreover, [16] focuses on
stationary systems and [17] adopts a frame-based scheme.

This section presents the performance results of PLC. We
focus on four metrics, detection efficiency, network utility,
service delay, and algorithm convergence. The metrics are
chosen to represent robustness, resource utilization efficiency,
quality-of-service, and adaptability, respectively.
A. Detection and estimation
We first look at the detection and estimation part. The
following lemma summarizes the performance of ADE, which
is affected by the prediction accuracy as expected.
Lemma 1. Under ADE(Tl , d, d ), we have:
(a) Suppose at a time t, π(τ1 ) = π 1 for τ1 ∈ Wd (t) and
π(τ2 ) = π 2 6= π 1 for all τ2 ∈ Wm (t) and max |π1i − π2i | >
4(w + 1)ew /d. Then, by choosing d < 0 , max |π1i −
π2i |/2 − (w + 1)ew /d and d > ln 4δ · 212 + w + 1, if Wm (t) ≥
d
Wd (t) = d, with probability at least 1−δ, bm (t+1) = t+w+1
and Wm (t + 1) = φ, i.e., Wm (t + 1) = 0.
(b) Suppose π(t) = π ∀ t. Then, if Wm (t) ≥ Wd (t) = d,
under ADE(Tl , d, d ) with d ≥ ln 4δ · 22 +w+1, with probability
d

−2 log(Tl )

at least 1 − δ − (w + 1)M Tl

, bm (t + 1) = bm (t). ♦

Proof. See Appendix A.
Lemma 1 shows that for a stationary system, i.e., π(t) = π,
Wm (t) will likely grow to a large value (Part (b)), in which
case π a (t) will stay close to π most of the time. If instead
Wm (t) and Wd (t) contain samples from different distributions, ADE will reset Wm (t) with high probability. Note that
since the first w + 1 slots are predicted, this means that PLC
detects changes O(w) slots faster compared to that without
prediction. The condition max |π1i − π2i | > 4(w + 1)ew /d
can be understood as follows. If we want to distinguish
two different distributions, we want the detection threshold
to be no more than half of the distribution distance. Now
with prediction, we want the potential prediction error to
be no more than half of the threshold, hence the factor 4.
Also note that the delay involved in detecting a distribution change is nearly order-optimal, in that it requires only
d = O(1/ mini |π1i − π2i |2 ) time, which is known to be
necessary for distinguishing two distributions [42]. Moreover,
d = O(ln(1/δ)) shows that a logarithmic window size is
enough to ensure a high detection accuracy.
B. Utility and delay
In this section, we look at the utility and delay performance
of PLC. To state our results, we first define the following
structural property of the system.
Definition 1. A system is called polyhedral with parameter
ρ > 0 under distribution π if the dual function g(γ, π)
satisfies:
g(γ ∗ , π) ≥ g(γ, π) + ρkγ ∗π − γk. ♦

(16)

The polyhedral property typically holds for practical systems, especially when action sets are finite (see [38] for more
discussions).

7

1) Stationary system: We first consider stationary systems,
i.e., π(t) = π. Our theorem shows that PLC achieves the nearoptimal utility-delay tradeoff for stationary networks. This
result is important, as any good adaptive algorithm must be
able to handle stationary settings well.
Theorem 1. Suppose π(t) = π, the system is polyhedral with
ρ = Θ(1), ew > 0, and q(0) = 0. Choose 0 < d < 0 ,
−2
2(w + 1)ew /d, d = log(V )3 /2d , Tl = max(V c , ew
) for c ∈
(0, 1) and
V
(17)
θ = 2 log(V )2 (1 + √ ),
Tl
Then, with a sufficiently large V , PLC achieves the following:
PLC
π
(a) Utility: fav
= fav
+ O(1/V )
(b) Delay: For all but an O( V1 ) fraction of traffic, the
average packet delay is D = O(log(V )2 )
(c) Dropping: The packet dropping rate is O(V −1 ). ♦
Proof. See Appendix B.
Choosing  = 1/V , we see that PLC achieves the nearoptimal [O(), O(log(1/)2 )] utility-delay tradeoff. Moreover,
prediction enables PLC to also greatly reduce the queue size
(see Part (b) of Theorem 2). Our result is different from the
results in [20] and [22] for proactive service settings, where
delay vanishes as prediction power increases. This is because
we only assume observability of future states but not preservice, and highlights the difference between pre-service and
pure prediction. Note that the performance of PLC does not
depend heavily on d in Theorem 1. The value d is more
crucial for non-stationary systems, where a low false-negative
rate is critical for performance. Also note that although packet
dropping can occur during operation, the fraction of packets
dropped is very small, and the resulting performance guarantee
cannot be obtained by simply dropping the same amount of
packets, in which case the delay will still be Θ(1/).
Although Theorem 1 has a similar form as those in [17] and
[16], the analysis is very different, in that (i) prediction error
must be taken into account, and (ii) PLC performs sequential
detection and decision-making.
2) Piecewise stationary system: We now turn to the nonstationary case and consider the scenario where π(t) changes
over time. In this case, we see that prediction is critical as
it significantly accelerates convergence and helps to achieve
good performance when each distribution only lasts for a
finite time. As we know that when the distribution can change
arbitrarily, it is hard to even define optimality. Thus, we
consider the case when the system is piecewise stationary, i.e.,
each distribution lasts for a duration of time, and study how
the algorithm optimizes the performance for each distribution.
The following theorem summarizes the performance of PLC
in this case. In the theorem, we define Dk , tk +d−t∗ , where
t∗ , sup{t < tk + d : t is a reset point}, i.e., the most recent
ending time after having a cycle with size Tl (recall that reset
points are marked in step (ii) of ADE and d ≥ w + 1).
Theorem 2. Suppose dk ≥ 4d and the system is polyhedral
with ρ = Θ(1) for all k,. Also, suppose there exists ∗0 =
0
Θ(1) > 0 such that ∗0 ≤ inf k,i |πki − πk−1i
| and q(0) = 0.

Choose d < ∗0 in ADE, and choose d, θ and Tl as in Theorem
1. Fix any distribution π k with length dk = Θ(V 1+a Tl ) for
some a = Θ(1) > 0. Then, under PLC with a sufficiently large
V , if Wm (tk ) only contains samples after tk−1 , we achieve
the following with probability 1 − O(V −3 log(V )/4 ):
)
PLC
πk
(a) Utility: fav
= fav
+ O(1/V ) + O( DTkl Vlog(V
1+a )
1−c/2
(b) Queueing: q av = O((min(V
, V ew )+1) log2 (V )+
Dk + d).
(c) In particular, if dk−1 = Θ(Tl V a1 ) for a1 = Θ(1) > 0
and Wm (tk−1 ) only contains samples after tk−2 , then with
PLC
πk
probability 1 − O(V −2 ), Dk = O(d), fav
= fav
+ O(1/V )
2
1−c/2
, V ew ) + log (V )). ♦
and q av = O(min(V
Proof. See Appendix C.
A few remarks are in place. (i) Theorem 2 shows that,
with an increasing prediction power, i.e., a smaller ew , it is
possible to simultaneously reduce network queue size and the
time it takes to achieve a desired average performance (even
if we do not execute actions ahead of time). The requirement
dk = Θ(V 1+a Tl ) can be strictly less than the O(V 2−c/2+a )
requirement for RLC in [17] and the O(V 2 ) requirement of
BP for achieving the same average utility. This implies that
PLC finds a good system operating point faster than previous
algorithms, a desirable feature for network algorithms. (ii) The
dependency on Dk here is necessary. This is because PLC
does not perform packet dropping if previous intervals do
not exceed length Tl . As a result, the accumulated backlog
can affect decision making in the current interval. Fortunately
the queues are shown to be small and do not heavily affect
performance (also see simulations). (iii) To appreciate the
queueing result, note that BP (without learning) under the same
setting will result in an O(V ) queue size.
Compared to the analysis in [17], one complicating factor
in proving Theorem 2 is that ADE may not always throw
away samples from a previous interval. Instead, ADE ensures
that with high probability, only o(d) samples from a previous
interval will remain. This ensures high learning accuracy and
fast convergence of PLC. One interesting special case not
covered in the last two theorems is when ew = 0. In this
case, prediction is perfect
Pw and Tl = ∞, and PLC always runs
1
with π a (t) = w+1
k=0 π̂(t + k), which is the exact average
distribution. For this case, we have the following result.
Theorem 3. Suppose ew = 0 and q(0) = 0. Then, PLC
achieves the following:
(a) Suppose π(t) = π and the system is polyhedral with
ρ = Θ(1). Then, under the conditions of Theorem 1, PLC
achieves the [O(), O(log(1/)2 )] utility-delay tradeoff.
(b) Suppose dk ≥ d log2 (V ) and the system is polyhedral
with ρ = Θ(1) under each π k . Under the conditions of Theorem 2, for an interval dk ≥ V 1+ for
 any  > 0, PLC achieves
PLC
πk
+ O(1/V ) and E q(tk ) = O(log4 (V )). ♦
that fav
= fav
Proof. See Appendix D.
The intuition here is that since prediction is perfect, π a (t) =
π k during [tk + d, tk+1 − w]. Therefore, a better performance
can be achieved. The key challenge in this case is that PLC
does not perform any packet dropping. Thus, queues can build

8

A1 (t)

up and one needs to show that the queues will be concentrating
around θ · 1 even when the distribution changes.
C. Convergence time
We now consider the algorithm convergence time, which
is an important evaluation metric and measures how long it
takes for an algorithm to reach its steady-state. While recent
works [17], [16], [43], and [44] also investigate algorithm
convergence time, they do not consider utilizing prediction
in learning and do not study the impact of prediction error.
To formally state our results, we adopt the following definition of convergence time from [16].
Definition 2. Let ζ > 0 be a given constant and let π be
a system distribution. The ζ-convergence time of a control
algorithm, denoted by Tζ , is the time it takes for the effective
queue vector Q(t) to get to within ζ distance of γ ∗π , i.e.,
Tζ , inf{t | ||Q(t) − γ ∗π || ≤ ζ}. ♦

(18)

We have the following theorem. Recall that w ≤ d =
Θ(log(V )2 ).
Theorem 4. Assuming all conditions in Theorem 2, except
that π(t) = π k for all t ≥ tk . If ew = 0, under PLC,

E TG
= O(log4 (V )).
(19)
Else suppose ew > 0. Under the conditions of Theorem 2,
with probability 1 − O( V 1Tl + VD2kTl ),

E TG
= O(θ + Tl + Dk + w)
(20)

E TG1
= O(d).
(21)
Here G = Θ(1) and G1 = Θ(Dk + 2 log(V )2 (1 + V ew )),
where Dk is defined in Theorem 2 as the most recent reset
point prior to tk . In particular, if dk−1 = Θ(Tl V a1 ) for some
2
a1 = Θ(1) > 0 and θ = O(log(V
 ) ), then with2 probability
−2
1 − O(V ), Dk = O(d), and E TG1 = O(log (V )). ♦
Proof. See Appendix E.
Here the assumption π(t) = π k for all t ≥ tk is made to
avoid the need for specifying the length of the intervals. It is
interesting to compare (19), (20) and (21) with the convergence
results in [16] and [17] without prediction, where it was shown
that the convergence time is O(V 1−c/2 log(V )2 + V c ), with
a minimum of O(V 2/3 ). Here although we may still need
O(V 2/3 ) time for getting into an G-neighborhood (depending
on ew ), getting to the G1 -neighborhood can take only an
O(log2 (V )) time, which is much faster compared to previous
results, e.g., when ew = o(V −2 ) and Dk = O(w), we have
G1 = O(log2 (V )). This confirms our intuition that prediction accelerates algorithm convergence and demonstrates the
power of (even imperfect) prediction.

A2 (t)

CH2 (t)

Fig. 3. A single-server two-queue system. Each queue receives random
arrivals. The server can only serve one queue at a time.

Aj (t) denotes the number of arriving packets to queue j
at time t. We assume Aj (t) is i.i.d. with either 1 or 0 with
probabilities pj and 1 − pj , and use p1 = 0.3 and p2 = 0.6.
Thus, λ1 = 0.3 and λ2 = 0.6. Each queue has a time-varying
channel condition. We denote CHj (t) the channel condition
of queue j at time t. We assume that CHj (t) ∈ CHj with
CH1 = {0, 1} and CH2 = {1, 2}. The channel distributions
are assumed to be uniform. At each time, the server determines
the power allocation to each queue. We use Pj (t) to denote the
power allocated to queue j at time t. Then, the instantaneous
service rate qj (t) gets is given by:
µj (t) = log(1 + CHj (t)Pj (t)).

(22)

We assume that Pj (t) ∈ P = {0, 1, 2} for j = 1, 2, and at
each time only one queue can be served. The objective is to
stabilize the system with minimum average power. It can be
verified that Assumptions 1 and 2 both hold in this example.
We compare PLC with BP in two cases. The first case
is a stationary system where the arrival distributions remain
constant. The second case is a non-stationary case, where we
change the arrival distributions during the simulation. In both
cases we simulate the system for T = 5 × 104 slots. We
simulate V ∈ {20, 50, 100, 150, 200, 300}. We set w + 1 = 5
and generate prediction error by adding uniform random noise
to distributions with max value e(k) (specified below). We also
use d = 0.1, δ = 0.005 and d = 2 ln(4/δ)/2 + w + 1. We
also simplify the choice of θ and set it to θ = log(V )2 .
We first examine the long-term performance. Fig. 4 shows
the utility-delay performance of PLC compared to BP in the
stationary setting. There are two PLC we simulated, one is
with ew = 0 (PLC) and the other is with ew = 0.04 (PLCe). From the plot, we see that both PLCs achieve a similar
utility as BP, but guarantee a much smaller delay. The reason
PLC-e has a better performance is due to packet dropping. We
observe around an average packet dropping rate of 0.06. As
noted before, the delay reduction of PLC cannot be achieved
by simply dropping this amount of packets.
1.16

1400

Power

Queue

1.14

1200

1.12

PLC
BP
PLC−e

1000
1.1
800

1.08

PLC
BP
PLC−e

1.06

VIII. S IMULATION
In this section, we present simulation results of PLC in
a two-queue system shown in Fig. 3. Though being simple,
the system models various settings, e.g., a two-user downlink
transmission problem in a mobile network, a CPU scheduling
problem with two applications, or an inventory control system
where two types of orders are being processed.

CH1 (t)

1.04

600

400

1.02
200

1
0.98

0

50

100

150

V

200

250

300

0

0

50

100

150

200

250

300

V

Fig. 4. Utility and delay performance comparison between PLC and BP.

Next, we take a look at the detection and convergence

9

performance of PLC. Fig. 5 shows the performance of PLC
with perfect prediction (ew = 0), PLC with prediction error
(ew = 0.04) and BP when the underlying distribution changes.
Specifically, we run the simulation for T = 5000 slots and
start with the arrival rates of p1 = 0.2 and p2 = 0.4. Then,
we change them to p1 = 0.3 and p2 = 0.6 at time T /2.
300

Q(t) − PLC (ew=0)
250

200

Q(t) − PLC (ew=0.04)
150

Actual Queue − BP

100

Actual Queue − PLC (ew=0)
50

Actual Queue − PLC (ew=0.04)
0

0

500

1000

1500

2000

2500

3000

3500

4000

4500

5000

Time

Fig. 5. Convergence comparison between PLC and BP for queue 1 under
V = 100. Here PLC (ew = 0) is the perfect case and PLC (ew = 0.04)
contains prediction error. Both versions converge much faster compared to
BP.

We can see from the green and red curves that PLC quickly
adapts to the change and modifies the Lagrange multiplier
accordingly. By doing so, the actual queues under PLC (the
purple and the brown curves) remain largely unaffected. For
comparison, we see that BP takes a longer time to adapt to the
new distribution and results in a larger queue size. We also see
that during the 5000 slots, PLC (ew = 0.04) drops packets 3
times (zero for the first half), validating the results in Lemma 1
and Theorem 1. Moreover, after the distribution change, PLC
(ew = 0.04) quickly adapts to the new equilibrium, despite
having imperfect prediction. The fast convergence result also
validates our theorem about short term utility performance
under PLC. Indeed, if we look at slots during time 200 − 500,
and slots between 2500−3500, we see that when BP is learning
the target backlog, PLC already operates near the optimal
mode. This shows the benefits of prediction and learning in
stochastic network control.
IX. C ONCLUSION
We investigate the problem of stochastic network optimization in the presence of imperfect state prediction and
non-stationarity. Based on a novel distribution-accuracy curve
prediction model, we develop the predictive learning-aided
control (PLC) algorithm. PLC is an online algorithm that requires zero a-prior system statistical information, and contains
three main functionalities, sequential distribution estimation
and change detection, dual learning, and online queue-based
control. We show that PLC simultaneously achieves good longterm performance, short-term queue size reduction, accurate
change detection, and fast algorithm convergence. Our results
demonstrate that state prediction (even imperfect) can help
improve performance and quantify the benefits of prediction in
four important metrics, i.e., utility (efficiency), delay (qualityof-service), detection (robustness), and convergence (adaptability). They provide new insight for joint prediction, learning
and optimization in stochastic networks.

R EFERENCES
[1] L. Georgiadis, M. J. Neely, and L. Tassiulas. Resource Allocation and
Cross-Layer Control in Wireless Networks. Foundations and Trends in
Networking Vol. 1, no. 1, pp. 1-144, 2006.
[2] Y. Chon, E. Talipov, H. Shin, and H. Cha. Mobility prediction-based
smartphone energy optimization for everyday location monitoring. ACM
Sensys, 2011.
[3] G. Ananthanarayanan, A. Ghodsi, S. Shenker, and I. Stoica. Effective
straggler mitigation: Attack of the clones. ACM NSDI, 2014.
[4] X. Zou, J. Erman, V. Gopalakrishnan, E. Halepovic, R. Jana, . Jin,
J. Rexford, and R. K. Sinha. Can accurate predictions improve video
streaming in cellular networks? ACM HotMobile, 2015.
[5] TechCrunch.
Amazon
patents
“anticipatory”
shipping
to
start
sending
stuff
before
you’ve
bought
it.
http://techcrunch.com/2014/01/18/amazon-pre-ships/, Jan 2014.
[6] Adweek. Facebook begins prefetching to improve mobile site speed.
http://www.adweek.com/socialtimes/prefetching/644281, Aug 2016.
[7] M. Gatzianas, L. Georgiadis, and L. Tassiulas. Control of wireless
networks with rechargeable batteries. IEEE Trans. on Wireless Communications, Vol. 9, No. 2, Feb. 2010.
[8] A. Eryilmaz and R. Srikant. Fair resource allocation in wireless networks
using queue-length-based scheduling and congestion control. IEEE/ACM
Trans. Netw., 15(6):1333–1344, 2007.
[9] B. Li and R. Srikant. Queue-proportional rate allocation with per-link
information in multihop networks. Proceedings of ACM Sigmetrics,
2015.
[10] B. Ji and Y. Sang. Throughput characterization of node-based scheduling
in multihop wireless networks: A novel application of the gallaiedmonds structure theorem. Proceedings of ACM MobiHoc, 2016.
[11] H. Zhao, C. H. Xia, Z. Liu, and D. Towsley. A unified modeling
framework for distributed resource allocation of general fork and join
processing networks. Proc. of ACM Sigmetrics, 2010.
[12] L. Jiang and J. Walrand. Stable and utility-maximizing scheduling for
stochastic processing networks. Allerton Conference on Communication,
Control, and Computing, 2009.
[13] R. Urgaonkar and M. J. Neely. Opportunistic scheduling with reliability
guarantees in cognitive radio networks. IEEE Transactions on Mobile
Computing, 8(6):766–777, June 2009.
[14] H. Su and A. El Gamal. Modeling and analysis of the role of fastresponse energy storage in the smart grid. Proc. of Allerton, 2011.
[15] M. J. Neely R. Urgaonkar, B. Urgaonkar and A. Sivasubramaniam.
Optimal power cost management using stored energy in data centers.
Proceedings of ACM Sigmetrics, June 2011.
[16] L. Huang, X. Liu, and X. Hao. The power of online learning in stochastic
network optimization. Proceedings of ACM Sigmetrics, 2014.
[17] L. Huang. Receding learning-aided control in stochastic networks. IFIP
Performance, Oct 2015.
[18] J. Tadrous, A. Eryilmaz, and H. El Gamal. Proactive resource allocation:
harnessing the diversity and multicast gains. IEEE Tansactions on
Information Theory, 2013.
[19] J. Spencer, M. Sudan, and K Xu. Queueing with future information.
ArXiv Technical Report arxiv:1211.0618, 2012.
[20] S. Zhang, L. Huang, M. Chen, and X. Liu. Proactive serving reduces
user delay exponentially. Proceedings of ACM Sigmetrics (Poster Paper),
2014.
[21] K. Xu. Necessity of future information in admission control. Operations
Research, 2015.
[22] L. Huang, S. Zhang, M. Chen, and X. Liu. When Backpressure meets
Predictive Scheduling. Proceedings of ACM MobiHoc, 2014.
[23] L. Muppirisetty, J. Tadrous, A. Eryilmaz, and H. Wymeersch. On
proactive caching with demand and channel uncertainties. Proceedings
of Allerton Conference, 2015.
[24] S. Zhao, X. Lin, and M. Chen. Peak-minimizing online ev charging:
Price-ofuncertainty and algorithm robustification. Proceedings of IEEE
INFOCOM, 2015.
[25] N. Chen, A. Agarwal, A. Wierman, S. Barman, and L. L. H. Andrew.
Online convex optimization using predictions. Proceedings of ACM
Sigmetrics, 2015.
[26] N. Chen, J. Comden, Z. Liu, A. Gandhi, and A. Wierman. Using
predictions in online optimization: Looking forward with an eye on the
past. Proceedings of ACM Sigmetrics, 2016.
[27] M. Hajiesmaili, C. Chau, M. Chen, and L. Huang. Online microgrid
energy generation scheduling revisited: The benefits of randomization
and interval prediction. Proceedings of ACM e-Energy, 2016.
[28] M. Lin, Z. Liu, A. Wierman, and L. L. H. Andrew. Online algorithms
for geographical load balancing. IEEE IGCC, 2012.

10

[29] J. Tadrous, A. Eryilmaz, and H. El Gamal. Pricing for demand
shaping and proactive download in smart data networks. The 2nd
IEEE International Workshop on Smart Data Pricing (SDP), INFOCOM,
2013.
[30] M. Qu, H. Zhu, J. Liu, G. Liu, and H. Xiong. A cost-effective
recommender system for taxi drivers. ACM KDD, 2014.
[31] L. Huang.
The value-of-information in matching with queues.
IEEE/ACM Trans. on Netwroking, to appear.
[32] O. Simeone C. Tapparello and M. Rossi. Dynamic compressiontransmission for energy-harvesting multihop networks with correlated
sources. IEEE/ACM Trans. on Networking, 2014.
[33] Y. Yao, L. Huang, A. Sharma, L. Golubchik, and M. J. Neely. Data
centers power reduction: A two time scale approach for delay tolerant
workloads. IEEE Transactions on Parallel and Distributed Systems
(TPDS), vol. 25, no. 1, pp. 200-211, Jan 2014.
[34] W. Wang, K. Zhu, Lei Ying, J. Tan, and L. Zhang. Map task
scheduling in mapreduce with data locality: Throughput and heavytraffic optimality. IEEE/ACM Transactions on Networking, to appear.
[35] L. Gan, A. Wierman, U. Topcu, N. Chen, and S. Low. Real-time
deferrable load control: Handling the uncertainties of renewable generation. ACM e-Energy, 2013.
[36] L. Ying, S. Shakkottai, and A. Reddy. On combining shortest-path and
back-pressure routing over multihop wireless networks. Proceedings of
IEEE INFOCOM, April 2009.
[37] L. Bui, R. Srikant, and A. Stolyar. Novel architectures and algorithms for
delay reduction in back-pressure scheduling and routing. Proceedings
of IEEE INFOCOM Mini-Conference, April 2009.
[38] L. Huang and M. J. Neely. Delay reduction via Lagrange multipliers
in stochastic network optimization. IEEE Trans. on Automatic Control,
56(4):842–857, April 2011.
[39] D. P. Bertsekas, A. Nedic, and A. E. Ozdaglar. Convex Analysis and
Optimization. Boston: Athena Scientific, 2003.
[40] L. Huang and M. J. Neely.
Max-weight achieves the exact [O(1/V ), O(V )] utility-delay tradeoff under Markov dynamics.
arXiv:1008.0200v1, 2010.
[41] L. Huang and M. J. Neely. The optimality of two prices: Maximizing
revenue in a stochastic network. IEEE/ACM Transactions on Networking, 18(2):406–419, April 2010.
[42] T. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules.
Advances in Applied Mathematics, 6, 4-22., 1985.
[43] M. J. Neely. Energy-aware wireless scheduling with near optimal backlog and convergence time tradeoffs. Proceedings of IEEE INFOCOM,
2016.
[44] J. Liu. Achieving low-delay and fast-convergence in stochastic network
optimization: A nesterovian approach. Proceedings of ACM Sigmetrics,
2016.
[45] Albert Bifet and Ricard Gavald. Learning from time-changing data with
adaptive windowing. SIAM International Conference on Data Mining,
2007.
[46] F. Chung and L. Lu. Concentration inequalities and martingale inequalities - a survey. Internet Math., 3 (2006-2007), 79–127.
[47] W. Hoeffding. Probability inequalities for sums of bounded random
variables. Journal of the American Statistical Association 58 (301):
13-30, 1963.

A PPENDIX A - P ROOF OF L EMMA 1
(Proof of Lemma 1) We prove the performance of
ADE(Tl , d, ) with an argument inspired by [45]. We will make
use of the following concentration result.
Theorem 5. [46]
random
 Let X1 , ..., Xn be independent

variables with Pr
X
=
1
=
p
,
and
Pr
X
=
0
=
i
i
Pn i
P1n− pi .
Consider X = i=1 Xi with expectation E X = i=1 pi .
Then, we have:


−m2
Pr X ≤ E X − m
≤ e 2E{X} ,
(23)


−m2
Pr X ≥ E X + m
≤ e 2(E{X}+m/3) . ♦ (24)

Proof. (Lemma 1) (Part (a)) In this case, it suffices to check
condition (i) in ADE. Define


t−1
X
X
1
d
π̃i (t) ,
1[S(τ )=si ] +
πi (τ ) ,
d
τ =(t+w−d)+

τ ∈Ww (t)

π̃id (t)

i.e.,
is defined with the true distributions in Wd (t).
Denote 1 = (w + 1)ew /d, we see then kπ̃ d (t) − π̂ d (t)k ≤ 1 .
Thus, for any  > 0, we have:

Pr kπ̂ d (t) − π̂ m (t)ktv ≤ 

≤ Pr kπ̃ d (t) − π̂ m (t)ktv ≤  + 1

≤ Pr |π̃id (t) − π̂im (t)| ≤  + 1 .
(25)
Choose  = 21 max |π1i − π2i | − 21 > 0 and let 0 =  + 1 .
Fix α ∈ (0, 1) and consider i ∈ arg maxi |π1i −π2i |. We have:

Pr |π̃id (t) − π̂im (t)| ≤ 0

≤ Pr {|π̃id (t) − π1i | ≥ α0 }
∪{|π̂im (t) − π2i | ≥ (1 − α)0 }
 d
≤ Pr |π̃i (t) − π1i | ≥ α0

+Pr |π̂im (t) − π2i | ≥ (1 − α)0 . (26)

Here the first inequality follows because if we have both
{|π̃id (t) − π1i | < α0 } and {|π̂im (t) − π2i | < (1 − α)0 , and
|π̃id (t) − π̂im (t)| ≤ 0 , we must have:

|π1i − π2i | ≤ |π̃id (t) − π1i | + |π̂im (t) − π2i | + |π̃id (t) − π̂im (t)|
= 20 < |π1i − π2i |,

which contradicts the fact that i achieves maxi |π1i − π2i |.
Using (26) and Hoeffding inequality [47], we first have:

Pr |π̂im (t) − π2i | ≥ (1 − α)0
≤ 2 exp(−2((1 − α)0 )2 Wm (t)).

(27)

≤ 2 exp(−2(α0 )2 (Wd (t) − w − 1)).

(28)

For the first term in (26), we have:

Pr |π̃id (t) − π1i | ≥ α0

Equating the above two
√ probabilities and setting the sum equal
W (t)/(Wd (t)−w−1)
to δ, we have α = √ m
, and
1+ Wm (t)/(Wd (t)−w−1)
r
p
4 1 + (Wd (t) − w − 1)/Wm (t)
p
0 = ln ·
.
(29)
δ
2(Wd (t) − w − 1)

In order to detect the different distributions, we can choose
d < 0 , which on the other hand requires that:
s
r
(∗)
4
1
d ≤ ln ·
< 0
δ
2(d − w − 1)
4 1
⇒ d > ln · 2 + w + 1.
(30)
δ 2d
Here (*) follows because Wd (t) = d ≤ Wm (t). This shows
that whenever Wd (t) = d ≤ Wm (t) and the windows are
loaded with non-coherent samples, error will be detected with
probability 1 − δ.
(Part (b)) Note that for any time t, the distribution will be
declared changed if ||π̂ d (t) − π̂ m (t)||tv > d . Choose d =
21 . Similar to the above, we have:

Pr kπ̂ d (t) − π̂ m (t)ktv ≥ d
(31)

11


≤ Pr kπ̃ d (t) − π̂ m (t)ktv ≥ d − 1

≤ Pr kπ̂ d (t) − πktv ≥ αd /2

+Pr kπ̂ m (t) − πktv ≥ (1 − α)d /2 .

Using the same argument as in (26), (27) and (28), we get:

Pr kπ̂ d (t) − π̂ m (t)ktv ≥ d ≤ δ.

This shows that step (i) declares change with probability δ.
Next we show that step (ii) does not declare a distribution
change with high probability.
To do so, we first use Theorem
√
5 with m = 2 log(Tl ) Tl to have that when Wm (t) ≥ Tl ,

2
2 log(Tl )
−2 log(Tl )
Pr kπim (t) − πi k > √
≤ e−2 log(Tl ) = Tl
.
Tl
Using the union bound, we get

2M log(Tl )
−2 log(Tl )
√
Pr kπ m (t) − πk >
≤ M Tl
. (32)
Tl
Thus, part (b) follows from the union bound over k.

Proof. (Theorem 1)P(Part (a) - Utility) Define a Lyapunov
function L(t) , 21 j qj (t)2 . Then, define the one-slot Lya
punov drift ∆(t) , E L(t + 1) − L(t) | q(t) . Using the
queueing dynamic equation (3), we have:
X

∆(t) ≤ B −
qj (t)E µj (t) − Aj (t) | q(t) .
(38)
j

2
rδmax
,

Here B ,
and the expectation is taken over π and the
potential randomness
in action selection. Adding to both sides

the term V E f (t) | q(t) , we first obtain:

∆(t) + V E f (t) | q(t) ≤ B
(39)
X 
+
E V f (t) − qj (t)[µj (t) − Aj (t)] | q(t) .
j


Now add to both sides the term ∆1 (t) , E (γj∗ (t) −
θ)+ [µj (t) − Aj (t)] | q(t) , we get:

∆(t) + V E f (t) | q(t) + ∆1 (t)
(40)
X 
≤B+
E V f (t) + Qj (t)[µj (t) − Aj (t)] | q(t) .
j

A PPENDIX B - P ROOF OF T HEOREM 1

= B + g(Q(t))

(Proof of Theorem 1) Here we prove the utility-delay
performance of PLC for a stationary system. We sometimes
omit the π when it is clear. For our analysis, define:
gsi (γ) =

inf

x(si ) ∈Xi

V f (si , x(si ) )

(33)

X 

(si )
(si )
+
γj Aj (si , x ) − µj (si , x ) ,
j

to be the dual function when there is only a single state si . It
is clear from equations (9) and (33) that:
X
g(γ) =
πi gsi (γ).
(34)
i

We will also make use of the following results.

Eπ {kq(t + 1) − γ ∗ k | q(t)} ≤ kq(t) − γ ∗ k − η1 . ♦ (35)

Lemma 3. [16] If kπ a (t)−πktv ≤  and (6) holds for π a (t),
then γ ∗ (t) satisfies:
∗

kγ (t) − γ k ≤ b0 V ,

Here the equality follows from the definition of g(γ) and (34),
∗
π
and the last inequality uses g(Q(t)) ≤ gπ
= fav
. Taking an
expectation over q(t), carrying out a telescoping sum from
t = 0 to t = T − 1, and dividing both sides by V T , we
obtain:
T −1
T −1
1 X 
1 X 
π
E f (t) ≤ fav
E ∆1 (t) . (42)
+ B/V −
T t=0
V T t=0
To prove the utility performance, it remains to show that the
last term is O(1) in the limit, i.e.,
T −1
1 XX  ∗
E (γj (t) − θ)+ [µj (t) − Aj (t)] = O(1). (43)
T →∞ T
t=0 j

(36)

To prove (43), consider the system evolution over the timeline. From the detection algorithm, we see that the timeline
is divided into intervals separated by reset points. Moreover,
since Wm (t) and Wd (t) are restarted, and q(t) is reset at reset
points, these intervals form renewal cycles with initial backlog
q(t) = 0 (see Fig. 6).
Wm

where b0 = Θ(1). ♦

Lemma 4. [43] Suppose Z(t) is a real-value random process
with initial value z0 that satisfies:
1) |Z(t
 + 1) − Z(t)| ≤ Zmax where Zmax > 0
2) E Z(t + 1) − Z(t) | Z(t) ≤ z(t) where z(t) = Zmax
when Z(t) < Zu and z(t) = −η with 0 ≤ η ≤ Zmax
when Z(t) ≥ Zu for some constant Zu .

Then, there exist constants rz = Θ(1), 0 < ρz < 1, and
rz Zmax
−ρz )erz Zu
D = (e
, such that for every slot t,
1−ρz
 rz Z(t)
≤ D + (erz z0 − D)ρtz . ♦
(37)
E e
Now we prove Theorem 1.

(41)

lim

Lemma 2. [38] Suppose the conditions in Theorem 1 hold.
Then, under PLC with Q(t) = q(t), there exist constants
G, η = Θ(1), i.e., both independent of V , such that whenever
kq(t) − γ ∗ k > G,

∗

π
≤ B + fav
.

Wm (t) = Tl

C

Wd
C0

next round

t reset point
t+w+1

Fig. 6. Timeline divided into intervals.

Label the cycles by {Ck , k = 0, 1, ...}. We thus have:

T −1
1 XX  ∗
E (γj (t) − θ)+ [µj (t) − Aj (t)]
(44)
T →∞ T
t=0 j
P
P ∗

+
E
E cost
t∈Ck
j (γj (t) − θ) [µj (t) − Aj (t)]

= 
,
.
E length
E |Ck |

lim

Below, we omit the index k and use dm , maxt {bsd (t) −
bm (t)} to denote the size of C. Also, let c0 be such that ew =
Θ(V −c0 /2 ), and write Tl = V c1 where c1 , max(c, c0 ). Since
ew > 0, we have Tl < ∞.

12

We first show that the probability for having a small dm
(w.r.t. Tl ) is small. Denote the event E1 that dm ≥ V 2+c1 and
Wm (t) = Tl at t = Tl + d − w slots from the beginning of
C, i.e., step (i) of ADE does not declare any change before
Wm (t) = Tl occurs. Using Lemma 1, Tl ≥ V c , and the fact
that for a large V , d = log(V )3 /2d ≥ 22 ln(4/δ) + w + 1 for
d

δ = V − log(V ) , we have that:

−2 log(Tl )
Pr E1c
≤ δTl + V 2+c1 · (δ + (w + 1)M Tl
)
2

E1c

≤ V −c

log(V )

≤ V −3 .

(45)

Here
denotes the complementary event of E1 . Therefore,
with probability at least 1 − V −3 , dm ≥ V 2+c1 , which implies
that:

(46)
E |C| ≥ V 2+c1 /2.

Conditioning on E1 , we see that PLC will compute the empirical multiplier with statistics in Wm (t) after t = Tl + d − w
slots, and use it until a new change is declared (see Fig. 6).
Denote this period of time, i.e., after the multiplier is computed
until the cycle ends, by C 0 and its length by d0m (see Fig. 6).
We have d0m = dm − O(V c1 ) − w − 1 = Ω(V 2+c1 ) time (the
first V c1 slots are for learning and the last O(w + 1) slots are
not contained in both Wm (t) and Wd (t) due to ADE).
)
Denote another event E2 , {kπ m (t) − πk ≤ 4Vlog(V
c1 /2 },
m
where t is when Wm (t) = Tl . That is, the distribution π̂ (t)
is close to the true distribution, for t ∈ C 0 (Note that π̂ m (t)
remains constant during C 0 ). Using Theorem 5, we have that:

2
Pr E2 ≥ 1 − M e−4 log(V ) .
(47)

Thus,


Pr E2 ∩ E1

Pr E2 | E1 =
Pr E1

2

≥ 1 − M e−4 log(V ) − V −3

Here we have used Lemma 1 in [38] and the learning step in
PLC that ensures γ ∗ (t) = O(V log(V )). On the other hand,


E cost | E1 , E2c ≤ V log(V )δmax E |C| | E1 , E2c .
(52)

c
c
Let us now try to bound E |C| | E1 , E2 . Define E2a = {y ∈
c
(σ, 2σ]} and E2b
= {y > 2σ}. We have:
 m
Pr kπ − π d (t)k > d | E1 , E2c
(53)
 m
 c
d
c
c
= Pr kπ − π (t)k > d | E1 , E2a Pr E2a |E1 , E2

 c
c
+Pr kπ m − π d (t)k > d | E1 , E2b
Pr E2b
|E1 .
 m
d
c
Nowmwe tryd to relate Pr kπ − π (t)k > d |dE1 , E2a to
Pr kπ − π (t)k > d | E1 , E2 . Consider a π (t) is such
that kπ m − π d (t)k > d given E1 , E2 . We note that there exist
i and j such that πid (t) ≤ πi and πjd (t) ≥ πj . Then, we can
always change π d (t) to π̃ d (t) by having one more sample for
j and one less sample for i (this can be ensured with high
probability since d = O(log3 (V ))). Since σ = O(V −c1 /2 )
and d = O(1/ log3 (V )), we will have kπ m − π̃ d (t)k > d
c
given E1 , E2a
. Therefore,
 m
c
Pr kπ − π d (t)k > d | E1 , E2a
 m
≥ P0 , c0 Pr kπ − π d (t)k > d | E1 , E2 .
Here c0 = mini πi / maxj πj . This shows that the probability
c
of having a change declared under E1 , E2a
is more than a
constant factor of that
under
E
,
E
.
As
a
result,
using (53)
1
2
 c
and the fact that Pr E2a
|E1 , E2c ≥ 1 − O(V −3 ),

Pr kπ m − π d (t)k > d | E1 , E2c ≥ P1 ,
where P1 = c1 P0 and c1 ≥ c0 (1 − O(V −3 )). Thus,

E |C| | E1 , E2c ≤ d/P1 .

(54)

This is obtained by considering only testing for changes at
multiples
of d slots. On the other hand, it can be shown that

≥ 1 − 2V −3 .
(48) E |C| | E1 , E2 ≥ Θ(1/P1 ). This is so since, conditioning on

E1 , E2 , samples in Wd (t) evolves according to a Markov chain,
E2 , we now bound E cost , where cost ,
PWithPE1 and
with each state being a sequence of d samples. Moreover, the
∗
+
c
t∈C
j (γj (t) − θ) [µj (t) − Aj (t)]. First, when E1 takes
total mass of the set of states resulting in kπ m −π d (t)k > d is
c
, or
place, we either have dm ≤ V 2+c1 , denoted by E1a
P0 /c0 and that after V 2+c1 time, the first Wd (t) is drawn with
dm ≥ V 2+c1 but step (i) of ADE declares changes before
the steady state probability (due to S(t) being i.i.d.). Thus, the
c
c
Wm (t) = Tl , denoted by E1b
. Given E1a
, the cost is no more
Markov chain is in steady state from then, showing that the
c
, we first see that:
than V log(V )δmax V 2+c1 . For E1b
time it takes to hit a violating state is Θ(1/P1 ). Combining
 c
Pr E1b
this with (54), we conclude that:




= Pr dm ≥ V 2+c1 and
E |C| | E1 , E2c ≤ dE |C| | E1 , E2 ≤ 2dE |C| . (55)
at least one change declared in the first Tl + d − w slots The last inequality follows since PrE , E ≥ 1 − 2V −3 .
1 2
≤ δ(Tl + d − w) ≤ V − log(V )/2 .
(49) Now consider the event E1 ∩ E2 . Using the fact that
c1
−3
c
Also, given E1b
, if we denote the first time a change is declared Tl = Θ(V ), Pr E2 ∩ E1 ≥ 1 − O(V ), and using almost
verbatim arguments as in the proofs of Lemmas 8 and 9 in
by T1b , we have:


[17], it can be shown that:10
c
E |C| | E1b
≤ T1b + E |C| | dm ≥ V 2+c1 − T1b
X


E
[µj (t) − Aj (t)] | E1 , E2
(56)
≤ Tl + d + 2E |C| ≤ 3E |C| .
(50)
t∈C 0


The first step follows because after the first declaration, the ≤ E qjs − qje | E1 , E2 + δmax (1 + b1 E |C| | E1 , E2 /V log V ),
requirement for any additional declaration is removed,
 and the where b1 = Θ(1), and qjs and qje denote the beginning and
second step follows because
T
≤
T
+d−w
and
E
|C| | dm ≥
1b
l

ending sizes of queue j during
C 0 , respectively.

V 2+c1 − T1b ≤ 2E |C| . Thus,
We first bound the E qjs . Conditioning on E1 , we see

E cost | E1c
(51)

10 The fact that the event holds with probability almost 1 enables an analysis
3E |C|
V 2+c1
≤ V log(V )δmax · ( c2 log(V ) + log(V )/2 ).
similar to that without conditioning.
V
V

13

that
 there will be Tl + d − w time until Wm (t) = Tl . Thus,
E qjs ≤ δmax b2 (V c1 + d − w) for some b2 = Θ(1).
Combining (51), (52), and (56), we obtain:

E cost

3E |C|
V 2+c1
≤ V log(V )δmax · ( c2 log(V ) + log(V )/2 )
(57)
V
V

2
+V log(V )δmax E |C| | E1 , E2c · M e−4 log(V )
+(δmax b2 (V c1 + d − w) + w + 1)δmax V log(V )

+V log(V )δmax (1 + b1 E |C| | E1 , E2 /V log V ).

The term (w + 1)δmax V log(V ) in the last w + 1 slots after
a change detection. Combining (57) with (44), (46), and (55),
we obtain (43).
(Part (b) - Delay) From the above, we see that the event
E1 ∩ E2 happens with probability at least 1 − O(1/V 3 ). Hence,
we only need to show that most packets that arrive during the
C 0 intervals experience small delay, conditioning on E1 ∩ E2 .
Denote ts and te the beginning and ending slots of C 0 . Using
(48) and Lemma 3, we get that with probability at least 1 −
2V −3
Define

kγ ∗ (t) − γ ∗ k ≤ dγ , 4b0 V 1−c1 /2 log(V ).

(58)

θ̂ , γ ∗ − (γ ∗ (t) − θ)+ ,

(59)

we see from Lemma 2 that whenever kq(t) − θ̂k > G, which
is equivalent to kQ(t) − γ ∗ k > G,

E kq(t + 1) − θ̂k | q(t) ≤ kq(t) − θ̂k − η,

for the same G = Θ(1) and η = Θ(1) < η1 in Lemma 2.11
Using (58) and θ in (17), we see that θ̂ = Θ(dγ log(V ) +
log(V )2 ). Therefore, using Theorem 4 in [16], if we assume
that C 0 never ends,

E TG (q(t)) ≤ b3 dq /η,
(60)
where b3 = Θ(1), dq = kθ̂ − q(ts )k and TG (q(t)) , inf{t −
ts : kq(t) − θ̂k ≤ G}. Note that this is after Wm (t) = Tl
in PLC, which happens after Tc = d − w + Tl slots from the
beginning of the interval. By Markov inequality,

1
Pr TG (q(t)) + Tc > (b3 dq /η + d − w + Tl )V = . (61)
V
Denote E3 , {TG (q(t)) + Tc (t) ≤ (b3 dq + d − w + Tl )V }
and let t∗ the first time after ts that Y (t) , kq(t) − θ̂k ≤
G. Following an argument almost identical to the proof of
Theorem 1 in [38], we obtain that:
te
X
√
∗
νη  νY (t)
E e
≤ (te − t∗ )e2ν rδmax + eνY (t ) , (62)
2
t=t∗
where ν , δ2 +δηmax η/3 = Θ(1). Define b4 ,
max
√
∗
2e2ν rδmax /νη = Θ(1) and b5 , eνY (t ) ≤ eνG = Θ(1),
2
and choose m = log(V ) . We have from (62) that:
te
X

1
Pr Y (t) > G + m
te − ts t=t
s

11 This

is due to conditioning on E1 ∩ E2 .

(63)

te
X

1
(
Pr Y (t) > G + m + (t∗ − 1 − ts ))
te − ts t=t∗


≤ (b4 + b5 (te − t∗ ))V − log(V ) + (t∗ − ts ) /(te − ts )
(b3 dq + d − w + Tl )V + 1
) = O(1/V ).
= O(
V 2+c1
Thus, the above implies that, given the joint event E1 ∩ E2 ,
which happens with probability 1 − O(1/V 3 ), the fraction of
packets enter and depart from each qj (t) when kq(t)− θ̂k ≤ G
is given by (1 − O(1/V ))(1 − O(1/V )), i.e., 1 − O( V1 ). This
means they enter and depart when qj (t) ∈ [θ̂−G−log(V )2 , θ̂+
G + log(V )2 ] (due to LIFO), which implies that their average
delay in the queue is O(log(V )2 ).
c
(Part (c) - Dropping) First, conditioning on E1a
, which
− log(V )/2
happens probability V
, we see that we drop at most
O(V 2+c1 ) packets in this case.
Now consider when E1 takes place, and denote as above
by ts and te the starting and ending timeslots of a cycle.
In this case, from the rules of ADE, we see that rule (ii) is
inactive, since if it is satisfied at time Tl , it remains so because
π̂ m (t) remains unchanged until the cycle ends. Hence, the
only case when an interval ends is due to violation rule (i).
Let us suppose the interval ends because at some time t0 , we
have kπ̂ m (t0 ) − π̂ d (t0 )k > d . We know then PLC drops all
packets at time t0 + w + 1, i.e., q(t0 + w + 1).
We now bound E q(t0 + w + 1) . To do so, consider the
time t∗ = t0 − 2d. We see then q(t∗ ) and
sizes
P all queue
d 0
∗
0
before
t
are
independent
of
π̂
(t
).
Also,
q
(t
+w+1)
≤
j j
P
∗
q
(t
)
+
r(2d
+
w
+
1)δ
.
max
j j
Consider the time interval from when Wm (t) = Tl utill
t∗ and consider two cases, (i) ew = Ω(V −c/2 ) and (ii) ew =
O(V −c/2 ). In the first case, we see that Tl = V c . Thus, qj (ts +
Tl ) ≤ δmax V c .
In the second case, since ew = O(V −c/2 ), Tl = e−2
w . We
have from Lemma 3 that before time Tl , the estimated multiplier kγ ∗ (t) − γ ∗ k ≤ V ew = O(V 1−c/2 ). As a result, using
the definition of θ̂ in (59) and denoting
 Z(t) = k(q(t)− θ̂)+ k,
we see that whenever Z(t) ≥ G, E |Z(t+1)−Z(t) | Z(t) ≤
−η. It can also be checked that the other conditions in Lemma
4 are satisfied by Z(t). Moreover, q(ts ) = 0 and Z(0) = 0.
Thus,

√
(64)
E Z(Tl ) ≤ G + rδmax + O(1).

1−c1 /2
Thus, E q(ts + Tl ) = O(V
). Combining the two
cases, we have E q(ts + Tl ) = O(V 1−c1 /2 + V c ) = O(V ).
After ts + Tl , the distribution π̂ m (t) is used to compute
the multiplier. Since Tl = max(V c , e−2
w ), we see that the
argument
above
similarly
holds.
Thus,
using
 Lemma 4, we see

that E q(t∗ ) = O(V ), which implies E q(t0 + w + 1) =
O(V + d). Therefore, packets will be dropped no more than
every V 2+c1 slots, and at every time we drop no more than
O(V ) packets on average.
c
Finally, consider given E1b
. Using (46) and (50), wenote
c
that conditioning on E1b , the cycle lasts no more than 3E |C|
on average, which
 means that the number of packets dropped
is at most O(E |C| ) every cycle on average. Moreover, using
(49), we see that this happens with probability O(V −3 ).
The result follows by combining the above cases.

≤

14

A PPENDIX C - P ROOF OF T HEOREM 2
(Proof of Theorem 2) We first have the following lemma to
show that if each dk ≥ 4d, then ADE keeps only o(d) samples
(timeslots) from the previous distribution in Wm (t) after
change detection. This step is important, as if Wm (t) contains
too many samples from a previous distribution interval, the
distribution estimation π̂ m (t) can be inaccurate and lead to
a high false-negative rate, which in turn affects performance
during Ik . The proof of the lemma is given at the end of this
section.
Lemma 5. Under the conditions of Theorem 2, with probability 1 − O(V −3 log(V )/4 ) only o(d) samples from Ik−1 remain
in Wm (t) ∪ Wd (t) for t ≥ tk + d. ♦
We now prove Theorem 2.
Proof. (Theorem 2) We first have from Lemma 1 that with
probability at least 1 − V −3 log(V )/4 (δ = V −3 log(V )/4 ),
distribution change will be detected before tk + d − w. Denote
this event by E4 .
reset point t⇤

new cycle starts

Dk

Wm

Wd

tk

Fig. 7. Intervals in a non-stationary system.

(Part (a) - Utility) Using Lemma 5, we see that o(d)
samples will remain in Wm (t). This implies that when V is
large and Wm (t) = d, with probability 1 − O(V − log(V )/2 ),
m

|π̂im (t) − πki | ≤ d /8, ∀ i,

(65)

where π̂ (t) is the distribution in window Wm (t) (can contain
timeslots from the previous interval). This shows that the
empirical distribution of Wm (t) is close to the true distribution
even though it may contain samples from Ik−1 . Thus, as
Wm (t) increases, π̂ m (t) will only become closer to π k , so
that (65) holds whenever Wd (t) ⊂ Ik . Denote (65) event E5 .
Now use an argument similar to the proof of Lemma 1, we
can show that:

Pr kπ̂ d (t) − π̂ m (t)ktv ≥ d ≤ V − log(V )/3 .

Hence, for each cycle C ⊂ Ik , if we denote E6 the event
that ADE does not declare any distribution change in steps (i)
and (ii) for V 1+a Tl log(V ) slots, and E2 before equation (47)
holds, we see that

Pr E6 ≥ 1 − V −2 .
(66)
This implies that Ik mostly likely only contains one cycle
C. Therefore, conditioning on E4 ∩ E5 ∩ E6 , which happens
with probability 1 − O(V −2 ) and implies that for cycle C 0 ,
q(ts ) = Θ(Dk + Tl + d − w), we have:

E cost ≤ r(Dk + Tl + d − w)b2 δmax V log(V )

+V log(V )δmax (1 + b1 E |C| /V log V ).

Applying
argument
in the proof of Theorem 1, we see

Pdthe
)
k −1
that d1k t=0
E ∆1 (t) = O( DkTlog(V
). Hence, the result
a
lV
follows.
(Part (b) - Queue) From the above, we see that at
time tk , q(tk ) = O(Dk ). We also know that the current

cycle C will start no later than tk + d − w with probability
1 − O(V −3 log(V )/4 ), in which case q(ts ) = O(Dk + d − w).
Since the system is polyhedral with ρ, using an argument
similar to the proof for Part (c) of Theorem 1, if we define
θ̃ = Θ((min(V 1−c/2 , V ew ) + 1) log2 (V ) + Dk + d − w) and
Z(t) = k(q(t) − θ̃)+ k, then throughout t ∈ [ts , tk+1 − 1],

√
(67)
E Z(t) ≤ G + rδmax + O(1).
Therefore, Part (b) follows.

Here we provide the proof for Lemma 5.
Proof. (Lemma 5) Consider time t = tk − w. We have the
following cases.
(i) Wd (t) = d and Wm (t) < d. Since dk−1 ≥ 4d, we see
that the change point tk will be detected with probability at
least 1 − δ at time t0 ≤ t + d, because Wd (t0 ) will contain
samples from π k while Wm (t0 ) will contain samples from
π k−1 (Note that although this is conditioning on Wd (t) = d
and Wm (t) < d, since at this point no statistical comparison
will be assumed, it is independent of the realizations in the two
windows). Moreover, all samples from Ik−1 will be removed
and not remain in Wm (t) and Wd (t), while at most w + 1
samples from Ik will be discarded.
(ii) Wd (t) = d and Wm (t) ≥ d. In this case, if a change
is declared, then we turn to case (iii). Otherwise, since the
samples in Wm (t) are drawn from π k−1 , we have:

Pr kπ̂ m (t) − π k−1 k ≤ d /2 ≥ 1 − V −3 log(V )/4 .
(68)

Now suppose no change is detected till time t + d. Then
Wm (t + d) ≥ d. Denote E6 , {kπ̂ m (t) − π k−1 k ≤ d /2}.
Conditioning on E6 and using (68), we have:

d
| E6 ≥ 1 − 2V −3 log(V )/4 . (69)
Pr kπ̂ m (t + d) − π k−1 k ≤
2

The inequality follows since Pr E6 ≥ 1 − V −3 log(V )/4 . Now
Wd (t + d) contains only samples from π k , in which case we
similarly have:

Pr kπ̂ d (t + d) − π k k ≤ d /2 ≤ 1 − V −3 log(V )/4 . (70)
Since the events (69) and (70) are independent, we conclude
that with probability 1 − 3V −3 log(V )/4 , a change will be
declared before tk and all samples from Ik−1 will be removed
and not remain in Wm (t) ∪ Wd (t).
(iii) Wd (t) < d. We argue that with high probability, at
most o(d) samples can remain at time tk + 2d − Wd (t). First,
note that Wd (t) < d only occurs when a detection has been
declared at a time t+w−d ≤ t0 ≤ t. Thus, if t+w−t0 = o(d),
then we are done. Otherwise suppose t + w − t0 = αd for α =
Θ(1). If they are removed, then at time t0 + 2d, Wm (t0 + 2d)
contains samples with mixed distribution π 0 = απ k−1 + (1 −
α)π k and Wd (t0 + 2d) containing samples with distribution
π k 6= π 0 . Similar to case (i), the condition Wd (t) < d is
independent of the state realizations in the two windows. Using
Lemma 1 (it can be checked that the conditions in the lemma
are satisfied), we see that this will be detected by ADE with
probability 1 − δ with a large V .
Combining all three cases completes the proof.
A PPENDIX D - P ROOF OF T HEOREM 3
(Proof of Theorem 3) We prove Theorem 3 here.

15

Proof. (Part (a) - Stationary) The results follow from the fact
that when ew = 0, PLC is equivalent to OLAC in [16] with
perfect statistics. Hence the results follow from Theorems 1
and 2 in [16].
(Part (b) - Non-Stationary) We first see that at time t, ADE
detects distribution change in time t + w through step (ii) with
probability 1. Then, after time tk + d − w, π a (t) = π k and we
see that whenever Z(t) , kq(t) − θk > G for θ = 2 log2 (V )
and G = Θ(1),

E Z(t + 1) | q(t) ≤ Z(t) − η.
(71)

change before time tk + d. Recall the event E1 that ADE does
not declare change in the first V 2+c1 slots from the proof of
Theorem 1, where c1 is such that Tl = V c1 . Note that this
implies {dm ≥ V 2+c1 }). From (45), we know that:

Pr E1 ≥ 1 − V −3 .
(75)

Conditioning on E1 , the time it takes to achieve ||Q(t)−γ ∗ || ≤
G is no more than the sum of (i) the time it takes to reach
Wm (t) = Tl , and (ii) the time it takes to go from the estimated
multiplier γ ∗ (t)−θ to γ ∗ . Denote E7 (t) = {kπ m (t)−πktv ≤
−1/2
2M log(Tl )Tl
}. When Wm (t) = Tl , we have

−2 log(Tl )
Pr E7 (t) ≥ 1 − O(M Tl
),
(76)

Denote b6 = r1z log(erz rδmax −ρz /(1 − ρz )). We want to show
via induction that for all k,
V log(V )
X
∗
∗
E
qj (tk ) ≤ qth , 2r log2 (V ) + b6 + 2G + drδmax . (72) in which case kγ (t) − γ k = Θ( √Tl ). As in the
proof of Theorem 2, we see that when Wm (t) = Tl ,
j
∗
k + Tl + d), which implies that kQ(t) − γ k =
First, it holds for time zero. Suppose it holds for interval Ik . q(t) = O(D
2
V
Θ((1 + √T ) log (V ) + Tl + Dk + d). Using Lemma 5 in [16]
We now show that it also holds for interval k + 1.
l
To do so, first we see that during time [tk , tk + d − w], there again, we see that if ADE always does not declare change,
can be an increment of qj (t) since π a (t) during this interval
(77)
E TG = O(θ + Tl + Dk + d).
is a mixed version of π k−1 and π k . Thus,
Using Markov inequality, we see that:
X

0
E
qj (tk + d) ≤ qth
, qth + drδmax .
(73)
Pr TG ≥ V 2+c1 ≤ O(V −1−c1 + Dk V −2−c1 ).
(78)
j

Using Lemma 4, we have:

E erz Z(tk+1 −d)
0
erz rδmax −ρz rz G
e
+ (erz qth − b6 erz G )ρdz k −2d .
≤
1 − ρz

Using the definition of qth and the fact that dk ≥ d log2 (V ),
0
we have that for a large V , (erz qth − b6 erz G )ρdk −2d ≤ G.
Thus,

E Z(tk+1 − d) ≤ b6 + 2G,
(74)
P
2
which implies E
j (tk+1 − d) ≤ 2r log (V ) + b6 + 2G.
jqP
4
It thus follows that E
j qj (tk+1 − d) ≤ qth ≤ b7 log (V )
for some b7 = Θ(1).
Having established this result, using an argument similar to
that in the proof of Theorem 2, we have:

E cost ≤ b7 log4 (V ) · V log(V )

+V log(V )δmax (1 + b1 E |C| /V log V ).
Using dk ≥ V 1+ , we see that Part (b) follows.

A PPENDIX E - P ROOF OF T HEOREM 4
(Proof of Theorem 4) Here we prove the convergence
results. We sometimes drop the subscript k when it is clear.
Proof. (Theorem 4) First, when ew = 0, we see that for
any interval Ik , for all time t ≥ tk + d, π a (t) = π k , and
γ ∗ (t) = γ − θ. Using Lemma 5 in [16] and the fact that
d = O(log2 (V )), we have:

 
E TG = E E TG | q(tk )
(∗) 
(∗∗)
= E Θ(kq(tk ) − θk) = Θ(log4 (V )).
Here (*) follows from Lemma 5 in [16] and (**) follows from
(72).
Consider the other case ew > 0. Using Lemma 5, we see
that with probability at least 1−V −3 , PLC detects distribution

Thus, with probability 1 − O(V −1−c1 + Dk V −2−c1 ), convergence occurs before V 2+c1 . This proves (20).
To prove (21), define G1 = Θ(Dk + 2 log(V )2 (1 + V ew )).
Then, we see from Lemma 5 that with probability 1 −
O(V −3 log(V )/4 ), distribution change will be detected before
t0 ≤ tk + d. At that time, we have kγ ∗ (t) − γ ∗ k = O(V ew ).
Combining this with the fact that q(t0 ) = O(Dk + d), we see
that (21) follows. This completes the proof.

