# Model approximation in MDPs with unbounded per-step cost

Berk Bozkurt, Aditya Mahajan, Ashutosh Nayyar, and Yi Ouyang A preliminary
version of this paper was presented at CDC 2023 [1].Berk Bozkurt and Aditya
Mahajan are with the Department of Electrical and Computer Engineering, McGill
University, Montreal, QC, Canada. (email<EMAIL_ADDRESS>aditya.mahajan@mcgill.ca)Ashutosh Nayyar is with the Department of Electrical
and Computer Engineering, University of Southern California, Los Angeles, CA,
USA. (email: ashutoshn@usc.edu)Yi Ouyang is with Preferred Networks America,
Burlingame, CA, USA (email: ouyangyi@preferred-america.com)The work at McGill
was supported by IDEaS grant CFPMN2-30, NSERC grant RGPIN-2021-03511, and
IVADO MSc Excellence Fellowship. The work at USC was supported by NSF grants
ECCS 2025732 and ECCS 1750041.

###### Abstract

We consider the problem of designing a control policy for an infinite-horizon
discounted cost Markov decision process $\mathcal{M}$ when we only have access
to an approximate model $\hat{\mathcal{M}}$. How well does an optimal policy
$\hat{\pi}^{\star}$ of the approximate model perform when used in the original
model $\mathcal{M}$? We answer this question by bounding a weighted norm of
the difference between the value function of $\hat{\pi}^{\star}$ when used in
$\mathcal{M}$ and the optimal value function of $\mathcal{M}$. We then extend
our results and obtain potentially tighter upper bounds by considering affine
transformations of the per-step cost. We further provide upper bounds that
explicitly depend on the weighted distance between cost functions and weighted
distance between transition kernels of the original and approximate models. We
present examples to illustrate our results.

###### Index Terms:

Markov decision processes, model approximation, Bellman operators, integral
probability metrics.

##  I Introduction

We consider the problem of model approximation in Markov decision processes
(MDPs), i.e., the problem of designing an optimal controller for an MDP using
an approximate model (e.g. designing gait controller of a robot using a
simulation model). Let $\mathcal{M}$ denote the true model of the system and
let $\hat{\mathcal{M}}$ denote the approximate model. Suppose we solve the
approximate model $\hat{\mathcal{M}}$ to identify a policy $\hat{\pi}^{\star}$
which is optimal for $\hat{\mathcal{M}}$. How well does $\hat{\pi}^{\star}$
perform in the original model $\mathcal{M}$?

Several variations of this question have been studied in the MDP literature.
Perhaps the earliest work investigating this is that of Fox [2], who
investigated approximating MDPs by a finite state approximation. In a series
of papers, Whitt generalized these results to approximating general MDPs via
state aggregation [3, 4, 5]. Similar results for state discretization were
obtained in [6, 7], state and action discretization in [8] and for models with
state dependent discounting in [9]. A general framework to view model
approximation using the lens of integral probability metrics was presented by
Müller [10]. There have been considerable advances on these ideas in recent
years [11, 12, 13], including generalizations to partially observed models
[14, 15]. However, these approximation results are restricted to models with
bounded per-step cost.

A related question is that of continuity of optimal policy in model
approximation. In particular, if $\\{\hat{\mathcal{M}_{n}}\\}_{n\geq 1}$ is a
sequence of models that converge to $\mathcal{M}$ in some sense, do the
corresponding optimal policies $\\{\hat{\pi}_{n}^{\star}\\}_{n\geq 1}$, where
$\hat{\pi}_{n}^{\star}$ is optimal for $\hat{\mathcal{M}_{n}}$, converge to an
optimal policy for $\mathcal{M}$? One of the earliest work in this direction
is that of Fox [16], who studied the continuity of state discretization
procedures. Sufficient conditions for continuity of value function on model
parameters were presented in [17]. There are series of recent papers which
significantly generalize these results, including characterizing conditions
under which the optimal policy is continuous in model parameters [11, 18, 12,
19, 20, 21, 22].

The question of model approximation is also relevant for learning optimal
policies when the system model is unknown. Therefore, several notions related
to model approximation have been studied in the reinforcement learning
literature including approximate homeomorphisms [23, 24], bisimulation metrics
[25, 26, 27], state abstraction [28], and approximate latent state models [29,
30].

The basic results of model approximation may be characterized as follows. Let
$\mathcal{M}$ and $\hat{\mathcal{M}}$ be two MDP models with the same state
space $\mathcal{S}$ and action space $\mathcal{A}$. Let
$\hat{\pi}^{\star}\colon\mathcal{S}\to\mathcal{A}$ be an optimal policy for
model $\hat{\mathcal{M}}$. Let
$V^{\hat{\pi}^{\star}}\colon\mathcal{S}\to\mathds{R}$ denote the performance
of policy $\hat{\pi}^{\star}$ in model $\mathcal{M}$ and let
$V^{\star}\colon\mathcal{S}\to\mathds{R}$ denote the optimal value function of
model $\mathcal{M}$. Most of the existing literature on model approximation
provides bounds on
$\|V^{\hat{\pi}^{\star}}-V^{\star}\|_{\infty}\coloneqq\sup_{s\in\mathcal{S}}\bigl{|}V^{\hat{\pi}^{\star}}(s)-V^{\star}(s)\bigr{|}$
in terms of the parameters of the models $\mathcal{M}$ and
$\hat{\mathcal{M}}$.

However, such bounds are not appropriate for models with non-compact state
spaces and unbounded per-step cost. To illustrate this limitation, consider
the linear quadratic regulation (LQR) problem in which the objective is to
minimize the infinite-horizon expected discounted total cost. Let
$\mathcal{M}$ and $\hat{\mathcal{M}}$ be two such LQR models and
$\hat{\pi}^{\star}$ be the optimal policy of $\hat{\mathcal{M}}$. It is well
known that

$V^{\star}(s)=s^{\intercal}Ps+q\quad\text{and}\quad
V^{\hat{\pi}^{\star}}(s)=s^{\intercal}P^{\hat{\pi}^{\star}}s+q^{\hat{\pi}^{\star}},$

where $s\in\mathds{R}^{n_{s}}$ is the state, $P$ is the solution of an
appropriate Riccati equation, $P^{\hat{\pi}^{\star}}$ is a solution of an
appropriate Lyapunov equation (which depends on the gain of policy
$\hat{\pi}^{\star}$) and $q$ and $q^{\hat{\pi}^{\star}}$ are constants (where
$q^{\hat{\pi}^{\star}}$ depends on $P^{\hat{\pi}^{\star}}$). See Sec. IV-D for
exact details. For this model, and for many models with unbounded per-step
cost, $\|V^{\star}-V^{\hat{\pi}^{\star}}\|_{\infty}=\infty$. Therefore, the
approximation bounds on $\|V^{\star}-V^{\hat{\pi}^{\star}}\|_{\infty}$
provided by the existing literature will also evaluate to $\infty$ and, as a
result, do not provide any insights into the quality of the approximation.

The standard approach to deal with unbounded per-step cost is to use a
weighted norm rather than a sup norm [10, 12, 31, 32]. However, in most of the
existing literature a weighted norm is used to establish existence and
uniqueness of a dynamic programming solution. As far as we are aware, the only
paper which uses the weighted norm for model approximation in models with
unbounded per-step cost is [12], where the authors establish sufficient
conditions under which $\hat{V}^{\star}_{n}\to V^{\star}$ and
$V^{\hat{\pi}^{\star}_{n}}\to V^{\star}$, where $\hat{V}^{\star}_{n}$ and
$\hat{\pi}^{\star}_{n}$ are value function and optimal policy of a discretized
model with grid cells of size less than $1/n$. However, they do not establish
the approximation error when a specific approximate model is used.

Our main contributions in this paper are as follows:

  * •

We provide upper bounds on the approximation error in terms of the weighted-
norm:

$\|V^{\hat{\pi}^{\star}}-V^{\star}\|_{w}\coloneqq\sup_{s\in\mathcal{S}}\frac{\bigl{|}V^{\hat{\pi}^{\star}}(s)-V^{\star}(s)\bigr{|}}{w(s)},$

where $w\colon\mathcal{S}\to[1,\infty)$ is a weight function. Our bounds are
derived using a new functional, which we call the _Bellman mismatch
functional_.

  * •

In the literature on the existence of dynamic programming solution for models
with unbounded per-step cost, it is assumed that the weight function is such
that the dynamics under all policies satisfies a Lyaponov stability-type
condition [10, 12, 31, 32]. In contrast, we assume that such a stability
condition is satisfied for only a few policies, including the optimal policies
of the original and the approximate model, and policies obtained by using
optimal and approximate value functions as one-step look ahead value function.
(See Assumptions 2–4 for the precise definition).

  * •

We then extend our results and obtain potentially tighter upper bounds by
considering affine transformations of the per-step cost. These transformations
allow us to trade off between the mismatches in the dynamics with the
mismatches in the per-step cost.

  * •

We present examples to illustrate that for suitable choices of the weight
functions and affine transformations our bounds are tighter than existing sup-
norm bounds, even for models with bounded per-step cost. In addition, we
revisit the LQR example mentioned previously and show that the weighted-norm
approximation bounds provide meaningful approximation guarantees for such
unbounded-cost models.

  * •

We provide further upper bounds that explicitly depend on the weighted
distance between cost functions and weighted distance between transition
kernels of the original and approximate models. In the special case when
$w(s)\equiv 1$, our bounds recover the existing sup-norm bounds [10, 28, 30]

#### Notation

We use calligraphic letters to denote sets (e.g. $\mathcal{S}$), uppercase
letters to denote random variables (e.g. $S$) and lowercase letters to denote
their realizations (e.g. $s$). The space of probability measures on a set
$\mathcal{S}$ is expressed by $\Delta(\mathcal{S})$. Subscripts indicate time,
so $S_{t}$ denotes a random variable at time $t$. $S_{1:t}$ is a short hand
notation for $(S_{1},\dots,S_{t})$.

We use $\mathds{R}$ to denote the set of real numbers, $\mathds{Z}_{\geq 0}$
to denote the set of non-negative integers, $\mathds{P}(\cdot)$ to denote the
probability of an event, $\mathds{E}[\cdot]$ to denote expectation of a random
variable, and $\mathds{1}\\{\cdot\\}$ to denote indicator of an event. For
functions $v_{1},v_{2}\colon\mathcal{S}\to\mathds{R}$, the notation $v_{1}\leq
v_{2}$ denotes that $v_{1}(s)\leq v_{2}(s)$ for all $s\in\mathcal{S}$.

##  II Preliminaries

###  II-A Markov decision processes

A discrete-time infinite-horizon discounted cost Markov decision process (MDP)
is a tuple $\mathcal{M}=\langle\mathcal{S},\mathcal{A},P,c,\gamma\rangle$
where

  * •

$\mathcal{S}$ is the state space, which is assumed to be a Borel space. The
state at time $t$ is denoted by $S_{t}\in\mathcal{S}$.

  * •

$\mathcal{A}$ is the action space, which is assumed to be a Borel space. The
action at time $t$ is denoted by $A_{t}\in\mathcal{A}$.

  * •

$P\colon\mathcal{S}\times\mathcal{A}\to\Delta(\mathcal{S})$ is a controlled
stochastic kernel, which specifies the system dynamics. In particular, for any
time $t$ and any $s_{1:t}\in\mathcal{S}^{t}$, $a_{1:t}\in\mathcal{A}^{t}$ and
any Borel set $B\subset\mathcal{S}$, we have

$\displaystyle\mathds{P}(S_{t+1}\in B\mid S_{1:t}=s_{1:t},A_{1:t}=a_{1:t})$
$\displaystyle\quad=\mathds{P}(S_{t+1}\in B\mid
S_{t}=s_{t},A_{t}=a_{t})\eqqcolon P(B\mid s_{t},a_{t}).$

  * •

$c\colon\mathcal{S}\times\mathcal{A}\to\mathds{R}$ is the per-step cost
function which is assumed to be measurable. We further assume that the per-
step cost is bounded from below, i.e., there exists a finite constant
$c_{\min}$ such that $c(s,a)\geq c_{\min}$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$.

  * •

$\gamma\in(0,1)$ is the discount factor.

A stochastic kernel $\pi\colon\mathcal{S}\to\Delta(\mathcal{A})$ is called a
(time-homogeneous) policy. Let $\Pi$ denote the space of all time-homogeneous
(and possibly randomized) policies. The performance of any policy $\pi\in\Pi$
starting from an initial state $s\in\mathcal{S}$ is given by

$V^{\pi}(s)=\mathds{E}^{\pi}\biggl{[}\sum_{t=1}^{\infty}\gamma^{t-1}c(S_{t},A_{t})\,\biggm{|}\,S_{1}=s\biggr{]}$
(1)

where $\mathds{E}^{\pi}$ denotes the expectation with respect to the
probability measure on all system variables induced by the choice of policy
$\pi$. The function $V^{\pi}$ is called the _value function_ of policy $\pi$.

A policy $\pi^{\star}\in\Pi$ is called an _optimal policy_ if

$V^{\pi^{\star}}(s)\leq V^{\pi}(s),\quad\forall
s\in\mathcal{S},\forall\pi\in\Pi.$ (2)

Since we consider Borel state and action spaces with possibly unbounded (from
above) per-step cost function, an optimal policy is not guaranteed to exist.
If an optimal policy exists, its value function is called the _optimal value
function_. We focus on MDPs for which optimal value function exists and can be
obtained via dynamic programming. We formally define this as dynamic
programming solvability in the next section.

###  II-B Dynamic programming solvability

Let $\mathcal{V}$ denote the space of measurable functions from
$\mathcal{S}\to[\frac{c_{\min}}{1-\gamma},\infty)\cup\\{+\infty\\}$.

[Weighted norm] Given a weight function $w\colon\mathcal{S}\to[1,\infty)$, we
define the weighted norm $\|\cdot\|_{w}$ on $\mathcal{V}$ as follows: for any
$v\in\mathcal{V}$,

$\|v\|_{w}=\sup_{s\in\mathcal{S}}\frac{|v(s)|}{w(s)}.$

$\mathcal{V}_{w}=\bigl{\\{}v\in\mathcal{V}:\|v\|_{w}<\infty\bigr{\\}}$ and
$\mathcal{P}_{w}=\bigl{\\{}p\in\Delta(\mathcal{S}):\int wdp<\infty\bigr{\\}}$.
It can be easily verified that $\|\cdot\|_{w}$ is a norm and that
$\mathcal{V}_{w}$ is a Banach space.

When the weight function $w(s)\equiv 1$, then the weighted norm $\|v\|_{w}$ is
equal to the sup-norm $\|v\|_{\infty}\coloneqq\sup_{s\in\mathcal{S}}|v(s)|$.
In this case, $\mathcal{V}_{w}$ is the subset of all bounded functions in
$\mathcal{V}$ and $\mathcal{P}_{w}$ is the set of all probability measures on
$\mathcal{S}$.

[Bellman operators] Define the following two operators:

  * •

For any $\pi\in\Pi$, define the _Bellman operator_
$\mathscr{B}^{\pi}\colon\mathcal{V}\to\mathcal{V}$ as follows: for any
$v\in\mathcal{V}$,

$[\mathscr{B}^{\pi}v](s)=c_{\pi}(s)+\gamma\int_{\mathcal{S}}v(s^{\prime})P_{\pi}(ds^{\prime}\mid
s),$

where $c_{\pi}(s)=\int_{\mathcal{A}}c(s,a)\pi(da|s),$ and
$P_{\pi}(ds^{\prime}|s)=\int_{\mathcal{A}}\pi(da|s)P(ds^{\prime}|s,a)$.

  * •

Define the _Bellman optimality operator_ $\mathscr{B}^{\star}$ as follows: for
any $v\in\mathcal{V}$,

$[\mathscr{B}^{\star}v](s)=\inf_{a\in\mathcal{A}}\biggl{\\{}c(s,a)+\gamma\int_{\mathcal{S}}v(s^{\prime})P(ds^{\prime}\mid
s,a)\biggr{\\}}.$

[One-step greedy policy] We say that a policy $\pi\in\Pi$ is _one-step greedy_
with respect to a value function $v\in\mathcal{V}$ if
$\mathscr{B}^{\pi}v=\mathscr{B}^{\star}v$. We denote by $\mathcal{G}(v)$ the
set of all one-step greedy policies with respect to $v$.

[Dynamic programming solvability] An MDP $\mathcal{M}$ is said to be _dynamic
programming solvable_ (DP-solvable, for short) with respect to a weight
function $w\colon\mathcal{S}\to[1,\infty)$ if the following conditions are
satisfied:

  1. 1.

For any $v\in\mathcal{V}_{w}$, $\mathscr{B}^{\star}v\in\mathcal{V}_{w}$.

  2. 2.

There exists a $V^{\star}\in\mathcal{V}_{w}$ such that for all $\pi\in\Pi$,

$V^{\star}(s)\leq V^{\pi}(s),\quad\forall s\in\mathcal{S}$

with equality at all states for at least one $\pi\in\Pi$.

  3. 3.

$V^{\star}$ is a fixed point of $\mathscr{B}^{\star}$, i.e., it satisfies the
dynamic programming equation

$V=\mathscr{B}^{\star}V.$

MDPs with finite state and action spaces are always DP-solvable. For MDPs with
general state and action spaces, there are several conditions in the
literature which imply DP-solvability. See [31] for an overview.

###  II-C Weighted-norm stability

[$(\kappa,w)$ stability of a policy] Given an MDP $\mathcal{M}$ and a tuple
$(\kappa,w)$, where $\kappa$ is a positive constant with $\gamma\kappa<1$ and
$w$ is a function from $\mathcal{S}$ to $[1,\infty)$, we say a policy
$\pi\in\Pi$ is $(\kappa,w)$ stable if

$\|c_{\pi}\|_{w}<\infty,$ (3)

where $c_{\pi}(s)=\int_{\mathcal{A}}c(s,a)\pi(da|s),$ and $\forall
s\in\mathcal{S}$,

$\int_{\mathcal{S}}w(s^{\prime})P_{\pi}(ds^{\prime}\mid s)\leq\kappa w(s),$
(4)

where $P_{\pi}(ds^{\prime}|s)=\int_{\mathcal{A}}\pi(da|s)P(ds^{\prime}|s,a)$.
Let $\Pi_{S}(\kappa,w)$ denote the set of all $(\kappa,w)$-stable policies for
MDP $\mathcal{M}$. Note that depending on the choice of $(\kappa,w)$, the set
$\Pi_{S}(\kappa,w)$ might be empty. As stated in Remark II-B, when $w(s)\equiv
1$, the weighted norm is the same as the sup-norm. Further, with $w(s)\equiv
1$, inequality (4) of Definition II-C holds with $\kappa=1$ for any policy
$\pi$. Thus, for the case of $w(s)\equiv 1$, $\Pi_{S}(1,w\equiv 1)$ is the set
of all policies $\pi$ for which $\|c_{\pi}\|_{\infty}<\infty$.

For our model approximation results developed later, we will assume that
certain policies are $(\kappa,w)$ stable. It is worthwhile to contrast the
$(\kappa,w)$-stability of a policy with a stronger assumption that is
typically imposed in the literature [10, 12, 31, 32]. To make that comparison,
we define the following (which is the same as [32, Assumption 8.3.2]):
[$(\bar{\kappa},\bar{w})$ stability of the model] Given an MDP $\mathcal{M}$
and a tuple $(\bar{\kappa},\bar{w})$, where $\bar{\kappa}$ is a positive
constant with $\gamma\bar{\kappa}<1$ and $\bar{w}$ is a function from
$\mathcal{S}$ to $[1,\infty)$, we say that $\mathcal{M}$ is
$(\bar{\kappa},\bar{w})$ stable if there exists a $c_{\max}<\infty$ such that

$\|c(\cdot,a)\|_{\bar{w}}\leq c_{\max},\quad\forall a\in\mathcal{A}$ (5)

and

$\int_{\mathcal{S}}\bar{w}(s^{\prime})P(ds^{\prime}\mid
s,a)\leq\bar{\kappa}\bar{w}(s),\quad\forall s\in\mathcal{S},\forall
a\in\mathcal{A}.$ (6)

It is shown in [32] that $(\bar{\kappa},\bar{w})$ stability of the model is
sufficient for DP-solvability. The notion of $(\kappa,w)$ stability of a
policy is weaker. In particular, $(\bar{\kappa},\bar{w})$ stability of the
model implies that any (time-homogeneous) policy is also
$(\bar{\kappa},\bar{w})$ stable. However, $(\kappa,w)$ stability of a
particular policy does not imply $(\kappa,w)$ stability of the model. For a
given weight function, the smallest value of $\kappa$ that satisfies (4) is
given by

$\kappa_{w}=\sup_{s\in\mathcal{S}}\frac{\int_{\mathcal{S}}w(s^{\prime})P_{\pi}(ds^{\prime}|s)}{w(s)}$
(7)

while the smallest value of $\bar{\kappa}$ that satisfies equation (6) is
given by

$\bar{\kappa}_{w}=\sup_{s\in\mathcal{S},a\in\mathcal{A}}\frac{\int_{\mathcal{S}}w(s^{\prime})P(ds^{\prime}|s,a)}{w(s)}.$
(8)

It is clear from the definitions that $\kappa_{w}\leq\bar{\kappa}_{w}$. We
show via an example in Sec. IV-E that using the weaker notion of $(\kappa,w)$
stability of a policy drastically increases the range of possible choices of
the weight function and leads to tighter approximation bounds.

Given an MDP $\mathcal{M}$ and a tuple $(\kappa,w)$, for any policy
$\pi\in\Pi_{S}(\kappa,w)$, we have the following:

  1. 1.

If $v\in\mathcal{V}_{w}$, then $\mathscr{B}^{\pi}v\in\mathcal{V}_{w}$.

  2. 2.

$\mathscr{B}^{\pi}$ is a $\|\cdot\|_{w}$-norm contraction with contraction
factor $\gamma\kappa$, i.e., for any $v_{1},v_{2}\in\mathcal{V}_{w}$, we have

$\|\mathscr{B}^{\pi}v_{1}-\mathscr{B}^{\pi}v_{2}\|_{w}\leq\gamma\kappa\|v_{1}-v_{2}\|_{w}.$

  3. 3.

The fixed point equation

$V=\mathscr{B}^{\pi}V$

has a unique solution in $\mathcal{V}_{w}$ and that solution is equal to
$V^{\pi}$.

See Appendix A for proof.

##  III Problem formulation and approximation bounds

###  III-A Model approximation in MDPs

We are interested in the problem of model approximation in MDPs. In
particular, suppose there is an MDP
$\mathcal{M}=\langle\mathcal{S},\mathcal{A},P,c,\gamma\rangle$ of interest,
but the system designer has access to only an approximate model
$\hat{\mathcal{M}}=\langle\mathcal{S},\mathcal{A},\hat{P},\hat{c},\gamma\rangle$.
Note that both models $\mathcal{M}$ and $\hat{\mathcal{M}}$ have the same
state and action spaces, but have different transition dynamics and per-step
cost. As before, we assume that both $c$ and $\hat{c}$ are bounded from below.
Thus, there exists a finite constant $c_{\min}$ such that $c(s,a)\geq
c_{\min}$ and $\hat{c}(s,a)\geq c_{\min}$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$.

We further assume that both models $\mathcal{M}$ and $\hat{\mathcal{M}}$ are
well-behaved in the following sense, which we assume to hold in the rest of
the paper.

######  Assumption 1.

Models $\mathcal{M}$ and $\hat{\mathcal{M}}$ are DP-solvable.

TABLE I: Notation for the variables used for the two models Variable | Model $\mathcal{M}$ | Model $\hat{\mathcal{M}}$
---|---|---
Dynamics | $P$ | $\hat{P}$
per-step cost | $c$ | $\hat{c}$
Value function of policy $\pi$ | $V^{\pi}$ | $\hat{V}^{\pi}$
Optimal value function | $V^{\star}$ | $\hat{V}^{\star}$
Optimal policy | $\pi^{\star}$ | $\hat{\pi}^{\star}$
Bellman operator of policy $\pi$ | $\mathscr{B}^{\pi}$ | $\hat{\mathscr{B}}^{\pi}$
Bellman optimality operator | $\mathscr{B}^{\star}$ | $\hat{\mathscr{B}}^{\star}$
Set of one-step greedy policies w.r.t. $v$ | $\mathcal{G}(v)$ | $\hat{\mathcal{G}}(v)$
Set of $(\kappa,w)$-stable policies | $\Pi_{S}(\kappa,w)$ | $\hat{\Pi}_{S}(\kappa,w)$

We will use the superscript $\hat{}$ (hat) to denote variables/operators
corresponding to the approximate model, as summarized in Table I. We are
interested in the following approximation problem.

######  Problem 1.

Let $\hat{\pi}^{\star}$ be an optimal policy for the approximate model
$\hat{\mathcal{M}}$. For each start state $s$, provide a bound for the loss in
performance when using $\hat{\pi}^{\star}$ in the original model
$\mathcal{M}$, i.e., bound $V^{\hat{\pi}^{\star}}(s)-V^{\star}(s)$.

###  III-B Approximation bounds

In the rest of the paper, we will work with a fixed $(\kappa,w)$ where
$\kappa$ is a non-negative constant such that $\gamma\kappa<1$ and
$w\colon\mathcal{S}\to[1,\infty)$. Note that $\Pi_{S}(\kappa,w)$ and
$\hat{\Pi}_{S}(\kappa,w)$ denote the sets of $(\kappa,w)$-stable policies for
models $\mathcal{M}$ and $\hat{\mathcal{M}}$, respectively. Also,
$\mathcal{G}(v)$ and $\hat{\mathcal{G}}(v)$ denote the sets of one-step greedy
polices with respect to $v$ for models $\mathcal{M}$ and $\hat{\mathcal{M}}$,
respectively. We impose the following additional assumption on the models.

######  Assumption 2.

We assume that

  1. 1.

The set $\mathcal{G}(V^{\star})\cap\Pi_{S}(\kappa,w)$ is nonempty.

  2. 2.

The set
$\hat{\mathcal{G}}(\hat{V}^{\star})\cap\Pi_{S}(\kappa,w)\cap\hat{\Pi}_{S}(\kappa,w)$
is nonempty.

When $\mathcal{G}(V^{\star})\cap\Pi_{S}(\kappa,w)\neq\emptyset$, we can show
that any policy $\pi\in\mathcal{G}(V^{\star})\cap\Pi_{S}(\kappa,w)$ is
optimal, i.e., $V^{\pi}=V^{\star}$. From now on, we assume that the optimal
policy $\pi^{\star}$ for Model $\mathcal{M}$ belongs to
$\mathcal{G}(V^{\star})\cap\Pi_{S}(\kappa,w)$. Similarly, we assume that the
optimal policy $\hat{\pi}^{\star}$ for Model $\hat{\mathcal{M}}$ belongs to
$\hat{\mathcal{G}}(\hat{V}^{\star})\cap\Pi_{S}(\kappa,w)\cap\hat{\Pi}_{S}(\kappa,w)$.

For some of the results, we impose one of the following assumptions:

######  Assumption 3.

The set $\mathcal{G}(\hat{V}^{\star})\cap\Pi_{S}(\kappa,w)$ is nonempty.

######  Assumption 4.

The set $\hat{\mathcal{G}}(V^{\star})\cap\hat{\Pi}_{S}(\kappa,w)$ is nonempty.

Assumption 3 effectively states using $\hat{V}^{\star}$ as the one-step look
ahead value function in the original model produces a stable policy.
Similarly, Assumption 4 effectively states that using $V^{\star}$ as the one-
step look ahead value function in the approximate model produces a stable
policy.

[Bellman mismatch functionals] Suppose Assumptions 1 and 2 hold. Define the
following functionals:

  * •

For any $\pi\in\Pi_{S}(\kappa,w)$ and $\hat{\pi}\in\hat{\Pi}_{S}(\kappa,w)$,
define the _Bellman mismatch functional_
$\mathscr{D}_{w}^{\pi,\hat{\pi}}\colon\mathcal{V}_{w}\to\mathds{R}_{\geq 0}$
as follows: for any $v\in\mathcal{V}_{w}$,

$\mathscr{D}^{\pi,\hat{\pi}}_{w}v=\|\mathscr{B}^{\pi}v-\hat{\mathscr{B}}^{\hat{\pi}}v\|_{w}.$

  * •

For any $\pi\in\Pi_{S}(\kappa,w)\cap\hat{\Pi}_{S}(\kappa,w)$, define the
_Bellman mismatch functional_
$\mathscr{D}^{\pi}_{w}\colon\mathcal{V}_{w}\to\mathds{R}_{\geq 0}$ as follows:
for any $v\in\mathcal{V}_{w}$,

$\mathscr{D}_{w}^{\pi}v=\mathscr{D}_{w}^{\pi,\pi}v=\|\mathscr{B}^{\pi}v-\hat{\mathscr{B}}^{\pi}v\|_{w}.$

  * •

Define the _Bellman optimality mismatch functional_
$\mathscr{D}^{\star}_{w}\colon\mathcal{V}_{w}\to\mathds{R}_{\geq 0}$ as
follows: for any $v\in\mathcal{V}_{w}$,

$\mathscr{D}_{w}^{\star}v=\|\mathscr{B}^{\star}v-\hat{\mathscr{B}}^{\star}v\|_{w}.$

In the rest of the paper, we assume that Assumption 2 holds and $w$ is fixed.
Therefore, we omit the subscript $w$ in the mismatch functionals in the rest
of the discussion.

[Policy error bounds] For any two policies $\pi\in\Pi_{S}(\kappa,w)$ and
$\hat{\pi}\in\hat{\Pi}_{S}(\kappa,w)$, we have

$\|V^{\pi}-\hat{V}^{\hat{\pi}}\|_{w}\leq\frac{1}{1-\gamma\kappa}\min\bigl{\\{}\mathscr{D}^{\pi,\hat{\pi}}V^{\pi},\mathscr{D}^{\pi,\hat{\pi}}\hat{V}^{\hat{\pi}}\bigr{\\}}.$
(9)

See Appendix B for proof.

[Value error bounds] The following hold:

  1. 1.

If Assumptions 1 and 2 hold, we have

$\|V^{\star}-\hat{V}^{\star}\|_{w}\leq\frac{1}{(1-\gamma\kappa)}\mathscr{D}^{\pi^{\star},\hat{\pi}^{\star}}\hat{V}^{\star}.$
(10)

and

$\|V^{\star}-\hat{V}^{\star}\|_{w}\leq\frac{1}{(1-\gamma\kappa)}\mathscr{D}^{\pi^{\star},\hat{\pi}^{\star}}V^{\star}.$
(11)

  2. 2.

If Assumptions 1, 2 and 3 hold, we have

$\|V^{\star}-\hat{V}^{\star}\|_{w}\leq\frac{1}{(1-\gamma\kappa)}\mathscr{D}^{\star}\hat{V}^{\star}.$
(12)

  3. 3.

If Assumptions 1, 2 and 4 hold, we have

$\|V^{\star}-\hat{V}^{\star}\|_{w}\leq\frac{1}{(1-\gamma\kappa)}\mathscr{D}^{\star}V^{\star}.$
(13)

See Appendix C for proof.

We can establish the following theorem by combining policy and value error
bounds. We have the following bounds on $V^{\hat{\pi}^{\star}}-V^{\star}$:

  1. 1.

Under Assumptions 1 and 2, we have

$\displaystyle\bigl{\|}V^{\hat{\pi}^{\star}}-V^{\star}\bigr{\|}_{w}$
$\displaystyle\leq\frac{1}{1-\gamma\kappa}\bigl{[}\mathscr{D}^{\hat{\pi}^{\star}}\hat{V}^{\star}+\mathscr{D}^{\pi^{\star},\hat{\pi}^{\star}}\hat{V}^{\star}\bigr{]}$

and

$\displaystyle\bigl{\|}V^{\hat{\pi}^{\star}}-V^{\star}\bigr{\|}_{w}$
$\displaystyle\leq\frac{1}{1-\gamma\kappa}\mathscr{D}^{\hat{\pi}^{\star}}V^{\star}+\frac{(1+\gamma\kappa)}{(1-\gamma\kappa)^{2}}\mathscr{D}^{\pi^{\star},\hat{\pi}^{\star}}V^{\star}.$

  2. 2.

Under Assumptions 1, 2, and 3, we have

$\displaystyle\bigl{\|}V^{\hat{\pi}^{\star}}-V^{\star}\bigr{\|}_{w}$
$\displaystyle\leq\frac{1}{1-\gamma\kappa}\bigl{[}\mathscr{D}^{\hat{\pi}^{\star}}\hat{V}^{\star}+\mathscr{D}^{\star}\hat{V}^{\star}\bigr{]}.$

  3. 3.

Under Assumptions 1, 2, and 4, we have

$\displaystyle\bigl{\|}V^{\hat{\pi}^{\star}}-V^{\star}\bigr{\|}_{w}$
$\displaystyle\leq\frac{1}{1-\gamma\kappa}\mathscr{D}^{\hat{\pi}^{\star}}V^{\star}+\frac{(1+\gamma\kappa)}{(1-\gamma\kappa)^{2}}\mathscr{D}^{\star}V^{\star}.$

See Appendix D for proof.

Since $V^{\hat{\pi}^{\star}}(s)\geq V^{\star}(s)$, we have

$V^{\hat{\pi}^{\star}}(s)-V^{\star}(s)\leq\bigl{\|}V^{\hat{\pi}^{\star}}-V^{\star}\bigr{\|}_{w}w(s).$
(14)

Thus, the bounds on $\bigl{\|}V^{\hat{\pi}^{\star}}-V^{\star}\bigr{\|}_{w}$
stated in Theorem III-B provide a bound on the performance loss when
$\hat{\pi}^{\star}$ is used in the original model $\mathcal{M}$ with a start
state $s$.

###  III-C Discussion

Obtaining a solution of Problem 1 requires some knowledge of the model. If we
were to obtain an exact expression for
$\|V^{\star}-V^{\hat{\pi}^{\star}}\|_{w}$, we would need to compute
$V^{\star}$ and $V^{\hat{\pi}^{\star}}$, which are the fixed points of
$\mathscr{B}^{\star}$ and $\mathscr{B}^{\hat{\pi}^{\star}}$, respectively.
Computing $V^{\star}$ and $V^{\hat{\pi}^{\star}}$ requires starting with an
initial choice $V_{0}$ and then iteratively computing
$\\{(\mathscr{B}^{\star})^{n}V_{0}\\}_{n\geq 1}$ and
$\\{(\mathscr{B}^{\hat{\pi}^{\star}})^{n}V_{0}\\}_{n\geq 1}$ until
convergence. In contrast, our upper bounds of Theorem III-B, part 2, are in
terms of the mismatch Bellman operators, which require _one_ update of the
Bellman operators $\mathscr{B}^{\star}$ and $\mathscr{B}^{\hat{\pi}^{\star}}$.
It is worth highlighting that we do not need to compute $V^{\star}$ or
$\pi^{\star}$ in order to use the bounds of Theorem III-B, part 2. Thus, our
upper bounds provide significant computational savings, especially when
computing a Bellman update in the original model is computationally expensive.

Another feature of our results is that they characterize the sensitivity of
the optimal performance to model approximation. To make this notion precise,
we need to define a notion of _distance_ between the original and approximate
model. We elaborate on this direction in Sec. V. We first present a few
generalizations of the bounds.

###  III-D Bounds under stability of deterministic open loop policies

Let $\pi_{a}$ denote the deterministic open loop policy that selects action
$a$ with probability $1$ in all states, i.e., $\pi_{a}(s)=a$ for all $s$. In
this section, we assume that all such policies are $(\kappa,w)$ stable in
${\mathcal{M}}$ and $\hat{\mathcal{M}}$, and simplify the bounds of Theorem
III-B.

######  Assumption 5.

For each $a\in\mathcal{A}$,
$\pi_{a}\in\Pi_{S}(\kappa,w)\cap\hat{\Pi}_{S}(\kappa,w)$. Moreover
$\mathcal{G}(\hat{V}^{\star})$ and $\hat{\mathcal{G}}(V^{\star})$ are
nonempty.

Assumption 5 is weaker than $(\kappa,w)$ stability of the model because
Assumption 5 does not imply a _uniform_ upper bound on $\|c(\cdot,a)\|_{w}$
over all $a\in\mathcal{A}$.

Assumptions 1 and 5 imply Assumptions 3 and 4. See Appendix E for proof.

Suppose Assumption 5 holds. Define the _Bellman maximum mismatch functional_
$\mathscr{D}^{\max}_{w}\colon\mathcal{V}_{w}\to\mathds{R}_{\geq 0}$ as
follows: for any $v\in\mathcal{V}_{w}$,

$\displaystyle\mathscr{D}_{w}^{\max}v$
$\displaystyle=\sup_{a\in\mathcal{A}}\mathscr{D}^{\pi_{a}}_{w}v=\sup_{a\in\mathcal{A}}\|\mathscr{B}^{\pi_{a}}v-\hat{\mathscr{B}}^{\pi_{a}}v\|_{w}.$

In the sequel, we omit the subscript $w$ from the functional defined above for
simplicity.

Under Assumptions 1, 2 and 5, the Bellman mismatch functionals satisfy the
following for any $v\in\mathcal{V}_{w}$:

$\sup_{\pi\in\Pi_{S}(\kappa,w)\cap\hat{\Pi}_{S}(\kappa,w)}\mathscr{D}^{\pi}v=\mathscr{D}^{\max}v\quad\text{and}\quad\mathscr{D}^{\star}v\leq\mathscr{D}^{\max}v.$
(15)

See Appendix F for proof.

Under Assumptions 1, 2 and 5, we have the following two bounds on
$V^{\hat{\pi}^{\star}}-V^{\star}$:

  1. 1.

Bound in terms of properties of $\hat{V}^{\star}$:

$\displaystyle\bigl{\|}V^{\hat{\pi}^{\star}}-V^{\star}\bigr{\|}_{w}$
$\displaystyle\leq\frac{2}{1-\gamma\kappa}\mathscr{D}^{\max}(\hat{V}^{\star}).$

  2. 2.

Bound in terms of properties of $V^{\star}$:

$\displaystyle\bigl{\|}V^{\hat{\pi}^{\star}}-V^{\star}\bigr{\|}_{w}$
$\displaystyle\leq\frac{2}{(1-\gamma\kappa)^{2}}\mathscr{D}^{\max}(V^{\star}).$

###### Proof.

The result follows from Theorem III-B (parts 2 and 3), Lemma III-D, and Lemma
III-D.

###  III-E Generalized bounds based on affine transformations of the cost

Given an MDP $\mathcal{M}$ and a tuple
$\boldsymbol{\alpha}=(\alpha_{1},\alpha_{2})$ of real numbers where
$\alpha_{1}>0$, define a new MDP $\mathcal{M}_{\boldsymbol{\alpha}}$ with the
same dynamics as $\mathcal{M}$ but with the cost function modified to
$\alpha_{1}c(s,a)+\alpha_{2}$. For any policy $\pi$, let
$V^{\pi}_{\boldsymbol{\alpha}}$ denote the value function of $\pi$ in
$\mathcal{M}_{\boldsymbol{\alpha}}$. Similarly, let
$V^{\star}_{\boldsymbol{\alpha}}$ denote the optimal value function for
$\mathcal{M}_{\boldsymbol{\alpha}}$.

The following properties hold for any $s\in\mathcal{S}$:

  1. 1.

For any policy $\pi$,
$V^{\pi}_{\boldsymbol{\alpha}}(s)=\alpha_{1}V^{\pi}(s)+{\alpha_{2}}/{(1-\gamma)}$.

  2. 2.

If $\pi^{\star}$ is optimal for $\mathcal{M}$, then it is also optimal for
$\mathcal{M}_{\boldsymbol{\alpha}}$ and
$V^{\star}_{\boldsymbol{\alpha}}(s)=\alpha_{1}V^{\star}(s)+{\alpha_{2}}/{(1-\gamma)}$.

  3. 3.

For any policy $\pi$ and weight function $w\colon\mathcal{S}\to[1,\infty)$,
$\|V^{\pi}_{\boldsymbol{\alpha}}-V^{\star}_{\boldsymbol{\alpha}}\|_{w}=\alpha_{1}\|V^{\pi}-V^{\star}\|_{w}$.

###### Proof.

Properties 1 and 2 are immediate consequences of the definitions. Property 3
follows from properties 1 and 2.

Lemma III-E provides an alternative way of bounding the performance loss when
the optimal policy $\hat{\pi}^{\star}$ for the approximate model
$\hat{\mathcal{M}}$ is used in the true model ${\mathcal{M}}$. We can first
view $\hat{\mathcal{M}}$ as an approximation for
$\mathcal{M}_{\boldsymbol{\alpha}}$ and bound the approximation error
$\|V^{\hat{\pi}^{\star}}_{\boldsymbol{\alpha}}-V^{\star}_{\boldsymbol{\alpha}}\|_{w}$
in $\mathcal{M}_{\boldsymbol{\alpha}}$. Part 3 of Lemma III-E implies that the
approximation error in $\mathcal{M}$ is simply $1/\alpha_{1}$ times the
approximation error in $\mathcal{M}_{\boldsymbol{\alpha}}$.

To bound the approximation error in $\mathcal{M}_{\boldsymbol{\alpha}}$, let
$\mathscr{B}^{\pi}_{\boldsymbol{\alpha}}$ and
$\mathscr{B}^{\star}_{\boldsymbol{\alpha}}$ denote the Bellman operator and
Bellman optimality operator for $\mathcal{M}_{\boldsymbol{\alpha}}$. Let
$\mathcal{G}_{\boldsymbol{\alpha}}(v)$ denote the set of one-step greedy
policies with respect to $v$ in model $\mathcal{M}_{\boldsymbol{\alpha}}$.

Note that for any $(\alpha_{1},\alpha_{2})$ with $\alpha_{1}>0$, we have that:
(i) If $\mathcal{M}$ is DP-solvable, then so is
$\mathcal{M}_{\boldsymbol{\alpha}}$; (ii) the set of $(\kappa,w)$-stable
policies is the same for $\mathcal{M}$ and
$\mathcal{M}_{\boldsymbol{\alpha}}$. Consequently, if any of Assumptions 1, 2
or 5 holds for $\mathcal{M}$ and $\hat{\mathcal{M}}$, then it also holds for
$\mathcal{M}_{\boldsymbol{\alpha}}$ and $\hat{\mathcal{M}}$. Instead of
Assumptions 3 and 4, we need the following alternative assumptions.

######  Assumption 6.

The set
$\mathcal{G}_{\boldsymbol{\alpha}}(\hat{V}^{\star})\cap\Pi_{S}(\kappa,w)$ is
nonempty.

######  Assumption 7.

The set
$\hat{\mathcal{G}}(V_{\boldsymbol{\alpha}}^{\star})\cap\hat{\Pi}_{S}(\kappa,w)$
is nonempty.

We can now define mismatch functionals (analogous to those defined in
Definitions 4 and III-D) using $\mathcal{M}_{\boldsymbol{\alpha}}$ and
$\hat{\mathcal{M}}$.

Suppose Assumptions 1 and 2 hold. Define the following functionals:

  * •

For any $\pi\in\Pi_{S}(\kappa,w)$ and $\hat{\pi}\in\hat{\Pi}_{S}(\kappa,w)$,
define the _Bellman mismatch functional_
$\mathscr{D}_{\boldsymbol{\alpha}}^{\pi,\hat{\pi}}\colon\mathcal{V}_{w}\to\mathds{R}_{\geq
0}$ as follows: for any $v\in\mathcal{V}_{w}$,

$\mathscr{D}^{\pi,\hat{\pi}}_{\boldsymbol{\alpha}}v=\|\mathscr{B}^{\pi}_{\boldsymbol{\alpha}}v-\hat{\mathscr{B}}^{\hat{\pi}}v\|_{w}.$

  * •

For any $\pi\in\Pi_{S}(\kappa,w)\cap\hat{\Pi}_{S}(\kappa,w)$, define the
_Bellman mismatch functional_
$\mathscr{D}^{\pi}_{\boldsymbol{\alpha}}\colon\mathcal{V}_{w}\to\mathds{R}_{\geq
0}$ as follows: for any $v\in\mathcal{V}_{w}$

$\mathscr{D}^{\pi}_{\boldsymbol{\alpha}}v=\mathscr{D}^{\pi,\pi}_{\boldsymbol{\alpha}}v=\|\mathscr{B}^{\pi}_{\boldsymbol{\alpha}}v-\hat{\mathscr{B}}^{\pi}v\|_{w}.$

  * •

Define the _Bellman optimality mismatch functional_
$\mathscr{D}^{\star}_{\boldsymbol{\alpha}}\colon\mathcal{V}_{w}\to\mathds{R}_{\geq
0}$ as follows: for any $v\in\mathcal{V}_{w}$,

$\mathscr{D}_{\boldsymbol{\alpha}}^{\star}v=\|\mathscr{B}^{\star}_{\boldsymbol{\alpha}}v-\hat{\mathscr{B}}^{\star}v\|_{w}.$

Suppose Assumption 5 holds. Define the _Bellman maximum mismatch functional_
$\mathscr{D}^{\max}_{\boldsymbol{\alpha}}\colon\mathcal{V}_{w}\to\mathds{R}_{\geq
0}$ as follows: for any $v\in\mathcal{V}_{w}$,

$\mathscr{D}_{\boldsymbol{\alpha}}^{\max}v=\sup_{a\in\mathcal{A}}\mathscr{D}_{\boldsymbol{\alpha}}^{\pi_{a}}v=\sup_{a\in\mathcal{A}}\|\mathscr{B}^{\pi_{a}}_{\boldsymbol{\alpha}}v-\hat{\mathscr{B}}^{\pi_{a}}v\|_{w}.$

We can now use Lemma III-E to present variants of Theorem III-B and Theorem
III-D.

For any $\boldsymbol{\alpha}=(\alpha_{1},\alpha_{2})$ with $\alpha_{1}>0$, we
have the following bounds on $V^{\hat{\pi}^{\star}}-V^{\star}$:

  1. 1.

Under Assumptions 1 and 2, we have

$\displaystyle\bigl{\|}V^{\hat{\pi}^{\star}}-V^{\star}\bigr{\|}_{w}$
$\displaystyle\leq\frac{1}{\alpha_{1}(1-\gamma\kappa)}\bigl{[}\mathscr{D}_{\boldsymbol{\alpha}}^{\hat{\pi}^{\star}}\hat{V}^{\star}+\mathscr{D}_{\boldsymbol{\alpha}}^{\pi^{\star},\hat{\pi}^{\star}}\hat{V}^{\star}\bigr{]}$

and

$\displaystyle\bigl{\|}V^{\hat{\pi}^{\star}}-V^{\star}\bigr{\|}_{w}$
$\displaystyle\leq\frac{1}{\alpha_{1}(1-\gamma\kappa)}\mathscr{D}_{\boldsymbol{\alpha}}^{\hat{\pi}^{\star}}(\alpha_{1}V^{\star})$
$\displaystyle\quad+\frac{(1+\gamma\kappa)}{\alpha_{1}(1-\gamma\kappa)^{2}}\mathscr{D}_{\boldsymbol{\alpha}}^{\pi^{\star},\hat{\pi}^{\star}}(\alpha_{1}V^{\star}).$

  2. 2.

Under Assumptions 1, 2 and 6, we have

$\displaystyle\bigl{\|}V^{\hat{\pi}^{\star}}-V^{\star}\bigr{\|}_{w}$
$\displaystyle\leq\frac{1}{\alpha_{1}(1-\gamma\kappa)}\bigl{[}\mathscr{D}^{\hat{\pi}^{\star}}_{\boldsymbol{\alpha}}\hat{V}^{\star}+\mathscr{D}^{\star}_{\boldsymbol{\alpha}}\hat{V}^{\star}\bigr{]}.$

  3. 3.

Under Assumptions 1, 2 and 7, we have

$\displaystyle\bigl{\|}V^{\hat{\pi}^{\star}}-V^{\star}\bigr{\|}_{w}$
$\displaystyle\leq\frac{1}{\alpha_{1}(1-\gamma\kappa)}\mathscr{D}^{\hat{\pi}^{\star}}_{\boldsymbol{\alpha}}(\alpha_{1}V^{\star})$
$\displaystyle\quad+\frac{(1+\gamma\kappa)}{\alpha_{1}(1-\gamma\kappa)^{2}}\mathscr{D}^{\star}_{\boldsymbol{\alpha}}(\alpha_{1}V^{\star}).$

See Appendix G for the proof.

Under Assumptions 1, 2 and 5, we have the following two bounds on
$V^{\hat{\pi}^{\star}}-V^{\star}$:

  1. 1.

Bound in terms of properties of $\hat{V}^{\star}$:

$\displaystyle\bigl{\|}V^{\hat{\pi}^{\star}}-V^{\star}\bigr{\|}_{w}$
$\displaystyle\leq\frac{2}{\alpha_{1}(1-\gamma\kappa)}\mathscr{D}_{\boldsymbol{\alpha}}^{\max}\hat{V}^{\star}.$

  2. 2.

Bound in terms of properties of $V^{\star}$:

$\displaystyle\bigl{\|}V^{\hat{\pi}^{\star}}-V^{\star}\bigr{\|}_{w}\leq\frac{2}{\alpha_{1}(1-\gamma\kappa)^{2}}\mathscr{D}_{\boldsymbol{\alpha}}^{\max}(\alpha_{1}V^{\star}).$

###### Proof.

The result follows from Theorem III-E (parts 2 and 3), Lemma III-D and the
fact that Assumption 5 implies Assumptions 6 and 7 (using the same argument as
Lemma III-D).

#### Some remarks

  * •

It is possible to optimize the bounds in Theorems III-E and III-E by
optimizing over multiple choices of $\boldsymbol{\alpha}$. For Theorem III-E,
parts 2 and 3, we need to ensure that the choice of $\alpha$ satisfies
Assumption 6 or 7, as appropriate.

  * •

For $(\alpha_{1},\alpha_{2})=(1,0)$,
$\mathcal{M}_{\boldsymbol{\alpha}}=\mathcal{M}$ and hence, the bounds in
Theorems III-E and III-E are identical to those in Theorems III-B and III-D,
respectively.

  * •

Thus, if we optimize over appropriate $(\alpha_{1},\alpha_{2})$, then the
bounds of Theorems III-E and III-E are tighter than those of Theorems III-B
and III-D. For instance, if $\hat{\mathcal{M}}=\mathcal{M}_{(2,1)}$, then the
bounds of Theorems III-E and III-E are zero for $\boldsymbol{\alpha}=(2,1)$,
while the bounds of Theorems III-B and III-D may be positive.

##  IV Some instances of the main results

###  IV-A Inventory management

In this section, we illustrate the results of Theorem III-B for an inventory
management problem with state space
$\mathcal{S}=\\{-S_{\max},-S_{\max}+1,\dots S_{\max}\\}$ and action space
$\mathcal{A}=\\{0,1,\dots,S_{\max}\\}$. Let $S_{t}\in\mathcal{S}$ denote the
amount of stock at the beginning of day $t$, $A_{t}\in\mathcal{A}$ denote the
stock ordered at the beginning of day $t$, and $W_{t}\in\mathds{Z}_{\geq 0}$
denote the demand during day $t$. The dynamics are given by

$S_{t+1}=\bigl{[}S_{t}+A_{t}-W_{t}\bigr{]}_{-S_{\max}}^{S_{\max}}$

where $[\cdot]_{-S_{\max}}^{S_{\max}}$ denotes a function which clips its
value between $-S_{\max}$ and $S_{\max}$. The demand $W_{t}$ is assumed to be
an i.i.d. Binomial$(n,q)$ process. The per-step cost is given by

$c(s,a)=pa+c_{h}s\mathds{1}_{\\{s\geq 0\\}}-c_{s}s\mathds{1}_{\\{s<0\\}}$

where $c_{h}$ is the per-unit holding cost, $c_{s}$ is the per-unit shortage
cost, and $p$ is the per-unit procurement cost. We denote the above model by
$\mathcal{M}=(S_{\max},\gamma,n,q,c_{h},c_{s},p)$.

We consider two models:

$\bullet$ | True model |  $\mathcal{M}=(500,0.75,10,0.4,4.0,2,5)$.
---|---|---
$\bullet$ | Approx. model |  $\hat{\mathcal{M}}=(500,0.75,10,0.5,3.8,2,5)$.

Since both models have finite state and action spaces, Assumption 1 is
satisfied (with any choice of weight function). We choose the weight function
to have a similar shape as the per-step cost. In particular, we take
$w(s)=1+(1.5\cdot 10^{-2})\bigl{[}\hat{c}_{h}s\mathds{1}_{\\{s\geq
0\\}}-\hat{c}_{s}s\mathds{1}_{\\{s<0\\}}\bigr{]}$, where $\hat{c}_{h}$ and
$\hat{c}_{s}$ denote the per-unit holding and shortage costs of the
approximate model, respectively. We verify that Assumptions 2 and 3 are
satisfied with $\kappa=1.07$.

The weighted-norm bound of Theorem III-B, part 2 implies that

$V^{\hat{\pi}^{\star}}(s)-\frac{1}{1-\gamma\kappa}\bigl{[}\mathscr{D}^{\hat{\pi}^{\star}}\hat{V}^{\star}+\mathscr{D}^{\star}\hat{V}^{\star}\bigr{]}w(s)\leq
V^{\star}(s)\leq V^{\hat{\pi}^{\star}}(s).$ (16)

We compare these bounds with the sup-norm bounds obtained by taking $w\equiv
1$.

(a) weighted-norm bound

(b) sup-norm bound

Figure 1: Comparison of the bounds on $V^{\star}(s)$ based on weighted-norm
and sup-norm.

(c) weighted-norm bound

(d) sup-norm bound

Figure 2: Zoomed-in versions of the bounds of Fig. 2

For the models $\mathcal{M}$ and $\hat{\mathcal{M}}$ described above, we
compute the policy $\hat{\pi}^{\star}$ using value iteration, compute
$V^{\hat{\pi}^{\star}}$ using policy evaluation, and then plot the upper bound
$V^{\hat{\pi}^{\star}}$, and the weighted- and sup-norm lower bounds on
$V^{\star}(s)$ given by the left hand side of (16) in Fig. 2.

Fig. 2 shows that the weighted-norm bound is slightly tighter than the sup-
norm bound for most states. To better compare the error bounds, we zoom into
the region of $\bar{\mathcal{S}}\coloneqq\\{-10,-9,\dots,10\\}$ in Fig. 2,
where the weighted-norm bound is significantly better than the sup-norm bound.

The optimal policy for the inventory management model described above is a
base-stock policy [33]: $\pi^{\star}(s)=\max(0,\allowbreak{s^{\star}-s}),$
where there is an optimal base-stock level $s^{\star}$ and whenever the
inventory is less than $s^{\star}$, the optimal action is to order goods so
that the inventory becomes $s^{\star}$. For the model $\hat{\mathcal{M}}$, the
base-stock level $s^{\star}=2$. Since the demand has finite support of
$\\{0,1,\dots,10\\}$, after an initial transient period, the inventory level
always remains between $\\{-8,-7,\dots,2\\}$. Thus, we care about the
performance of an approximate policy in this region and, here, the weighted-
norm bounds are substantially tighter than the sup-norm bounds. These results
show that even for finite state and action spaces, weighted-norm bounds can be
better than sup-norm bounds.

###  IV-B Initial State dependent weight function

Suppose there is a family $\mathcal{W}$ of weight functions such that for
every $w\in\mathcal{W}$, there exists a $\kappa_{w}<1/\gamma$ such that
$(\kappa_{w},w)$ satisfies Assumption 2. Then, we can strengthen the result of
(14) as follows:

$V^{\hat{\pi}^{\star}}(s)-\inf_{w\in\mathcal{W}}\Bigl{\\{}\bigl{\|}V^{\hat{\pi}^{\star}}-V^{\star}\bigr{\|}_{w}w(s)\Bigr{\\}}\leq
V^{\star}(s)\leq V^{\hat{\pi}^{\star}}(s).$ (17)

Note that the choice of weight function that gives the tightest bound can vary
with the start state $s$. We illustrate the benefit of such a state dependent
choice of weight function for the inventory management model of the previous
section.

We consider the following family of weight functions for the inventory
management model:

$\mathcal{W}=\big{\\{}1+\ell\bar{c}(s):\ell\in\\{0,0.5\cdot
10^{-2},10^{-2},\dots,2.5\cdot 10^{-2}\\}\bigr{\\}},$ (18)

where $\bar{c}(s)=\hat{c}_{h}s\mathds{1}_{\\{s\geq
0\\}}-\hat{c}_{s}s\mathds{1}_{\\{s<0\\}}$. Note that for $\ell=0$, $w(s)=1$
which corresponds to the sup-norm. For each $w\in\mathcal{W}$, we compute the
smallest $\kappa_{w}$ such that Assumption 2 is satisfied as per (7) and
further verify that this value satisfies Assumption 3. We plot the lower
bounds on $V^{\star}(s)$ corresponding to each $w\in\mathcal{W}$ in Fig. 3. As
can be seen from the figure, the best choice of weight function depends on the
state. Minimizing over all $w\in\mathcal{W}$ as per (17) gives a tighter
bound. This tighter lower bound is highlighted in Fig. 3 using the shaded area
shown in red.

(a) entire state space

(b) zoomed in

Figure 3: Lower bounds obtained by different weight functions. Note that the
curve corresponding to $\ell=0$ is not visible in the zoomed in plot (b).

###  IV-C Generalized bounds based on cost transformation

The generalized bounds of Theorem III-E, part 2, imply that

$V^{\hat{\pi}^{\star}}(s)-\frac{1}{\alpha_{1}(1-\gamma\kappa)}\bigl{[}\mathscr{D}^{\hat{\pi}^{\star}}_{\boldsymbol{\alpha}}\hat{V}^{\star}+\mathscr{D}^{\star}_{\boldsymbol{\alpha}}\hat{V}^{\star}\bigr{]}w(s)\leq
V^{\star}(s)\\\ \leq V^{\hat{\pi}^{\star}}(s)$ (19)

To show that this bound can be better than that of (16) obtained from Theorem
III-B, part 2, we consider the setup of Sec. IV-B with $\ell=1.5\times
10^{-2}$ and compare $\boldsymbol{\alpha}=(0.98,0.8)$ with
$\boldsymbol{\alpha}=(1,0)$. We verify that the appropriate assumptions are
satisfied and plot the two bounds in Fig. 4. As can be seen from the plots,
the bound corresponding to Theorem III-E is tighter.

(a) entire state space

(b) zoomed in

Figure 4: Lower bounds obtained by different choices of $\boldsymbol{\alpha}$.

###  IV-D Linear quadratic regulator

In this section, we use the linear quadratic regulator (LQR) to show that
weighted norm bounds of Theorem III-B provide meaningful results for models
with unbounded per-step cost. Consider a LQR problem with state space
$\mathcal{S}=\mathds{R}^{n_{s}}$ and action space
$\mathcal{A}=\mathds{R}^{n_{a}}$. The dynamics are given by

$s_{t+1}=As_{t}+Ba_{t}+w_{t},$

where $A$ and $B$ are system matrices of appropriate dimensions and
$\\{w_{t}\\}_{t\geq 1}$ is an i.i.d. zero-mean noise process with covariance
$\Sigma_{W}$. The per-step cost is given by

$c(s_{t},a_{t})=s_{t}^{\intercal}Qs_{t}+a_{t}^{\intercal}Ra_{t},$

where $Q$ and $R$ are, respectively, positive semidefinite and positive
definite matrices of appropriate dimensions. We will denote this model by
$\mathcal{M}=(A,B,Q,R,\Sigma_{W},\gamma)$ where $\gamma$ is the discount
factor.

Under standard assumptions of stabilizability and detectability, it is known
that the optimal value function is

$V^{\star}(s)=s^{\intercal}Ps+q,$

where $P$ is the unique positive semidefinite solution of the discounted
Riccati equation

$P=Q+\gamma A^{\intercal}PA-\gamma^{2}A^{\intercal}PB(R+\gamma
B^{\intercal}PB)^{-1}B^{\intercal}PA,$ (20)

and $q=\gamma\operatorname{Tr}(\Sigma_{W}P)/(1-\gamma).$ Furthermore, the
optimal policy is given as $\pi^{\star}(s)=-K^{\star}s$ where
$K^{\star}=\gamma(R+\gamma B^{\intercal}PB)^{-1}B^{\intercal}PA$ is the
optimal gain matrix [34].

We consider two models, a true model $\mathcal{M}=(A,B,Q,R,\Sigma_{W},\gamma)$
and an approximate model
$\hat{\mathcal{M}}=(\hat{A},\hat{B},\hat{Q},\hat{R},\hat{\Sigma}_{W},\gamma)$.
We take the weight function to be $w(s)=1+\ell s^{\intercal}s$, where $\ell>0$
is a parameter. Under standard conditions of stabilizability and detectability
(see [34]), both models $\mathcal{M}$ and $\hat{\mathcal{M}}$ satisfy
Assumption 1. Let $P$ and $\hat{P}$ denote the solutions of the Riccati
equations corresponding to models $\mathcal{M}$ and $\hat{\mathcal{M}}$, and
let $\pi^{\star}(s)=-K^{\star}s$ and $\hat{\pi}^{\star}(s)=-\hat{K}^{\star}s$
denote the optimal policies of models ${\mathcal{M}}$ and $\hat{\mathcal{M}}$.

For any linear policy $\pi(s)=-Ks$, we use the notation $A_{K}=A-BK$ and
$\hat{A}_{K}=\hat{A}-\hat{B}K$. We further use $K_{\mu^{\star}}$ to denote the
gain matrix of the (unique) policy
${\mu^{\star}}\in\mathcal{G}(\hat{V}^{\star})$. We impose the following
assumption.

######  Assumption 8.

The models $\mathcal{M}$ and $\hat{\mathcal{M}}$ are such that

$b_{\Sigma}\coloneqq\max\bigl{\\{}1+\ell\operatorname{Tr}(\Sigma_{W}),1+\ell\operatorname{Tr}(\hat{\Sigma}_{W})\bigr{\\}}\leq\frac{1}{\gamma}$

and

$b_{\sigma}\coloneqq\max\bigl{\\{}\sigma_{1}^{2}(A_{K^{\star}}),\sigma_{1}^{2}(A_{\hat{K}^{\star}}),\sigma_{1}^{2}(\hat{A}_{\hat{K}^{\star}}),\sigma_{1}^{2}(A_{K_{\mu^{\star}}})\bigr{\\}}\leq\frac{1}{\gamma}$

where $\sigma_{1}(A)$ is the operator norm of $A$ (i.e., the largest singular
value of $A$).

Assumption 8 implies Assumptions 2 and 3.

###### Proof.

Fix a policy $\pi(s)=Ks$. Eq. (3) is always satisfied because

$\|c_{\pi}\|_{w}=\sup_{s\in\mathcal{S}}\frac{s^{\intercal}(Q+K^{\intercal}RK)s}{1+\ell
s^{\intercal}s}\leq\frac{1}{\ell}\rho(Q+K^{\intercal}RK)<\infty$

where $\rho(\cdot)$ denotes the spectral radius of a matrix.

Moreover largest value of $\kappa$ for which (4) is satisfied is given by (7),
which simplifies to

$\displaystyle\kappa_{w}$
$\displaystyle=\sup_{s\in\mathcal{S}}\frac{\mathds{E}[w(s_{t+1})|s_{t}=s]}{w(s)}$
$\displaystyle=\sup_{s\in\mathcal{S}}\frac{1+\ell\operatorname{Tr}(\Sigma_{W})+\ell
s^{\intercal}A_{K}^{\intercal}A_{K}s}{1+\ell s^{\intercal}s}$
$\displaystyle\leq\max(1+\ell\operatorname{Tr}(\Sigma_{W}),\sigma_{1}^{2}(A_{K})).$

Thus, if Assumption 8 holds, then Assumptions 2 and 3 hold with
$\kappa\coloneqq\max\\{b_{\Sigma},b_{\sigma}\\}$.

Then, the result of Theorem III-E, part 2 simplifies as follows: Under
Assumptions 1 and 8, we have for $\alpha_{1}=1$ and any $\alpha_{2}$,

$\displaystyle\bigl{\lVert}V^{\hat{\pi}^{\star}}-V^{\star}\bigr{\rVert}_{w}\leq$
$\displaystyle\frac{1}{1-\gamma\kappa}\bigl{[}\max\\{\rho(D^{\star})/\ell,|d_{\Sigma}+\alpha_{2}|\\}$
$\displaystyle\quad+\max\\{\rho(D^{\hat{\pi}^{\star}})/\ell,|d_{\Sigma}+\alpha_{2}|\\}\bigr{]},$
(21)

where $\rho(\cdot)$ denotes the spectral radius of a matrix and

$\displaystyle D^{\star}$ $\displaystyle=\bigl{(}Q+\gamma
A^{\intercal}\hat{P}A-\gamma^{2}A^{\intercal}\hat{P}B(R+\gamma
B^{\intercal}\hat{P}B)^{-1}B^{\intercal}\hat{P}A\bigr{)}$
$\displaystyle\quad-\hat{P}$ (22) $\displaystyle D^{\hat{\pi}^{\star}}$
$\displaystyle=\big{(}Q+(\hat{K}^{\star})^{\intercal}R\hat{K}^{\star}+\gamma
A_{\hat{K}^{\star}}^{\intercal}\hat{P}A_{\hat{K}^{\star}}\big{)}-\hat{P}$ (23)
$\displaystyle\hat{K}^{\star}$
$\displaystyle=\gamma(\hat{R}+\gamma\hat{B}^{\intercal}\hat{P}\hat{B})^{-1}\hat{B}^{\intercal}\hat{P}\hat{A},$
(24) and $\displaystyle d_{\Sigma}$
$\displaystyle=\gamma\operatorname{Tr}((\Sigma_{W}-\hat{\Sigma}_{W})\hat{P}).$
(25)

By taking $\alpha_{2}=-d_{\Sigma}$ we obtain

$\bigl{\lVert}V^{\hat{\pi}^{\star}}-V^{\star}\bigr{\rVert}_{w}\leq\frac{1}{\ell(1-\gamma\kappa)}\bigl{[}\rho(D^{\star})+\rho(D^{\hat{\pi}^{\star}})\bigr{]}.$
(26)

See Appendix H for proof. Under Assumptions 1 and 8, the bound obtained in
(26) does not depend on the Riccati solution $(P,K)$ of the true model
$\mathcal{M}$.

Consider the case when $\hat{\mathcal{M}}$ is the same model as $\mathcal{M}$
except $\hat{\Sigma}_{W}=0$. In this case, $D^{\star}=0$ and
$D^{\hat{\pi}^{\star}}=0$. Therefore, from (26), we get that
$\|V^{\hat{\pi}^{\star}}-V^{\star}\|_{w}=0$, which corresponds to the
classical certainty equivalence principle of LQR control.

###  IV-E Advantage of using $(\kappa,w)$ stability of policy over
$(\kappa,w)$ stability of model

As mentioned in Remark II-C, it is typically assumed in the literature that
the model is $(\bar{\kappa},\bar{w})$ stable, while we impose a weaker
assumption that certain policies are $(\kappa,w)$ stable. In this section, we
illustrate two advantages of imposing the weaker assumption.

First, when the per-step cost is unbounded in the actions, as is the case for
the LQR problem considered in Sec. IV-D, the model $\mathcal{M}$ is not
$(\bar{\kappa},\bar{w})$ stable for any choice of weight function $\bar{w}$.
However, as illustrated in Sec. IV-D, specific policies may be $(\kappa,w)$
stable for $w(s)=1+s^{\intercal}s$. Thus, imposing a weaker assumption of
stability allows us to derive approximation bounds for a larger class of
models.

Second, imposing a weak assumption of stability allows us to derive tighter
approximation bounds. To illustrate this, we reconsider the inventory
management problem in the setting of Sec. IV-B. In Sec. IV-B, we had computed
the lower bounds of (16) when using $(\kappa,w)$ that satisfy Definition II-C.
Now, we consider $(\bar{\kappa},\bar{w})$ that satisfy Definition II-C
instead. In particular, consider a family of weight functions $\mathcal{W}$ as
defined in (18). For each $\bar{w}\in\mathcal{W}$, we compute the smallest
$\bar{\kappa}_{\bar{w}}$ such that (6) is satisfied as per (8). The largest
value of $\ell$ for which $\bar{\kappa}_{\bar{w}}<1/{\gamma}$ is
$\ell=1.75\cdot 10^{-4}$.

We plot the corresponding lower bound given in (16) in Fig. 5. As can be seen
from the plot, in this case the weight function $\bar{w}(s)\equiv 1$
(equivalent to the sup-norm) gives the tightest lower bound. But, as was seen
by the bounds of Fig. 3, the bounds obtained by weighted functions in class
$\mathcal{W}$ were significantly tighter. This highlights the importance of
imposing the weaker assumption of $(\kappa,w)$-stability of policy rather than
the $(\bar{\kappa},\bar{w})$-stability of the model.

(a) entire state space

(b) zoomed in

Figure 5: Lower bounds obtained using stability of the model. Note that the
curves corresponding to $\ell=1.50\cdot 10^{-4}$ and $\ell=1.75\cdot 10^{-4}$
are not visible in both plots.

##  V Integral probability metrics (IPM) and bounds based on distance between
models

In this section, we provide upper bounds for the results of Sec. III that can
be computed in terms of the distance between models $\mathcal{M}$ and
$\hat{\mathcal{M}}$. To define such a distance, we first start with the
definition of integral probability metrics (IPM) [10].

###  V-A Integral probability metrics (IPM)

Let $\mathfrak{F}$ be a convex and balanced subset of $\mathcal{V}_{w}$. Then,
the IPM distance (w.r.t. $\mathfrak{F}$) between two probability laws
$\nu_{1},\nu_{2}\in\mathcal{P}_{w}$ is given by111Since
$\nu_{i}\in\mathcal{P}_{w}$, $i\in\\{1,2\\}$, we have $\int fd\nu_{i}<\infty$
for any $f\in\mathcal{V}_{w}$.

$d_{\mathfrak{F}}(\nu_{1},\nu_{2})=\sup_{f\in\mathfrak{F}}\biggr{|}\int
fd\nu_{1}-\int fd\nu_{2}\biggl{|}.$

In the setting of Definition V-A, the Minkowski functional of any measurable
function $f\in\mathcal{V}_{w}$ is defined as

$\rho_{\mathfrak{F}}(f)=\inf\Bigl{\\{}\rho\in\mathbb{R}_{>0}:\frac{f}{\rho}\in\mathfrak{F}\Bigr{\\}}.$

Note that if for every positive $\rho$, $f/\rho\not\in\mathfrak{F}$, then
$\rho_{\mathfrak{F}}(f)=\infty$.

An immediate consequence of the above two definitions is that for any
measurable function $f\in\mathcal{V}_{w}$,

$\biggl{|}\int fd\nu_{1}-\int
fd\nu_{2}\biggr{|}\leq\rho_{\mathfrak{F}}(f)d_{\mathfrak{F}}(\nu_{1},\nu_{2}).$
(27)

Many of the commonly used metrics on probability spaces are IPMs. For example

  * •

Total variation distance, denoted by $d_{\mathrm{TV}}$, corresponds to
$\mathfrak{F}=\mathfrak{F}_{\mathrm{TV}}\coloneqq\\{f\in\mathcal{V}_{w\equiv
1}:\tfrac{1}{2}\operatorname{span}(f)\leq 1\\}$, where
$\operatorname{span}(f)=\sup(f)-\inf(f)$ [10, 35]. In this case
$\rho_{\mathfrak{F}}(f)=\tfrac{1}{2}\operatorname{span}(f)$.

  * •

Wasserstein distance. Suppose $(\mathcal{S},d_{\mathcal{S}})$ is a metric
space Define
$\mathfrak{F}_{\mathrm{Was},w}\coloneqq\\{f\in\mathcal{V}_{w}:\operatorname{Lip}(f)\leq
1\\}$ where $\operatorname{Lip}(f)$ denotes the Lipschitz constant of a
function $f$. Then, for $\mathfrak{F}=\mathfrak{F}_{\mathrm{Was},w}$, Eq (27)
holds for $\rho_{\mathfrak{F}}(f)=\operatorname{Lip}(f)$. Moreover
$d_{\mathfrak{F}}(\nu_{1},\nu_{2})\leq d_{\mathrm{Was}}(\nu_{1},\nu_{2})$,
where $d_{\mathrm{Was}}$ is the Wasserstein distance [36, 35].

  * •

Weighted total variation distance, denoted by $d_{\mathrm{TV},w}$, corresponds
to
$\mathfrak{F}=\mathfrak{F}_{\mathrm{TV},w}\coloneqq\\{f\in\mathcal{V}_{w}:\operatorname{osc}_{w}(f)\leq
1\\}$, where
$\operatorname{osc}_{w}(f)=\sup_{s,s^{\prime}\in\mathcal{S}\times\mathcal{S}}|f(s)-f(s^{\prime})|/(w(s)+w(s^{\prime}))$
[37, 38, 39]. For this case,
$\rho_{\mathfrak{F}}(f)=\operatorname{osc}_{w}(f)$.

###  V-B Weighted distance between two MDP models

Note that if a policy $\pi$ is $(\kappa,w)$ stable, then Eq. (4) implies that
$P_{\pi}(\cdot|s)\in\mathcal{P}_{w}$ for every $s\in\mathcal{S}$. Therefore,
Assumption 2 implies that for all $s\in\mathcal{S}$,
$P_{\pi^{\star}}(\cdot|s),P_{\hat{\pi}^{\star}}(\cdot|s),\hat{P}_{\hat{\pi}^{\star}}(\cdot|s)\in\mathcal{P}_{w}$
and Assumption 5 implies that for all $(s,a)\in\mathcal{S}\times\mathcal{A}$,
we have $P(\cdot|s,a),\hat{P}(\cdot|s,a)\in\mathcal{P}_{w}$.

We now define two notions of weighted distance between two MDP models.
[Distance between MDP models] Given two MDP models
$\mathcal{M}=\langle\mathcal{S},\mathcal{A},P,c,\gamma\rangle$ and
$\hat{\mathcal{M}}=\langle\mathcal{S},\mathcal{A},\hat{P},\hat{c},\gamma\rangle$,
a weight function $w:\mathcal{S}\to[1,\infty)$ and an IPM $d_{\mathfrak{F}}$
as defined in Definition V-A, we define the following

  1. 1.

Distance between models for given policies: Given deterministic policies $\pi$
for model $\mathcal{M}$ and $\hat{\pi}$ for model $\hat{\mathcal{M}}$ such
that $P_{\pi}(\cdot|s),\hat{P}_{\hat{\pi}}(\cdot|s)\in\mathcal{P}_{w}$ for all
$s\in\mathcal{S}$, define

$\displaystyle\varepsilon_{\boldsymbol{\alpha}}(\pi,\hat{\pi})$
$\displaystyle\coloneqq\sup_{s\in\mathcal{S}}\frac{\bigl{|}\alpha_{1}c_{\pi}(s)+\alpha_{2}-\hat{c}_{\hat{\pi}}(s)\bigr{|}}{w(s)}$

and

$\delta_{\mathfrak{F}}(\pi,\hat{\pi})\coloneqq\sup_{s\in\mathcal{S}}\frac{d_{\mathfrak{F}}\bigl{(}P_{\pi}(\cdot|s\bigr{)},\hat{P}_{\hat{\pi}}\bigl{(}\cdot|s)\bigr{)}}{w(s)}.$

  2. 2.

Maximal distance between models: Under Assumption 5, define

$\varepsilon^{\max}_{\boldsymbol{\alpha}}\coloneqq\sup_{(s,a)\in\mathcal{S}\times\mathcal{A}}\frac{\left|\alpha_{1}c(s,a)+\alpha_{2}-\hat{c}(s,a)\right|}{w(s)}$

and

$\delta_{\mathfrak{F}}^{\max}\coloneqq\sup_{(s,a)\in\mathcal{S}\times\mathcal{A}}\frac{d_{\mathfrak{F}}\bigl{(}P(\cdot|s,a),\hat{P}(\cdot|s,a)\bigr{)}}{w(s)}.$

Note that the distances defined above depend on the weight function $w$, but
we don’t explicitly capture that dependence in the notation.

###  V-C IPM based approximation bounds

We have the following bounds for different mismatch functionals:

  1. 1.

If policies $\pi$ and $\hat{\pi}$ are such that for all $s\in\mathcal{S}$,
$P_{\pi}(\cdot|s)$, $\hat{P}_{\pi}(\cdot|s)$,
$P_{\hat{\pi}}(\cdot|s)\in\mathcal{P}_{w}$, then for all
$v\in\mathcal{V}_{w}$,

$\mathscr{D}^{\pi,\hat{\pi}}_{\boldsymbol{\alpha}}v\leq\varepsilon_{\boldsymbol{\alpha}}(\pi,\hat{\pi})+\gamma\rho_{\mathfrak{F}}(v)\delta_{\mathfrak{F}}(\pi,\hat{\pi}).$

  2. 2.

If Assumption 6 is satisfied,

$\mathscr{D}^{\star}_{\boldsymbol{\alpha}}\hat{V}^{\star}\leq\varepsilon_{\boldsymbol{\alpha}}(\mu^{\star},\hat{\pi}^{\star})+\gamma\rho_{\mathfrak{F}}(\hat{V}^{\star})\delta_{\mathfrak{F}}(\mu^{\star},\hat{\pi}^{\star}),$

for all
$\mu^{\star}\in\mathcal{G}_{\boldsymbol{\alpha}}(\hat{V}^{\star})\cap\Pi_{S}(\kappa,w)$
(see Assumption 6).

  3. 3.

If Assumption 7 is satisfied,

$\mathscr{D}^{\star}_{\boldsymbol{\alpha}}(\alpha_{1}V^{\star})\leq\varepsilon_{\boldsymbol{\alpha}}(\pi^{\star},\hat{\mu}^{\star})+\alpha_{1}\gamma\rho_{\mathfrak{F}}(V^{\star})\delta_{\mathfrak{F}}(\pi^{\star},\hat{\mu}^{\star}),$

for all
$\hat{\mu}^{\star}\in\hat{\mathcal{G}}(V^{\star}_{\boldsymbol{\alpha}})\cap\hat{\Pi}_{S}(\kappa,w)$
(see Assumption 7).

  4. 4.

If Assumption 5 is satisfied, then for all $v\in\mathcal{V}_{w}$,

$\mathscr{D}^{\max}_{\boldsymbol{\alpha}}v\leq\varepsilon^{\max}_{\boldsymbol{\alpha}}+\gamma\rho_{\mathfrak{F}}(v)\delta_{\mathfrak{F}}^{\max}.$

See Appendix I for proof.

Substituting the results of Lemma V-C in Theorem III-E and Theorem III-E, we
obtain the following:

We have the following bounds on $V^{\hat{\pi}^{\star}}-V^{\star}$:

  1. 1.

Under Assumptions 1 and 2, we have

$\displaystyle\hskip-10.00002pt\bigl{\|}V^{\hat{\pi}^{\star}}-V^{\star}\bigr{\|}_{w}$
$\displaystyle\leq\frac{1}{\alpha_{1}(1-\gamma\kappa)}\biggl{[}\varepsilon_{\boldsymbol{\alpha}}(\hat{\pi}^{\star},\hat{\pi}^{\star})+\varepsilon_{\boldsymbol{\alpha}}(\pi^{\star},\hat{\pi}^{\star})$
$\displaystyle\quad+\gamma\rho_{\mathfrak{F}}(\hat{V}^{\star})\bigl{(}\delta_{\mathfrak{F}}(\hat{\pi}^{\star},\hat{\pi}^{\star})+\delta_{\mathfrak{F}}(\pi^{\star},\hat{\pi}^{\star})\bigr{)}\biggr{]}$

and

$\displaystyle\bigl{\|}V^{\hat{\pi}^{\star}}-V^{\star}\bigr{\|}_{w}$
$\displaystyle\leq\frac{1}{\alpha_{1}(1-\gamma\kappa)}\bigl{[}\varepsilon_{\boldsymbol{\alpha}}(\hat{\pi}^{\star},\hat{\pi}^{\star})+\alpha_{1}\gamma\rho_{\mathfrak{F}}(V^{\star})\delta_{\mathfrak{F}}(\hat{\pi}^{\star},\hat{\pi}^{\star})\bigr{]}$
$\displaystyle+\frac{1+\gamma\kappa}{\alpha_{1}(1-\gamma\kappa)^{2}}\bigl{[}\varepsilon_{\boldsymbol{\alpha}}(\pi^{\star},\hat{\pi}^{\star})+\alpha_{1}\gamma\rho_{\mathfrak{F}}(V^{\star})\delta_{\mathfrak{F}}(\pi^{\star},\hat{\pi}^{\star})\bigr{]}.$

  2. 2.

Under Assumptions 1, 2 and 6, we have

$\displaystyle\hskip-10.00002pt\bigl{\|}V^{\hat{\pi}^{\star}}-V^{\star}\bigr{\|}_{w}$
$\displaystyle\leq\frac{1}{\alpha_{1}(1-\gamma\kappa)}\biggl{[}\varepsilon_{\boldsymbol{\alpha}}(\hat{\pi}^{\star},\hat{\pi}^{\star})+\varepsilon_{\boldsymbol{\alpha}}(\mu^{\star},\hat{\pi}^{\star})$
$\displaystyle\quad+\gamma\rho_{\mathfrak{F}}(\hat{V}^{\star})\bigl{(}\delta_{\mathfrak{F}}(\hat{\pi}^{\star},\hat{\pi}^{\star})+\delta_{\mathfrak{F}}(\mu^{\star},\hat{\pi}^{\star})\bigr{)}\biggr{]}$

for all
$\mu^{\star}\in\mathcal{G}_{\boldsymbol{\alpha}}(\hat{V}^{\star})\cap\Pi_{S}(\kappa,w)$
(see Assumption 6).

  3. 3.

Under Assumptions 1, 2 and 7, we have

$\displaystyle\bigl{\|}V^{\hat{\pi}^{\star}}-V^{\star}\bigr{\|}_{w}$
$\displaystyle\leq\frac{1}{\alpha_{1}(1-\gamma\kappa)}\bigl{[}\varepsilon_{\boldsymbol{\alpha}}(\hat{\pi}^{\star},\hat{\pi}^{\star})+\alpha_{1}\gamma\rho_{\mathfrak{F}}(V^{\star})\delta_{\mathfrak{F}}(\hat{\pi}^{\star},\hat{\pi}^{\star})\bigr{]}$
$\displaystyle+\frac{1+\gamma\kappa}{\alpha_{1}(1-\gamma\kappa)^{2}}\bigl{[}\varepsilon_{\boldsymbol{\alpha}}(\pi^{\star},\hat{\mu}^{\star})+\alpha_{1}\gamma\rho_{\mathfrak{F}}(V^{\star})\delta_{\mathfrak{F}}(\pi^{\star},\hat{\mu}^{\star})\bigr{]}.$

for all
$\hat{\mu}^{\star}\in\hat{\mathcal{G}}(V^{\star}_{\boldsymbol{\alpha}})\cap\hat{\Pi}_{S}(\kappa,w)$
(see Assumption 7).

  4. 4.

Under Assumptions 1, 2 and 5, we have

$\bigl{\|}V^{\hat{\pi}^{\star}}-V^{\star}\bigr{\|}_{w}\leq\frac{2}{\alpha_{1}(1-\gamma\kappa)}\Bigl{[}\varepsilon_{\boldsymbol{\alpha}}^{\max}+\gamma\rho_{\mathfrak{F}}(\hat{V}^{\star})\delta_{\mathfrak{F}}^{\max}\Bigr{]}$

and

$\displaystyle\hskip-10.00002pt\bigl{\|}V^{\hat{\pi}^{\star}}-V^{\star}\bigr{\|}_{w}\leq$
$\displaystyle\frac{2}{\alpha_{1}(1-\gamma\kappa)^{2}}\Bigl{[}\varepsilon_{\boldsymbol{\alpha}}^{\max}+\alpha_{1}\gamma\rho_{\mathfrak{F}}(V^{\star})\delta_{\mathfrak{F}}^{\max}\Bigr{]}.$

The bounds of Theorem V-C may be specialized for specific choices of IPMs. We
present these bounds in terms of
$(\varepsilon_{\boldsymbol{\alpha}}^{\max},\delta_{\mathfrak{F}}^{\max})$ and
$\hat{V}^{\star}$. The bounds in terms of
$(\varepsilon_{\boldsymbol{\alpha}}(\pi^{\star},\hat{\pi}^{\star}),\delta_{\mathfrak{F}}(\pi^{\star},\hat{\pi}^{\star}))$
etc. and/or $V^{\star}$ can be expressed in a similar manner.

Under Assumptions 1, 2 and 5, we have the following bounds on
$V^{\hat{\pi}^{\star}}-V^{\star}$:

  1. 1.

Bound in terms of total-variation distance:

$\displaystyle\bigl{\|}V^{\hat{\pi}^{\star}}-V^{\star}\bigr{\|}_{w}$
$\displaystyle\leq\frac{2}{\alpha_{1}(1-\gamma\kappa)}\biggl{[}\varepsilon_{\boldsymbol{\alpha}}^{\max}$
$\displaystyle\hskip-20.00003pt+\gamma\sup_{\begin{subarray}{c}s\in\mathcal{S}\\\
a\in\mathcal{A}\end{subarray}}\frac{d_{\mathrm{TV}}(P(\cdot|s,a),\hat{P}(\cdot|s,a))}{w(s)}\,\frac{\operatorname{span}(\hat{V}^{\star})}{2}\biggr{]}.$

  2. 2.

Bound in terms of Wasserstein distance:

$\displaystyle\bigl{\|}V^{\hat{\pi}^{\star}}-V^{\star}\bigr{\|}_{w}$
$\displaystyle\leq\frac{2}{\alpha_{1}(1-\gamma\kappa)}\biggl{[}\varepsilon_{\boldsymbol{\alpha}}^{\max}$
$\displaystyle\hskip-20.00003pt+\gamma\sup_{\begin{subarray}{c}s\in\mathcal{S}\\\
a\in\mathcal{A}\end{subarray}}\frac{d_{\mathrm{Was}}(P(\cdot|s,a),\hat{P}(\cdot|s,a))}{w(s)}\,\operatorname{Lip}(\hat{V}^{\star})\biggr{]}.$

  3. 3.

Bound in terms of weighted total variation distance:

$\displaystyle\bigl{\|}V^{\hat{\pi}^{\star}}-V^{\star}\bigr{\|}_{w}$
$\displaystyle\leq\frac{2}{\alpha_{1}(1-\gamma\kappa)}\biggl{[}\varepsilon_{\boldsymbol{\alpha}}^{\max}$
$\displaystyle\hskip-20.00003pt+\gamma\sup_{\begin{subarray}{c}s\in\mathcal{S}\\\
a\in\mathcal{A}\end{subarray}}\frac{d_{\mathrm{TV},w}(P(\cdot|s,a),\hat{P}(\cdot|s,a))}{w(s)}\,\operatorname{osc}_{w}(\hat{V}^{\star})\biggr{]}.$

Parts 1 and 2 of Corollary V-C may be viewed as weighted generalization of
approximation results presented in [10, 28, 30] (some of those results assumed
that the approximate model has a smaller state space than the original model).

###  V-D Performance loss in using certainty equivalent control

Certainty equivalence refers to the following design methodology to determine
a control policy for a stochastic control problem. Replace the random
variables in the stochastic control problem by their (conditional)
expectations, solve the resulting deterministic control problem to determine a
feedback control policy, and use the resulting _certainty equivalent control
policy_ in the original stochastic system [40, 41]. It is well known that for
systems with linear dynamics and quadratic cost (LQ problems), certainty
equivalent control policies are optimal. But this is not the case in general.
In this section, we use the results of Theorem V-C to characterize the
performance loss when using certainty equivalence for general dynamics with
additive noise.

Consider a system with state space $\mathds{R}^{n}$, action space
$\mathds{R}^{m}$, and dynamics

$S_{t+1}=f(S_{t},A_{t})+N_{t}$ (28)

where $f$ is a measurable function and $\\{N_{t}\\}_{t\geq 1}$ is a zero-mean
i.i.d. noise sequence with control law $\nu_{N}$. The per-step cost is given
by $c(S_{t},A_{t})$.

Now consider a deterministic model obtained by assuming that the noise
sequence in (28) takes its expected value, i.e., the dynamics are

$S_{t+1}=f(S_{t},A_{t}).$ (29)

The per-step cost is the same as before.

Let $\mathcal{M}$ denote the stochastic model and $\hat{\mathcal{M}}$ denote
the deterministic model. Then, the certainty equivalent design is to use the
control policy $\hat{\pi}^{\star}$ in original stochastic model $\mathcal{M}$.
Suppose Assumptions 1, 2, and 5 are satisfied for some $(\kappa,w)$. We use
the Wasserstein distance based bounds in Corollary V-C to bound
$\|V^{\hat{\pi}^{\star}}-V^{\star}\|_{w}$, where we take
$\boldsymbol{\alpha}=(1,0)$ for simplicity. We assume that there is some norm
$\|\cdot\|$ on $\mathds{R}^{n}$ and the Wasserstein distance and Lipschitz
constant are computed with respect to this norm.

Since the costs are the same for both models,
$\varepsilon_{\boldsymbol{\alpha}}^{\max}=0$. We now characterize
$\delta^{\max}$. For ease of notation, given random variables $X$ and $Y$ with
probability laws $\nu_{X}$ and $\nu_{Y}$, we will use $d_{\mathrm{Was}}(X,Y)$
to denote $d_{\mathrm{Was}}(\nu_{X},\nu_{Y})$. Wasserstein distance is defined
as [35]

$d_{\mathrm{Was}}(\nu_{X},\nu_{Y})=\inf_{(\tilde{X},\tilde{Y})\colon\tilde{X}\sim\nu_{X},\tilde{Y}\sim\nu_{Y}}\mathds{E}[\|\tilde{X}-\tilde{Y}\|].$
(30)

Now, for a fixed $(s,a)$, define $X=f(s,a)+N$, where $N\sim\nu_{N}$, and
$Y=f(s,a)$. Then, the Wasserstein distance between $P(\cdot|s,a)$ and
$\hat{P}(\cdot|s,a)$ is equal to $d_{\mathrm{Was}}(X,Y)$ which, by (30),
equals $\mathds{E}[\|N\|]$ for all $(s,a)$. Thus,

$\delta^{\max}_{\mathfrak{F}_{\mathrm{Was}}}=\sup_{(s,a)\in\mathcal{S}\times\mathcal{A}}\frac{\mathds{E}[\|N\|]}{w(s)}\leq\mathds{E}[\|N\|]$

Thus, by Corollary V-C, part 2, we get

$\|V^{\hat{\pi}^{\star}}-V^{\star}\|_{w}\leq\frac{2\gamma}{1-\gamma\kappa}\mathds{E}[\|N\|]\operatorname{Lip}(\hat{V}^{\star}).$
(31)

This bound precisely quantifies the engineering intuition that certainty
equivalent control laws are good when the noise is “small”.

The right hand side of (31) does not depend on the weight function (provided
the weight function satisfies Assumption 2). Suppose the per-step cost is such
that $c_{\min}\geq 0$ and $w=1+V^{\star}$ satisfies Assumption 2 for some
$\kappa<1/\gamma$. Then, Eq. (31) implies that

$V^{\star}(s)\leq
V^{\hat{\pi}^{\star}}(s)\leq\biggl{(}1+\frac{2\gamma}{1-\gamma\kappa}\mathds{E}[\|N\|]\operatorname{Lip}(\hat{V}^{\star})\biggr{)}\bigl{(}1+V^{\star}(s)\bigr{)}.$

This inequality may be viewed as a generalization of the approximation bounds
of [42] to dynamical systems.

##  VI Conclusion

In this paper, we present a series of bounds on the weighted approximation
error when using the optimal policy of an approximate model
$\hat{\mathcal{M}}$ in the original model $\mathcal{M}$. For each bound, we
have two types of bounds: one which depends on the value function
$\hat{V}^{\star}$ of the approximate model $\hat{\mathcal{M}}$ and the other
which depends on the value function $V^{\star}$ of the original model
$\mathcal{M}$. The first type of bound is more useful in practice because one
would obtain $\hat{V}^{\star}$ when computing the optimal policy of the
approximate model $\hat{\mathcal{M}}$. However, the second type of bound is a
theoretical upper bound that may be useful for obtaining bounds for
reinforcement learning algorithms, e.g., in obtaining sample complexity
bounds.

Our results rely on using an appropriate $(\kappa,w)$ such that certain
policies are $(\kappa,w)$ stable. The choice of the weight function $w$
impacts the tightness of the bounds. Understanding how to choose weight
functions is an interesting research direction.

In this paper, we assumed that the approximate model $\hat{\mathcal{M}}$ was
given. However, often the approximate model is a design choice. For example,
when solving continuous state models, we may decide how to quantize the state
space. The approximation bounds obtained in this paper may be useful in
guiding the design of such approximate models. They may also be useful in
generalizing the convergence guarantees and regret bounds of reinforcement
learning algorithms to models with unbounded per-step cost.

## References

  * [1] B. Bozkurt, A. Mahajan, A. Nayyar, and Y. Ouyang, “Weighted norm bounds in mdps with unbounded per-step cost,” in _Conference on Decision and Control_. Singapore: IEEE, Dec. 2023.
  * [2] B. L. Fox, “Finite-state approximations to denumerable-state dynamic programs,” _J. Math. Analy. Appl._ , vol. 34, no. 3, pp. 665–670, 1971.
  * [3] W. Whitt, “Approximations of dynamic programs, I,” _Math. Oper. Res._ , vol. 3, no. 3, pp. 231–243, 1978.
  * [4] ——, “Approximations of dynamic programs, II,” _Math. Oper. Res._ , vol. 4, no. 2, pp. 179–185, 1979.
  * [5] ——, “Representation and approximation of noncooperative sequential games,” _SIAM J. Contr. Optim._ , vol. 18, no. 1, pp. 33–48, 1980.
  * [6] D. Bertsekas, “Convergence of discretization procedures in dynamic programming,” _IEEE Trans. Autom. Control_ , vol. 20, no. 3, pp. 415–419, 1975.
  * [7] C.-S. Chow and J. N. Tsitsiklis, “An optimal one-way multigrid algorithm for discrete-time stochastic control,” _IEEE transactions on automatic control_ , vol. 36, no. 8, pp. 898–914, 1991.
  * [8] F. Dufour and T. Prieto-Rumeau, “Approximation of Markov decision processes with general state space,” _J. Math. Analy. Appl._ , vol. 388, no. 2, pp. 1254–1267, 2012.
  * [9] A. Haurie and P. L’ecuyer, “Approximation and bounds in discrete event dynamic programming,” _IEEE Trans. Autom. Control_ , vol. 31, no. 3, pp. 227–235, 1986.
  * [10] A. Müller, “How does the value function of a Markov decision process depend on the transition probabilities?” _Math. Oper. Res._ , vol. 22, no. 4, pp. 872–885, 1997.
  * [11] N. Saldi, T. Linder, and S. Yüksel, “Asymptotic optimality and rates of convergence of quantized stationary policies in stochastic control,” _IEEE Trans. Autom. Control_ , vol. 60, no. 2, pp. 553–558, 2014.
  * [12] N. Saldi, S. Yüksel, and T. Linder, “On the asymptotic optimality of finite approximations to Markov decision processes with borel spaces,” _Math. Oper. Res._ , vol. 42, no. 4, pp. 945–978, 2017.
  * [13] N. Saldi, T. Linder, and S. Yüksel, _Finite Approximations in discrete-time stochastic control_. Springer, 2018.
  * [14] A. D. Kara, “Near optimality of finite memory feedback policies in partially observed markov decision processes,” _J. Mach. Learn. Res._ , vol. 23, no. 1, pp. 437–482, 2022.
  * [15] J. Subramanian, A. Sinha, R. Seraj, and A. Mahajan, “Approximate information state for approximate planning and reinforcement learning in partially observed systems.” _J. Mach. Learn. Res._ , vol. 23, no. 12, pp. 1–83, 2022\.
  * [16] B. L. Fox, “Discretizing dynamic programs,” _J. Opt. Theory and Appl._ , vol. 11, pp. 228–234, 1973.
  * [17] P. K. Dutta, M. K. Majumdar, and R. K. Sundaram, “Parametric continuity in dynamic programming problems,” _J. Economic Dynamics and Control_ , vol. 18, no. 6, pp. 1069–1092, 1994.
  * [18] N. Saldi, S. Yüksel, and T. Linder, “Near optimality of quantized policies in stochastic control under weak continuity conditions,” _J. Math. Analy. Appl._ , vol. 435, no. 1, pp. 321–337, 2016.
  * [19] ——, “Asymptotic optimality of finite model approximations for partially observed markov decision processes with discounted cost,” _IEEE Trans. Autom. Control_ , vol. 65, no. 1, pp. 130–142, 2019.
  * [20] A. D. Kara and S. Yuksel, “Robustness to incorrect priors in partially observed stochastic control,” _SIAM J. Contr. Optim._ , vol. 57, no. 3, pp. 1929–1964, 2019.
  * [21] ——, “Robustness to incorrect system models in stochastic control,” _SIAM J. Cont. Optim._ , vol. 58, no. 2, pp. 1144–1182, 2020.
  * [22] A. D. Kara, M. Raginsky, and S. Yüksel, “Robustness to incorrect models and data-driven learning in average-cost optimal stochastic control,” _Automatica_ , vol. 139, p. 110179, 2022.
  * [23] B. Ravindran and A. G. Barto, “Approximate homomorphisms: A framework for non-exact minimization in Markov decision processes,” in _KBCS_ , 2004\.
  * [24] E. van der Pol, T. Kipf, F. A. Oliehoek, and M. Welling, “Plannable approximations to MDP homomorphisms: Equivariance under actions,” in _AAMAS_ , Auckland, New Zealand, May 2020.
  * [25] N. Ferns, P. Panangaden, and D. Precup, “Metrics for finite Markov decision processes.” in _UAI_ , vol. 4, 2004, pp. 162–169.
  * [26] ——, “Bisimulation metrics for continuous Markov decision processes,” _SIAM J. Comp._ , vol. 40, no. 6, pp. 1662–1714, 2011.
  * [27] P. S. Castro, P. Panangaden, and D. Precup, “Equivalence relations in fully and partially observable Markov decision processes.” in _IJCAI_ , vol. 9, 2009, pp. 1653–1658.
  * [28] D. Abel, D. Hershkowitz, and M. Littman, “Near optimal behavior via approximate state abstraction,” in _ICML_. PMLR, 2016, pp. 2915–2923.
  * [29] V. François-Lavet, G. Rabusseau, J. Pineau, D. Ernst, and R. Fonteneau, “On overfitting and asymptotic bias in batch reinforcement learning with partial observability,” _J. Artif. Intel. Res._ , vol. 65, pp. 1–30, 2019\.
  * [30] C. Gelada, S. Kumar, J. Buckman, O. Nachum, and M. G. Bellemare, “Deepmdp: Learning continuous latent space models for representation learning,” in _ICML_. PMLR, 2019, pp. 2170–2179.
  * [31] O. Hernández-Lerma and J. B. Lasserre, _Discrete-time Markov control processes: basic optimality criteria_. Springer Science & Business Media, 2012.
  * [32] ——, _Further topics on discrete-time Markov control processes_. Springer Science & Business Media, 2012.
  * [33] K. J. Arrow, T. Harris, and J. Marschak, “Optimal inventory policy,” _Econometrica: Journal of the Econometric Society_ , pp. 250–272, 1951.
  * [34] D. P. Bertsekas, “Dynamic programming and optimal control, volume II,” _Athena Scientific_ , 2015.
  * [35] C. Villani _et al._ , _Optimal transport: old and new_. Springer, 2008, vol. 338.
  * [36] L. N. Vaserstein, “Markov processes over denumerable products of spaces, describing large systems of automata,” _Problemy Peredachi Informatsii_ , vol. 5, no. 3, pp. 64–72, 1969.
  * [37] R. Douc, E. Moulines, P. Priouret, and P. Soulier, _Markov chains_. Springer, 2018.
  * [38] M. Hairer and J. C. Mattingly, “Yet another look at Harris’ ergodic theorem for Markov chains,” in _Seminar on Stochastic Analysis, Random Fields and Applications V_. Springer, 2011, pp. 109–117.
  * [39] S. P. Meyn and R. L. Tweedie, “Stability of Markovian processes I: Criteria for discrete-time chains,” _Advances in Applied Probability_ , vol. 24, no. 3, pp. 542–574, 1992.
  * [40] H. A. Simon, “Dynamic programming under uncertainty with a quadratic criterion function,” _Econometrica: Journal of the Econometric Society_ , pp. 74–81, 1956.
  * [41] H. Theil, “A note on certainty equivalence in dynamic planning,” _Econometrica: Journal of the Econometric Society_ , pp. 346–349, 1957.
  * [42] H. Witsenhausen, “Inequalities for the performance of suboptimal uncertain systems,” _Automatica_ , vol. 5, no. 4, pp. 507–512, Jul. 1969.

##  Appendix A Proof of Lemma II-C

We prove each part separately.

#### Proof of part 1)

Fix a state $s\in\mathcal{S}$. For a policy $\pi\in\Pi_{S}(\kappa,w)$ and a
value function $v\in\mathcal{V}_{w}$, we have

$\displaystyle\hskip-10.00002pt\left|\frac{\mathscr{B}^{\pi}v(s)}{w(s)}\right|$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\left|\frac{c_{\pi}(s)}{w(s)}\right|+\gamma\left|\int_{\mathcal{S}}P_{\pi}(ds^{\prime}\mid
s)\frac{v(s^{\prime})}{w(s^{\prime})}\frac{w(s^{\prime})}{w(s)}\right|$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\|c_{\pi}\|_{w}+\gamma\|v\|_{w}\left|\int_{\mathcal{S}}P_{\pi}(ds^{\prime}\mid
s)\frac{w(s^{\prime})}{w(s)}\right|$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\|c_{\pi}\|_{w}+\gamma\|v\|_{w}\kappa<\infty,$

where $(a)$ follows from the triangle inequality, $(b)$ follows from the
definition of $\|\cdot\|_{w}$ and $(c)$ follows from the fact that $\pi$ is
$(\kappa,w)$ stable.

#### Proof of part 2)

Fix a state $s\in\mathcal{S}$. We have

$\displaystyle\hskip-5.0pt\left|\frac{[\mathscr{B}^{\pi}v_{1}-\mathscr{B}^{\pi}v_{2}](s)}{w(s)}\right|$
$\displaystyle=\gamma\left|\int_{\mathcal{S}}P_{\pi}(ds^{\prime}\mid
s)\biggl{[}\frac{v_{1}(s^{\prime})-v_{2}(s^{\prime})}{w(s^{\prime})}\biggr{]}\frac{w(s^{\prime})}{w(s)}\right|$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\gamma\|v_{1}-v_{2}\|_{w}\left|\int_{\mathcal{S}}P_{\pi}(ds^{\prime}\mid
s)\frac{w(s^{\prime})}{w(s)}\right|$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\gamma\kappa\|v_{1}-v_{2}\|_{w}$

where $(a)$ holds from the definition of $\|\cdot\|_{w}$ and $(b)$ holds
because $\pi$ is $(\kappa,w)$ stable.

#### Proof of part 3)

From parts 1 and 2 of Lemma II-C, we know that
$\mathscr{B}^{\pi}:\mathcal{V}_{w}\to\mathcal{V}_{w}$ is a contraction. Since
$\mathcal{V}_{w}$ is a complete metric space (under the $\|\cdot\|_{w}$ norm),
it follows from Banach fixed point theorem that $\mathscr{B}^{\pi}$ has a
unique fixed point $F$ in $\mathcal{V}_{w}$. If $V^{\pi}_{n}$ denotes the
$n-$step discounted cost for policy $\pi$, then it can be shown that
$V^{\pi}_{n+1}=\mathscr{B}^{\pi}V^{\pi}_{n}$ and that
$V^{\pi}_{n}\in\mathcal{V}_{w}$ for all $n$. Thus, by Banach fixed point
theorem, $V^{\pi}_{n}$ converges to the fixed point $F$ of $\mathscr{B}^{\pi}$
in the $\|\cdot\|_{w}$ norm. Since convergence in $\|\cdot\|_{w}$ norm implies
pointwise convergence, we have $F(s)=\lim_{n\to\infty}V^{\pi}_{n}(s)$ for all
$s\in\mathcal{S}$. Furthermore, since per-step costs are bounded below, we
have that for all $s\in\mathcal{S}$,

$\displaystyle\lim_{n\to\infty}V^{\pi}_{n}(s)$
$\displaystyle=\lim_{n\to\infty}\mathds{E}^{\pi}\biggl{[}\sum_{t=1}^{n}\gamma^{t-1}c(S_{t},A_{t})\biggr{]}$
$\displaystyle=\mathds{E}^{\pi}\biggl{[}\lim_{n\to\infty}\sum_{t=1}^{n}\gamma^{t-1}c(S_{t},A_{t})\biggr{]}=V^{\pi}(s)$

where the second equality follows from the monotone convergence theorem when
$c_{\min}\geq 0$ (the case of $c_{\min}<0$ follows from a similar argument by
shifting $\\{V^{\pi}_{n}\\}_{n\geq 0}$ to make it non-negative and monotone).

##  Appendix B Proof of Lemma 4

Consider

$\displaystyle\hskip-20.00003pt\bigl{\|}V^{\pi}-\hat{V}^{\hat{\pi}}\bigr{\|}_{w}=\bigl{\|}\mathscr{B}^{\pi}V^{\pi}-\hat{\mathscr{B}}^{\hat{\pi}}\hat{V}^{\hat{\pi}}\bigr{\|}_{w}$
$\displaystyle\leq\bigl{\|}\mathscr{B}^{\pi}V^{\pi}-\hat{\mathscr{B}}^{\hat{\pi}}V^{\pi}\bigr{\|}_{w}+\bigl{\|}\hat{\mathscr{B}}^{\hat{\pi}}V^{\pi}-\hat{\mathscr{B}}^{\hat{\pi}}\hat{V}^{\hat{\pi}}\bigr{\|}_{w}$
$\displaystyle\leq\mathscr{D}^{\pi,\hat{\pi}}V^{\pi}+\gamma\kappa\bigl{\|}V^{\pi}-\hat{V}^{\hat{\pi}}\bigr{\|}_{w}$
(32)

where the first inequality follows from triangle inequality, and the last from
the definition of Bellman mismatch functional and Lemma II-C as
$\hat{\pi}\in\hat{\Pi}_{S}(\kappa,w)$. Re-arranging the terms in (32), we
obtain

$\bigl{\|}V^{\pi}-\hat{V}^{\hat{\pi}}\bigr{\|}_{w}\leq\frac{1}{1-\gamma\kappa}\mathscr{D}^{\pi,\hat{\pi}}V^{\pi}.$
(33)

Next consider

$\displaystyle\hskip-20.00003pt\bigl{\|}V^{\pi}-\hat{V}^{\hat{\pi}}\bigr{\|}_{w}=\bigl{\|}\mathscr{B}^{\pi}V^{\pi}-\hat{\mathscr{B}}^{\hat{\pi}}\hat{V}^{\hat{\pi}}\bigr{\|}_{w}$
$\displaystyle\leq\bigl{\|}\mathscr{B}^{\pi}V^{\pi}-\mathscr{B}^{\pi}\hat{V}^{\hat{\pi}}\bigr{\|}_{w}+\bigl{\|}\mathscr{B}^{\pi}\hat{V}^{\hat{\pi}}-\hat{\mathscr{B}}^{\hat{\pi}}\hat{V}^{\hat{\pi}}\bigr{\|}_{w}$
$\displaystyle\leq\gamma\kappa\bigl{\|}V^{\pi}-\hat{V}^{\hat{\pi}}\bigr{\|}_{w}+\mathscr{D}^{\pi,\hat{\pi}}\hat{V}^{\hat{\pi}}$
(34)

where the first inequality follows from triangle inequality, and the last from
Lemma II-C as $\pi\in\Pi_{S}(\kappa,w)$ and from the definition of Bellman
mismatch functional. Re-arranging the terms in (34), we obtain

$\bigl{\|}V^{\pi}-\hat{V}^{\hat{\pi}}\bigr{\|}_{w}\leq\frac{1}{1-\gamma\kappa}\mathscr{D}^{\pi,\hat{\pi}}\hat{V}^{\hat{\pi}}.$
(35)

Combining (33) and (35) establishes (9).

##  Appendix C Proof of Lemma 4

###  C-A Proof of part 1

For the bound in terms of $\hat{V}^{\star}$, we have

$\displaystyle\|V^{\star}-\hat{V}^{\star}\|_{w}$
$\displaystyle=\|\mathscr{B}^{\pi^{\star}}V^{\star}-\hat{\mathscr{B}}^{\hat{\pi}^{\star}}\hat{V}^{\star}\|_{w}$
$\displaystyle\leq\|\mathscr{B}^{\pi^{\star}}V^{\star}-\mathscr{B}^{\pi^{\star}}\hat{V}^{\star}\|_{w}+\|\mathscr{B}^{\pi^{\star}}\hat{V}^{\star}-\hat{\mathscr{B}}^{\hat{\pi}^{\star}}\hat{V}^{\star}\|_{w}$
$\displaystyle\leq\gamma\kappa\|V^{\star}-\hat{V}^{\star}\|_{w}+\mathscr{D}^{\pi^{\star},\hat{\pi}^{\star}}\hat{V}^{\star}$
(36)

where the last inequality holds from Lemma II-C as
$\pi^{\star}\in\Pi_{S}(\kappa,w)$ and from the definition of Bellman mismatch
functional. Re-arranging the terms in (36), we obtain

$\|V^{\star}-\hat{V}^{\star}\|_{w}\leq\frac{1}{(1-\gamma\kappa)}\mathscr{D}^{\pi^{\star},\hat{\pi}^{\star}}\hat{V}^{\star}.$
(37)

For the bound in terms of $V^{\star}$, we have

$\displaystyle\|V^{\star}-\hat{V}^{\star}\|_{w}$
$\displaystyle=\|\mathscr{B}^{\pi^{\star}}V^{\star}-\hat{\mathscr{B}}^{\hat{\pi}^{\star}}\hat{V}^{\star}\|_{w}$
$\displaystyle\leq\|\mathscr{B}^{\pi^{\star}}V^{\star}-\hat{\mathscr{B}}^{\hat{\pi}^{\star}}V^{\star}\|_{w}+\|\hat{\mathscr{B}}^{\hat{\pi}^{\star}}V^{\star}-\hat{\mathscr{B}}^{\hat{\pi}^{\star}}\hat{V}^{\star}\|_{w}$
$\displaystyle\leq\mathscr{D}^{\pi^{\star},\hat{\pi}^{\star}}V^{\star}+\gamma\kappa\|V^{\star}-\hat{V}^{\star}\|_{w}$
(38)

where the last inequality holds from the definition of Bellman mismatch
functional and Lemma II-C as $\hat{\pi}^{\star}\in\hat{\Pi}_{S}(\kappa,w)$.
Re-arranging the terms in (38), we obtain

$\|V^{\star}-\hat{V}^{\star}\|_{w}\leq\frac{1}{(1-\gamma\kappa)}\mathscr{D}^{\pi^{\star},\hat{\pi}^{\star}}V^{\star}.$
(39)

###  C-B Proof of part 2

If $\mathscr{B}^{\star}$ were a $\|\cdot\|_{w}$-norm contraction, then we
could have used the exact same proof argument as in proof of part 1. However,
we have not established that $\mathscr{B}^{\star}$ is a $\|\cdot\|_{w}$-norm
contraction under Assumptions 1, 2 and 3. So, we need a different proof
argument. We use the shorthand notation $[v]_{w}$ to denote
$\sup_{s\in\mathcal{S}}v(s)/w(s)$ (note that there is no absolute value sign
around $v(s)$).

Let $\mu^{\star}\in\mathcal{G}(\hat{V}^{\star})\cap\Pi_{S}(\kappa,w)$. Now,
consider

$\displaystyle[V^{\star}-\hat{V}^{\star}]_{w}$
$\displaystyle=[\mathscr{B}^{\star}V^{\star}-\hat{\mathscr{B}}^{\star}\hat{V}^{\star}]_{w}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}[\mathscr{B}^{\star}V^{\star}-\mathscr{B}^{\star}\hat{V}^{\star}]_{w}+[\mathscr{B}^{\star}\hat{V}^{\star}-\hat{\mathscr{B}}^{\star}\hat{V}^{\star}]_{w}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}[\mathscr{B}^{\mu^{\star}}V^{\star}-\mathscr{B}^{\mu^{\star}}\hat{V}^{\star}]_{w}+\mathscr{D}^{\star}\hat{V}^{\star}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\gamma\kappa\|V^{\star}-\hat{V}^{\star}\|_{w}+\mathscr{D}^{\star}\hat{V}^{\star}$
(40)

where $(a)$ follows from the definition supremum, $(b)$ follows from
$\mu^{\star}\in\mathcal{G}(\hat{V}^{\star})$ and the fact that
$\mathscr{B}^{\star}V^{\star}\leq\mathscr{B}^{\mu^{\star}}V^{\star}$ , and
$(c)$ follows from contraction of the Bellman operator
$\mathscr{B}^{\mu^{\star}}$ (since $\mu^{\star}\in\Pi_{S}(\kappa,w)$).

Now we consider the inequality in the other direction.

$\displaystyle[\hat{V}^{\star}-V^{\star}]_{w}$
$\displaystyle=[\hat{\mathscr{B}}^{\star}\hat{V}^{\star}-\mathscr{B}^{\star}V^{\star}]_{w}$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}[\hat{\mathscr{B}}^{\star}\hat{V}^{\star}-\mathscr{B}^{\star}\hat{V}^{\star}]_{w}+[\mathscr{B}^{\star}\hat{V}^{\star}-\mathscr{B}^{\star}V^{\star}]_{w}$
$\displaystyle\stackrel{{\scriptstyle(e)}}{{\leq}}\mathscr{D}^{\star}\hat{V}^{\star}+[\mathscr{B}^{\pi^{\star}}\hat{V}^{\star}-\mathscr{B}^{\pi^{\star}}V^{\star}]_{w}$
$\displaystyle\stackrel{{\scriptstyle(f)}}{{\leq}}\mathscr{D}^{\star}\hat{V}^{\star}+\gamma\kappa\|\hat{V}^{\star}-V^{\star}\|_{w}$
(41)

where $(d)$ follows from the definition of supremum, $(e)$ follows from
$\pi^{\star}\in\mathcal{G}(V^{\star})$ and the fact that
${\mathscr{B}}^{\star}\hat{V}^{\star}\leq\mathscr{B}^{\pi^{\star}}\hat{V}^{\star}$,
and $(f)$ follows from contraction of the Bellman operator
$\mathscr{B}^{\pi^{\star}}$ (since $\pi^{\star}\in\Pi_{S}(\kappa,w)$).

Combining (40) and (41) and rearranging terms, we get (12).

###  C-C Proof of part 3

The proof argument is similar to that of part 2. Consider

$\displaystyle[V^{\star}-\hat{V}^{\star}]_{w}$
$\displaystyle=[\mathscr{B}^{\star}V^{\star}-\hat{\mathscr{B}}^{\star}\hat{V}^{\star}]_{w}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}[\mathscr{B}^{\star}V^{\star}-\hat{\mathscr{B}}^{\star}V^{\star}]_{w}+[\hat{\mathscr{B}}^{\star}V^{\star}-\hat{\mathscr{B}}^{\star}\hat{V}^{\star}]_{w}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\mathscr{D}^{\star}V^{\star}+[\hat{\mathscr{B}}^{\hat{\pi}^{\star}}V^{\star}-\hat{\mathscr{B}}^{\hat{\pi}^{\star}}\hat{V}^{\star}]_{w}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\mathscr{D}^{\star}V^{\star}+\gamma\kappa\|V^{\star}-\hat{V}^{\star}\|_{w}$
(42)

where $(a)$ follows from the definition of supremum, $(b)$ follows the
definition of $\hat{\pi}^{\star}$ and the fact that
$\hat{\mathscr{B}}^{\star}V^{\star}\leq\hat{\mathscr{B}}^{\hat{\pi}^{\star}}V^{\star}$,
and $(c)$ follows from contraction of the Bellman operator
$\hat{\mathscr{B}}^{\hat{\pi}^{\star}}$.

Let
$\hat{\mu}^{\star}\in\hat{\mathcal{G}}(V^{\star})\cap\hat{\Pi}_{S}(\kappa,w)$.
Now, we consider the inequality in the other direction.

$\displaystyle[\hat{V}^{\star}-V^{\star}]_{w}$
$\displaystyle=[\hat{\mathscr{B}}^{\star}\hat{V}^{\star}-\mathscr{B}^{\star}V^{\star}]_{w}$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}[\hat{\mathscr{B}}^{\star}\hat{V}^{\star}-\hat{\mathscr{B}}^{\star}V^{\star}]_{w}+[\hat{\mathscr{B}}^{\star}V^{\star}-\mathscr{B}^{\star}V^{\star}]_{w}$
$\displaystyle\stackrel{{\scriptstyle(e)}}{{\leq}}[\hat{\mathscr{B}}^{\hat{\mu}^{\star}}\hat{V}^{\star}-\hat{\mathscr{B}}^{\hat{\mu}^{\star}}V^{\star}]_{w}+\mathscr{D}^{\star}V^{\star}$
$\displaystyle\stackrel{{\scriptstyle(f)}}{{\leq}}\gamma\kappa\|\hat{V}^{\star}-V^{\star}\|_{w}+\mathscr{D}^{\star}V^{\star}$
(43)

where $(d)$ follows from the definition of supremum, $(e)$ follows the
definition of $\hat{\mu}^{\star}$ and the fact that
$\hat{\mathscr{B}}^{\star}\hat{V}^{\star}\leq\hat{\mathscr{B}}^{\hat{\mu}^{\star}}\hat{V}^{\star}$,
and $(f)$ follows from contraction of the Bellman operator
$\hat{\mathscr{B}}^{\hat{\mu}^{\star}}$.

Combining (42) and (43) and rearranging terms, we get (13).

##  Appendix D Proof of Theorem III-B

We prove each part separately.

###  D-A Proof of part 1

For the bound in terms of $\hat{V}^{\star}$, by triangle inequality, we have

$\bigl{\|}V^{\hat{\pi}^{\star}}-V^{\star}\bigr{\|}_{w}\leq\bigl{\|}V^{\hat{\pi}^{\star}}-\hat{V}^{\star}\bigr{\|}_{w}+\bigl{\|}\hat{V}^{\star}-V^{\star}\bigr{\|}_{w}$
(44)

Recall that $\hat{V}^{\star}=\hat{V}^{\hat{\pi}^{\star}}$. Since
$\hat{\pi}^{\star}\in\Pi_{S}(\kappa,w)\cap\hat{\Pi}_{S}(\kappa,w)$, we can use
Lemma 4 to bound the first term of (44) by

$\displaystyle\bigl{\|}V^{\hat{\pi}^{\star}}-\hat{V}^{\star}\bigr{\|}_{w}$
$\displaystyle\leq\frac{1}{1-\gamma\kappa}\mathscr{D}^{\hat{\pi}^{\star},\hat{\pi}^{\star}}\hat{V}^{\hat{\pi}^{\star}}=\frac{1}{1-\gamma\kappa}\mathscr{D}^{\hat{\pi}^{\star}}\hat{V}^{\hat{\pi}^{\star}}$
$\displaystyle=\frac{1}{1-\gamma\kappa}\mathscr{D}^{\hat{\pi}^{\star}}\hat{V}^{\star}.$
(45)

We can bound the second term in (44) using Lemma 4, part 1 by

$\|\hat{V}^{\star}-V^{\star}\|_{w}\leq\frac{1}{(1-\gamma\kappa)}\mathscr{D}^{\pi^{\star},\hat{\pi}^{\star}}\hat{V}^{\star}.$
(46)

We obtain the result by combining (D-A) and (46).

For the bound in terms of $V^{\star}$, we can write

$\displaystyle\hskip-20.00003pt\bigl{\|}V^{\hat{\pi}^{\star}}-V^{\star}\bigr{\|}_{w}=\bigl{\|}\mathscr{B}^{\hat{\pi}^{\star}}V^{\hat{\pi}^{\star}}-\mathscr{B}^{\star}V^{\star}\bigr{\|}_{w}$
$\displaystyle\leq\bigl{\|}\mathscr{B}^{\hat{\pi}^{\star}}V^{\hat{\pi}^{\star}}-\mathscr{B}^{\hat{\pi}^{\star}}V^{\star}\bigr{\|}_{w}+\bigl{\|}\mathscr{B}^{\hat{\pi}^{\star}}V^{\star}-\hat{\mathscr{B}}^{\hat{\pi}^{\star}}{V^{\star}}\bigr{\|}_{w}$
$\displaystyle\quad+\bigl{\|}\hat{\mathscr{B}}^{\hat{\pi}^{\star}}V^{\star}-\hat{\mathscr{B}}^{\hat{\pi}^{\star}}\hat{V}^{\star}\bigr{\|}_{w}+\bigl{\|}\hat{\mathscr{B}}^{\hat{\pi}^{\star}}\hat{V}^{\star}-\mathscr{B}^{\star}V^{\star}\bigr{\|}_{w}$
$\displaystyle\leq\gamma\kappa\bigl{\|}V^{\hat{\pi}^{\star}}-V^{\star}\bigr{\|}_{w}+\mathscr{D}^{\hat{\pi}^{\star}}V^{\star}$
$\displaystyle\quad+\gamma\kappa\bigl{\|}V^{\star}-\hat{V}^{\star}\bigr{\|}_{w}+\bigl{\|}\hat{V}^{\star}-V^{\star}\bigr{\|}_{w}$
(47)

where the first inequality holds from triangle inequality and the last from
the definition of Bellman mismatch functional and from Lemma II-C as
$\hat{\pi}^{\star}\in\Pi_{S}(\kappa,w)\cap\hat{\Pi}_{S}(\kappa,w)$. Re-
arranging the terms in (47), we obtain

$\displaystyle\bigl{\|}V^{\hat{\pi}^{\star}}-V^{\star}\bigr{\|}_{w}\leq\frac{1}{1-\gamma\kappa}\bigl{[}\mathscr{D}^{\hat{\pi}^{\star}}V^{\star}+(1+\gamma\kappa)\bigl{\|}\hat{V}^{\star}-V^{\star}\bigr{\|}_{w}\bigr{]}.$
(48)

We use Lemma 4, part 1, to bound the last term of (48) by

$\|\hat{V}^{\star}-V^{\star}\|_{w}\leq\frac{1}{(1-\gamma\kappa)}\mathscr{D}^{\pi^{\star},\hat{\pi}^{\star}}V^{\star}.$
(49)

We obtain the result by combining (48) and (49).

###  D-B Proof of part 2

Since Assumption 3 holds, we can use Lemma 4 part 2 to bound the second term
of (44) by

$\bigl{\|}\hat{V}^{\star}-V^{\star}\bigr{\|}_{w}\leq\frac{1}{1-\gamma\kappa}\mathscr{D}^{\star}\hat{V}^{\star}.$
(50)

Combining (D-A) and (50) completes the proof.

###  D-C Proof of part 3

Since Assumption 4 holds, we can use Lemma 4 part 3 to bound the last term of
(48) by

$\bigl{\|}\hat{V}^{\star}-V^{\star}\bigr{\|}_{w}\leq\frac{1}{1-\gamma\kappa}\mathscr{D}^{\star}V^{\star}.$
(51)

Combining (48) and (51) completes the proof.

##  Appendix E Proof of Lemma III-D

Assumption 5 implies that, for each $a\in\mathcal{A}$,

$\int_{\mathcal{S}}w(s^{\prime})P(ds^{\prime}\mid s,a)\leq\kappa
w(s),\quad\forall s\in\mathcal{S}.$ (52)

For any $v\in\mathcal{V}_{w}$ such that $\mathcal{G}(v)$ is nonempty, let
$\pi_{v}$ denote a policy in $\mathcal{G}(v)$. We will first show that
$\pi_{v}\in\Pi_{S}(\kappa,w)$ and then use this to prove Assumption 3.

For policy $\pi_{v}$, we have that

$\displaystyle\int_{\mathcal{S}}w(s^{\prime})P_{\pi_{v}}(ds^{\prime}|s)=$
$\displaystyle\int_{\mathcal{S}}\int_{\mathcal{A}}w(s^{\prime})\pi_{v}(da|s)P(ds^{\prime}|s,a)$
$\displaystyle=$
$\displaystyle\int_{\mathcal{A}}\int_{\mathcal{S}}w(s^{\prime})P(ds^{\prime}|s,a)\pi_{v}(da|s)$
$\displaystyle\leq$ $\displaystyle\int_{\mathcal{A}}\kappa
w(s)\pi_{v}(da|s)=\kappa w(s),\quad\forall s\in\mathcal{S}.$

Thus, $\pi_{v}$ satisfies (4).

Next, from the definition of the Bellman operator, we have

$\displaystyle c_{\pi_{v}}(s)=$
$\displaystyle[\mathscr{B}^{\pi_{v}}v](s)-{\gamma}\int_{\mathcal{A}}\pi_{v}(da\mid
s)\int_{\mathcal{S}}v(s^{\prime})P(ds^{\prime}\mid s,a)$ $\displaystyle\leq$
$\displaystyle[\mathscr{B}^{\pi_{v}}v](s)+{\gamma}|c_{\min}/(1-\gamma)|,$

where the inequality above is due to the fact that
$-v(s)\leq|c_{\min}/(1-\gamma)|$ for all $v\in\mathcal{V}_{w}$. Therefore,

$\displaystyle\|c_{\pi_{v}}\|_{w}=$
$\displaystyle\sup_{s\in\mathcal{S}}\frac{|c_{\pi_{v}}(s)|}{w(s)}$
$\displaystyle\leq$
$\displaystyle\sup_{s\in\mathcal{S}}\frac{[\mathscr{B}^{\pi_{v}}v](s)+{\gamma}|c_{\min}/(1-\gamma)|}{w(s)}$
$\displaystyle\leq$
$\displaystyle\|\mathscr{B}^{\pi_{v}}v\|_{w}+{\gamma}|c_{\min}/(1-\gamma)|$
$\displaystyle=$
$\displaystyle\|\mathscr{B}^{\star}v\|_{w}+{\gamma}|c_{\min}/(1-\gamma)|<\infty.$

Thus, $\pi_{v}$ satisfies (3). Hence, $\pi_{v}\in\Pi_{S}(\kappa,w)$.

With $v=\hat{V}^{\star}$ in the above argument, it follows that
$\pi_{\hat{V}^{\star}}\in\Pi_{S}(\kappa,w)$. Hence, Assumption 3 is satisfied.

Similarly, for any $v\in\mathcal{V}_{w}$, let $\hat{\pi}_{v}$ denote a policy
in $\hat{\mathcal{G}}(v)$. Using arguments identical to the ones used above,
we can show that $\hat{\pi}_{v}\in\hat{\Pi}_{S}(\kappa,w)$. Setting
$v=V^{\star}$ then implies that
$\hat{\pi}_{V^{\star}}\in\hat{\Pi}_{S}(\kappa,w)$. Hence, Assumption 4 is
satisfied.

##  Appendix F Proof of Lemma III-D

By definition,
$\mathscr{D}^{\max}v=\sup_{a\in\mathcal{A}}\mathscr{D}^{\pi_{a}}v$. Since, by
Assumption 5, $\pi_{a}\in\Pi_{S}(\kappa,w)\cap\hat{\Pi}_{S}(\kappa,w)$ for all
$a\in\mathcal{A}$, it follows that

$\mathscr{D}^{\max}v\leq\sup_{\pi\in\Pi_{S}(\kappa,w)\cap\hat{\Pi}_{S}(\kappa,w)}\mathscr{D}^{\pi}v.$
(53)

Define

$\Xi^{(s,a)}v=c(s,a)-\hat{c}(s,a)\\\
+\gamma\int_{\mathcal{S}}v(s^{\prime})P(ds^{\prime}|s,a)-\gamma\int_{\mathcal{S}}v(s^{\prime})\hat{P}(ds^{\prime}|s,a).$

Then, we have that

$\mathscr{D}^{\max}v=\sup_{a\in\mathcal{A}}\|\mathscr{B}^{\pi_{a}}v-\hat{\mathscr{B}}^{\pi_{a}}v\|_{w}=\sup_{a\in\mathcal{A}}\sup_{s\in\mathcal{S}}\frac{\bigl{|}\Xi^{(s,a)}v\bigr{|}}{w(s)}$

and for every $\pi\in\Pi_{S}(\kappa,w)\cap\hat{\Pi}_{S}(\kappa,w)$,

$[\mathscr{B}^{\pi}v](s)-[\hat{\mathscr{B}}^{\pi}v](s)=\int_{\mathcal{A}}\pi(da\mid
s)\Xi^{(s,a)}v$

Therefore,

$\displaystyle\mathscr{D}^{\pi}v$
$\displaystyle=\sup_{s\in\mathcal{S}}\frac{\bigl{|}\int_{\mathcal{A}}\pi(da\mid
s)\Xi^{(s,a)}v\bigr{|}}{w(s)}$
$\displaystyle\leq\sup_{s\in\mathcal{S}}\sup_{a\in\mathcal{A}}\frac{|\Xi^{(s,a)}v|}{w(s)}=\mathscr{D}^{\max}v.$
(54)

Combining (53) and (54), we get the first part of (15)

For the second part, note that for any set $\mathcal{X}$,
$|\inf_{x\in\mathcal{X}}f(x)-\inf_{x\in\mathcal{X}}g(x)|\leq\sup_{x\in\mathcal{X}}|f(x)-g(x)|$.
Therefore,

$|[\mathscr{B}^{\star}v](s)-[\hat{\mathscr{B}}^{\star}v](s)|\leq\sup_{a\in\mathcal{A}}|\Xi^{(s,a)}v|.$

Using the above inequality in the definition of $\mathscr{D}^{\star}$, we get

$\displaystyle\mathscr{D}^{\star}v$
$\displaystyle=\sup_{s\in\mathcal{S}}\frac{\bigl{|}[\mathscr{B}^{\star}v](s)-[\hat{\mathscr{B}}^{\star}v](s)\bigr{|}}{w(s)}$
$\displaystyle\leq\sup_{s\in\mathcal{S}}\frac{\sup_{a\in\mathcal{A}}\bigl{|}\Xi^{(s,a)}v\bigr{|}}{w(s)}=\mathscr{D}^{\max}v,$
(55)

which establishes the second part of (15).

##  Appendix G Proof of Theorem III-E

###  G-A Proof of part 1

The bound in terms of $\hat{V}^{\star}$ follows from Theorem III-B, part 1
(the bound in terms of $\hat{V}^{\star}$) and Lemma III-E, part 3.

For the bound in terms of $V^{\star}$, we can use Lemma III-E, part 3 and
Theorem III-B, part 1 to write

$\displaystyle\hskip-10.00002pt\bigl{\|}V^{\hat{\pi}^{\star}}-V^{\star}\bigr{\|}_{w}=\frac{1}{\alpha_{1}}\bigl{\|}V^{\hat{\pi}^{\star}}_{\boldsymbol{\alpha}}-V^{\star}_{\boldsymbol{\alpha}}\bigr{\|}_{w}$
$\displaystyle\leq\frac{1}{\alpha_{1}(1-\gamma\kappa)}\mathscr{D}^{\hat{\pi}^{\star}}_{\boldsymbol{\alpha}}V^{\star}_{\boldsymbol{\alpha}}+\frac{(1+\gamma\kappa)}{\alpha_{1}(1-\gamma\kappa)^{2}}\mathscr{D}^{\pi^{\star},\hat{\pi}^{\star}}V_{\boldsymbol{\alpha}}^{\star}$
$\displaystyle=\frac{1}{\alpha_{1}(1-\gamma\kappa)}\mathscr{D}^{\hat{\pi}^{\star}}_{\boldsymbol{\alpha}}(\alpha_{1}V^{\star})+\frac{(1+\gamma\kappa)}{\alpha_{1}(1-\gamma\kappa)^{2}}\mathscr{D}^{\pi^{\star},\hat{\pi}^{\star}}(\alpha_{1}V^{\star}),$
(56)

where, in the last step, we used the fact that part 2 of Lemma III-E implies
that

$\mathscr{D}^{\hat{\pi}^{\star}}_{\boldsymbol{\alpha}}V^{\star}_{\boldsymbol{\alpha}}=\mathscr{D}^{\hat{\pi}^{\star}}_{\boldsymbol{\alpha}}(\alpha_{1}V^{\star})\quad\text{and}\quad\mathscr{D}_{\boldsymbol{\alpha}}^{\pi^{\star},\hat{\pi}^{\star}}V^{\star}_{\boldsymbol{\alpha}}=\mathscr{D}_{\boldsymbol{\alpha}}^{\pi^{\star},\hat{\pi}^{\star}}(\alpha_{1}V^{\star}).$

###  G-B Proof of part 2

Assumption 6 is the same as Assumption 3 for model
$\mathcal{M}_{\boldsymbol{\alpha}}$. Hence, the result follows immediately
from Theorem III-B, part 2 and Lemma III-E, part 3.

###  G-C Proof of part 3

Assumption 7 is the same as Assumption 4 for model
$\mathcal{M}_{\boldsymbol{\alpha}}$. Hence, the result follows from Theorem
III-B, part 3 together with Lemma III-E, part 3 and the fact that part 2 of
Lemma III-E implies

$\mathscr{D}^{\star}_{\boldsymbol{\alpha}}V^{\star}_{\boldsymbol{\alpha}}=\mathscr{D}^{\star}_{\boldsymbol{\alpha}}(\alpha_{1}V^{\star}).$

##  Appendix H Proof of Proposition 8

When $\alpha_{1}=1$, Assumptions 3 and 6 are equivalent. To apply Theorem
III-E, we consider $\alpha_{1}=1$ and an arbitrary $\alpha_{2}$. Then the
corresponding Bellman updates for $\hat{V}^{\star}(s)$ can be calculated as

$\displaystyle\mathscr{B}^{\star}_{(1,\alpha_{2})}\hat{V}^{\star}(s)$
$\displaystyle=s^{\intercal}\left(Q+\gamma
A^{\intercal}\hat{P}A-\gamma^{2}A^{\intercal}\hat{P}B(R+\gamma
B^{\intercal}\hat{P}B)^{-1}B^{\intercal}\hat{P}A\right)s$
$\displaystyle\quad+\gamma(\hat{q}+\operatorname{Tr}(\Sigma_{W}\hat{P}))+\alpha_{2},$

and

$\displaystyle\hat{\mathscr{B}}^{\star}\hat{V}^{\star}(s)$
$\displaystyle=\hat{V}^{\star}(s)=s^{\intercal}\hat{P}s+\hat{q}.$
$\displaystyle=s^{\intercal}\hat{P}s+\gamma(\hat{q}+\operatorname{Tr}(\hat{\Sigma}_{W}\hat{P}))$

where the last term uses the fact that
$\hat{q}=\gamma\operatorname{Tr}(\hat{\Sigma}_{W}\hat{P})/(1-\gamma)$.

Therefore, we have

$\displaystyle|\mathscr{B}^{\star}_{(1,\alpha_{2})}\hat{V}^{\star}(s)-\hat{\mathscr{B}}^{\star}\hat{V}^{\star}(s)|$
$\displaystyle\quad=\left|s^{\intercal}D^{\star}s+\gamma\operatorname{Tr}((\Sigma_{W}-\hat{\Sigma}_{W})\hat{P})+\alpha_{2}\right|,$

where $D^{\star}$ is given by (22).

Note that
$\hat{\pi}^{\star}(s)=-\hat{K}^{\star}s=-\gamma(\hat{R}+\gamma\hat{B}^{\intercal}\hat{P}\hat{B})^{-1}\hat{B}^{\intercal}\hat{P}\hat{A}s$.
As a result, for any $\alpha_{2}$,
$\mathscr{B}^{\hat{\pi}^{\star}}_{(1,\alpha_{2})}\hat{V}^{\star}(s)$ is given
by

$\displaystyle\mathscr{B}^{\hat{\pi}^{\star}}_{(1,\alpha_{2})}\hat{V}^{\star}(s)$
$\displaystyle=s^{\intercal}\big{(}Q+(\hat{K}^{\star})^{\intercal}R\hat{K}^{\star}+\gamma
A_{\hat{K}^{\star}}^{\intercal}\hat{P}A_{\hat{K}^{\star}}\big{)}s$
$\displaystyle\quad+\gamma(\hat{q}+\operatorname{Tr}(\Sigma_{W}\hat{P}))+\alpha_{2},$

and
$\hat{\mathscr{B}}^{\hat{\pi}^{\star}}\hat{V}^{\star}(s)=\hat{\mathscr{B}}^{\star}\hat{V}^{\star}(s)=\hat{V}^{\star}(s)$.
Therefore, we have

$\displaystyle|\mathscr{B}^{\hat{\pi}^{\star}}_{(1,\alpha_{2})}\hat{V}^{\star}(s)-\hat{\mathscr{B}}^{\hat{\pi}^{\star}}\hat{V}^{\star}(s)|$
$\displaystyle\quad=\left|s^{\intercal}D^{\hat{\pi}^{\star}}s+\gamma\operatorname{Tr}((\Sigma_{W}-\hat{\Sigma}_{W})\hat{P})+\alpha_{2}\right|,$

where $D^{\hat{\pi}^{\star}}$ is given by (23). Then, the Bellman mismatches
functionals of Section III-E for $\hat{V}$ with $(1,\alpha_{2})$ can be
calculated as follows:

$\displaystyle\mathscr{D}^{\hat{\pi}^{\star}}_{(1,\alpha_{2})}\hat{V}^{\star}$
$\displaystyle=\sup_{s\in\mathcal{S}}\frac{\left|s^{\intercal}D^{\hat{\pi}^{\star}}s+d_{\Sigma}+\alpha_{2}\right|}{w(s)},$
$\displaystyle\mathscr{D}^{\star}_{(1,\alpha_{2})}\hat{V}^{\star}$
$\displaystyle=\sup_{s\in\mathcal{S}}\frac{\left|s^{\intercal}D^{\star}s+d_{\Sigma}+\alpha_{2}\right|}{w(s)},$

where $d_{\Sigma}$ is given by (25).

Eq. (21) then then follows from Theorem III-E part 2 by observing that for any
symmetric matrix $D$

$\sup_{s\in\mathcal{S}}\frac{\left|s^{\intercal}Ds+d_{\Sigma}+\alpha_{2}\right|}{1+\ell
s^{\intercal}s}\leq\max\bigg{\\{}\frac{\rho(D)}{\ell},|d_{\Sigma}+\alpha_{2}|\biggr{\\}}.$

##  Appendix I Proof of Lemma V-C

###  I-A Proof of part 1

For any $(\alpha_{1},\alpha_{2})$ with $\alpha_{2}>0$, we have

$\displaystyle\mathscr{D}^{\pi,\hat{\pi}}_{\boldsymbol{\alpha}}v=$
$\displaystyle\sup_{s\in\mathcal{S}}\frac{\bigl{|}\mathscr{B}_{\boldsymbol{\alpha}}^{\pi}v(s)-\hat{\mathscr{B}}^{\hat{\pi}}v(s)\bigr{|}}{w(s)}$
$\displaystyle\leq$
$\displaystyle\sup_{s\in\mathcal{S}}\frac{\bigl{|}\alpha_{1}c_{\pi}(s)+\alpha_{2}-\hat{c}_{\hat{\pi}}(s)\bigr{|}}{w(s)}$
$\displaystyle+\gamma\sup_{s\in\mathcal{S}}\frac{\biggl{|}\int_{\mathcal{S}}v(s^{\prime})\Bigl{[}P_{\pi}\bigl{(}ds^{\prime}|s)\bigr{)}-\hat{P}_{\hat{\pi}}\bigl{(}ds^{\prime}|s)\bigr{)}\Bigr{]}\biggr{|}}{w(s)}$
$\displaystyle\leq$
$\displaystyle\varepsilon_{\boldsymbol{\alpha}}(\pi,\hat{\pi})$
$\displaystyle+\gamma\rho_{\mathfrak{F}}(v)\sup_{s\in\mathcal{S}}\frac{d_{\mathfrak{F}}\Bigl{(}P_{\pi}\bigl{(}\cdot|s\bigr{)},\hat{P}_{\hat{\pi}}\bigl{(}\cdot|s\bigr{)}\Bigr{)}}{w(s)}$
$\displaystyle=$
$\displaystyle\varepsilon_{\boldsymbol{\alpha}}(\pi,\hat{\pi})+\gamma\rho_{\mathfrak{F}}(v)\delta_{\mathfrak{F}}(\pi,\hat{\pi})$
(57)

###  I-B Proofs of part 2 and 3

Part 2 follows because
$\mathscr{D}^{\star}_{\boldsymbol{\alpha}}\hat{V}^{\star}=\mathscr{D}^{\mu^{\star},\hat{\pi}^{\star}}\hat{V}^{\star}$.
Similarly, part 3 follows because
$\mathscr{D}^{\star}_{\boldsymbol{\alpha}}(\alpha_{1}V^{\star})=\mathscr{D}^{\pi^{\star},\hat{\mu}^{\star}}(\alpha_{1}V^{\star})$.

###  I-C Proof of part 4

Define

$\Xi^{(s,a)}_{\boldsymbol{\alpha}}v=\alpha_{1}c(s,a)+\alpha_{2}-\hat{c}(s,a)\\\
+\gamma\int_{\mathcal{S}}v(s^{\prime})P(ds^{\prime}|s,a)-\gamma\int_{\mathcal{S}}v(s^{\prime})\hat{P}(ds^{\prime}|s,a).$

Then, we have

$\displaystyle\mathscr{D}_{\boldsymbol{\alpha}}^{\max}v$
$\displaystyle=\sup_{a\in\mathcal{A}}\|\mathscr{B}^{\pi_{a}}_{\boldsymbol{\alpha}}v-\hat{\mathscr{B}}^{\pi_{a}}v\|_{w}$
$\displaystyle=\sup_{(s,a)\in\mathcal{S}\times\mathcal{A}}\frac{\bigl{|}\Xi^{(s,a)}_{\boldsymbol{\alpha}}v\bigr{|}}{w(s)}$
$\displaystyle\leq\sup_{(s,a)\in\mathcal{S}\times\mathcal{A}}\frac{\bigl{|}\alpha_{1}c(s,a)+\alpha_{2}-\hat{c}(s,a)\bigr{|}}{w(s)}$
$\displaystyle\quad+\gamma\sup_{(s,a)\in\mathcal{S}\times\mathcal{A}}\frac{\bigl{|}\int_{\mathcal{S}}v(s^{\prime})[P(ds^{\prime}|s,a)-\hat{P}(ds^{\prime}|s,a)]\bigr{|}}{w(s)}$
$\displaystyle\leq\varepsilon_{\boldsymbol{\alpha}}^{\max}+\gamma\rho_{\mathfrak{F}}(v)\sup_{(s,a)\in\mathcal{S}\times\mathcal{A}}\frac{d_{\mathfrak{F}}\bigl{(}P(\cdot|s,a),\hat{P}(\cdot|s,a)\bigr{)}}{w(s)}$
$\displaystyle=\varepsilon_{\boldsymbol{\alpha}}^{\max}+\gamma\rho_{\mathfrak{F}}(v)\delta_{\mathfrak{F}}^{\max}.$
(58)

|  Berk Bozkurt (Student Member, IEEE) received his BSc degree in Electrical
and Electronics Engineering from Bilkent University, Ankara, Turkey, in 2021.
He is currently a MSc student in Electrical and Computer Engineering
Department at McGill University, Montreal, Canada. His research interests
include reinforcement learning, game theory, stochastic control and Markov
decision theory.
---|---
|  Aditya Mahajan (Senior Member, IEEE) is Professor of Electrical and
Computer Engineering at McGill University, Montreal, Canada. He received the
B.Tech degree in Electrical Engineering from the Indian Institute of
Technology, Kanpur, India in 2003 and the MS and PhD degrees in Electrical
Engineering and Computer Science from the University of Michigan, Ann Arbor,
USA in 2006 and 2008, respectively. He serves as Associate Editor of
Transactions on Automatic Control, Control Systems Letters, and Math. of
Control, Signal, and Systems.
---|---
|  Ashutosh Nayyar (Senior Member, IEEE) is an Associate Professor of
Electrical and Computer Engineering at the University of Southern California.
He received a M.S. degree in electrical engineering and computer science, a
M.S. degree in applied mathematics, and a Ph.D. degree in electrical
engineering and computer science from the University of Michigan, Ann Arbor,
MI, USA, in 2008, 2011, and 2011, respectively. His research interests are in
decentralized stochastic control, decentralized decision-making in sensing and
communication systems, reinforcement learning, game theory and mechanism
design.
---|---
|  Yi Ouyang received the B.S. degree in Electrical Engineering from the
National Taiwan University, Taipei, Taiwan in 2009, and the M.Sc and Ph.D. in
Electrical Engineering and Computer Science at the University of Michigan, in
2012 and 2015, respectively. He is currently a researcher at Preferred
Networks, Burlingame, CA. His research interests include reinforcement
learning, stochastic control, and stochastic dynamic games.
---|---