ROBUSTNESS TO INCORRECT SYSTEM MODELS AND APPLICATION TO
DATA-DRIVEN LEARNING IN STOCHASTIC CONTROL ∗

arXiv:1803.06046v2 [cs.SY] 19 Mar 2018

ALİ DEVRAN KARA AND SERDAR YÜKSEL

†

Abstract. We study the continuity properties of stochastic control problems with respect to transition kernels
and applications of these to the robustness of optimal control policies applied to systems with incomplete or incorrect
probabilistic models. We study both fully observed and partially observed Markov Decision Processes. We show that
for infinite horizon discounted cost setup, continuity and robustness cannot be established under weak convergence
and set-wise convergence of transition kernels in general, but that the optimal cost is continuous in the transition
kernels under the convergence in total variation under mild conditions. By imposing further assumptions on the
measurement models and on the kernel itself, we also show that the optimal cost can be made continuous under
weak convergence of transition kernels. Using these continuity results we find bounds on the mismatch error that
occurs due to the application of a control policy which is designed for an incorrectly estimated system model in terms
of a distance measure between true model and the incorrect one. In particular, compared to the existing literature, we
obtain strictly refined and strong robustness results that are applicable even under the errors that can be investigated
under weak convergence criteria, in addition to total variation criteria. These lead to practically important results
on empirical learning in (data-driven) stochastic control since often, in engineering applications, system models are
learned through training data.

1. Introduction.
1.1. Preliminaries. In this paper, we study the continuity properties of stochastic control problems with respect to transition kernels and applications of these to the robustness of
optimal control policies applied to systems with incomplete or incorrect probabilistic models.
We start with the probabilistic setup of the problem. Let X ⊂ Rm denote a Borel set
which is the state space of a partially observed controlled Markov process. Thus, the state
elements of the model, {Xt , t ∈ Z+ }, live in X. Here and throughout the paper Z+ denotes
the set of non-negative integers and N denotes the set of positive integers. Let Y ⊂ Rn be a
Borel set denoting the observation space of the model, and let the state be observed through
an observation channel Q. The observation channel, Q, is defined as a stochastic kernel
(regular conditional probability) from X to Y, such that Q( · |x) is a probability measure on
the (Borel) σ-algebra B(Y) of Y for every x ∈ X, and Q(A| · ) : X → [0, 1] is a Borel
measurable function for every A ∈ B(Y). A decision maker (DM) is located at the output of
the channel Q, hence it only sees the observations {Yt , t ∈ Z+ } and chooses its actions from
U, the action space which is a Borel subset of some Euclidean space. An admissible policy
γ is a sequence of control functions {γt , t ∈ Z+ } such that γt is measurable with respect to
the σ-algebra generated by the information variables
It = {Y[0,t] , U[0,t−1] },

t ∈ N,

I0 = {Y0 },

where
Ut = γt (It ),

t ∈ Z+

(1.1)

are the U-valued control actions and
Y[0,t] = {Ys , 0 ≤ s ≤ t},

U[0,t−1] = {Us , 0 ≤ s ≤ t − 1}.

We define Γ to be the set of all such admissible policies.
The update rules of the system are determined by (1.1) and the following relationships:
Z

P (dx0 )Q(dy0 |x0 ), B ∈ B(X × Y),
Pr (X0 , Y0 ) ∈ B =
B

∗ This research was supported in part by the Natural Sciences and Engineering Research Council (NSERC) of
Canada.
† The authors are with the Department of Mathematics and Statistics, Queen’s University, Kingston, ON, Canada,
Email: {16adk,yuksel}@mast.queensu.ca

1

where P is the (prior) distribution of the initial state X0 , and


Pr (Xt , Yt ) ∈ B (X, Y, U )[0,t−1] = (x, y, u)[0,t−1]
Z
T (dxt |xt−1 , ut−1 )Q(dyt |xt ), B ∈ B(X × Y), t ∈ N,
=
B

where T is the transition kernel of the model which is a stochastic kernel from X × U to X.
Using stochastic realization results (see Lemma 1.2 in [1], or Lemma 3.1 of [2]), the
above dynamics can be represented in a functional form as follows: we can consider a dynamical system described by the discrete-time equations
Xt+1 = f (Xt , Ut , Wt ),
Yt = g(Xt , Vt )

(1.2)

for some measurable functions f, g, with {Wt } being an independent and identically distributed (i.i.d) system noise process and {Vt } an i.i.d. disturbance process, which are independent of X0 and each other. Here, the first equation represents the transition kernel T as
it gives the relation of the most recent state and action variables to the upcoming state. From
this representation it can be seen that the probabilistic nature of the kernel is determined by
the function f and the probability model of the noise Wt . The second equation represents
the communication channel Q, as it describes the relation between the state and observation
variables.
We let the objective of the agent(decision maker) be the minimization of the infinite
horizon discounted cost,
"∞
#
X
Jβ (P, T , γ) = EPT ,γ
β t c(Xt , Ut ),
t=0

for some discount factor β ∈ (0, 1), over the set of admissible policies γ ∈ Γ, where c :
X×U → R is a Borel-measurable stage-wise cost function and EPT ,γ denotes the expectation
with initial state probability measure P and transition kernel T under policy γ. Note that
P ∈ P(X), where we let P(X) denote the set of probability measures on X.
We define the optimal cost for the discounted infinite horizon setup as a function of the
priors and the transition kernels as
Jβ∗ (P, T ) = inf Jβ (P, T , γ).
γ∈Γ

The focus of the paper will be to address the following problems:
Problem P1: Continuity of Jβ∗ (P, T ) under the convergence of the transition kernels.
Let {Tn , n ∈ N} be a sequence of transition kernels which converge in some sense to another
transition kernel T . Does that imply that
Jβ∗ (P, Tn ) → Jβ∗ (P, T )?
Problem P2: Robustness to incorrect models. A problem of major practical importance
is robustness of an optimal controller to modeling errors. Suppose that an optimal policy is
constructed according to a model which is incorrect: how does the application of the control
to the true model affect the system performance and does the error decrease to zero as the
models become closer to each other? In particular, suppose that γn∗ is an optimal policy
designed for Tn , an incorrect model for a true model T . Is it the case that if Tn → T then
Jβ (P, T , γn∗ ) → Jβ∗ (P, T )?
2

Problem P3: Empirical consistency of learned probabilistic models and data-driven
stochastic control. Let T (·|x, u) be a transition kernel given previous state and action variables x ∈ X, u ∈ U, which is unknown to the decision maker (DM). Suppose, the DM builds
a model for the transition kernels, Tn (·|x, u), for all possible x ∈ X, u ∈ U by collecting
training data (e.g. from the evolving system). Do we have that the cost calculated under Tn
converges to the true cost (i.e., do we have that the cost obtained from applying the optimal
policy for the empirical model converges to the true cost as the training length increases)?
We refer the reader to Section 2.2 for a flavor of the application models.
In the rest of the paper, we will first provide a brief review of the related literature. In
Section 2, we introduce some convergence notions on the set of probability measures that we
will use in the paper and convergence criteria for controlled transition kernels are introduced.
In Section 3, continuity properties of the optimal cost are studied under different convergence
notions and Problem P1 is studied. Building on these results, we will analyze the robustness
of the optimal control problem with respect to incorrectly estimated system models/kernels
in Section 4. We devote Section 5 to fully observed controlled stochastic systems. Finally,
we apply our results to the setup where a system model is learned through the collection of
empirical data (i.e., the so-called data-driven stochastic control problem) at Section 6.
1.2. Literature Review. Robustness is a desired property for the optimal control of
stochastic or deterministic systems when a given model does not reflect the actual system
perfectly, as is usually the case in practice. A common approach in the literature has been to
design controllers that works sufficiently well for all possible uncertain systems under some
structured constraints, such as H∞ norm bounded perturbations (see [3, 4, 5]). The design for
robust controllers has also been developed through a game formulation where minimizer is the
controller and the strategic maximizer is the uncertainty. The connections of this formulation
to risk sensitive control was established in [6, 7, 8].
Using Legendre-type transforms, the relative entropy constraints came in to the literature to probabilistically model the uncertainties, see e.g. [9, Eqn. (4)] or [8, Eqns. (2)-(3)].
Here, one selects a nominal system which satisfies a relative entropy bound between the actual measure and the nominal measure, solves a risk sensitive optimal control problem, and
this solution value provides an upper bound for the original system performance. As such, a
common approach in robust stochastic control has been to consider all models which satisfy
certain bounds in terms of relative entropy distance (or Kullback-Leibler divergence), see
e.g. [8, 9, 10, 11]. [9] studies the relation of this problem to the dynamic games for general
nonlinear systems in both the discrete and the continuous time setup. [11] relates the same
problem to the risk sensitive optimal control problem for a general nonlinear discrete time
system and obtains a robust solution for a partially observed linear system. [10] considers
optimal control of uncertain systems where the uncertainty is described by a relative entropy
constraint and the authors establish a relation between this problem and the induced norms
(such as H∞ ) of the considered model and minimax game problems. In these contributions,
the relative entropy pseudo-distance is utilized to measure the discrepancy between the joint
probability measure (that governs the finite-horizon path) for the actual system and an incorrectly modeled system. Through the chain rule, for the specific case where the noise affecting
the system is additive and i.i.d., the relative entropy distance between these joint measures is
equivalent to the sum of the relative entropy distance between the noise variables up to the
time horizon of the system, and this turns out to be the summation of the relative entropy
distances between transition kernels. We also note here that the relative entropy is a very
restrictive pseudo-distance measure (note though that this does not define a metric) and in
particular, through Pinsker’s inequality [12, Lemma 5.2.8], it is stronger than even total variation which has also been studied in robust stochastic control. [13] also makes use of similar
techniques for control-free filtering problems; they propose error bounds using the relative
entropy between probability measures for the actual model and an assumed model.
[14, 15] are also among the papers which study the robust H∞ control of continuous time
3

systems. [14] considers stochastic uncertainties while [15] considers deterministic structured
uncertainties. Some connections with our paper can be seen in subsection 2.2.
[16] studies the optimal control of systems with unknown dynamics similar to our case.
The authors consider the Linear Quadratic Regulator problem when the state transitions are
not known perfectly. They propose an algorithm to learn a nominal model for the unknown
dynamics from observed data and estimate some probabilistic guarantees for the error of
the nominal model. Using the nominal model and the bounds on the estimation error, they
solve the robust control problem for the LQR problem and give a bound for the relative error
between the optimal cost and the cost achieved by the robust controller in terms of the size of
the data used to estimate the nominal model.
Other metrics, different from the relative entropy pseudo-distance, are also used to measure the uncertainties. Reference [17] have studied a min-max formulation for robust control
where the one-stage transition kernel belongs to a ball under the total variation metric for
each state action pair and develops a dynamic programming based solution for both finite
and discounted cost infinite horizon problems. Further related work with model uncertainty
includes [18, 19], with some further work in the economics literature [20, 21].
On a related direction, in [22], the authors considered an optimal filtering problem for
a control-free system with uncertainties in transition kernels and measurement channels. It
is shown that under some continuity restrictions, the total variation distance error in the estimated probability measures on the state variables can be bounded.
[23, 24, 25] have studied robust dynamic programming approaches through a min-max
formulation for fully observed finite state-action space models with uncertain transition probabilities. These papers use the likelihood functions as a distance measure between the transition matrices when building ambiguity sets; [25] and [24] also investigate the relative entropy
between the transition matrices. [24] further discusses the total variation distance as a metric
between transition matrices.
Through an ”uncertainty set” approach,[26, 27] also study the robustness of Markov
decision processes for fully observed finite state-action space models. In [27], the authors
consider a problem where there are nested uncertainty sets for unknown parameters of the
system and they show that distributionally robust policies can be solved with a Bellman type
equation through a backward iteration. [26] works on a problem where transitions from some
states are fixed but for a set of states the transitions can change arbitrarily and these are not
known by the decision maker. For the problem, a learning algorithm is proposed and it is
shown that the learned policies can perform as good as the ones that know which states have
arbitrary transitions as well as the fixed transitions.
Distributionally robust stochastic optimization problem is also related to our setting. For
this problem it is assumed that the underlying probability measure of the system lies within an
ambiguity set and a worst case single-stage optimization is made considering the probability
measures in the ambiguity set. [28, 29, 30, 31, 32, 33] are among the notable works in
this direction. To construct the ambiguity sets different distance measures are used for the
probability measures: [28, 29, 30] use Wasserstein metric which upper bounds the weak
topology metrics in general (see Section 2). [31] uses Prokhorov metric which metrizes the
weak topology. [32] uses total variation distance among the sets of probability measures and
[33] works with the relative entropy distance.
Related work also includes our recent studies [34], [35] (see also [36]). [34] considers
various topologies on the sets of observation channels and quantizers in partially observed
stochastic control and provides some supporting results. [35] presents robustness and continuity properties for stochastic control problems with respect to the prior measures with fixed
transition kernels; that is, the robustness only to initial priors is studied in [35]. Different from
these studies, here we study continuity in and robustness to incorrect transition kernels which
requires significantly different analytical tools due to the dynamic nature of the problems.
Contributions. Complementing much of the literature cited above, this paper provides
4

an analytical approach to robustness and continuity under much weaker convergence criteria:
We show that for infinite horizon discounted cost setup, continuity and robustness cannot always be established under weak convergence and setwise convergence of transition kernels
(or approximate models) to a true kernel in general, but that the optimal cost is continuous
in the transition kernels under the convergence in total variation, under mild conditions. By
imposing further assumptions on the measurement models and on the actual kernel itself, we
also show that the optimal cost can be made continuous under weak convergence of transition
kernels. Using these continuity results we find bounds on the mismatch error that occurs due
to the application of a control policy which is designed for an incorrectly estimated system
model in terms of a distance measure between true model and the incorrect one; and thus we
establish robustness properties and error bounds. Implications of these results in empirical
learning for control will be presented. These lead to practically important results on empirical learning in stochastic control since often, in engineering applications, system models
are learned through training data. In particular, compared to the existing literature reviewed
earlier, we obtain refined convergence results that are applicable even under the weak convergence criteria, in addition to total variation criteria. We consider both fully observed and
partially observed settings.
2. Some Examples and Convergence Criteria for Transition Kernels.
2.1. Convergence of probability measures and convergence criteria for transition
kernels. Before presenting convergence criteria for controlled transition kernels, we first review convergence of probability measures. Three important notions of convergences for sets
of probability measures to be studied in the paper are weak convergence, setwise convergence
and convergence under total variation. For some N ∈ N a sequence {µn , n ∈ N} in P(RN )
is said to converge to µ ∈ P(RN ) weakly if
Z
Z
c(x)µ(dx)
(∗)
c(x)µn (dx) →
RN

RN

for every continuous and bounded c : RN → R.
{µn } is said to converge setwise to µ ∈ P(RN ) if ∗ holds for all measurable and bounded
c : RN → R. Setwise convergence can also be equivalently defined through pointwise
convergence on Borel subsets of RN , that is, µn (A) → µ(A) for all A ∈ B(RN ).
For probability measures µ, ν ∈ P(RN ), the total variation metric is given by
kµ − νkT V = 2

sup

|µ(B) − ν(B)|

B∈B(RN )

=

sup
f :kf k∞ ≤1

Z

f (x)µ(dx) −

Z

f (x)ν(dx) ,

where the supremum is taken over all measurable real f such that kf k∞ = supx∈RN |f (x)| ≤
1. A sequence {µn } is said to converge in total variation to µ ∈ P(RN ) if kµn − µkT V → 0.
We should again note that the convergence of two probability measures under relative
entropy distance implies the convergence in total variation through Pinsker’s inequality [12,
Lemma 5.2.8].
Another metric for probability measures is the Wasserstein distance. For compact spaces,
the Wasserstein distance of order 1 denoted by W1 , metrizes the weak topology on the set
of probability measures defined on that compact space (see [37, Theorem 6.9]). For noncompact spaces convergence in the W1 metric implies weak convergence (in particular this
metric bounds from above the Bounded-Lipschitz metric [37, p.109]). Considering these
relations, our results in this paper can be directly generalized to the relative entropy distance
or the Wasserstein distance.
5

Building on the above, we introduce the following convergence notions for (controlled)
transition kernels.
D EFINITION 2.1. For a sequence of transition kernels {Tn , n ∈ N}, we say that
(i) Tn → T weakly if Tn (·|x, u) → T (·|x, u) weakly, for all x ∈ X and u ∈ U.
(ii) Tn → T setwise if Tn (·|x, u) → T (·|x, u) setwise, for all x ∈ X and u ∈ U.
(iii) Tn → T under the total variation distance if Tn (·|x, u) → T (·|x, u) under total
variation, for all x ∈ X and u ∈ U.
2.2. Examples. Let a controlled model be given as
xt+1 = F (xt , ut , wt ),
where {wt } is an i.i.d. noise process. As it is stated earlier, the probabilistic nature of the
transition kernel is affected by the function F and the probability model of the noise wt . Thus,
the uncertainty on the transition kernel may arise from lack of information about the function
F or about the probability model of the noise wt or both. In the following, we sometimes
assume the function F is not known perfectly or the exact probability model of the noise is
unknown or both of them are unknown simultaneously.
(i) Let {Fn } denote an approximating sequence for F , so that Fn (x, u, w) →
F (x, u, w) pointwise. Assume that the probability measure of the noise is known.
Then, corresponding kernels Tn converges weakly to T as the following argument
shows: If we denote the probability measure of w with µ, for any g ∈ Cb (X) and
for any (x0 , u0 ) ∈ X × U using the dominated convergence theorem we have
Z
Z
lim
g(x1 )Tn (dx1 |x0 , u0 ) = lim
g(Fn (x0 , u0 , w))µ(dw)
n→∞
n→∞
Z
Z
= g(F (x0 , u0 , w))µ(dw) = g(x1 )T (dx1 |x0 , u0 ).
(ii) Much of the robust control literature deals with deterministic systems where
the nominal model is a deterministic perturbation of the actual model (see e.g.
[38, 39, 15, 16]). The considered model is in the following form; F̃ (xt , ut ) =
F (xt , ut ) + ∆F (xt , ut ), where F (·) represents the nominal model and ∆F (·) is the
model uncertainties satisfying some norm bounds. Although, the methodology in
the cited papers is quite different then ours, for these systems, xt+1 = F̃ (xt , ut ),
can be viewed to be a special case of the analysis here in view of the discussion
in (i): For such deterministic systems, pointwise convergence of F̃ to the nominal
model F , i.e. ∆F (xt , ut ) → 0, ∀xt , ut , can be viewed as weak convergence for
deterministic systems in the context of the discussion in (i). It is evident, however,
that total variation convergence would be too strong for such a convergence criterion, since δF̃ (xt ,ut ) → δF (xt ,ut ) weakly but kδF̃ (xt ,ut ) − δF (xt ,ut ) kT V = 2 for all
∆F (xt , ut ) > 0.
(iii) Let F (xt , ut , wt ) = f (xt , ut ) + wt be such that the function f is known and wt ∼ µ
is not known correctly and an incorrect model µn is assumed. If µn → µ weakly,
setwise and total variation then the corresponding transition kernels Tn converges in
the same sense to T . Observe the following,
Z
Z
g(x1 )Tn (dx1 |x0 , u0 ) − g(x1 )T (dx1 |x0 , u0 )
Z
Z
= g(w0 + f (x0 , u0 ))µn (dw0 ) − g(w0 + f (x0 , u0 ))µ(dw0 ).
(2.1)
a. Suppose µn → µ weakly, if g is a continuous and bounded function then
g(w0 + f (x0 , u0 )) is a continuous and bounded function of w0 for all
6

(x0 , u0 ) ∈ X × U. Thus, (2.1) goes to 0. Note that f does not need to be
continuous.
b. Suppose µn → µ setwise, similarly if g is a measurable and bounded function
then g(w0 + f (x0 , u0 )) is measurable and bounded in w0 for all (x0 , u0 ) ∈
X × U. Thus, (2.1) goes to 0.
c. Finally, assume µn → µ in total variation. If g(x1 ) is uniformly bounded in
x1 then so does g(w0 + f (x0 , u0 )) in w0 . Therefore, (2.1) converges to 0. A
special case for this would be the following: Assume µn and µ admit densities
hn and h respectively, then the pointwise convergence of hn to h implies the
convergence of µn to µ in total variation by Scheffe’s Theorem ([40]).
(iv) Suppose now neither F nor the probability model of wt is known perfectly. It is
assumed that wt admits a measure µn and µn → µ weakly. For the function F we
again have an approximating sequence {Fn }. If Fn (x, u, wn ) → F (x, u, w) for all
(x, u) ∈ X × U and for any {wn } ⊂ W and w ∈ W such that wn → w, then the
transition kernel Tn corresponding to the model Fn converges weakly to the one of
F , T . To see this, observe the following: For any g ∈ Cb (X),
Z
Z
lim
g(x1 )Tn (dx1 |x0 , u0 ) = lim
g(Fn (x0 , u0 , w))µn (dw)
n→∞
n→∞
Z
Z
= g(F (x0 , u0 , w))µ(dw) = g(x1 )T (dx1 |x0 , u0 ).
In the analysis above we used a result, Lemma 3.3, to be presented later building on
[41, Theorem 3.5] and [42, Theorem 3.5].
(v) Let again {Fn } denote an approximating sequence for F and suppose now
Fx0 ,u0 ,n (·) := Fn (x0 , u0 , ·) : W → X is invertible for all x0 , u0 ∈ X ×
−1
U and F(x
(·) denotes the inverse for fixed (x0 , u0 ). It is assumed that
0 ,u0 ),n
−1
(x1 ) pointwise for all (x0 , u0 ). Suppose further that the
F(x0 ,u0 ),n (x1 ) → Fx−1
0 ,u0
noise process wt admits a continuous density fW (w).
1
The Jacobian matrix, ∂x
∂w , is the matrix whose components are the partial derivatives
of x1 , i.e. with x1 ∈ X ⊂ Rm and w ∈ W ⊂ Rm , it is a m × m matrix with
∂x1
1 )i
components ∂(x
∂wj , 1 ≤ i, j ≤ m . If the Jacobian matrix of derivatives ∂w (w)
is continuous in w and nonsingular for all w then by the inverse function theorem
of vector calculus (see [43, Section 1.11]), we have that the density of the state
variables can be written as
fX1 ,n,(x0 ,u0 ) (x1 ) = fW (Fx−1
(x1 ))
0 ,u0 ,n
(x1 ))
fX1 ,(x0 ,u0 ) (x1 ) = fW (Fx−1
0 ,u0

∂x1 −1
(F
(x1 ))
∂w x0 ,u0 ,n

∂x1 −1
(x1 ))
(F
∂w x0 ,u0

−1

−1

.

With the stated assumptions, we have that fX1 ,n,(x0 ,u0 ) (x1 ) → fX1 ,(x0 ,u0 ) (x1 )
pointwise for all fixed (x0 , u0 ). Therefore, by an application of Scheffe’s Theorem
([40]), the corresponding the kernels Tn (·|x0 , u0 ) → T (·|x0 , u0 ) in total variation
for all (x0 , u0 ).
(vi) These studies will be used and analyzed in detail in Section 6, where data-driven
stochastic control problems will be considered where estimated models are obtained
through empirical measurements of the state action pairs and the subsequent state
values. We will make the point that, for empirical learning weak convergence is
a naturally applicable convergence criterion, whereas the applicability of convergence and robustness under stronger notions such as total variation require nontrivial knowledge on and restrictions for the system model.
7

The analysis in the paper will thus provide robustness results for a large class of control
systems as studied in the aforementioned examples.
3. Continuity of Optimal Cost with respect to Convergence of Transition Kernels.
In this section, we will look at the uncertainty in the dynamics of the partially observed controlled Markov chains. In particular, we will study the continuity of the optimal discounted
cost under the convergence of the transition kernels.
3.1. Absence of continuity under weak convergence. The following result shows that
the optimal discounted cost may not be continuous under the weak convergence of transition
kernels.
T HEOREM 3.1. Let Tn → T weakly then it is not necessarily true that Jβ∗ (P, Tn ) →
∗
Jβ (P, T ) even when the prior distributions are same, the measurement channel Q is continuous in total variation and c(x, u) is continuous and bounded in X × U.
Proof. We prove the result with a counterexample. Let X = U = Y = [−1, 1] and
c(x, u) = (x − u)2 , the observation channel is chosen to be uniformly distributed over [-1,1],
Q ∼ U ([−1, 1]), the initial distributions of the state variable are chosen to be same as P ∼ δ1
that is X0 = 1 and the transition kernels are defined to be,
1
1
1
1
T (x1 |x, u) = δ−1 (x)[ δ1 + δ−1 ] + δ1 (x)[ δ1 + δ−1 ]
2
2
2
2
+ (1 − δ−1 (x))(1 − δ1 (x))δ0
1
1
Tn (x1 |x, u) = δ−1 (x)[ δ(1−1/n) + δ(−1+1/n) ]
2
2
1
1
+ δ1 (x)[ δ(1−1/n) + δ(−1+1/n) ]
2
2
+ (1 − δ−1 (x))(1 − δ1 (x))δ0
It can be seen that Tn → T weakly according to Definition 2.1(i).
The measurement channel is non-informative and the control actions do not have any
impact on the progress of the chain which happens symmetrically around zero. Therefore,
the optimal control actions are given by,
(
0 if k > 0
γk∗ (y[0,k] ) = E[Xk ] =
1 if k = 0
Also note that the cost function is continuous, observation channel is continuous in total
variation and the initial distributions are same.
Under this setup the optimal discounted costs can be found as,
Jβ∗ (P, T ) =

∞
X

ET [β k Xk2 ] =

k=1
∞
X

Jβ∗ (P, Tn ) =

k=1

∞
X

k=1

βk =

β
1−β

1
1
1
1
ETn [β k Xk2 ] = β[ (1 − )2 + (−1 + )2 ].
2
n
2
n

Then we have Jβ∗ (P, Tn ) → β 6=

β
1−β

3.2. A sufficient condition for continuity under weak convergence. In the following,
we will establish and utilize some regularity properties for the optimal cost in the space of
priors and the transition kernels.
8

3.2.1. Partially observable Markov Decision Processes and the reduction to a beliefMDP. Consider a partially observed Markov decision process (POMDP), with state space
X, action space U, and observation space Y, all Borel spaces Define the history spaces
Ht = (Y × U)t × Y, t = 0, 1, 2, . . . endowed with their product Borel σ-algebras generated
by B(Y) and B(U). A policy π = {πt } is a sequence of stochastic kernels on U given Ht .
We denote by Π the set of all policies. For any initial distribution µ and policy π we can
think of the POMDP as a stochastic process Xt , Yt , Ut t≥0 defined on the probability space

Ω, B(Ω), Pµπ , where Ω = H∞ × X∞ , the Xt are X-valued random variables, the Yt are
Y-valued random variables, the Ut are U-valued random variables.
It is known that any POMDP can be reduced to a (completely observable) MDP [44],
[45], whose states are the posterior state distributions or ’beliefs‘ of the observer; that is, the
state at time t is
Zt ( · ) := Pr{Xt ∈ · |Y0 , . . . , Yt , U0 , . . . , Ut−1 } ∈ P(X).
We call this equivalent MDP the belief-MDP . The belief-MDP has state space Z = P(X)
and action space U. Recall that Z is equipped with the Borel σ-algebra generated by the
topology of weak convergence [46]. Since X is a Borel space, Z is metrizable with the
Prokhorov metric which makes Z into a Borel space [47]. The transition probability η of
the belief-MDP can be constructed as follows (see also [48]). If we define the measurable
function F (z, a, y) := Pr{Xt+1 ∈ · |Zt = z, Ut = u, Yt+1 = y} from Z × U × Y to Z and
the stochastic kernel H( · |z, u) := Pr{Yt+1 ∈ · |Zt = z, Ut = u} on Y given Z × U, then
η can be written as
Z
1{F (z,u,y)∈ · } H(dy|z, u).
(3.1)
η( · |z, u) =
Y

The one-stage cost function c of the belief-MDP is given by
Z
c(x, u)z(dx).
c̃(z, u) :=

(3.2)

X

Hence, the belief-MDP is a Markov decision process with the components (Z, U, η, c̃).
For the belief-MDP define the history spaces H̃t = (Z × U)t × Z, t = 0, 1, 2, . . . and let
Π̃ denote the set of all policies for the belief-MDP, where the policies are defined in an usual
manner. Let Jβ (π̃, ξ) denote the cost function of policy π̃ ∈ Π̃ for initial distribution ξ of the
belief-MDP.
It is a standard result that an optimal control policy will use the belief zt as a sufficient
statistic for optimal policies (see [44], [45]).
Notice that any history vector h̃t = (z0 , . . . , zt , u0 , . . . , ut−1 ) of the belief-MDP is a
function of the history vector ht = (y0 , . . . , yt , u0 , . . . , ut−1 ) of the POMDP. Let us write
this relation as i(ht ) = h̃t . Hence, for a policy π̃ = {π̃t } ∈ Π̃, we can define a policy
π π̃ = {πtπ̃ } ∈ Π as
πtπ̃ ( · |ht ) := π̃t ( · |i(ht )).

(3.3)

Let us write this as a mapping from Π̃ to Π: Π̃ ∋ π̃ 7→ i(π̃) = π π̃ ∈ Π. It is straightforward
to show that the cost functions Jβ (π̃, ξ) and W (π π̃ , µ) are the same, where ξ = δµ . One can
also prove that (see [44], [45])
inf Jβ (π̃, ξ) = inf Jβ (π, µ)
π∈Π

π̃∈Π̃

(3.4)

and furthermore, that if π̃ is an optimal policy for belief-MDP, then π π̃ is optimal for the
POMDP as well. Hence, the POMDP and the corresponding belief-MDP are equivalent in
9

the sense of cost minimization. Therefore, results developed for MDPs can be applied to the
belief-MDP and so, to the POMDP. However, one should keep in mind that the correspondence between policies of the belief-MDP and the POMDP is quite complicated as one has to
compute the so-called non-linear filtering equation F : Z × U × Y → Z at each time step.
Furthermore, stationary policies in the belief-MDP can be history dependent in the original
POMDP.
3.2.2. Continuity properties of the belief-MDP.
A SSUMPTION 3.1.
(a) The stochastic kernel T (dx1 |x0 = x, u0 = u) is weakly continuous in (x, u).
(b) The observation channel Q(dy|x) is continuous in total variation i.e., if xk → x,
then Q( · |xk ) → Q( · |x) in total variation.
(c) The stage-wise cost function c(x, u) is non-negative, bounded and continuous on
X×U
(d) U is compact.
Note that by [49, Proposition 7.30], the one stage cost function c̃ of the belief-MDP,
which is defined in (3.2), is continuous and bounded, that is in Cb (Z × U), under Assumption
3.1-(a),(b). The following theorem is from [50, Theorem 3.7, Example 4.1] and [51, Example
2.1].
T HEOREM 3.2.
(i) Under Assumption 3.1, the stochastic kernel η for belief-MDP is weakly continuous
in (z, u).
(ii) If we relax the continuity in total variation of the observation channel to weak continuity, then η may not be weakly continuous even if the transition probability T of
POMDP is continuous in total variation.
(iii) η may not be setwise continuous in u even if the observation channel is continuous
in total variation.
Now we give some conditions under which the weak convergence of transition kernels
for POMDP implies the continuity of optimal discounted costs.
For the main result, we will use the following lemmas. The first one is a result of [41,
Theorem 3.5] and [42, Theorem 3.5]. The second one is a relatively standard and immediate
result (which again follows from [42], among other references).
L EMMA 3.3. Suppose {µn }n ⊂ P(X), where X is metric space, converges weakly
to some µ ∈ P(X). For a bounded real valued sequence of functions {fn }n such that
kfn k∞ < C for all n > 0 with C < ∞, if limn→∞ fn (xn ) = f (x) for all xn → x, i.e. fn
continuously converges to f , then
Z
Z
f (x)µ(dx).
fn (x)µn (dx) =
lim
n→∞

X

X

L EMMA 3.4. Suppose {µn }n ⊂ P(X), where X is metric space, converges to some
µ ∈ P(X) in total variation. For a bounded real valued sequence of functions {fn }n such
that kfn k∞ < C for all n > 0 with C < ∞, if limn→∞ fn (x) = f (x) for all x, then
Z
Z
f (x)µ(dx).
fn (x)µn (dx) =
lim
n→∞

X

X

Proof.
lim |

Z

Z

fn (x)µn (dx) − f (x)µ(dx)|
Z
Z
Z
≤ lim | fn (x)µn (dx) − fn (x)µ(dx)| + lim
|fn (x) − f (x)|µ(dx)

n→∞

n→∞

n→∞

10

≤ lim Ckµn − µkT V + lim
n→∞

n→∞

Z

|fn (x) − f (x)|µ(dx) = 0.

L EMMA 3.5. Suppose Assumption 3.1 holds. If a sequence of transition kernels Tn satisfies the following; {Tn (·|xn , un ), n ∈ N} converges weakly to T (·|x, u) for any sequence
{xn , un } ⊂ X × U and (x, u) ∈ X × U such that (xn , un ) → (x, u), then for any z n → z
(weakly) and un → u
ηn (·|z n , un ) → η(·|z, u) weakly.
Proof. The claim is for every f ∈ Cb (P(X)),
Z
Z
n
f (z1 )ηn (dz1 |z0 , un ) → f (z1 )η(dz1 |z0 , u),
where ηn is as in (3.1).
We have
Z
f (z1 (z0n , y1 , un ))Pn (dy1 |x0 , un )z0n (dx0 )
Z
= f (z1 (z0n , y1 , un ))Q(dy1 |x1 )Tn (dx1 |x0 , un )z0n (dx0 )
R
n
n
By Lemma 3.3, if we can show that f (z
R 1 (z0 , y1 , un ))Q(dy1 |x1 )Tn (dx1 |x0 , un ), as
a function of x0 , continuously converges to f (z1 (z0 , y1 , u))Q(dy1 |x1 )T (dx1 |x0 , u) the
result follows as z0n → z0 weakly. Thus, the goal is to show that
Z
Z
n
n
lim
f (z1 (z0 , y1 , un ))Q(dy1 |x1 )Tn (dx1 |x0 , un ) = f (z1 (z0 , y1 , u))Q(dy1 |x1 )T (dx1 |x0 , u).

n→∞

To show this we use Lemma 3.3; by assumption Tn (dx1 |xn0 , un ) → T (dx1 |x0 , u) weakly,
thus we need to show that
Z
Z
lim
f (z1 (z0n , y1 , un ))Q(dy1 |xn1 ) = f (z1 (z0 , y1 , u))Q(dy1 |x1 ).
n→∞

Since Q(dy1 |x1 ) is continuous in total variation by Assumption 3.1, using Lemma 3.4 it
reduces to show that
lim f (z1 (z0n , y1 , un )) = f (z1 (z0 , y1 , u)).

n→∞

Since f is continuous, we need to show that z1 (z0 , y1 , u) is a continuous function of z0
and u. In other words, the goal is to show the convergence of z1 (z0n , y1 , un ) ∈ P(X) to
z1 (z0 , y1 , u) ∈ P(X) in the weak topology.
For any f ∈ Cb (P(X)), we will analyze the following;
lim

n→∞

Z

x1 ∈X

f (x1 )z1 (z0n , y1 , un )(dx1 )

= lim

n→∞

Z

x1 ∈X

f (x1 )P (dx1 |z0n , y1 , un ).

(3.5)

Notice that for any A ∈ B(X), P ((x1 , y1 ) ∈ A × ·|z0n , un ) ≪ P (y1 ∈ ·|z0n , un ) that is
P ((x1 , y1 ) ∈ A × ·|z0n , un ) is absolutely continuous with respect to P (y1 ∈ ·|z0n , un ). Then,
there exists a measurable gA : Y → [0, ∞) such that for any B ∈ B(Y),
Z
gA (y1 )P (dy1 |z0n , un ).
P (x1 , y1 ∈ A × B|z0n , un ) =
B

11

gA is called the Radon-Nikodym derivative and we have

gdx1 (y1 ) :=

dP (x1 , y1 |z0n , un )
= P (dx1 |z0n , y1 , un ).
dP (y1 |z0n , un )

Thus, we can rewrite 3.5 as
Z
dP (x1 , y1 |z0n , un )
f (x1 )
f (x1 )z1 (z0n , y1 , un )(dx1 ) = lim
n→∞ x ∈X
n→∞ x ∈X
dP (y1 |z0n , un )
1
1
R
Z
z n (dx0 )Q(dy1 |x1 )Tn (dx1 |x0 , un )
R 0 n
f (x1 ) R x0 ∈X
= lim
.
(3.6)
n→∞ x ∈X
1
x1 ∈X x0 ∈X z0 (dx0 )Q(dy1 |x1 )Tn (dx1 |x0 , un )
lim

Z

R
R
Notice that x1 ∈X x0 ∈X z0n (dx0 )Q(dy1 |x1 )Tn (dx1 |x0 , un ) is a constant that does not depend on x1 . Let us denote it by αn . Then 3.6 becomes
Z
Z
1
lim
f (x1 )
z0n (dx0 )Q(dy1 |x1 )Tn (dx1 |x0 , un )
n→∞ αn x ∈X
x0 ∈X
1

R
Now we have that gn (xn0 ) := x1 ∈X f (x1 )Q(dy1 |x1 )Tn (dx1 |xn0 , un ) converges to
R
g(x0 ) := x1 ∈X f (x1 )Q(dy1 |x1 )T (dx1 |x0 , u). This is true as Tn (dx1 |xn0 , un ) →
R
T (dx1 |x0 , u) weakly
and
f (x1 )Q(dy1 |x1 ) is continuous and bounded in x1 .
R
R
For αn := x1 ∈X x0 ∈X z0n (dx0 )Q(dy1 |x1 )Tn (dx1 |x0 , u0 ) with the almost similar argument above we have that
Z
Z
z0 (dx0 )Q(dy1 |x1 )T (dx1 |x0 , u0 )
αn → α :=
x1 ∈X

x0 ∈X

With this result if we look at 3.6 again;
Z
Z
n
lim 1/αn
z0 (dx0 )gn (x0 ) = 1/α
n→∞

x0 ∈X

z0 (dx0 )g(x0 ).

x0 ∈X

At the last step we used Lemma 3.3 with the fact that z0n → z0 weakly and gn (xn0 ) → g(x0 ).
We showed that z1 (z0n , y1 , un ) converges weakly to z1 (z0 , y1 , u) as un → u and z0n →
z0 in the weak topology.
Combining the results, ∀f ∈ Cb (P(X)) we have,
Z
Z
n
f (z1 )ηn (dz1 |z0 , un ) = f (z1 (z0n , y1 , un ))Q(dy1 |x1 )Tn (dx1 |x0 , un )z n (dx0 )
Z
Z
→ f (z1 (z0 , y1 , u))Q(dy1 |x1 )T (dx1 |x0 , u)z(dx0 ) = f (z1 )η(dz1 |z0 , u),
which completes the proof.
We now give the continuity result under weak convergence of priors and transition kernels. In the following we will use the successive approximations for the optimal cost. To do
this, we will need an fully observed system, that is why we will be using the belief-MDP and
its components instead of using the partially observed system directly.
T HEOREM 3.6. Suppose a sequence of prior measures {Pn } converges weakly to P and
a sequence of transition kernels Tn satisfies the following; {Tn (·|xn , un ), n ∈ N} converges
12

weakly to T (·|x, u) for any sequence {xn , un } ⊂ X × U and x, u ∈ X × U such that
xn , un → x, u. Under Assumption 3.1
lim |Jβ∗ (Tn , Pn ) − Jβ∗ (T , P )| = 0.

n→∞

Proof. The proof mostly mimic the proof of Proposition 3.10 in [52]. We will use the successive approximations for an inductive argument. We will denote v k (z) = inf u∈U c̃(z, u) +
βE[v k−1 (z1 )|z, u] and for the model with elements Tn and Pn we will use vnk (zn ) to denote
the approximation functions. Then, for the first step of the induction we have
v 1 (z) = c̃(z, u∗ ) vn1 (zn ) = c̃(zn , u∗n )
thus we can write,

|v 1 (z) − vn1 (zn )| ≤ sup c̃(z, u) − c̃(zn , u)
u∈U

since c̃ ∈ Cb (P(X) × U) and the action space, U, is compact, first step of the induction
holds, i.e. limn→∞ |v 1 (z) − vn1 (zn )| = 0.
For the k th step similarly,
sup |v k (z, u) − vnk (zn , u)|


Z
Z
vnk−1 (z 1 )ηn (dz 1 |zn , u)|
≤ sup |c̃(z, u) − c̃(zn , u)| + | v k−1 (z 1 )η(dz 1 |z, u) −

u∈U

u∈U

Z

Z

the first term goes to 0 as c̃(z, u) is continuous in z uniformly over all u ∈ U. For the second
term we write,
Z
Z
sup |
v k−1 (z 1 )η(dz 1 |z, u) −
vnk−1 (z 1 )ηn (dz 1 |zn , u)|
u∈U
Z
Z
Z

v k−1 (z 1 ) − vnk−1 (z 1 ) ηn (dz 1 |zn , u)|
≤ sup |
u∈U
Z
Z
Z
k−1 1
1
+ sup | v
(z )η(dz |z, u) −
v k−1 (z 1 )ηn (dz 1 |zn , u)|
u∈U

Z

Z

for the first term, by the induction argument for any zn1 → z 1 , v k−1 (z 1 ) − vnk−1 (zn1 ) →
0. By Lemma 3.5 we have that ηn (dx|zn , u) → η(·|z, u) weakly uniformly over u ∈ U as U
is compact. Therefore, using Lemma 3.3 the first term goes to 0.
For the second term we again use that ηn (·|zn , u) converges weakly to η(·|z, u) uniformly over u ∈ U and by the induction argument v k−1 (z 1 ) is continuous in z 1 , thus the
second term also goes to 0.
So far, we have showed that for any k ∈ N, limn→∞ vnk (zn ) − v k (z) = 0. It can be
shown that the approximation operator is a contractive operator under supremum norm with
modulus β. Thus, we have
Jβ∗ (T , P ) − v k (z) ≤ kck∞

βk
,
1−β

Jβ∗ (Tn , Pn ) − vnk (zn ) ≤ kck∞

βk
.
1−β

(3.7)

Combining the results,
|Jβ∗ (Tn , Pn ) − |Jβ∗ (T , P )|
≤ |Jβ∗ (Tn , Pn ) − vnk (zn )| + |vnk (zn ) − v k (z)| + |Jβ∗ (T , P ) − v k (z)|.
Note that the first and the last term can be made arbitrarily small since 3.7 is true for all k ∈ N
and the second term goes to 0 as we showed with an inductive argument for all k ∈ N.
13

3.3. Absence of Continuity Under Setwise Convergence. We present a result that
shows continuity of optimal costs fails under the setwise convergence of transition kernels
(i.e. Tn (·|x, u) → T (·|x, u) setwise for every x ∈ X and u ∈ U).
T HEOREM 3.7. Suppose Tn (·|x, u) → T (·|x, u) setwise for every x ∈ X and u ∈ U,
then it is not true in general that Jβ∗ (P, Tn ) → Jβ∗ (P, T ), even when X, Y and U are compact
and c(x, u) is continuous and bounded in X × U.
Proof. We prove the result with a counter example building on a related discussion in
[35].
Let X = Y = U = [0, 1] and let c(x, u) = (x − u)2 . For n ∈ N and k = 1, . . . , n, we
define




2k − 1 k
2k − 2 2k − 1
, Rn,k =
.
,
,
Ln,k =
2n
2n
2n
n
For ease of notation, let L = {y ∈ ∪nk=1 Ln,k } and R = {y ∈ ∪nk=1 Rn,k }. Next, define the
square-wave function by
hn (t) = 1{t∈L} − 1{t∈R} .
and the function
fn (t) = (1 + hn (t))1{t∈[0,1]}
is a probability density function.
Assume the transition kernels Tn , T , prior distribution P and channel Q are given by;
Tn (·|x, u) ∼ 1L (x)fn (·) + 1R (x)U ([0, 1])
T (·|x, u) ∼ U ([0, 1])
P (·) ∼ δ0 (·)
1
1
Q(·|x) ∼ δx (·) + U ([0, 1])
2
2
The control does not have any effect on the transition. Considering this fact and building
on the calculations in [35], for every time step k > 0,
(
1
− 1
if yk ∈ ∪nk=1 Rn,k
γnk (y[0,k] ) = En [Xk |Y[0,k] = y[0,k] ] = 21 14n 1  2
if yk ∈ ∪nk=1 Ln,k .
3 · 2 − 4n + 3 yk


1 1
+ yk ,
γ k (y[0,k] ) = E[Xk |Y[0,k] = y[0,k] ] =
2 2
for k=0,
γn0 (y) = γ 0 (y) = 0.
Then the expected cost is zero when k = 0, for k > 0 we have,
1
1
−
18 24n2
1
E[(Xk − γ k (Y[0,k] ))2 ] = .
16

En [(Xk − γnk (Y[0,k] ))2 ] =

So the optimal discounted cost can be calculated as




∞
X
1
β
1
1
1
Jβ∗ (Tn ) =
βk
=
−
−
18 24n2
1 − β 18 24n2
k=1

14

Jβ∗ (T ) =

∞
X

βk

k=1

1
β
=
16
16(1 − β)

Thus, we can see that Tn (·|x, u) → T (·|x, u) setwise for every x ∈ X and u ∈ U but
β
β
6= 16(1−β)
= Jβ∗ (T ).
Jβ∗ (Tn ) → 18(1−β)
3.4. Continuity under total variation. We now give two continuity results for convergence under the total variation metric.
T HEOREM 3.8. Suppose that the action space U is compact and Tn is such that for any
sequence {un } ⊂ U converging to some u ∈ U, Tn (·|x, un ) → T (·|x, u) in total variation
for all x ∈ X. Also assume that the kernel T (·|x, u) is continuous in total variation in u for
every given x ∈ X. If the stage-wise cost function c is bounded on X × U then
Jβ∗ (P, Tn ) → Jβ∗ (P, T ).
Proof. We start with the following bound,


∗
∗
∗
∗
∗
∗
|Jβ (Tn ) − Jβ (T )| ≤ max Jβ (Tn , γ ) − Jβ (T , γ ), Jβ (T , γn ) − Jβ (Tn , γn )
where γ ∗ and γn∗ are the optimal policies respectively for T and Tn .
To show the continuity, we first start with the second term,


∞
h
h
X
i
i
∗
∗
k
Jβ (Tn , γn ) − Jβ (T , γn ) =
β ETn c Xk , γn (Y[0,k] ) − ET c Xk , γn (Y[0,k] )
.
k=0

For the terms inside of the summation, we will look at every time step k separately. For
easiness of notation we will first study the case where k = 3.
h
h
i
i
ET c X3 , γn (Y[0,3] ) − ETn c X3 , γn (Y[0,3] )
Z
= P (dx0 )Q(dy0 |x0 )T (dx1 |x0 , γn (y0 ))Q(dy1 |x1 )T (dx2 |x1 , γn (y[0,1] ))
× Q(dy2 |x2 )T (dx3 |x2 , γn (y[0,2] ))Q(dy3 |x3 )c(x3 , γn (y[0,3] ))

−

Z

P (dx0 )Q(dy0 |x0 )Tn (dx1 |x0 , γn (y0 ))Q(dy1 |x1 )Tn (dx2 |x1 , γn (y[0,1] ))
× Q(dy2 |x2 )Tn (dx3 |x2 , γn (y[0,2] ))Q(dy3 |x3 )c(x3 , γn (y[0,3] )).

Then, we must show the following
Z
lim
T (dx1 |x0 , γn (y0 ))Q(dy1 |x1 )T (dx2 |x1 , γn (y[0,1] ))
n→∞

× Q(dy2 |x2 )T (dx3 |x2 , γn (y[0,2] ))Q(dy3 |x3 )c(x3 , γn (y[0,3] ))

−

Z

Tn (dx1 |x0 , γn (y0 ))Q(dy1 |x1 )Tn (dx2 |x1 , γn (y[0,1] ))
× Q(dy2 |x2 )Tn (dx3 |x2 , γn (y[0,2] ))Q(dy3 |x3 )c(x3 , γn (y[0,3] ))

= 0.
15

First notice that with the given assumption, T (·|x, u) is continuous in total variation in u.
Thus, Tn (dx1 |x0 , γn (y0 )) and T (dx1 |x0 , γn (y0 )) converge each other in total variation since
U is compact. Thus, using Lemma 3.4 we must show that
Z
Q(dy1 |x1 )T (dx2 |x1 , γn (y[0,1] ))Q(dy2 |x2 )T (dx3 |x2 , γn (y[0,2] ))Q(dy3 |x3 )c(x3 , γn (y[0,3] ))
and
Z
Q(dy1 |x1 )Tn (dx2 |x1 , γn (y[0,1] ))Q(dy2 |x2 )Tn (dx3 |x2 , γn (y[0,2] ))Q(dy3 |x3 )c(x3 , γn (y[0,3] ))
converge each other. To show this, we use the same argument as before so that
Tn (dx2 |x1 , γn (y[0,1] )) and T (dx2 |x1 , γn (y[0,1] )) converges each other in total variation, thus
it reduces to show that
Z
Q(dy2 |x2 )T (dx3 |x2 , γn (y[0,2] ))Q(dy3 |x3 )c(x3 , γn (y[0,3] ))
and
Z

Q(dy2 |x2 )Tn (dx3 |x2 , γn (y[0,2] ))Q(dy3 |x3 )c(x3 , γn (y[0,3] ))

converge to each other which holds true using the same argument.
The same argument can P
be generalized for any time step k < ∞. For any ǫ > 0, we
∞
choose a K < ∞ such that k=K+1 β k 2kck∞ ≤ ǫ/2. For the chosen K, we choose an
N < ∞ such that
h
h
i
i
ET c Xk , γn (Y[0,k] ) − ETn c Xk , γn (Y[0,k] ) ≤ ǫ/2K

for all time stages k ≤ K and for all n > N . Thus, we have that for any given ǫ > 0, for
n>N
Jβ∗ (Tn , γn∗ ) − Jβ∗ (T , γn∗ ) < ǫ

(3.8)

The same arguments can be repeated to show that Jβ∗ (Tn , γ ∗ ) − Jβ∗ (T , γ ∗ ) → 0 as
n → ∞. Thus, the result follows.
We now propose a result that gives an upper bound for the rate of convergence. For
the result we will make use of strategic measures . For stochastic control problems, strategic
measures are defined (see Schäl [53], also [54, 55]) as the set of probability measures induced
on the product spaces of the state and action pairs by measurable control policies: Given an
initial distribution on the state, and a policy, one can uniquely define a probability measure on
the infinite product space consistent with finite dimensional distributions, by Ionescu Tulcea
theorem [56]. Now, define a strategic measure under a policy γ n = {γ0n , γ1n , · · · , γkn , · · · } as
a probability measure defined on B(X × Y × U)Z+ by:
n

PTγ (d(x0 , y0 , u0 ), d(x1 , y1 , u1 ), · · · )
= P (dx0 )Q(dy0 |x0 )1{γ n (y0 )∈du0 } T (dx1 |x0 , u0 )Q(dy1 |x1 )1{γ n (y0 ,y1 )∈du1 } · · ·
T HEOREM 3.9. If the cost function c is bounded,
|Jβ∗ (P, Tn ) − Jβ∗ (P, T )| ≤
16

kck∞

β
(β − 1)2

sup
x∈X,u∈U

kTn (.|x, u) − T (.|x, u)kT V .

Proof. We start with the following bound as before,


∗
∗
∗
∗
∗
∗
|Jβ (Tn ) − Jβ (T )| ≤ max Jβ (Tn , γ ) − Jβ (T , γ ), Jβ (T , γn ) − Jβ (Tn , γn )
where γ ∗ and γn∗ are the optimal policies respectively for T and Tn .
Then, with PTγn and PTγ denoting the strategic measures for two chains with a policy γ
and kernels Tn and T , we have
|Jβ (Tn , γ) − Jβ (T , γ)|
Z
Z
X
≤
β k | c(xk , γ(y[0,k] ))PTγn (dxk , dy[0,k] ) − c(xk , γ(y[0,k] ))PTγ (dxk , dy[0,k] )|
k

≤

X

β k kck∞ kPTγn (d(x, y, u)[0,k] ) − PTγ (d(x, y, u)[0,k] )kT V

k

Now we can show the relation between the total variation distance of strategic measures
of the chains until time stage k and the total variation distance of transition kernels,
kPTγn (d(x, y, u)[0,k] ) − PTγ (d(x, y, u)[0,k] )kT V
Z
Z
γ
= sup | f (x, y, u)[0,k] PTn (d(x, y, u)[0,k] ) − f (x, y, u)[0,k] PTγ (d(x, y, u)[0,k] )|
||f ||∞ ≤1

≤

sup |
||f ||∞ ≤1

Z

Z
Z
PTγ ,Tn (dx0 , dy0 , du0 )
T (dx1 |x0 , u0 ) f (x, y, u)[0,k] PTγ ,Tn (dx[2,k] , dy[1,k] , du[1,k] )
−

Z

Z



f (x, y, u)[0,k] PTγ ,Tn (dx[2,k] , dy[1,k] , du[1,k] )

Tn (dx1 |x0 , u0 )
|
Z
Z
+ | PTγ ,Tn (dx[0,1] , dy[0,1] , du[0,1] )
T (dx2 |x1 , u1 ) f (x, y, u)[0,k] PTγ ,Tn (dx[3,k] , dy[2,k] , du[3,k] )

Z
Z
− Tn (dx2 |x1 , u1 ) f (x, y, u)[0,k] PTγ ,Tn (dx[3,k] , dy[2,k] , du[2,k] ) |
Z
Z
· · · + | PTγ ,Tn (dx[0,k−1] , dy[0,k−1] , du[0,k−1] )
T (dxk |xk−1 , uk−1 )f (x, y, u)[0,k]

Z
− Tn (dxk |xk−1 , uk−1 )f (x, y, u)[0,k] |
Z
≤ PTγ ,Tn (dx0 , dy0 , du0 )kT (·|x0 , u0 ) − Tn (·|x0 , u0 )kT V
Z
+ PTγ ,Tn (dx[0,1] , dy[0,1] , du[0,1] )kT (·|x1 , u1 ) − Tn (·|x1 , u1 )kT V
Z
· · · + PTγ ,Tn (dx[0,k−1] , dy[0,k−1] , du[0,k−1] ))kT (·|xk−1 , uk−1 ) − Tn (·|xk−1 , uk−1 )kT V
Z

≤k

sup

x∈X,u∈U

kT (.|x, u) − Tn (.|x, u)kT V .

In the above argument PTγ ,Tn denotes a strategic measure that uses T or Tn at various steps.
The terms are arranged so that at every term the used strategic measures coincide so that they
use same T or Tn at the same steps.
17

Then combining the results we have
X
kJβ∗ (Tn ) − Jβ∗ (T )| ≤
β k kck∞ k
k

= kck∞

sup
x∈X,u∈U

β
(β − 1)2

kT (.|x, u) − Tn (.|x, u)kT V

sup
x∈X,u∈U

kT (.|x, u) − Tn (.|x, u)kT V

4. Robustness to incorrect transition kernels. Suppose we design an optimal policy,
γn∗ , for a transition kernel, Tn , assuming it is the correct model and apply the policy to the
true model whose transition kernel is T . In this section, we study the robustness of the suboptimal policy γn∗ ; in particular, we ask the following question: Does the cost caused by γn∗
converge to the true optimal cost as Tn converges in some sense to T ?
4.1. Total variation. We propose a result for bounding our loss that arises because of
applying the incorrectly calculated policy to the actual model.
T HEOREM 4.1. Suppose the stage-wise cost function c(x, u) is bounded in X × U, then
|Jβ (P, T ,γn∗ ) − Jβ∗ (P, T )| ≤
β
sup kT (.|x, u) − Tn (.|x, u)kT V
2kck∞
(β − 1)2 x∈X,u∈U
for a fixed prior distribution P ∈ P(X), where γn∗ is the optimal policy designed for the
transition kernel Tn .
Proof. We begin with the following,
|Jβ (T , γn∗ ) − Jβ∗ (T )| ≤ |Jβ (T , γn∗ ) − Jβ (Tn , γn∗ )| + |Jβ (Tn , γn∗ ) − Jβ (T , γ ∗ )|
The second term is bounded using Theorem 3.9. For the first term, we use the proof of
Theorem 3.9 where we showed for any γ ∈ Γ
|Jβ (T , γ) − Jβ (Tn , γ)| ≤ kck∞

β
(β − 1)2

sup
x∈X,u∈U

kT (.|x, u) − Tn (.|x, u)kT V .

Thus, the result follows.
The next theorem gives an asymptotic robustness result.
T HEOREM 4.2. Assume that the conditions of Theorem 3.8 hold, then
|Jβ (P, T , γn∗ ) − Jβ∗ (P, T )| → 0
where γn∗ is the optimal policy designed for the kernel Tn .
Proof. We write the following;
|Jβ (P, T , γn∗ ) − Jβ∗ (P, T )| ≤ |Jβ (P, T , γn∗ ) − Jβ∗ (P, Tn )| + |Jβ∗ (P, Tn ) − Jβ∗ (P, T ).
The second term goes to 0 by Theorem 3.8 and the first term goes to 0 using (3.8) again from
the proof of Theorem 3.8.
4.2. Weak convergence. We now propose robustness results for the case of weak convergence.
L EMMA 4.3. Suppose the conditions of Theorem 3.6 hold. Then for any sequence
{γn } ⊂ Γ,
|Jβ (P, Tn , γn ) − Jβ (P, T , γn )| → 0
18

Proof.
Jβ (P, Tn , γn ) − Jβ (P, T , γn ) =

∞
X

k=0


 h
h
i
i
β k ET c Xk , γn (Y[0,k] ) − ETn c Xk , γn (Y[0,k] )

For the terms inside of the summation, we will look at every time step k separately. For
easiness of notation we will first study the case where k = 3.
h
h
i
i
ET c X3 , γn (Y[0,3] ) − ETn c X3 , γn (Y[0,3] )
Z
= P (dx0 )Q(dy0 |x0 )T (dx1 |x0 , γn (y0 ))Q(dy1 |x1 )T (dx2 |x1 , γn (y[0,1] ))
× Q(dy2 |x2 )T (dx3 |x2 , γn (y[0,2] ))Q(dy3 |x3 )c(x3 , γn (y[0,3] ))

−

Z

P (dx0 )Q(dy0 |x0 )Tn (dx1 |x0 , γn (y0 ))Q(dy1 |x1 )Tn (dx2 |x1 , γn (y[0,1] ))
× Q(dy2 |x2 )Tn (dx3 |x2 , γn (y[0,2] ))Q(dy3 |x3 )c(x3 , γn (y[0,3] )).

Then, using the dominated convergence theorem, we must show the following
Z
lim
T (dx1 |x0 , γn (y0 ))Q(dy1 |x1 )T (dx2 |x1 , γn (y[0,1] ))
n→∞

× Q(dy2 |x2 )T (dx3 |x2 , γn (y[0,2] ))Q(dy3 |x3 )c(x3 , γn (y[0,3] ))

−

Z

Tn (dx1 |x0 , γn (y0 ))Q(dy1 |x1 )Tn (dx2 |x1 , γn (y[0,1] ))
× Q(dy2 |x2 )Tn (dx3 |x2 , γn (y[0,2] ))Q(dy3 |x3 )c(x3 , γn (y[0,3] ))

= 0.
For the above, we have that T (dx1 |x0 , γn (y0 )) and Tn (dx1 |x0 , γn (y0 )) converge weakly to
each other with the assumptions. If we define the functions
Z
fn1 (x1 ) := Q(dy1 |x1 )T (dx2 |x1 , γn (y[0,1] ))Q(dy2 |x2 )
× T (dx3 |x2 , γn (y[0,2] ))Q(dy3 |x3 )c(x3 , γn (y[0,3] )),

gn1 (x1 ) :=

Z

Q(dy1 |x1 )Tn (dx2 |x1 , γn (y[0,1] ))Q(dy2 |x2 )
× Tn (dx3 |x2 , γn (y[0,2] ))Q(dy3 |x3 )c(x3 , γn (y[0,3] )),

by Lemma 3.3, we need to show that these functions converge continuously to each other, i.e.
limn→∞ |fn1 (xn1 ) − gn1 (xn1 )| = 0 for some xn1 → x1 .
lim |fn1 (xn1 ) − gn1 (xn1 )|
Z
= lim
Q(dy1 |xn1 )T (dx2 |xn1 , γn (y[0,1] ))Q(dy2 |x2 )

n→∞

n→∞

× T (dx3 |x2 , γn (y[0,2] ))Q(dy3 |x3 )c(x3 , γn (y[0,3] ))

−

Z

Q(dy1 |xn1 )Tn (dx2 |xn1 , γn (y[0,1] ))Q(dy2 |x2 )
19

× Tn (dx3 |x2 , γn (y[0,2] ))Q(dy3 |x3 )c(x3 , γn (y[0,3] ))
Q(·|xn1 ) converges in total variation to Q(·|x1 ), thus, using Lemma 3.4, we have to show that
the functions
Z
2
fn (y1 ) := T (dx2 |x1 , γn (y[0,1] ))Q(dy2 |x2 )
× T (dx3 |x2 , γn (y[0,2] ))Q(dy3 |x3 )c(x3 , γn (y[0,3] )),

gn2 (y1 ) :=

Z

Tn (dx2 |x1 , γn (y[0,1] ))Q(dy2 |x2 )
× Tn (dx3 |x2 , γn (y[0,2] ))Q(dy3 |x3 )c(x3 , γn (y[0,3] ))

converge point-wise to each other, i.e. limn→∞ |fn2 (y1 ) − gn2 (y1 )| for all y1 ∈ Y.
lim |fn2 (y1 ) − gn2 (y1 )|
Z
= lim
T (dx2 |xn1 , γn (y[0,1] ))Q(dy2 |x2 )T (dx3 |x2 , γn (y[0,2] ))Q(dy3 |x3 )c(x3 , γn (y[0,3] ))
n→∞
Z
− Tn (dx2 |xn1 , γn (y[0,1] ))Q(dy2 |x2 )Tn (dx3 |x2 , γn (y[0,2] ))Q(dy3 |x3 )c(x3 , γn (y[0,3] )) .

n→∞

Similarly, T (dx2 |xn1 , γn (y[0,1] )) and Tn (dx2 |xn1 , γn (y[0,1] )) converge weakly to each other,
using Lemma 3.3 we need to show that
Z
Q(dy2 |xn2 )T (dx3 |xn2 , γn (y[0,2] ))Q(dy3 |x3 )c(x3 , γn (y[0,3] ))
and

Z

Q(dy2 |xn2 )Tn (dx3 |xn2 , γn (y[0,2] ))Q(dy3 |x3 )c(x3 , γn (y[0,3] ))

converge to each other for some xn2 → xn . Thus, using the same steps as before; since
Q(·|xn2 ) converges in total variation and Tn (dx3 |xn2 , γn (y[0,2] )) and T (dx3 |xn2 , γn (y[0,2] ))
converges weakly to each other the result follows.
For a general time stage k, we can again use the iterative approach we used when k = 3.
Thus, we can generalize that
h
h
i
i
ET c Xk , γn (Y[0,k] ) − ETn c Xk , γn (Y[0,k] ) → 0.

P
k
For any ǫ > 0, we choose a K < ∞ such that ∞
k=K+1 β 2kck∞ ≤ ǫ/2. For the chosen
K, we choose an N < ∞ such that
h
h
i
i
ET c Xk , γn (Y[0,k] ) − ETn c Xk , γn (Y[0,k] ) ≤ ǫ/2K

for all time stages k ≤ K and for all n > N . Thus, we have that Jβ (P, Tn , γn ) −
Jβ (P, T , γn ) → 0 as n → ∞.
T HEOREM 4.4. Under the conditions of Theorem 3.6
|Jβ (P, T ,γn∗ ) − Jβ∗ (P, T )| → 0

for a fixed prior distribution P ∈ P(X), where γn∗ is the optimal policy designed for the
transition kernel Tn .
Proof. We write
|Jβ (T , γn∗ ) − Jβ∗ (T )| ≤ |Jβ (T , γn∗ ) − Jβ (Tn , γn∗ )| + |Jβ (Tn , γn∗ ) − Jβ (T , γ ∗ )|.
The first term goes to 0 by Lemma 4.3. For the second term we use Theorem 3.6.
20

5. Fully Observed Case. In this section, we review the previous results for the fully
observed case where the controller has direct access to the state variables. We present the
results for the fully observed case separately, since the results often are more direct. Furthermore, since a very large class of problems involve fully observed MDPs, the results are stated
more explicitly in this section.
Again, an admissible policy γ is a sequence of control functions {γt , t ∈ Z+ } such that
γt is measurable with respect to the σ-algebra generated by the information variables
It = {X[0,t] , U[0,t−1] },

t ∈ N,

I0 = {X0 }.

where
Ut = γt (It ),

t ∈ Z+

are the U-valued control actions.
It is a well known result that any admissible policy can be replaced with one which is
Markov and which is at least as good as the original policy (see [57, page 457]). Therefore
for this section we will restrict the policies to the ones that are Markov i.e.
Ut = γt (Xt ),

t ∈ Z+ .

Now we give the continuity and robustness results for the fully observed case.
5.1. Weak convergence.
5.1.1. Continuity under weak convergence.
T HEOREM 5.1. Let Tn → T weakly then it is not necessarily true that Jβ∗ (Tn ) → Jβ∗ (T )
even when the prior distributions are same and c(x, u) is continuous and bounded in X × U.
Proof. We prove the result with a counterexample, similar to the model used in the
proof of Theorem 3.1 Let X = [−1, 1], U = {−1, 1} and c(x, u) = (x − u)2 , the initial
distributions are given by P ∼ δ1 that is X0 = 1 and the transition kernels are
1
1
1
1
T (x1 |x, u) = δ−1 (x)[ δ1 + δ−1 ] + δ1 (x)[ δ1 + δ−1 ]
2
2
2
2
+ (1 − δ−1 (x))(1 − δ1 (x))δ0
1
1
Tn (x1 |x, u) = δ−1 (x)[ δ(1−1/n) + δ(−1+1/n) ]
2
2
1
1
+ δ1 (x)[ δ(1−1/n) + δ(−1+1/n) ]
2
2
+ (1 − δ−1 (x))(1 − δ1 (x))δ0 .
It can be seen that Tn → T weakly according to Definition 2.1(i).
Under this setup we can calculate the optimal costs as follows;
Jβ∗ (T ) = 0
∞

Jβ∗ (Tn ) =

X
1
1
β2
k
+
β
=
+
.
n2
n2
1−β
k=2

We can see that the continuity does not hold.
L EMMA 5.2. Suppose a sequence of transition kernels Tn satisfies the following;
{Tn (·|xn , un ), n ∈ N} converges weakly to T (·|x, u) for any sequence {xn , un } ⊂ X × U
and x, u ∈ X × U such that xn , un → x, u. If further, the kernel T (·|x, u) is weakly continuous in (x, u), c(x, u) is continuous and bounded on X × U and U is compact, then for any
{γn } ⊂ Γ
lim |Jβ (Tn , γn ) − Jβ (T , γn )| = 0.

n→∞

21

Proof. The proof uses the same technique with Lemma 4.3.

 h
∞
h
X
i
i
k
Jβ (Tn , γn ) − Jβ (T , γn ) =
β ET c Xk , γn (Xk )) − ETn c Xk , γn (Xk )
k=0

For the terms inside of the summation, we will again look at every time step k separately. We
will first study the case where k = 3.
h
h
i
i
ET c X3 , γn (X3 ) − ETn c X3 , γn (X3 )
Z
= P (dx0 )T (dx1 |x0 , γn (x0 ))T (dx2 |x1 , γn (x1 ))T (dx3 |x2 , γn (x2 ))c(x3 , γn (x3 ))
Z
− P (dx0 )Tn (dx1 |x0 , γn (x0 ))Tn (dx2 |x1 , γn (x1 ))Tn (dx3 |x2 , γn (x2 ))c(x3 , γn (x3 )).
We need to show that
Z
lim
T (dx1 |x0 , γn (x0 ))T (dx2 |x1 , γn (x1 ))T (dx3 |x2 , γn (x2 ))c(x3 , γn (x3 ))
n→∞
Z
− Tn (dx1 |x0 , γn (x0 ))Tn (dx2 |x1 , γn (x1 ))Tn (dx3 |x2 , γn (x2 ))c(x3 , γn (x3 ))
= 0.

(5.1)

Above, we have that Tn (dx1 |x0 , γn (x0 )) and T (dx1 |x0 , γn (x0 )) converges weakly to each
other, also
Z
T (dx2 |xn1 , γn (xn1 ))T (dx3 |x2 , γn (x2 ))c(x3 , γn (x3 ))
and
Z

Tn (dx2 |xn1 , γn (xn1 ))Tn (dx3 |x2 , γn (x2 ))c(x3 , γn (x3 ))

converge each other for xn1 → x1 with a similar argument and with the assumptions. Thus,
5.1 follows using Lemma 3.3.
P∞
Similar to before, for any ǫ > 0, we choose a K < ∞ such that k=K+1 β k 2kck∞ ≤
ǫ/2. For the chosen K, we choose an N < ∞ such that
h
h
i
i
ET c Xk , γn (Y[0,k] ) − ETn c Xk , γn (Y[0,k] ) ≤ ǫ/2K

for all time stages k ≤ K and for all n > N . Thus, we have that Jβ (Tn , γn )−Jβ (T , γn ) → 0
as n → ∞.
T HEOREM 5.3. Suppose the conditions of Lemma 5.2 hold, then
lim |Jβ∗ (Tn ) − Jβ∗ (T )| = 0.

n→∞

Proof. Using the usual bound we have


|Jβ∗ (Tn ) − Jβ∗ (T )| ≤ max Jβ (Tn , γ ∗ ) − Jβ (T , γ ∗ ), Jβ (T , γn∗ ) − Jβ (Tn , γn∗ )
where γ ∗ and γn∗ are the optimal policies respectively for T and Tn . Both terms go to 0 using
Lemma 5.2.
22

5.1.2. Robustness under weak convergence.
T HEOREM 5.4. Under the conditions of Lemma 5.2
|Jβ (T ,γn∗ ) − Jβ∗ (T )| → 0
where γn∗ is the optimal policy designed for the transition kernel Tn .
Proof.
|Jβ (T , γn∗ ) − Jβ∗ (T )| ≤ |Jβ (T , γn∗ ) − Jβ (Tn , γn∗ )| + |Jβ (Tn , γn∗ ) − Jβ (T , γ ∗ )|.
The first terms goes to 0 by Lemma 5.2, the second one goes to 0 by Theorem 5.3.
5.2. Setwise convergence. We give a negative result similar to Theorem 3.7.
T HEOREM 5.5. Let Tn → T setwise then it is not necessarily true that Jβ∗ (Tn ) → Jβ∗ (T )
even when the prior distributions are same and c(x, u) is continuous and bounded in X × U.
Proof. We give a similar counter example with the proof of Theorem 3.7.
Let X = [0, 1], U = {0, 1} and let c(x, u) = (x − u)2 . For n ∈ N and k = 1, . . . , n, as
before we define




2k − 2 2k − 1
2k − 1 k
Ln,k =
, Rn,k =
.
,
,
2n
2n
2n
n
For ease of notation, let L = {y ∈ ∪nk=1 Ln,k } and R = {y ∈ ∪nk=1 Rn,k }. Next, define the
square-wave function by
hn (t) = 1{t∈L} − 1{t∈R} .
and the function
fn (t) = (1 + hn (t))1{t∈[0,1]}
is a probability density function.
Assume the transition kernels Tn , T , prior distribution P are
Tn (·|x, u) ∼ 1L (x)fn (·) + 1R (x)δ1 (·)
T (·|x, u) ∼ 1L (x)U ([0, 1]) + 1R (x)δ1 (·)
P (·) ∼ δ0 (·).
We can see that Tn (·|x, u) → T (·|x, u) setwise for every (x, u) ∈ X × U. Then, with the
help of calculations from [35], we can calculate the optimal cost for Tn as;
Jβ∗ (Tn )

 X
n/2
2
y3
=
β
3
t=1
∞
X

t

k=1

2k−1
2n
2k−2
2n

2
+
3

n
X

3

(y − 1)

k=n/2+1

2k−1
2n
2k−2
2n



=

β
1
1
( +
).
(1 − β) 12 8n

The optimal cost for T is given by,
Jβ∗ (T ) =
Thus, we have that Jβ∗ (Tn ) →

1 β2
1 β3
β
β
+ (
+ (
+ ··· =
.
12 2 12 2 12
12 − 6β
β
1
(1−β) ( 12 )

6=

β(1+β)
12

5.3. Total variation.
23

= Jβ∗ (T ).

5.3.1. Continuity under total variation.
L EMMA 5.6. Suppose that the action space U is compact and Tn is such that for any
sequence {un } ⊂ U converging to some u ∈ U, Tn (·|x, un ) → T (·|x, u) in total variation
for all x ∈ X. Also assume that the kernel T (·|x, u) is continuous in total variation in u
for every given x ∈ X. If the stage-wise cost function c is bounded on X × U then for any
{γ}n ⊂ Γ
|Jβ (Tn , γn ) − Jβ (T , γn )| → 0.
Proof. Similar to before, it is enough to show the continuity that for any time k < ∞,
e.g. for k = 3, we will again analyze
h
h
i
i
ET c X3 , γn (X3 ) − ETn c X3 , γn (X3 )
Z
= P (dx0 )T (dx1 |x0 , γn (x0 ))T (dx2 |x1 , γn (x1 ))T (dx3 |x2 , γn (x2 ))c(x3 , γn (x3 ))
Z
− P (dx0 )Tn (dx1 |x0 , γn (x0 ))Tn (dx2 |x1 , γn (x1 ))Tn (dx3 |x2 , γn (x2 ))c(x3 , γn (x3 )).
Since Tn (dx1 |x0 , γn (x0 )) and T (dx1 |x0 , γn (x0 )) converge each other in total variation, by
Lemma 3.4, we should show
Z
T (dx2 |x1 , γn (x1 ))T (dx3 |x2 , γn (x2 ))c(x3 , γn (x3 ))
and
Z

Tn (dx2 |x1 , γn (x1 ))Tn (dx3 |x2 , γn (x2 ))c(x3 , γn (x3 ))

converge each other as functions of x1 . Which holds with the same argument as
T (dx2 |x1 , γn (x1 )) and Tn (dx2 |x1 , γn (x1 )) converge each other in total variation and the
inside terms as a function of x2 converge to each other. Thus, the result follows.
T HEOREM 5.7. Under the conditions of Lemma 5.6
Jβ∗ (Tn ) → Jβ∗ (T ).
Proof.
|Jβ∗ (Tn )

−

Jβ∗ (T



∗
∗
∗
∗
)| ≤ max Jβ (Tn , γ ) − Jβ (T , γ ), Jβ (T , γn ) − Jβ (Tn , γn )

where γ ∗ and γn∗ are the optimal policies respectively for T and Tn . Both terms go to 0 using
Lemma 5.6.
5.3.2. Robustness under total variation.
T HEOREM 5.8. Under the conditions of Lemma 5.6
|Jβ (T ,γn∗ ) − Jβ∗ (T )| → 0
where γn∗ is the optimal policy designed for the transition kernel Tn .
Proof.
|Jβ (T , γn∗ ) − Jβ∗ (T )| ≤ |Jβ (T , γn∗ ) − Jβ (Tn , γn∗ )| + |Jβ (Tn , γn∗ ) − Jβ (T , γ ∗ )|.
The first terms goes to 0 by Lemma 5.6, the second one goes to 0 by Theorem 5.7.
24

6. Implications for Data-Driven Learning Methods in Stochastic Control. In practice, it is unrealistic to assume that the transition law of a controlled Markov chain is known
perfectly. Thus, one might try to learn the transition kernel of the chain from the observed
data. This can be done using the empirical history of the process, i.e. up to a finite time
horizon N , the state and action sequence {x1 , u1 , x2 , u2 , · · · , xN , uN } can be used to infer
some information about the transition laws of the process.
Some of the related works, which use empirical data to infer information about the transition laws, are summarized in the following: In the control-free case, in [58], the history
data is used to estimate the transition probabilities of Markov Chains with finite state spaces
with some regularity conditions like irreducubility; the results are also generalized for autoregressive progresses. Similarly [23] uses the history data to build ambiguity sets for possible
transition matrices for finite models when solving for robust dynamic programming equations. In [24, 25], the authors assume that the initial state can be controlled so that they can
use any sample transition to build ambiguity sets for the kernels for systems with finite action
and state spaces.
Let us briefly discuss the case where a random variable is repeatedly observed, buts its
probability measure is not known apriori. Let {(Xi ), i ∈ N} be an X-valued i.i.d random
variable sequence generated according to some distribution µ.
Defining for every (fixed) Borel B ⊂ X, and n ∈ N, the empirical occupation measures
n

µn (B) =

1X
1{Xi ∈B} ,
n i=1

one has µn (B) → µ(B) almost surely (a.s.) by the strong law of large numbers. Also,
µn → µ weakly with probability one ([59], Theorem 11.4.1).
However, µn can not converge to µ in total variation, in general. On the other hand, if
we know that µ admits a density, we can find estimators to estimate µ under total variation
[60].
In the previous sections, we established some robustness results under the convergence
of transition kernels in the weak topology and the total variation topology. Thus, if we can
show the convergence of the empirically constructed transition kernels to the true models, we
can make use of our results.
6.1. Application of robustness results to data-driven learning.
C OROLLARY 6.1 (to Theorem 3.9 and Theorem 4.1 ). Suppose we are given the following dynamics for finite state space, X, and finite action space, U,
xt+1 =f (xt , ut , wt )
yt =g(xt , vt )
where {wt } and {vt } are i.i.d.noise processes and the noise models are unknown. Suppose
that there is an initial training period so that under some policy, every x, u pair is visited
infinitely often if training were to continue indefinitely, but that the training ends at some
finite time. Let us assume that, through this training, we empirically learn the transition
dynamics with the measurements such that for every (fixed) Borel B ⊂ X, for every x ∈ X,
u ∈ U and n ∈ N, the empirical occupation measures are
Pn
1{X ∈B,Xi−1 =x,Ui−1 =u}
Pn i
.
Tn (B|x0 = x, u0 = u) = i=1
i=1 1{Xi−1 =x,Ui−1 =u}
Then we have that

Jβ∗ (Tn ) → Jβ∗ (T )
25

Jβ (T , γn∗ ) → Jβ∗ (T )
where γn∗ is the optimal policy designed for Tn .
Proof. We have that Tn (B|x, u) → T (B|x, u) weakly for every x ∈ X, u ∈ U almost
surely by law of large numbers. Since the spaces are finite, we have Tn (·|x, u) → T (·|x, u)
under total variation. Therefore, by Theorem 3.9 and Theorem 4.1,
Jβ∗ (Tn ) → Jβ∗ (T )
Jβ (T , γn∗ ) → Jβ∗ (T ).
We can generalize the spaces with some assumptions.
C OROLLARY 6.2 (to Theorem 4.4 and Theorem 3.6 ). Suppose we are given the following dynamics with state space X and action space U,
xt+1 =f (xt , ut , wt )
yt =g(xt , vt )
where {wt } and {vt } are i.i.d.noise processes and the noise models are unknown. Suppose
that f (x, u, w) : W → X is invertible for all (x, u) and f (x, u, w) is continuous and bounded
on X × U × W. We construct the empirical measures for the noise process wt such that for
every (fixed) Borel B ⊂ W, and for every n ∈ N, the empirical occupation measures are
n

µn (B) =

1X
1 −1
n t=0 {fxi−1 ,ui−1 (xi )∈B}

(6.1)

(xi ) denotes the inverse of f (xi−1 , ui−1 , w) : W → X for given
where fx−1
i−1 ,ui−1
(xi−1 , ui−1 ).
Using the noise empirical measures, we can construct the empirical transition kernels
such that for any (x0 , u0 ) and every (fixed) Borel B ⊂ X
(B)).
Tn (B|x0 , u0 ) = µn (fx−1
0 ,u0
If the measurement channel represented by the function g is continuous in total variation then
Jβ∗ (Tn ) → Jβ∗ (T )
Jβ (T , γn∗ ) → Jβ∗ (T )
where γn∗ is the optimal policy designed for Tn .
Proof. We have µn → µ weakly with probability one where µ is the model. We claim
that the transition kernels are such that Tn (·|xn , un ) → T (·|x, u) weakly for any (xn , un ) →
(x, u). To see that observe the following for g ∈ Cb (X),
Z
Z
g(x1 )Tn (dx1 |xn , un ) − g(x1 )T (dx1 |x, u)
Z
Z
= g(f (xn , un , w))µn (dw) − g(f (x, u, w))µ(dw) → 0.
where µn is the empirical measure for wt and µ is the true measure again. For the last step, we
used that µn → µ weakly and g(f (xn , un , w)) continuously converge to g(f (x, u, w)) i.e.
g(f (xn , un , wn )) → g(f (x, u, w) for some wn → w since f and g are continuous functions.
Similarly, it can be also shown that Tn (·|x, u) and T (·|x, u) are weakly continuous on (x, u).
26

Thus, by Theorem 4.4 and Theorem 3.6 if c(x, u) is bounded and U is compact, the result
follows.
Now, we give a similar result with the assumption that the noise process of the dynamics
admits a continuous probability density function.
C OROLLARY 6.3 (to Theorem 3.9 and Theorem 4.1). Suppose we are given the following dynamics for a general state space, X, and action space, U,
xt+1 =f (xt , ut , wt )
yt =g(xt , vt )
where {wt } and {vt } are i.i.d.noise processes and the noise models are unknown however it
is known that the noise wt admits a continuous probability density function.
Suppose that f (x, u, w) : W → X is invertible for all (x, u) . We construct the empirical
measures for the noise process wt as in 6.1.
Using the noise empirical measures, we can construct the empirical transition kernels
such that for any (x0 , u0 ) and every (fixed) Borel B ⊂ X
(B)).
Tn (B|x0 , u0 ) = µn (fx−1
0 ,u0
Then independent of the channel
Jβ∗ (Tn ) → Jβ∗ (T )
Jβ (T , γn∗ ) → Jβ∗ (T )
where γn∗ is the optimal policy designed for Tn .
Proof. By [60] we can estimate µ in total variation so that almost surely limn→∞ kµn −
µkT V = 0. We claim that the convergence of µn to µ under total variation metric implies
the convergence of Tn to T in total variation uniformly over all x ∈ X and u ∈ U i.e.
limn→∞ supx,u kTn (·|x, u) − T (·|x, u)kT V = 0. Observe the following,
sup kTn (·|x, u) − T (·|x, u)kT V
x,u
Z
Z
h(x1 )Tn (dx1 |x, u) − h(x1 )T (dx1 |x, u)
= sup sup
x,u ||h||∞ ≤1

= sup sup
x,u ||h||∞ ≤1

Z

−

h(f (x, u, w))µn (dw)
Z

h(f (x, u, w))µ(dw)

≤ kµn − µkT V → 0.
Thus, by Theorem 3.9 and Theorem 4.1, the result follows.
E XAMPLE 1. Suppose we have an additive system for general spaces X, Y and U such
that
xt+1 =f (xt , ut ) + wt
yt =h(xt , vt )
for unknown i.i.d. noise processes {wt } and {vt }.
(i) If the channel is in the following form; yt = h(xt , vt ) = xt + vt where vt admits
a density (e.g. Gaussian density). It can be shown by an application of Scheffe’s
theorem that the channels in this form are continuous in total variation so this system
satisfies the conditions of Corollary 6.2 and the empirical consistency holds.
(ii) If the noise process wt admits a continuous density then the conditions of Corollary
6.3 holds.
⋄
27

7. Conclusion. We studied the topological properties of multi stage optimization problems in stochastic control on the space of transition kernels, and applications of these to
robustness of the control policies applied to systems with incomplete models. We made the
observation that while weak convergence is in general too weak for continuity and robustness, channel and transition kernel regularities often allow for continuity and robustness under weak convergence. This is a practically very important result since often in engineering
applications, system models are learned through training data which only guarantees weak
convergence to the true model in general.
REFERENCES
[1] I. I. Gihman and A. V. Skorohod, Controlled stochastic processes. Springer Science & Business Media,
2012.
[2] V. S. Borkar, “White-noise representations in stochastic realization theory,” SIAM J. on Control and Optimization, vol. 31, pp. 1093–1102, 1993.
[3] G. Zames, “Feedback and optimal sensitivity: Model reference transformations, multiplicative seminorms,
and approximate inverses,” IEEE Transactions on Automatic Control, vol. 26, no. 2, pp. 301–320, 1981.
[4] T. Başar and P. Bernhard, H-infinity Optimal Control and Related Minimax Design Problems: A Dynamic
Game Approach. Boston, MA: Birkhäuser, 1995.
[5] K. Zhou, J. C. Doyle, and K. Glover, Robust and optimal control. Prentice-Hall, 1996, vol. 40.
[6] D. Jacobson, “Optimal stochastic linear systems with exponential performance criteria and their relation to
deterministic differential games,” IEEE Transactions on Automatic control, vol. 18, no. 2, pp. 124–131,
1973.
[7] P. Whittle, “A risk-sensitive maximum principle: The case of imperfect state observation,” IEEE Transactions
on Automatic Control, vol. 36, no. 7, pp. 793–801, 1991.
[8] P. Dupuis, M. R. James, and I. Petersen, “Robust properties of risk-sensitive control,” Mathematics of Control,
Signals and Systems, vol. 13, no. 4, pp. 318–332, 2000.
[9] P. D. Pra, L. Meneghini, and W. J. Runggaldier, “Connections between stochastic control and dynamic games,”
Mathematics of Control, Signals and Systems, vol. 9, no. 4, pp. 303–326, 1996.
[10] C. D. Charalambous and F. Rezaei, “Stochastic uncertain systems subject to relative entropy constraints: Induced norms and monotonicity properties of minimax games,” IEEE Transactions on Automatic Control,
vol. 52, no. 4, pp. 647–663, May 2007.
[11] I. Petersen, M. R. James, and P. Dupuis, “Minimax optimal control of stochastic uncertain systems with
relative entropy constraints,” IEEE Transactions on Automatic Control, vol. 45, no. 3, pp. 398–412,
2000.
[12] R. M. Gray, Entropy and Information Theory. New York: Springer-Verlag, 1990.
[13] R. K. Boel, M. R. James, and I. R. Petersen, “Robustness and risk-sensitive filtering,” IEEE Transactions on
Automatic Control, vol. 47, no. 3, pp. 451–461, 2002.
[14] V. A. Ugrinovskii, “Robust h- infinity control in the presence of stochastic uncertainty,” International Journal
of Control, vol. 71, no. 2, pp. 219–237, 1998.
[15] A. V. Savkin and I. R. Petersen, “Robust... control of uncertain systems with structured uncertainty,” Journal
of Mathematical Systems, Estimation, and Control, vol. 6, no. 3, pp. 1–14, 1996.
[16] S. Dean, H. Mania, N. Matni, B. Recht, and S. Tu, “On the sample complexity of the linear quadratic regulator,” arXiv preprint arXiv:1710.01688v2, 2018.
[17] I. I. Tzortzis, C. Charalambous, and T. Charalambous, “Dynamic programming subject to total variation
distance ambiguity,” SIAM Journal on Control and Optimization, vol. 53, no. 4, pp. 2040–2075, 2015.
[18] B. Øksendal and A. Sulem, “Forward–backward stochastic differential games and stochastic control under
model uncertainty,” Journal of Optimization Theory and Applications, vol. 161, no. 1, pp. 22–55, 2014.
[19] A. Benavoli and L. Chisci, “Robust stochastic control based on imprecise probabilities,” IFAC Proceedings
Volumes, vol. 44, no. 1, pp. 4606–4613, 2011.
[20] L. P. Hansen and T. J. Sargent, “Robust control and model uncertainty,” American Economic Review, vol. 91,
no. 2, pp. 60–66, 2001.
[21] O. Gossner and T. Tomala, “Entropy bounds on bayesian learning,” Journal of Mathematical Economics,
vol. 44, no. 1, pp. 24–32, 2008.
[22] M. L. Kleptsyna and A. Y. Veretennikov, “On robustness of discrete time optimal filters,” Mathematical Methods of Statistics, vol. 25, no. 3, pp. 207–218, 2016.
[23] W. Wiesemann, D. Kuhn, and B. Rustem, “Robust markov decision processes,” Mathematics of Operations
Research, vol. 38, no. 1, pp. 153–183, 2012.
[24] G. N. Iyengar, “Robust dynamic programming,” Mathematics of Operations Research, vol. 30, no. 2, pp.
257–280, 2005.
[25] A. Nilim and L. E. Ghaoui, “Robust control of markov decision processes with uncertain transition matrices,”
Operations Research, vol. 53, no. 5, pp. 780–798, 2005.
[26] S. H. Lim, H. Xu, and S. Mannor, “Reinforcement learning in robust markov decision processes,” in Advances
28

[27]

[28]
[29]
[30]
[31]
[32]
[33]
[34]
[35]
[36]
[37]
[38]
[39]
[40]
[41]
[42]
[43]
[44]
[45]
[46]
[47]
[48]
[49]
[50]
[51]
[52]
[53]
[54]
[55]
[56]
[57]
[58]
[59]
[60]

in Neural Information Processing Systems 26, C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani,
and K. Q. Weinberger, Eds. Curran Associates, Inc., 2013, pp. 701–709. [Online]. Available:
http://papers.nips.cc/paper/5183-reinforcement-learning-in-robust-markov-decision-processes.pdf
H. Xu and S. Mannor, “Distributionally robust markov decision processes,” in Advances in Neural
Information Processing Systems 23, J. D. Lafferty, C. K. I. Williams, J. Shawe-Taylor, R. S.
Zemel, and A. Culotta, Eds. Curran Associates, Inc., 2010, pp. 2505–2513. [Online]. Available:
http://papers.nips.cc/paper/3927-distributionally-robust-markov-decision-processes.pdf
J. Blanchet and K. Murthy, “Quantifying distributional model risk via optimal transport,” 04 2016.
P. Mohajerin Esfahani and D. Kuhn, “Data-driven distributionally robust optimization using the wasserstein
metric: Performance guarantees and tractable reformulations,” 05 2015.
R. Gao and A. J. Kleywegt, “Distributionally robust stochastic optimization with wasserstein distance,” arXiv,
2016.
E. Erdoğan and G. Iyengar, “Ambiguous chance constrained problems and robust optimization,” Mathematical
Programming, vol. 107, no. 1-2, pp. 37–61, 2005.
H. Sun and H. Xu, “Convergence analysis for distributionally robust optimization and equilibrium problems,”
vol. 41, pp. 377–401, 07 2015.
H. Lam, “Robust sensitivity analysis for stochastic systems,” Mathematics of Operations Research, vol. 41,
no. 4, pp. 1248–1275, 2016.
S. Yüksel and T. Linder, “Optimization and convergence of observation channels in stochastic control,” SIAM
J. on Control and Optimization, vol. 50, pp. 864–887, 2012.
A. D. Kara and S. Yüksel, “Robustness to incorrect priors in partially observed stochastic control,” arXiv
preprint arXiv :1803.05103, 2018.
G. Baker and S. Yuksel, “Continuity and robustness to incorrect priors in estimation and control,” in Proceedings of the IEEE Int. Symp. on Information Theory (ISIT). IEEE, 2016, pp. 1999–2003.
C. Villani, Optimal transport: old and new. Springer, 2008.
L. Xie and E. de Souza Carlos, “Robust h infinity control for linear systems with norm-bounded time-varying
uncertainty,” IEEE Transactions on Automatic Control, vol. 37, no. 8, pp. 1188–1191, Aug 1992.
M. A. Rotea and P. P. Khargonekar, “Stabilization of uncertain systems with norm bounded uncertaintya
control lyapunov function approach,” SIAM Journal on Control and Optimization, vol. 27, no. 6, pp.
1462–1476, 1989.
P. Billingsley, Probability and Measure. 3rd ed.), New York: Wiley, 1995.
H.-J. Langen, “Convergence of dynamic programming models,” Mathematics of Operations Research, vol. 6,
no. 4, pp. 493–512, 1981.
R. Serfozo, “Convergence of lebesgue integrals with varying measures,” Sankhyā: The Indian Journal of
Statistics, Series A, pp. 380–402, 1982.
B. Hajek, Random Processes for Engineers. Cambridge University Press, 2015.
A. Yushkevich, “Reduction of a controlled Markov model with incomplete data to a problem with complete
information in the case of Borel state and control spaces,” Theory Prob. Appl., vol. 21, pp. 153–158,
1976.
D. Rhenius, “Incomplete information in Markovian decision models,” Ann. Statist., vol. 2, pp. 1327–1334,
1974.
P. Billingsley, Convergence of probability measures, 2nd ed. New York: Wiley, 1999.
K. Parthasarathy, Probability Measures on Metric Spaces. AMS Bookstore, 1967.
O. Hernández-Lerma, Adaptive Markov Control Processes. Springer-Verlag, 1989.
D. P. Bertsekas and S. Shreve, Stochastic Optimal Control: The Discrete Time Case. New York: Academic
Press, 1978.
E. Feinberg, P. Kasyanov, and M. Zgurovsky, “Partially observable total-cost Markov decision process with
weakly continuous transition probabilities,” arXiv:1401.2168, 2014.
N. Saldi, S. Yüksel, and T. Linder, “Near optimality of quantized policies in stochastic control under weak
continuity conditions,” Journal of Mathematical Analysis and Applications, vol. 435, no. 1, pp. 321–337,
2016.
N. Saldi, T. Başar, and M. Raginsky, “Markov-nash equilibria in mean-field games with discounted cost,”
arXiv preprint arXiv:1612.07878, 2016.
M. Schäl, “Conditions for optimality in dynamic programming and for the limit of n-stage optimal policies to
be optimal,” Z. Wahrscheinlichkeitsth, vol. 32, pp. 179–296, 1975.
E. B. Dynkin and A. A. Yushkevich, Controlled markov processes. Springer, 1979, vol. 235.
E. A. Feinberg, “On measurability and representation of strategic measures in markov decision processes,”
Lecture Notes-Monograph Series, pp. 29–43, 1996.
O. Hernandez-Lerma and J. Lasserre, Discrete-time Markov control processes. Springer, 1996.
S. Yüksel and T. Başar, Stochastic Networked Control Systems: Stabilization and Optimization under Information Constraints. New York: Birkhäuser, 2013.
P. Billingsley, “Statistical methods in markov chains,” The Annals of Mathematical Statistics, pp. 12–40, 1961.
R. M. Dudley, Real Analysis and Probability, 2nd ed. Cambridge: Cambridge University Press, 2002.
L. Devroye and L. Györfi, Non-parametric Density Estimation: The L1 View. New York: John Wiley, 1985.

29

