Quickest Change Detection Approach to Optimal Control in Markov
Decision Processes with Model Changes

arXiv:1609.06757v2 [stat.AP] 1 Mar 2017

Taposh Banerjee1 , Miao Liu2 and Jonathan P. How3
Abstract— Optimal control in non-stationary Markov decision processes (MDP) is a challenging problem. The aim in
such a control problem is to maximize the long-term discounted
reward when the transition dynamics or the reward function
can change over time. When a prior knowledge of change
statistics is available, the standard Bayesian approach to this
problem is to reformulate it as a partially observable MDP
(POMDP) and solve it using approximate POMDP solvers,
which are typically computationally demanding. In this paper,
the problem is analyzed through the viewpoint of quickest
change detection (QCD), a set of tools for detecting a change
in the distribution of a sequence of random variables. Current
methods applying QCD to such problems only passively detect
changes by following prescribed policies, without optimizing
the choice of actions for long term performance. We demonstrate that ignoring the reward-detection trade-off can cause
a significant loss in long term rewards, and propose a two
threshold switching strategy to solve the issue. A non-Bayesian
problem formulation is also proposed for scenarios where
a Bayesian formulation cannot be defined. The performance
of the proposed two threshold strategy is examined through
numerical analysis on a non-stationary MDP task, and the
strategy outperforms the state-of-the-art QCD methods in both
Bayesian and non-Bayesian settings.

I. I NTRODUCTION AND M OTIVATION
In their life time, autonomous agents may be required
to deal with non-stationary stochastic environments, where
parameters of the world (dynamics, cost and goals) change
over time (for the same states spaces). For example, in
robotic navigation, a path planner might need to accommodate
dynamically changing friction coefficients of road surfaces
or wind conditions to ensure safety. In inventory control,
an order management agent might need to account for the
time varying distribution of demands for goods and services
when determining the order at each decision period. A service
robot may have to adapt to different personality or behavior
of the person it is assisting. In a multi-agent system, an agent
may have to adapt to changing strategies of the opponent or
other players [1]. In order to maximize long term rewards,
it is paramount that the agents are able to quickly detect
the changes in the environment and adapt their policies
accordingly.
When the environment is stationary, many of these problems for autonomous agents, path planning or robot control
can be formulated as an MDP, for which there is a rich
1 Taposh Banerjee is with the School of Engineering and Applied Sciences,
Harvard University, Cambridge, MA. tbanerjee@seas.harvard.edu
2 Miao Liu is with IBM T. J. Watson Research Center, Yorktown Heights,
New York. miao.liu1@ibm.com
3 Jonathan P. How is with the Laboratory for Information and Decision
Systems (LIDS), Massachusetts Institute of Technology, Cambridge, MA.
jhow@mit.edu
Work completed while the first two authors were at LIDS, MIT.

literature [2].When the environment is non-stationary, there
is a limited understanding on the best strategy to employ.
In this paper, we are interested in the case where the nonstationary process consists of several stationary processes.
Each stationary process corresponds to an MDP, and the
non-stationary nature is captured by changes in the transition
and/or reward structure of the MDPs. That is, we consider
the whole operation in a non-stationary environment as a
global task, which can be decomposed into several stationary
subtasks. This is a general case often encountered in real
world applications, such as robotics, inventory controls, etc.
For example, in inventory control, it is reasonable to assume
that the demand rate would be steady for some time, before
changing to another value. For path planning, one can assume
that the road surfaces or wind conditions are steady for a
while before changing, etc.
Solving dynamic decision making in non-stationary environments optimally is an extremely hard problem. Although
it is extensively studied in the literature, due to the analytical
intractability of the problem, however, existing works aim
towards developing approximate solutions. For example, in
some papers, the problem is reformulated as a Partially Observable MDP (POMDP), and approximate POMDP solvers
are used to obtain a solution; e.g., see [3] and [4]. In others,
estimates are maintained of the current MDP parameters, and
next state or reward predictors are used to assess whether
the parameters of the active MDP has changed; see e.g. [5]
and [6]. In [7] and [8], new models such as hidden mode
MDPs (hmMDPs) and mixed observability MDPs (MOMDPs)
are proposed to capture the transition between different
MDPs, and approximate solutions are obtained. Although
these approximate solutions are promising tools for solving
non-stationary MDPs, they are restricted to problems where
the model sizes are known a priori, and they might still suffer
from high computational overhead. The approach of multitask
or transfer learning has also been used to study these problems.
However, in these approaches, tasks are usually assumed to
be well separated and given before learning and planning
take place. There is no explicit concept of automatic change
detection in these problems. Problems of this nature are also
explored in the adaptive control literature. For example, in [9]
and [10], the authors study optimal control of an MDP with
unknown parameters in the transition kernel. Again, there is
no concept of a change in this problem.
In this paper, we approach the problem of optimal control
in MDPs with model changes through the viewpoint of
classical quickest change detection (QCD) [11]. The changes
in properties of MDPs (transition or reward) cause a change
in the law of the state-action sequence. Tools and ideas

from the QCD literature can be used to detect these changes
in law. QCD algorithms are scalable, and are optimized
for quickest detection. In spite of these properties, these
tools are either never used, or are not fully exploited in
science and engineering literature, especially in the problem
of interest in this paper. For example, sequential detection
approaches are applied in [12] and [13], where the optimal
policy for each MDP is executed, and a change detection
algorithm is employed to detect model changes. We will
show in this paper that such a naive approach may lead to
significant loss in performance. The key idea is that what
is optimal for optimizing rewards may not necessarily be
optimal for quickest detection of model changes. Thus, there
is a fundamental reward-detection trade-off to be exploited.
The purpose of this paper is to articulate this trade-off in
a mathematically precise manner, and to propose solutions
that we claim best exploit this trade-off. Specifically, we
propose a computationally efficient, simple two-threshold
strategy to quickly detect model changes, without significant
loss in rewards. We show that such an approach is superior to
the existing methods in the literature. Specifically, we show
that the two-threshold strategy leads to better performance
as compared to the single threshold classical QCD tests, as
employed in [13]. Note that it is shown in [13] that a QCD
approach is better (with respect to the Bayesian problem we
use in this paper; see (2) below) than other approaches in
the literature, e.g., [6]. For benchmarking purposes, we also
compare with the MOMDP solution [8] and a random action
strategy.
II. P ROBLEM F ORMULATION
Assuming we have a family of MDPs {Mθ }, where θ
takes value in some index set Θ, which could be finite or
infinite. For each θ , an MDP is defined by a four tuple:
Mθ = (S , A , Tθ , Rθ ), where S and A are respectively
the state space and the action space common to all MDPs,
Tθ is the transition kernel, and Rθ is the reward function.
A decision maker observes a sequence of states {sk }k≥0 ,
sk ∈ S , ∀k, and for each observed state sk , it chooses an
action ak ∈ A . For each pair (sk , ak ), the next state sk+1
takes values according to the law dictated by the kernel: ∀k
Tθ (s, a, s0 ) :=P(sk+1 = s0 | ak = a, sk = s), s, s0 ∈ S , a ∈ A .
The reward obtained by choosing action ak after observing
sk is given by Rθ (sk , ak ).
We operate in a non-stationary environment, which means
that the transition structure or the reward structure can change
over time. Specifically, at time say γ1 , the parameter θ of the
MDP changes from θ = θ0 to say θ = θ1 . At a later time,
say γ2 , the parameter changes from θ = θ1 to θ = θ2 , and
so on. To be precise, denote the non-stationary dynamics for
k ≥ 0 as
P(sk+1 = s0 | ak = a,sk = s)

Tθ0 (s, a, s0 ), for k < γ1
=
Tθ1 (s, a, s0 ), for γ1 ≤ k < γ2
(1)
Reward for (sk , ak ) := Rk (sk , ak )

Rθ0 (sk , ak ), for k < γ1
=
Rθ1 (sk , ak ), for γ1 ≤ k < γ2 .

For simplicity of exposition, for now we restrict our
attention to the case where there is only one change point
γ, and there are only two models, a pre-change model
M0 = (S , A , T0 , R0 ) and a post-change model M1 =
(S , A , T1 , R1 ). In Section VI, we discuss extensions of
the ideas developed for the two model case, to the case
where there are more than two models (possibly infinite), and
possibly more than one change point.
We consider two different problem formulations: Bayesian
and Non-Bayesian.
A. Bayesian Formulation
Suppose we have a prior on the single change point γ = γ1 ,
and we have chosen a policy Π = (π1 , π2 , · · · ) that maps the
states {sk } to actions {ak }. The MDPs M0 and M1 , the policy
Π, and the prior on the change point, together induce a joint
distribution on the product space of state spaces and actions
which we denote by P, and the corresponding expectation by
E. The objective is to choose the policy Π so as to maximize
a long term reward.
h
i
∞
(2)
max E ∑k=0 β k Rk (sk , ak ) ,
Π

where β ∈ [0, 1) is a discount factor. Note that the change
point γ is unobservable. As a result, a Markov policy may
not be optimal, and the policy Π above has to use the past
history to choose the optimal action. To accommodate model
changes, problem (2) can be reformulated as a Partially
Observable MDP (POMDP) (see Lemma 1 below), and can
be solved using approximate POMDP solvers. However, it is
computationally expensive to solve this problem numerically,
especially when the number of possible models is large. We
thus use other approaches to obtain approximate solutions.
The vehicle we have chosen to obtain the approximate
solutions is the theory of QCD. We show in Section VII
that our proposed solutions performs as well as the solution
obtained from standard approximate POMDP solvers in the
literature, while at the same time it incurs significantly less
computational cost, online and off-line.
Lemma 1: The non-stationary MDP problem (2) is equivalent to a POMDP problem with the model specified as
f, Ω, R),
e where X = S × Θ is the
MPOMDP (X , A , O, T
POMDP state space, which concatenates the fully observable
MDP state space S and the unobservable model index space
Θ; O is the set of observations, which is equivalent to the set
f: X × A × X → [0, 1] is the POMDP state
of MDP states; T
transition function; Ω : X ×A ×O → [0, 1] is the observation
function; Re : X × A → R is the reward function with

f x0 = (s0 , θ 0 )|x = (s, θ ), a = Tθ 0 (s, a, s0 )F (θ 0 |θ )I(θ 0 6= θ )
T
+ Tθ (s, a, s0 )F (θ 0 |θ )I(θ 0 = θ )
ω(o|x0 , a) = I(o = s0 )
R̃(x, a) = Rθ (s, a)
(3)
where I(·) is an indicator function, and F is a model
transition matrix. Given the prior over a change point to

be geometric distribution, i.e.,γ ∼ Geom(λ ), it can be shown
that

λ I(θ 0 6= θ )+(1 − λ )I(θ 0 = θ ) if θ = 0
0
F (θ |θ ) =
.
I(θ 0 6= θ )
if θ = 1
(4)
By converting the original non-stationary MDP problem
into a POMDP problem, one can apply any existing POMDP
solvers to obtain an approximate POMDP policy, which maps
the belief state b(x) to an action a. Considering the fact that
here the state space can be factorized into an observable part
and an unobservable part, this POMDP model can be treated
as a mixed observable MDP (MOMDP). In an MOMDP, the
belief state becomes a union of |S| disjoint |Θ|-dimension
subspaces, and all the operations are performed in the lower
dimension, hence is more time efficient to solve a MOMDP
than to solve a POMDP.
B. Non-Bayesian Formulation
In practice, a prior on the change point is not often known.
Thus, a Bayesian formulation cannot be defined. If the change
point is treated as an unknown constant, there are infinite
possible laws on the state-action joint spaces, one for each
possible change point. In statistics, there are two ways to study
non-Bayesian problems: minimax or maxmin and NeymanPearson type criteria.
For minimax or maxmin criterion we may consider the
following problem:
h
i
∞
max min Eγ ∑k=0 β k Rk (sk , ak ) ,
Π

γ

where Eγ is the expectation with respect to the probability
measure when change occurs at time γ. However, there
are two major issues with such an approach in practice.
First, a minimax approach may lead to a conservative or
pessimistic approach to policy design. Secondly, it is not
always straightforward to compute such costs for comparing
various competing algorithms.
Since the problem under consideration is about identifying
the correct regime, we also consider a Neyman-Pearson
type of criterion: trying to maximize reward in one regime
subject to a constraint on the performance under alternative
regime. We take this approach (in addition to the Bayesian
formulation) in our paper and consider the following problem.
max
Π

subj. to

h
E1

,
i
∞
∑k=0 β k Rk (sk , ak ) ≥ α.

∑

h
E∞

i

∞
β k Rk (sk , ak )
k=0

(5)

Thus, the objective is to optimize rewards when the change
occurs at time 1, subject to a constraint on the performance
when the change never occurs. In sequential analysis literature,
one often uses a minimax objective rather than the average
under E1 . As mentioned earlier, this leads to a pessimistic
viewpoint. Also, for many sequential detection algorithms
in the literature,
the worst case is often achieved for γ = 1.

k
Thus, E1 ∑∞
k=0 β Rk (sk , ak ) can also be seen as a proxy for
the minimax or maxmin reward.

Another advantage of the Neyman-Pearson type criterion
is that it maintains a balance in reward structure between
the pre- and post-change regime. A discounted cost criterion
with a discount factor β < 1, as chosen in Bayesian and
maxmin problems, may not always be appropriate for the
application in hand. This is because such a criterion penalizes
under-performing under M0 more than it penalizes underperforming under M1 . In reality, we may be interested in
maintaining good performance under every regime.
C. Oracle Policy
Let V0 (x) and V1 (x) be the cost/reward to go at state x
for the MDP models M0 and M1 , respectively. Suppose the
following conditions are satisfied:
1) the change point is exactly known,
2) the change point γ >> 1,
3) for some small δ > 0, the function |V1 (x) − V1 (y)| ≤ δ ,
∀x, y, that is the reward to go for the model M1 is not
sensitive to the initial state x.
The implication of the first two conditions is that it is
approximately optimal to use the optimal policy for M0
before the change point. The implication of the last condition
is that, no matter which policy is used for model M0 , it
is still approximately optimal to use the optimal policy for
model M1 after the change point. As a result, if all three of
these conditions are satisfied, then one can just implement the
optimal policy for the model M0 before change and use the
optimal policy for the model M1 after change, and achieve
close to maximum average rewards. In the following, such a
policy is referred to as the Oracle.
Since the change point is unknown, it is clear that if the
change can be reliably detected, then one can hope to achieve
rewards close to what the Oracle can achieve. There are
powerful algorithms in the literature that one can use to
detect this change as quickly as possible. We briefly discuss
relevant ideas and algorithms in the next section, which serves
as a background to readers not familiar with the literature on
quickest change detection.
III. BACKGROUND ON Q UICKEST C HANGE D ETECTION
In the quickest change detection literature, algorithms are
developed that allows one to quickly detect a change in the
distribution of a stochastic process from one law to another.
The optimality properties of the algorithms are studied under
various modeling assumptions and problem formulations. The
theoretical foundations were laid by the work of Wald [14]
and Shiryaev [15]; see also [11] for a survey of the area. We
discuss three such algorithms in the context of problems (2)
and (5).
Suppose we employ a certain policy Π and observe a
sequence of states and actions (driven by the policy) {(sk , ak )}.
At the change point Γ, modeled as a random variable with
prior probability mass function φ , the model changes from
M0 to M1 . Thus, the law of the stochastic sequence {(sk , ak )}
changes. Then the following algorithm, called the Shiryaev
algorithm [16], has strong optimality properties. The Shiryaev
algorithm dictates that we compute the following statistic at

each time n:
T1 (si−1 , ai−1 , si )
,
T
i=k 0 (si−1 , ai−1 , si )
n

Sn =

∑
1≤k≤n

φ (k) ∏

(6)

and declare that a change in the model has occurred at the
stopping time
τs = min{n ≥ 1 : Sn > A}.

(7)

Here, A is a threshold chosen to control false alarms. If the
prior on the change point is geometric with parameter ρ, then
the statistic Sn can be computed recursively:
1 + Sn−1 T1 (sn−1 , an−1 , sn )
Sn =
;
1 − ρ T0 (sn−1 , an−1 , sn )
It is shown in [16] that if A =

1−ζ
ζ

S0 = 0.

(8)

then

| log ζ |
as ζ → 0.
Iπ + d
τ:P(τ≤Γ)≤ζ
(9)
Thus, the Shiryaev algorithm achieves the best average
detection delay over all stopping times that satisfied a
given probability of false alarm constraint of ζ , as ζ → 0.
Here, d is a constant that is a function of the prior φ and
equals | log(1 − ρ)| for Γ ∼ Geom(ρ). The quantity Iπ is the
Kullback-Leibler information number defined by


T1 (sk−1 , ak−1 , sk )
1 n
under P1 . (10)
Iπ = lim ∑ log
n→∞ n
T0 (sk−1 , ak−1 , sk )
k=1
E[(τs − Γ)+ ] ∼

E[(τ − Γ)+ ] ∼

min

Thus, larger this number Iπ is, the smaller is the detection delay. We use the subscript π to emphasize that the information
number is a function of the policy Π employed.
If the prior on the change point is not known, or if a prior
cannot be defined, one can replace the Shiryaev statistic by
the CUmulative SUM statistic (CUSUM) [17]
n

Wn =

T1 (si−1 , ai−1 , si )

∑ log T0 (si−1 , ai−1 , si ) ,
n−m≤k≤n
max

(11)

i=k

where m is a window size that depends on the false alarm
constraint. The CUSUM algorithm has strong optimality properties, similar to (9), but with average delay and probability
of false alarm expressions replaced by suitable minimax delay
and mean time to false alarm expressions [17]. Specifically,
if
τc = min{n ≥ 1 : Wn > A},
(12)
then, with A = log η,
sup Eγ [τc − γ|τc > γ] ∼
γ

∼

min

sup Eγ [τ − γ|τ > γ]

τ:E∞ [τ]≥η γ

| log η|
as η → ∞.
Iπ

(13)

Here, Eγ is the expectation when the change point is at γ, and
E∞ is the expectation when the change never occurs. Thus,
the CUSUM algorithm minimizes the maximum of detection
delay–maximum over all possible change points–subject to a
constraint η on the mean time to false alarm, as η → ∞.
Again, the optimal performance, for a given false alarm,
depends on the information number Iπ . Thus, the number Iπ

is the fundamental quantity of interest in quickest change
detection problems. It will also play a fundamental role in
the rest of the paper.
An alternative to CUSUM in the non-Bayesian setting is
to put ρ = 0 in the Shiryaev algorithm and obtain what is
called the Shiryaev-Roberts (SR) statistic
SRn = (1 + SRn−1 )

T1 (sn−1 , an−1 , sn )
;
T0 (sn−1 , an−1 , sn )

SR0 = 0,

(14)

and use the stopping time
τsr = min{n ≥ 1 : SRn > A}.

(15)

In the numerical results reported in Section VII, we use the SR
test instead of CUSUM because of the ease of implementation.
The algorithms discussed above can be easily modified
to also account for a change of distribution of rewards. We
do not discuss that here for simplicity of exposition. Also,
the state and action sequences are more informative. Thus,
unless only the reward undergoes a change, and the transition
functions do not change, only then it will be useful to consider
rewards for detection.
Trade-off Between Detection Performance and Reward
Note that the problems in (2) and (5) are not classical
change detection problems. The objective is not to optimize
delay subject to constraint on false alarms, but to optimize
long term rewards. Thus, while quick detection is key, what
is optimal for change detection may not be optimal with
respect to optimizing rewards, and vice versa. Thus, there
is a fundamental trade-off between detection performance
and maximizing rewards. See Section IV below for a more
rigorous statement.
The fundamental contribution of this paper is a computationally efficient two-threshold algorithm that optimizes
this detection-reward trade-off to achieve near optimal performance. As discussed in the introduction, most of the works
in the existing literature either do not exploit tools from the
change detection literature, or very few who exploit them,
ignore this trade-off in their design.
IV. Q UICKEST D ETECTION WITH L OCALLY O PTIMAL
S OLUTION
One approach to solving either (2) or (5) is to use a
locally optimal approach, i.e., to start with using the optimal
policy for model M0 , compute the change detection statistics
(Shiryaev, SR or CUSUM) over time, and switch to the
optimal policy for the model M1 at the time when the change
detection algorithm crosses its threshold. Mathematically, let
Π0 = (π0 , π0 , · · · ) be the (stationary) Markov optimal policy
for model M0 , and let Π1 = (π1 , π1 , · · · ) be the (stationary)
Markov optimal policy for model M1 . Then use the following
policy
Πloc = (π0 , π0 , · · · , π0 , π1 , π1 , · · ·),
(16)
|
{z
} | {z }
τ−1 times

τ onward

where τ is the stopping time for the Shiryaev, SR or the
CUSUM algorithm.

a) Choosing the threshold: In the quickest change
detection problem, the threshold A used in the Shiryaev, SR or
CUSUM tests is designed to satisfy the constraint on the rate
of false alarms. However, for problems in (2) and (5), there is
no notion of a false alarm. For the non-Bayesian criterion, one
can choose the threshold to satisfy the constraint of α (see
(5)). However, in the Bayesian setting, the threshold is a free
parameter, and can be optimized for optimal performance.
b) Issues with policy Πloc : As we will show in Section VII, the policy Πloc may lead to poor performance.
This is because, as discussed in Section III, the detection
performance of the stopping rule τ used depends on the
information number Iπ0 ; see (10). Let

Algorithm 5.1: ΠTT : Two-Threshold Switching Strategy
Require: Thresholds A and B, B < A; optimal policies π0 ,
π1 , πKL ; transition kernels T1 (s, a, s0 ) and T0 (s, a, s0 )
1: Start with S0 = 0
2: while Sn ≤ A do
3:
Use locally optimal policy Π0 = (π0 , π0 , · · · )
4:
Compute the statistic Sn using (8)
5:
If Sn ≤ B continue using the policy π0
6:
If Sn > B use πKL
7:
n=n+1
8: end while
9: Switch to policy Π1 = (π1 , π1 , · · · )
10: return

Imax := max Iπ .
π

Then, it is possible that
Iπ0  Imax ,
and that Iπ0 is itself quite small. This may lead to poor
detection performance, and hence may cause significant loss
of revenue or rewards. If it so happens that Iπ0 ≈ Imax , and
Iπ0 is significant, then one can expect that this simple strategy
Πloc itself may lead to near optimal performance. But, this is
more a matter of chance, and more sophisticated approaches
are needed that considers every possibility. We note that in
some cases one may be able to use MOMDP or POMDP based
approximations to compute the optimal policy for our problem,
but such solutions are computationally demanding. Using a
quickest change detection approach leads to computationally
efficient algorithmic techniques.
V. A T WO -T HRESHOLD S WITCHING S TRATEGY TO
E XPLOIT R EWARD -D ETECTION T RADE -O FF
One way to improve the performance of the policy Πloc is
to replace the policy Π0 by another policy that better exploits
the reward-detection trade-off. One option is to replace Π0 by
a policy that maximizes the information number Iπ . Define for
each state s ∈ S , the information maximizing policy πKL (s)
as
T1 (s, a, s0 )
πKL (s) = arg maxa ∑ T1 (s, a, s0 ) log
. (17)
T0 (s, a, s0 )
s0
Specifically, use
ΠKL = (πKL , πKL , · · · , πKL , π1 , π1 , · · ·).
|
{z
} | {z }
τ−1 times

(18)

τ onward

Using this policy will lead to quickest and most efficient
detection of model changes. However, since the policy πKL
may not be optimal for the MDP model M0 , it may cause
significant loss of rewards before the change point.
We propose to use a simple two-threshold strategy that
switches between π0 and πKL , using π0 to optimize rewards,
and switching to πKL for information extraction. The proposed
switching strategy is closely related to the notion of sequential
design of experiments [18], or to the notion of exploitation
and exploration in multi-arm bandit problems [19].
The two-threshold policy ΠTT is described in Algorithm 5.1.
In words, fix two thresholds A and B, with B < A. Also,

assume that we are in the Bayesian setting so that we can
compute the Shiryaev statistic Sn (8). Then the policy ΠTT is
defined as follows. Start with the locally optimal policy Π0 =
(π0 , π0 , · · · ) and compute the statistic Sn . As long as Sn ≤ B,
keep using the Markov policy π0 . If Sn > B, suggesting that
we may be in the wrong model, extract more information by
using πKL . If Sn goes below B again, switch back to π0 , else
we keep using πKL . If Sn > A, switch to the optimal Markov
policy for model M1 , that is π1 .
In short, use π0 when Sn ∈ [0, B], use πKL when Sn ∈ (B, A],
and use π1 when Sn ∈ (A, ∞). Thus, the change detection
statistic Sn is used as a belief on the unknown model, and is
used for detection between M0 and M1 , depending on whether
Sn is small or large, respectively. For moderate values of Sn ,
the policy πKL is used to improve detection performance.
ΠTT = (π0 , · · · , π0 , πKL , · · · , πKL , π0 , · · · , π0 , · · · ,
| {z } |
{z
} | {z }
Sn ≤B

B<Sn ≤A

Sn ≤B

· · · , πKL , · · · , πKL , π1 , π1 , · · ·).
|
{z
} | {z }
B<Sn ≤A until τ−1

(19)

τ onward

In the non-Bayesian setting, we can replace the Shiryaev
statistic Sn by the SR statistic SRn (14) or the CUSUM
statistic Wn (11).
a) On the choice of thresholds A and B: Note first that
setting A = B reduces the two-threshold policy ΠTT to the
locally optimum policy Πloc . Also, by setting B = 0 the policy
reduces to ΠKL . As discussed earlier, this will lead to good
detection performance, but may lead to loss of rewards. Akin
to Πloc , the thresholds A and B here are free parameters,
even for the non-Bayesian setting. Thus, the thresholds can
be optimized for best performance: choosing the optimal
thresholds is equivalent to choosing the best detection-reward
trade-off.
b) Bayesian vs Non-Bayesian: We emphasize that the
definition of ΠTT is implicitly different for Bayesian and
non-Bayesian cases. In the Bayesian case, we have access to
the prior on the change point, and we use that to compute the
Shiryaev statistic Sn . However, in the non-Bayesian case, we
replace the Shiryaev statistic by the Shiryaev-Roberts statistic
SRn or the CUSUM statistic Wn .
c) When will ΠTT outperform Πloc ?: The amount of
performance gain depends in general on the problem structure:

reward function and the transition kernel. However, a condition which must be satisfied is Iπ0  Imax . This condition often
leads to better detection performance for ΠTT as compared
to Πloc , resulting in efficient detection and more average
rewards. Another condition under which performance gains
are significant is when under-performing under any of the
models is penalized equally. For example, in the Bayesian
case (2), if the discount factor β is small, then the rewards
lost in delaying a transition to the optimal policy of M1 will
not affect the overall cost. As a result, a policy can cause
large delays, without significantly loosing rewards, and a good
detection performance may not necessarily lead to noticeable
gain in rewards. Numerical results are provided in the next
section to support these observations.
VI. M ULTIPLE M ODELS AND C HANGE P OINTS
For a parametrized family of models {Mθ }, if the model
changes from Mθ0 to some other unknown model in the
family, then the Shiryaev, SR or CUSUM statistic cannot
be used for change detection. This is because one needs the
exact knowledge of the post-change distribution to compute
those statistics. Popular alternatives are to use generalized
likelihood ratio (GLR) based tests or mixture based tests. We
only discuss the former. A GLR statistic for change detection
is defined as
n

Gn =

max

sup

Tθ (si−1 , ai−1 , si )

∑ log Tθ (si−1 , ai−1 , si ) ,

n−m≤k≤n kθ −θ k≥ε i=k
0

0

where ε is the minimum magnitude of change that can occur
in the problem.
A replacement for Πloc in this setting would be to use
locally optimal policy and switch at the time of stopping,
where now the stopping rule is
τg = min{n ≥ 1 : Gn > A}.
Since there is more than one possibility for the post-change
model, one can use the maximum likelihood estimate (the θ
that achieved the maximum in the expression for Gn at the
time of stopping) to choose the model. When the number of
models is finite, one can also use the theory of fault isolation
to choose the right model [20].
A replacement for ΠTT in this setting is even less obvious
because of the difficulty in defining an appropriate version
of πKL . We propose the following
πKL (s) = arg maxa

Tθ (s, a, s0 )

∑ Tθ (s, a, s0 ) log Tθ (s, a, s0 ) .
kθ −θ0 k≥ε 0
min

s

0

(20)
Thus, maximize the worst case KL divergence. Analytical
and numerical performance of these schemes will be reported
elsewhere.
If there are multiple change points, then as long as the
gap between the change points is large enough, we can
repeat the two model algorithm for consecutive change points.
Specifically, if the GLR based algorithm detects a change
and gives θ1 as an estimate for the post-change parameter,
then we can reset the algorithm with θ1 as the pre-change
parameter, and reapply the GLR based test. As long as there

is a significant gap between model parameters, one would
expect this technique to be close to optimal.
VII. N UMERICAL R ESULTS
We now compare the two policies ΠTT and Πloc for an
inventory control problem, and show that using ΠTT results
in significant gains. We use the inventory control problem to
illustrate the ideas because of its simplicity. The understanding
developed through this simple problem can be extended to
more complex problems.
a) Inventory control problem: The state sk is the level
of the inventory at time k, and the maximum size of the
inventory is N. The action ak is the additional inventory to
be ordered based on the state sk , making the total inventory
sk + ak . A stochastic demand wk arrives making the residual
inventory or the next state sk+1 = max{0, sk + ak − wk }. Let
c to be cost of ordering a unit of inventory, h be the holding
cost per unit, and p be the cost of loosing a unit of demand.
Thus the cost per unit time is given by
C(sk , ak ) = Ewk [ cak + h max{0, sk + ak − wk }
+p max{0, −(sk + ak − wk )}] .

(21)

It is assumed that at the change point, the distribution of the
demands changes from Poisson(λ ) to Uniform. The demands
are assumed to be independent, conditioned on the change
point. For clarification, note that the problem formulations
(2) and (5) are about maximizing rewards, but the objective
in the inventory control problem is to minimize cost.
b) Numerical results for Bayesian setting: Under the
Bayesian setting (2), it is assumed that the change occurs
with a geometric prior ρ = 0.01. The other parameter values
used are c = 1, h = 5, β = 0.99, λ = 2, N = 10, 20, and p
is chosen to be 100, 200 or 300. This is a classical optimal
control problem and the optimal policy under each model,
Poisson or Uniform, can be found using value iteration [2].
The performance of various policies discussed are tabulated in
Table I. The results are obtained by performing average over
1000 independent runs, each of horizon size 1000. The Oracle
policy is the one that knows the change point, and switches
from the optimal policy for the Poisson model to the optimal
policy for the Uniform model, exactly at the change point. The
policy Πloc employs the Shiryaev algorithm (7). Since there
is no concept of false alarms, the choice of threshold A is
optimized to achieve minimum possible cost. The policy ΠTT
also employs the Shiryaev algorithm, and the values of the
two thresholds are also chosen to achieve minimum possible
cost. For comparison, the costs achieved by performing an
MOMDP approximation and a random action strategy is also
shown. The performance of the policy ΠTT is comparable to
that of the MOMDP solution, and significantly better than
that of Πloc . Note that the gain is more significant when Imax
is much larger than Iπ0 . Also, since the Poisson arrival rate
chosen implies less demand as compared to the Uniform
arrival rate, the optimal control is more aggressive for the
Uniform arrival model. A delay in detecting the change will
result in significant loss of demands. The chosen value of
the discount factor β and p ensures that delays in detection,

TABLE I: Bayes discounted cost (2) for different policies: c = 1,
h = 5, β = 0.99, ρ = 0.01. The values in the table are obtained by
averaging costs over 1000 independent runs, each of horizon size
1000.
N
20
20
20
10
10
10

p
100
200
300
100
200
300

Oracle
4057
4229
4277
2336
2445
2550

Πloc
4980
5678
5884
2619
2902
2920

ΠTT
4579
5051
5238
2515
2728
2813

MOMDP
4688
5144
5325
2677
2876
3020

RANDOM
16489
27655
38821
7861
13623
19386

Imax
8.45
8.45
8.45
1.72
1.72
1.72

Iπ0
2.56
2.56
3.24
1.17
1.42
1.61

and outperform the state-of-the art QCD method and MOMDP
method for solving non-stationary MDP tasks. Future work
will include application of ideas developed in this paper
to design of reinforcement learning based algorithms for
decision making in non-stationary environments. See [21] for
a stochastic approximation based approach to this problem.
ACKNOWLEDGMENT
This research was funded in part by Northrop Grumman
and Lincoln Laboratory.
R EFERENCES

Fig. 1: Performance under M1 subject to constraints on the
performance under M0 . The SR algorithm (14) is used while
implementing the policies.

and hence loss in demands, are sufficiently penalized under
both regimes, pre-change and post-change.
c) Numerical results for Non-Bayesian setting: An
overall discounted criterion like (2) may not be the best
or even fair way to compare competing algorithms for a nonstationary environment. One of the primary reasons for using
(2) as a criterion was to show that the proposed algorithm
can perform comparable to an MOMDP approximation. A
more appropriate performance metric is a variational one (5).
In this setting, instead of optimizing the threshold used in the
policies, the thresholds are selected
to satisfy the constraint

kC (s , a ) , in which the change never
of α on E∞ ∑∞
β
k k k
k=0
occurs.
of the thresholds, the performance
 ∞ Fork these choices

E1 ∑k=0 β Ck (sk , ak ) is evaluated for both ΠTT and Πloc in
which the change occurs at time 1. This way, performance
under both the regimes or MDPs are equally weighted, and
an algorithm that performs well in every setting can be
obtained. The performance comparison is plotted in Fig. 1.
The parameter used are c = 1, h = 5, β = 0.99, λ = 2, N = 20,
and p = 200. We use the Shiryaev-Roberts (14) algorithm to
detect changes. Clearly, ΠTT is superior. Finally, note that
since we do not have a prior on the change point, a POMDP
or MOMDP solution cannot be obtained.
VIII. C ONCLUSIONS
This paper presents a novel way to combine techniques
used for stationary MDPs and quickest change detection
to solve non-stationary MDPs by considering the tradeoff between change detection and reward maximization, an
important problem that has not been adequate addressed
before. Our method uses a two threshold switching strategy
to exploit reward-detection trade-off. Our numerical results
show that the proposed method can achieve better trade-off,

[1] P. Hernandez-Leal, M. E. Taylor, B. Rosman, L. E. Sucar, and E. M.
de Cote, “Identifying and tracking switching, non-stationary opponents:
a Bayesian approach,” in Workshops at the Thirtieth AAAI Conference
on Artificial Intelligence, 2016.
[2] D. P. Bertsekas, Dynamic programming and optimal control. Athena
Scientific Belmont, MA, 1995, vol. 1, no. 2.
[3] E. Hadoux, A. Beynier, and P. Weng, “Solving hidden-semi-Markovmode Markov decision problems,” in Scalable Uncertainty Management.
Springer, 2014, pp. 176–189.
[4] P. Dayan and T. J. Sejnowski, “Exploration bonuses and dual control,”
Machine Learning, vol. 25, no. 1, pp. 5–22, 1996.
[5] K. Doya, K. Samejima, K.-i. Katagiri, and M. Kawato, “Multiple
model-based reinforcement learning,” Neural computation, vol. 14,
no. 6, pp. 1347–1369, 2002.
[6] B. C. Da Silva, E. W. Basso, A. L. Bazzan, and P. M. Engel,
“Dealing with non-stationary environments using context detection,” in
Proceedings of the 23rd international conference on Machine learning.
ACM, 2006, pp. 217–224.
[7] S. P. Choi, D.-Y. Yeung, and N. L. Zhang, “Hidden-mode Markov
decision processes for nonstationary sequential decision making,” in
Sequence Learning. Springer, 2000, pp. 264–287.
[8] I. Chades, J. Carwardine, T. Martin, S. Nicol, R. Sabbadin, and
O. Buffet, “MOMDPs: a solution for modelling adaptive management
problems,” in Twenty-Sixth AAAI Conference on Artificial Intelligence
(AAAI-12), 2012.
[9] V. Borkar and P. Varaiya, “Adaptive control of Markov chains, i: Finite
parameter set,” IEEE Transactions on Automatic Control, vol. 24, no. 6,
pp. 953–957, 1979.
[10] ——, “Identification and adaptive control of Markov chains,” SIAM
Journal on Control and Optimization, vol. 20, no. 4, pp. 470–489,
1982.
[11] V. V. Veeravalli and T. Banerjee, “Quickest change detection,” Academic press library in signal processing: Array and statistical signal
processing, vol. 3, pp. 209–256, 2013.
[12] R. Allamaraju, H. Kingravi, A. Axelrod, G. Chowdhary, R. Grande,
J. P. How, C. Crick, and W. Sheng, “Human aware UAS path planning
in urban environments using nonstationary MDPs,” in Robotics and
Automation (ICRA), 2014 IEEE International Conference on. IEEE,
2014, pp. 1161–1167.
[13] E. Hadoux, A. Beynier, and P. Weng, “Sequential decision-making under non-stationary environments via sequential change-point detection,”
in Learning over Multiple Contexts (LMCE), 2014.
[14] A. Wald, Sequential analysis. Courier Corporation, 1973.
[15] A. N. Shiryaev, “On optimum methods in quickest detection problems,”
Theory of Probability & Its Applications, vol. 8, no. 1, pp. 22–46,
1963.
[16] A. G. Tartakovsky and V. V. Veeravalli, “General asymptotic Bayesian
theory of quickest change detection,” Theory of Probability & Its
Applications, vol. 49, no. 3, pp. 458–497, 2005.
[17] T. L. Lai, “Information bounds and quick detection of parameter
changes in stochastic systems,” Information Theory, IEEE Transactions
on, vol. 44, no. 7, pp. 2917–2929, 1998.
[18] H. Chernoff, “Sequential design of experiments,” The Annals of
Mathematical Statistics, vol. 30, no. 3, pp. 755–770, 1959.
[19] J. Gittins, K. Glazebrook, and R. Weber, Multi-armed bandit allocation
indices. John Wiley & Sons, 2011.
[20] A. G. Tartakovsky, “Multidecision quickest change-point detection:
Previous achievements and open problems,” Sequential Analysis, vol. 27,
no. 2, pp. 201–231, 2008.
[21] R. Singh and T. Banerjee, “Kiefer wolfowitz algorithm is asymptotically
optimal for a class of non-stationary bandit problems,” arXiv preprint
arXiv:1702.08000, 2017.

