4 Model approximation

4.1 Motivation

Consider an MDP $\ALPHABET M = \langle \ALPHABET S, \ALPHABET A, P, c, T \rangle$. Suppose the components $\langle \ALPHABET S, \ALPHABET A, T \rangle$ are known exactly but the components $(P,c)$ are known approximately. Both $P = (P_1, \dots, P_T)$ and $c = (c_1, \dots, c_T)$ are assumed to be time varying. Consider the approximate MDP $\widehat {\ALPHABET M} = \langle \ALPHABET S, \ALPHABET A, \hat P, \hat c, T \rangle$. We will call $\ALPHABET M$ to be the true model and $\widehat {\ALPHABET M}$ to be the approximate model.

Let $\{V^\star_t\}_{t=1}^T$ and $\{\hat V^\star_t\}_{t =1}^T$ denote the optimal value functions of the true model $\ALPHABET M$ and the approximate model $\widehat {\ALPHABET M}$, respectively. Moreover, let $π^\star = (π^\star_1, \dots, π^\star_T)$ and $\hat π^\star = (\hat π^\star_1, \dots, \hat π^\star_T)$ be optimal policies for the true model $\ALPHABET M$ and the approximate model $\widehat {\ALPHABET M}$, respectively. We will use $\MODEL_t$ and $\hat \MODEL_t$ to denote the model operators in model $\ALPHABET M$ and $\widehat {\ALPHABET M}$.

We are interested in the following questions:

Policy error bounds: Given a policy $π = (π_1, \dots, π_T)$, what is the error if $\hat V^π_t$ is used as an approximation for $V^π_t$ (or equivalently, if $\hat Q^π_t$ is used as an approximation for $Q^π_t$)?
Value error bounds: What is the error if $\hat V^\star_t$ is used as an approximation for $V^\star_t$ (or equivalently, if $\hat Q^\star_t$ is used as an approximation for $Q^\star_t$)?
Model approximation error: What is the error if the policy $\hat π^\star$ is used instead of the optimal policy $π^\star$? Equivalently, how large is the gap between $(V^\star_t, Q^\star_t)$ and $(V^{\hat π^\star}_t, Q^{\hat π^\star}_t)$?

In this lecture, we will characterize these bounds in terms of the sup-norm: for any function $v \in \ALPHABET V$, $\NORM{v}_{∞} = \sup_{s \in \ALPHABET S} \ABS{v(s)}$. In the sequel, we use $\NORM{⋅}$ to denote $\NORM{⋅}_{∞}$ Later, we will revisit this problem to get more nuanced bounds.

4.2 Operator theoretic notation

We start with a notation to simplify how dynamic programs are written. Let $\ALPHABET M = \langle \ALPHABET S, \ALPHABET A, P, c, T\rangle$ denote a finite horizon MDP with state space $\ALPHABET S$, action space $\ALPHABET A$, dynamics $P = (P_1, \dots, P_T)$, and per-step cost $c = (c_1, \dots, c_T)$. For simplicity, we take $c_t \colon \ALPHABET S \times \ALPHABET A \to \reals$ and assume that there is no terminal cost.

We also use $\ALPHABET V$ to denote the space of value functions and $\ALPHABET Q$ to denote the space of action-value functions (for finite state space models, these are equivalent to $\reals^{\SIZE{S}}$ and $\reals^{\SIZE{S}\SIZE{A}}$).

4.2.1 Simple notation

Now we define the following operators. For simplicity, we write them for the case when state and action spaces are finite but the definitions are similar for general spaces.

For any policy $π \in Π$, define the policy Bellman operator $\BELLMAN^π_t \colon \ALPHABET V \to \ALPHABET V$ as follows: for any $v \in \ALPHABET V$, \[ [\BELLMAN^π_t v](s) = c_t(s, π(s)) + \sum_{s' \in \ALPHABET S} P_t(s'|s, π(s)) v(s'). \]
Define the optimality Bellman operator $\BELLMAN^\star_t \colon \ALPHABET V \to \ALPHABET V$ as follows: for any $v \in \ALPHABET V$, \[ [\BELLMAN^\star_t v](s) = \min_{a \in \ALPHABET A} \biggl\{ c_t(s, a) + \sum_{s' \in \ALPHABET S} P_t(s'|s, a) v(s') \biggr\}. \]

Then the dynamic programming decomposition can be written succinctly as: \[ V^\star_{T+1} = 0, \quad\text{and}\quad V^\star_t = \BELLMAN^\star_t V^\star_{t+1}, \quad \forall t \in \{T,\dots,1\}. \] Or, pictorially: \[ 0 ≡ V^\star_{T+1} \xrightarrow{\BELLMAN^\star} V^\star_T \xrightarrow{\BELLMAN^\star} V^\star_{T-1} \cdots \xrightarrow{\BELLMAN^\star} V^\star_1. \] Moreover, a policy $π^\star = (π^\star_1, \dots, π^\star_T) \in Π$ is optimal if and only if $\BELLMAN^\star_t V^\star_{t+1} = \BELLMAN^{π^\star}_t V^\star_{t+1}$ for all $t$.

Similarly, for a policy $π ∈ Π$, the policy evaluation dynamic program can be written as: \[ 0 ≡ V^π_{T+1} \xrightarrow{\BELLMAN^π} V^π_T \xrightarrow{\BELLMAN^π} V^π_{T-1} \cdots \xrightarrow{\BELLMAN^π} V^π_1. \]

4.2.2 More elaborate Notation

Sometimes we need to explicitly keep track of the action-value functions. So, we use a more elaborate notation (this is not a commonly used notation in the literature).

Define the operator $\MODEL_t \colon \ALPHABET V \to \ALPHABET Q$ as the model operator: for any $v \in \ALPHABET V$ \[ [\MODEL_t v](s,a) = c_t(s,a) + \sum_{s' \in \ALPHABET S} P_t(s'|s,a) v(s'). \]
For any $π \in Π$, define the Bellman target operator $\ALPHABET T^π$ as follows: for any $q \in \ALPHABET Q$, \[ [\ALPHABET T^π q](s) = q(s, π(s)) \quad\text{or for stochastic $π$ } [\ALPHABET T^π q](s) = \sum_{a \in \ALPHABET A} π(a | s)q(s, a). \]
Define the optimality Bellman target operator $\ALPHABET T^\star$ as follows: for any $q \in \ALPHABET Q$, \[ [\ALPHABET T^\star q](s) = \min_{a \in \ALPHABET A} q(s, a). \]
Define $\GREEDY \colon \ALPHABET Q \rightrightarrows Π$ as the greedy policy: given a $q \in \ALPHABET Q$, $π \in \GREEDY q$ means that $π(s) \in \arg\min_{a \in \ALPHABET A} q(s,a)$.

Observe that \[ \BELLMAN^π_t = \ALPHABET T^π \circ \MODEL_t, \quad \text{and}\quad \BELLMAN^\star_t = \ALPHABET T^\star \circ \MODEL_t. \]

Then, we can write the more elaborate dynamic programming decomposition as: \[ V^\star_{T+1} = 0, \quad\text{and}\quad Q^\star_t = \MODEL_t V^\star_{t+1}, \quad V^\star_t = \ALPHABET T^\star Q^\star_t, \quad \forall t \in \{T,\dots,1\}. \] Or, pictorially: \[ 0 ≡ V^\star_{T+1} \xrightarrow{\MODEL_T} Q^\star_T \xrightarrow{\ALPHABET T^\star} V^\star_T \xrightarrow{\MODEL_{T-1}} Q^\star_{T-1} \cdots \xrightarrow{\ALPHABET T^\star} V^\star_1. \] Moreover, a policy $π^\star = (π^\star_1, \dots, π^\star_T) \in Π$ is optimal if and only if $π^\star_t \in \GREEDY Q^\star_t$. An implication of this is that $\ALPHABET T^\star Q^\star_{t} = \ALPHABET T^{π^\star} Q^\star_t$.

Similarly, for a policy $π ∈ Π$, the policy evaluation dynamic program can be written as: \[ 0 ≡ V^π_{T+1} \xrightarrow{\MODEL_T} Q^π_T \xrightarrow{\ALPHABET T^π} V^π_T \xrightarrow{\MODEL_{T-1}} Q^π_{T-1} \cdots \xrightarrow{\ALPHABET T^π} V^π_1. \]

The advantage of this notation is that the model operator $\MODEL_t$ depends on the model; the target operators $\ALPHABET T^π$ and $\ALPHABET T^\star$ do not depend on the model. This makes it easy for us to describe model approximation.

4.2.3 Key property of the operators

Lemma 4.1 (Non-expansion properties) The operators $\MODEL_t$, $\hat \MODEL_t$, $\ALPHABET T^π$, and $\ALPHABET T^\star$ are non-expansions in the sup-norm. In particular:

For any $v, \hat v \in \ALPHABET V$, \[ \NORM{\MODEL_t v - \MODEL_t \hat v} \le \NORM{v - \hat v}. \] The same bound holds with $\MODEL_t$ replaced by $\hat \MODEL_t$.
For any $q, \hat q \in \ALPHABET Q$ and any (possibly randomized) policy $π$, \[ \NORM{\ALPHABET T^π q - \ALPHABET T^π \hat q} \le \NORM{q - \hat q}. \]
For any $q, \hat q \in \ALPHABET Q$, \[ \NORM{\ALPHABET T^\star q - \ALPHABET T^\star \hat q} \le \NORM{q - \hat q}. \]

Proof

For any $(s,a) \in \ALPHABET S \times \ALPHABET A$, \[ \ABS{[\MODEL_t v](s,a) - [\MODEL_t \hat v](s,a)} = \ABS{\sum_{s' \in \ALPHABET S} P_t(s'|s,a)[v(s') - \hat v(s')]} \le \NORM{v-\hat v}. \] Taking the supremum over $(s,a)$ gives the result.
For any $s \in \ALPHABET S$, \[ \ABS{[\ALPHABET T^π q](s) - [\ALPHABET T^π \hat q](s)} = \ABS{\sum_{a \in \ALPHABET A} π(a|s)[q(s,a)-\hat q(s,a)]} \le \NORM{q-\hat q}. \] Taking the supremum over $s$ gives the result.
Fix any $s \in \ALPHABET S$. Let $a^\star \in \arg\min_{a \in \ALPHABET A} q(s,a)$ and $\hat a^\star \in \arg\min_{a \in \ALPHABET A} \hat q(s,a)$. Then, \[\begin{align*} [\ALPHABET T^\star q](s) - [\ALPHABET T^\star \hat q](s) &= q(s,a^\star) - \hat q(s,\hat a^\star) \\ &\stackrel{(a)}\le q(s,\hat a^\star) - \hat q(s,\hat a^\star) \le \NORM{q-\hat q}, \end{align*}\] where $(a)$ uses that $a^\star$ minimizes $q(s,⋅)$. Reversing the roles of $q$ and $\hat q$ yields $[\ALPHABET T^\star \hat q](s) - [\ALPHABET T^\star q](s) \le \NORM{q-\hat q}$. Taking the supremum over $s$ completes the proof.

The previous notation separates the model-dependent part of dynamic programming from the policy/optimization part. We now use this separation to study what happens when the model-dependent part is perturbed.

4.3 Model approximation (Take 1)

4.3.1 Mismatch operator

Define the mismatch operator $\MISMATCH_t \colon \ALPHABET V \to \ALPHABET Q$ as follows: for any $v \in \ALPHABET V$, \[ \MISMATCH_t v = \MODEL_t v - \hat \MODEL_t v \]

Then, we have the following one-step estimate.

Lemma 4.2 (One step error propagation) Given $v_{t+1}, \hat v_{t+1} \in \ALPHABET V$, define $q_t = \MODEL_t v_{t+1}$ and $\hat q_t = \hat \MODEL_t \hat v_{t+1}$. Then, \[ \NORM{q_{t} - \hat q_t} \le \min\bigl\{ \NORM{\MISMATCH_t v_{t+1}}, \NORM{\MISMATCH_t \hat v_{t+1}} \bigr\} + \NORM{v_{t+1} - \hat v_{t+1}}. \]

Proof

Consider \[\begin{align*} \NORM{q_{t} - \hat q_t} &= \NORM{\MODEL_t v_{t+1} - \hat \MODEL_t \hat v_{t+1} } \\ &\stackrel{(a)}\le \NORM{\MODEL_t v_{t+1} - \hat \MODEL_t v_{t+1} } + \NORM{\hat \MODEL_t v_{t+1} - \hat \MODEL_t \hat v_{t+1} } \\ &\stackrel{(b)}\le \NORM{\MISMATCH_t v_{t+1}} + \NORM{v_{t+1} - \hat v_{t+1}}, \end{align*}\] where $(a)$ follows from the triangle inequality and $(b)$ uses the definition of $\MISMATCH_t$ and the non-expansion of $\hat \MODEL_t$ from Lemma 4.1.

The second inequality follows by reversing the roles of $v_{t+1}$ and $\hat v_{t+1}$: \[\begin{align*} \NORM{q_{t} - \hat q_t} &= \NORM{\MODEL_t v_{t+1} - \hat \MODEL_t \hat v_{t+1} } \\ &\stackrel{(c)}\le \NORM{\MODEL_t \hat v_{t+1} - \hat \MODEL_t \hat v_{t+1} } + \NORM{\MODEL_t v_{t+1} - \MODEL_t \hat v_{t+1} } \\ &\stackrel{(d)}\le \NORM{\MISMATCH_t \hat v_{t+1}} + \NORM{v_{t+1} - \hat v_{t+1}}, \end{align*}\] where $(c)$ follows from the triangle inequality and $(d)$ uses the definition of $\MISMATCH_t$ and the non-expansion of $\MODEL_t$ from Lemma 4.1.

The mismatch operator can be used to bound the difference between evaluating a fixed policy in the true and approximate models.

4.3.2 Policy error

Proposition 4.1 (Policy error) For any policy $π = (π_1, \dots, π_T)$, define the policy errors \[ α^π_t \coloneqq \NORM{V^π_t - \hat V^π_t}, \qquad β^π_t \coloneqq \NORM{Q^π_t - \hat Q^π_t}. \] Then, for any $t \in \{1,\dots,T\}$, \[ α^π_t \le β^π_t \le \sum_{\tau=t}^T Δ^π_\tau, \] where \[ Δ^π_t = \min\bigl\{ \NORM{\MISMATCH_t V^π_{t+1}}, \NORM{\MISMATCH_t \hat V^π_{t+1}} \bigr\}. \]

Proof

We prove the claim by backward induction on $t$.

Base case ($t = T+1$). The result holds trivially as $V^π_{T+1} = \hat V^π_{T+1} = 0$, so $α^π_{T+1} = 0$.

Induction step. Fix $t \in \{1,\dots,T\}$ and assume the claim holds at time $t+1$, i.e. \[ α^π_{t+1} \le \sum_{\tau=t+1}^{T} Δ^π_\tau. \] Recall that \[ Q^π_t = \MODEL_t V^π_{t+1}, \quad \hat Q^π_t = \hat \MODEL_t \hat V^π_{t+1}, \] and $V^π_t = \ALPHABET T^{π_t} Q^π_t$, $\hat V^π_t = \ALPHABET T^{π_t} \hat Q^π_t$. From the one-step lemma we get: \[ β^π_t = \NORM{Q^π_t - \hat Q^π_t} \le Δ^π_t + α^π_{t+1} \le \sum_{\tau=t}^{T} Δ^π_\tau. \] Now, using the non-expansion of $\ALPHABET T^{π_t}$ we get: \[ α^π_t = \NORM{V^π_t - \hat V^π_t} \le β^π_t \le \sum_{\tau=t}^{T} Δ^π_\tau, \] where the last step uses the induction hypothesis. This establishes the claim at time $t$.

By backward induction, the bound holds for all $t \in \{1,\dots,T\}$.

4.3.3 Value error

Similar to the above, we can also bound the difference between the optimal value functions of the true and approximate models.

Proposition 4.2 (Value error) Define the value errors \[ α^\star_t \coloneqq \NORM{V^\star_t - \hat V^\star_t}, \qquad β^\star_t \coloneqq \NORM{Q^\star_t - \hat Q^\star_t}. \] Then, for any $t \in \{1,\dots,T\}$, \[ α^\star_t \le β^\star_t \le \sum_{\tau=t}^T Δ^\star_\tau, \] where \[ Δ^\star_t = \min\bigl\{ \NORM{\MISMATCH_t V^\star_{t+1}}, \NORM{\MISMATCH_t \hat V^\star_{t+1}} \bigr\}. \]

The proof is similar to the proof of Proposition 4.1.

Proof

We prove the claim by backward induction on $t$.

Base case ($t = T+1$). The result holds trivially as $V^\star_{T+1} = \hat V^\star_{T+1} = 0$, so $α^\star_{T+1} = 0$.

Induction step. Fix $t \in \{1,\dots,T\}$ and assume the claim holds at time $t+1$, i.e. \[ α^\star_{t+1} \le \sum_{\tau=t+1}^{T} Δ^\star_\tau. \] Recall that \[ Q^\star_t = \MODEL_t V^\star_{t+1}, \quad \hat Q^\star_t = \hat \MODEL_t \hat V^\star_{t+1}, \] and $V^\star_t = \ALPHABET T^\star Q^\star_t$, $\hat V^\star_t = \ALPHABET T^\star \hat Q^\star_t$. From the one-step lemma we get: \[ β^\star_t = \NORM{Q^\star_t - \hat Q^\star_t} \le Δ^\star_t + α^\star_{t+1} \le \sum_{\tau=t}^{T} Δ^\star_\tau. \] Now, using the non-expansion of $\ALPHABET T^\star$ we get: \[ α^\star_t = \NORM{V^\star_t - \hat V^\star_t} \le β^\star_t \le \sum_{\tau=t}^{T} Δ^\star_\tau, \] where the last step uses the induction hypothesis. This establishes the claim at time $t$.

By backward induction, the bound holds for all $t \in \{1,\dots,T\}$.

4.3.4 Model approximation error

To bound the model approximation error, observe that \[\begin{align} \label{eq:triangle-model-error} α_t &\coloneqq \NORM{V^\star_t - V^{\hat π^\star}_t} \le \NORM{V^\star_t - \hat V^{\hat π^\star}_t} + \NORM{V^{\hat π^\star}_t - \hat V^{\hat π^\star}_t} \\ &\stackrel{(a)}= α^\star_t + α^{\hat π^\star}_t, \end{align}\] where $(a)$ uses that $\hat π^\star$ is optimal for the approximate model, so $\hat V^{\hat π^\star} = \hat V^\star$, and $α^\star_t$, $α^{\hat π^\star}_t$ are as in Proposition 4.2 and Proposition 4.1. The same triangle holds for the action-value gaps $β_t$, $β^\star_t$, and $β^{\hat π^\star}_t$. The key point is that because $\hat V^{\hat π^\star} = \hat V^\star$, the $\hat V$-sided one-step model errors that appear in those bounds are the same.

Theorem 4.1 (Model approximation error) Define the model approximation errors \[ α_t \coloneqq \NORM{V^\star_t - V^{\hat π^\star}_t}, \qquad β_t \coloneqq \NORM{Q^\star_t - Q^{\hat π^\star}_t}. \] Then, for any $t \in \{1,\dots,T\}$, \[ α_t \le β_t \le β^\star_t + β^{\hat π^\star}_t \le \sum_{\tau=t}^{T} \bigl( Δ^\star_\tau + Δ^{\hat π^\star}_\tau \bigr) \le 2 \sum_{\tau=t}^{T} \NORM{\MISMATCH_\tau \hat V^\star_{\tau+1}}, \] where $β^\star_t$, $β^{\hat π^\star}_t$, $Δ^\star_t$, and $Δ^{\hat π^\star}_t$ are as in Proposition 4.2 and Proposition 4.1. In particular, $\hat π^\star$ is $α_t$-optimal for $\ALPHABET M$ at time $t$.

Proof

The inequality $α_t \le β_t$ follows from non-expansion of the Bellman target operators: for every $s$, \[\begin{align*} V^\star_t(s) - V^{\hat π^\star}_t(s) &= Q^\star_t\bigl(s, π^\star_t(s)\bigr) - Q^{\hat π^\star}_t\bigl(s, \hat π^\star_t(s)\bigr) \le Q^\star_t\bigl(s, \hat π^\star_t(s)\bigr) - Q^{\hat π^\star}_t\bigl(s, \hat π^\star_t(s)\bigr) \le β_t, \end{align*}\] and \[\begin{align*} V^{\hat π^\star}_t(s) - V^\star_t(s) &= Q^{\hat π^\star}_t\bigl(s, \hat π^\star_t(s)\bigr) - Q^\star_t\bigl(s, π^\star_t(s)\bigr) \le Q^{\hat π^\star}_t\bigl(s, π^\star_t(s)\bigr) - Q^\star_t\bigl(s, π^\star_t(s)\bigr) \le β_t. \end{align*}\] Using $\hat Q^{\hat π^\star}_t = \hat Q^\star_t$, \[ β_t = \NORM{Q^\star_t - Q^{\hat π^\star}_t} \le \NORM{Q^\star_t - \hat Q^\star_t} + \NORM{Q^{\hat π^\star}_t - \hat Q^{\hat π^\star}_t} = β^\star_t + β^{\hat π^\star}_t. \] Proposition 4.2 and Proposition 4.1 then give \[ β^\star_t + β^{\hat π^\star}_t \le \sum_{\tau=t}^{T} Δ^\star_\tau + \sum_{\tau=t}^{T} Δ^{\hat π^\star}_\tau. \] For the last inequality, take the $\hat V$-sided term in each $\min$: \[ Δ^\star_\tau \le \NORM{\MISMATCH_\tau \hat V^\star_{\tau+1}}, \qquad Δ^{\hat π^\star}_\tau \le \NORM{\MISMATCH_\tau \hat V^{\hat π^\star}_{\tau+1}}. \] These upper bounds coincide because $\hat V^{\hat π^\star}_{\tau+1} = \hat V^\star_{\tau+1}$. Therefore \[ Δ^\star_\tau + Δ^{\hat π^\star}_\tau \le 2 \NORM{\MISMATCH_\tau \hat V^\star_{\tau+1}}, \] and summing over $\tau$ completes the proof.

In some applications, it is useful to have a bound on model approximation error that depends on $V^\star$ rather than $\hat V^\star$. The next result is the finite-horizon analogue of the discounted $V^\star$-based bound.

Theorem 4.2 (Model approximation error) Let $α_t$ and $β_t$ be as in Theorem 4.1. Then, for any $t \in \{1,\dots,T\}$, \[ β_t \le \bar β_t \coloneqq 2 \sum_{\tau=t}^{T} (\tau - t + 1) \NORM{\MISMATCH_\tau V^\star_{\tau+1}}, \] and \[ α_t \le \bar α_t \coloneqq \bar β_t. \] In particular, $\hat π^\star$ is $\bar α_t$-optimal for $\ALPHABET M$ at time $t$.

Proof

We claim that for any $t \in \{1,\dots,T\}$, \[ α_t \le α_{t+1} + 2 \sum_{\tau=t}^{T} \NORM{\MISMATCH_\tau V^\star_{\tau+1}}, \] with the convention $α_{T+1} = 0$. Unrolling the claim yields $α_t \le \bar α_t$.

We now prove the claim by backward induction.

Base case ($t = T+1$). The result holds trivially as $α_{T+1} = 0$.

Induction step. Fix $t \in \{1,\dots,T\}$ and assume the claim of the theorem holds at time $t+1$, i.e. \[ α_{t+1} \le 2 \sum_{\tau=t+1}^{T} (\tau - t) \NORM{\MISMATCH_\tau V^\star_{\tau+1}}. \] Combined with the recursive claim above, \[ α_t \le 2 \sum_{\tau=t}^{T} \NORM{\MISMATCH_\tau V^\star_{\tau+1}} + 2 \sum_{\tau=t+1}^{T} (\tau - t) \NORM{\MISMATCH_\tau V^\star_{\tau+1}} = \bar α_t. \] This establishes the value-gap bound at time $t$.

By backward induction, $α_t \le \bar α_t$ for all $t \in \{1,\dots,T\}$. The same recursive argument with action-value functions yields $β_t \le \bar β_t$.

It remains to prove the claim. From Proposition 4.2, taking the $V^\star$-sided term in the definition of $Δ^\star_\tau$ gives \[ \NORM{V^\star_t - \hat V^\star_t} \le \sum_{\tau=t}^{T} \NORM{\MISMATCH_\tau V^\star_{\tau+1}}. \] Moreover, since $\hat V^\star = \hat V^{\hat π^\star}$, \[\begin{align*} \NORM{V^{\hat π^\star}_t - \hat V^\star_t} &= \NORM{\ALPHABET T^{\hat π^\star} \MODEL_t V^{\hat π^\star}_{t+1} - \ALPHABET T^{\hat π^\star} \hat \MODEL_t \hat V^\star_{t+1}} \\ &\le \NORM{\MODEL_t V^{\hat π^\star}_{t+1} - \hat \MODEL_t \hat V^\star_{t+1}} \\ &\le \NORM{\MODEL_t V^{\hat π^\star}_{t+1} - \MODEL_t V^\star_{t+1}} + \NORM{\MODEL_t V^\star_{t+1} - \hat \MODEL_t V^\star_{t+1}} + \NORM{\hat \MODEL_t V^\star_{t+1} - \hat \MODEL_t \hat V^\star_{t+1}} \\ &\le α_{t+1} + \NORM{\MISMATCH_t V^\star_{t+1}} + \NORM{V^\star_{t+1} - \hat V^\star_{t+1}} \\ &\le α_{t+1} + \sum_{\tau=t}^{T} \NORM{\MISMATCH_\tau V^\star_{\tau+1}}. \end{align*}\] Therefore, using $\eqref{eq:triangle-model-error}$, \[ α_t \le \NORM{V^\star_t - \hat V^\star_t} + \NORM{V^{\hat π^\star}_t - \hat V^\star_t} \le α_{t+1} + 2 \sum_{\tau=t}^{T} \NORM{\MISMATCH_\tau V^\star_{\tau+1}}, \] which proves the claim.

4.4 IPM-based bounds on model approximation error

The above bounds require computing $\hat V^\star_t$ (or $V^\star_t$) and being able to evaluate $\MISMATCH_t \hat V^\star_{t+1}$ (or $\MISMATCH_t V^\star_{t+1}$). However, in some applications, the true model may not be known perfectly, and we may require guarantees in terms of the difference between the approximate model and the true model.

Comparing two models means comparing their cost functions and their transition dynamics. To compare transition dynamics, we need a metric on probability laws. Integral probability metrics (IPMs) are well suited for this purpose.

Let $\def\F{\mathfrak{F}}\F$ be a convex and balanced set of functions from $\ALPHABET S$ to $\reals$. The IPM distance with respect to $\F$ between two probability laws $ν_1$ and $ν_2$ is \[ d_{\F}(ν_1, ν_2) = \sup_{f \in \F} \left| \int f dν_1 - \int f dν_2 \right|. \] For this discussion, assume that $\F$ is a maximal generator. See the IPM notes for details. For any function $f$ (not in $\F$), the Minkowski functional $ρ_{\F}$ is defined as \[ ρ_{\F}(f) = \inf\left\{ r > 0 : \frac{f}{r} \in \F \right\}. \] An immediate implication of this inequality is \[\begin{equation}\label{eq:IPM-ineq} \left| \int f dν_1 - \int f dν_2 \right| \le ρ_{\F}(f) d_{\F}(ν_1, ν_2). \end{equation}\]

Now we define a corresponding distance between finite-horizon models.

Definition 4.1 (Model distance) Given a function class $\F$, we say that $\widehat{\ALPHABET M}$ is an $(ε,δ)$-approximation of $\ALPHABET M$, where $ε = (ε_1,\dots,ε_T)$ and $δ = (δ_1,\dots,δ_T)$, if for every time $t$ and all $(s,a) \in \ALPHABET S \times \ALPHABET A$,

$\ABS{c_t(s,a) - \hat c_t(s,a)} \le ε_t$;
$d_{\F}\bigl(P_t(\cdot \mid s,a), \hat P_t(\cdot \mid s,a)\bigr) \le δ_t$.

Equivalently, for any two models we may take the vectors $ε$ and $δ$ with components \[ ε_t = \NORM{c_t - \hat c_t}_{∞} \quad\text{and}\quad δ_t = \sup_{(s,a) \in \ALPHABET S \times \ALPHABET A} d_{\F}\bigl(P_t(\cdot \mid s,a), \hat P_t(\cdot \mid s,a)\bigr). \]

An immediate implication is a one-step bound on the mismatch operator.

Lemma 4.3 (IPM bound on mismatch) If $\widehat{\ALPHABET M}$ is an $(ε,δ)$-approximation of $\ALPHABET M$ with respect to $\F$, where $ε=(ε_1,\dots,ε_T)$ and $δ=(δ_1,\dots,δ_T)$, then for any time $t$ and any $v \colon \ALPHABET S \to \reals$, \[ \NORM{\MISMATCH_t v} \le ε_t + δ_t ρ_{\F}(v). \]

Proof

From the definition of the mismatch operator, \[\begin{align*} \NORM{\MISMATCH_t v} &= \max_{(s,a) \in \ALPHABET S \times \ALPHABET A} \biggl\lvert c_t(s,a) + \sum_{s' \in \ALPHABET S} P_t(s' \mid s,a)v(s') - \hat c_t(s,a) - \sum_{s' \in \ALPHABET S} \hat P_t(s' \mid s,a)v(s') \biggr\rvert \\ &\le \max_{(s,a) \in \ALPHABET S \times \ALPHABET A} \biggl\{ \ABS{c_t(s,a) - \hat c_t(s,a)} + \biggl\lvert \sum_{s' \in \ALPHABET S} P_t(s' \mid s,a)v(s') - \sum_{s' \in \ALPHABET S} \hat P_t(s' \mid s,a)v(s') \biggr\rvert \biggr\} \\ &\le \max_{(s,a) \in \ALPHABET S \times \ALPHABET A} \Bigl\{ \ABS{c_t(s,a) - \hat c_t(s,a)} + ρ_{\F}(v) d_{\F}\bigl(P_t(\cdot \mid s,a), \hat P_t(\cdot \mid s,a)\bigr) \Bigr\} \\ &\le ε_t + δ_t ρ_{\F}(v). \end{align*}\] The second inequality uses $\eqref{eq:IPM-ineq}$; the last inequality uses the $t$-th component of the $(ε,δ)$-approximation.

Combining Lemma 4.3 with Theorem 4.1 and Theorem 4.2 gives explicit model approximation bounds in terms of the cost and transition errors.

Theorem 4.3 (Model approximation error via IPMs) Suppose that $\widehat{\ALPHABET M}$ is an $(ε,δ)$-approximation of $\ALPHABET M$. Let $α_t$ and $β_t$ be as in Theorem 4.1. Then, for any $t \in \{1,\dots,T\}$, \[ β_t \le 2 \sum_{\tau=t}^{T} \bigl[ ε_\tau + δ_\tau ρ_{\F}(\hat V^\star_{\tau+1}) \bigr], \] and $α_t \le β_t$. Another upper bound is \[ β_t \le \bar β_t \coloneqq 2 \sum_{\tau=t}^{T} (\tau - t + 1) \bigl[ ε_\tau + δ_\tau ρ_{\F}(V^\star_{\tau+1}) \bigr], \] and $α_t \le \bar α_t \coloneqq \bar β_t$. In particular, $\hat π^\star$ is $α_t$-optimal for $\ALPHABET M$ at time $t$.

Note that the above bounds require knowledge of $\hat V^\star_t$. For specific choices of IPM, it is possible to obtain instance-independent upper bounds that do not require explicit knowledge of $\hat V^\star_t$.

Corollary 4.1 (Instance-independent model approximation bounds)

Suppose the approximation is with respect to total variation. Then \[ α_t \le 2 \sum_{\tau=t}^{T} ε_\tau + \sum_{\tau=t}^{T} δ_\tau \sum_{k=\tau+1}^{T} \SPAN(\hat c_k). \] Alternatively, \[ α_t \le 2 \sum_{\tau=t}^{T} (\tau-t+1) ε_\tau + \sum_{\tau=t}^{T} (\tau-t+1)δ_\tau \sum_{k=\tau+1}^{T} \SPAN(c_k). \]
Suppose the approximation is with respect to Wasserstein distance. If the approximate model has Lipschitz constants $(\hat L^c_t, \hat L^P_t)$, define $\hat L^V_{T+1}=0$ and \[ \hat L^V_t = \hat L^c_t + \hat L^P_t \hat L^V_{t+1}. \] Then \[ α_t \le 2 \sum_{\tau=t}^{T} \bigl[ ε_\tau + δ_\tau \hat L^V_{\tau+1} \bigr]. \] Alternatively, using the Lipschitz constants $(L^c_t, L^P_t)$ of the true model, define $L^V_{T+1}=0$ and \[ L^V_t = L^c_t + L^P_t L^V_{t+1}. \] Then \[ α_t \le 2 \sum_{\tau=t}^{T} (\tau-t+1) \bigl[ ε_\tau + δ_\tau L^V_{\tau+1} \bigr]. \]

4.5 Examples

4.5.1 Inventory management with incorrect demand distribution

Consider the finite-horizon inventory management problem with dynamics \[ S_{t+1} = S_t + A_t - W_t \] and per-step cost \[ c_t(s,a,w) = p a + h(s+a-w), \quad h(x) = \begin{cases} c_h x, & x \ge 0, \\ -c_s x, & x < 0. \end{cases} \] Suppose the true demand at time $t$ has law $ν_t$, but the approximate model uses $\hat ν_t$. Define \[ δ_t = W_1(ν_t,\hat ν_t), \quad \ell = \operatorname{Lip}(h) = \max\{c_h,c_s\}. \]

The transition kernels are shifted copies of the demand laws. For example, if the true and approximate demands have densities $f_{W_t}$ and $f_{\hat W_t}$, then the densities of the next-stock laws are \[ p_t(x \mid s,a) = f_{W_t}(s+a-x), \quad \hat p_t(x \mid s,a) = f_{\hat W_t}(s+a-x). \] Thus both distributions are shifted in the same way, and shifting two distributions does not change their Wasserstein distance.¹ Hence \[ W_1\bigl(P_t(\cdot \mid s,a),\hat P_t(\cdot \mid s,a)\bigr) = W_1(ν_t,\hat ν_t) = δ_t. \]

The primitive cost function is known, but the expected one-step cost changes because the demand law changes. Since $h$ is $\ell$-Lipschitz, \[ \ABS{ \EXP[h(s+a-W_t)] - \EXP[h(s+a-\hat W_t)] } \le \ell δ_t. \] Thus, in the notation of Definition 4.1, we may take $ε_t = \ell δ_t$.

Applying the Wasserstein part of Corollary 4.1, the policy $\hat π^\star$ computed from the approximate demand model is $α_t$-optimal for the true inventory model with \[ α_t \le 2 \sum_{\tau=t}^{T} \bigl[ ε_\tau + δ_\tau \hat L^V_{\tau+1} \bigr] = 2 \sum_{\tau=t}^{T} \bigl[ \ell δ_\tau + δ_\tau \hat L^V_{\tau+1} \bigr]. \]

It remains to bound the Lipschitz constants $\hat L^V_{\tau+1}$ of the approximate value functions. By Proposition 3.4 in the MDP properties notes, the approximate inventory model has \[ \hat L^P_t = 1, \quad \hat L^c_t = \operatorname{Lip}(h) = \ell, \quad t = 1,\dots,T, \] so the recursion of Proposition 3.3 gives \[ \hat L^V_{T+1} = 0, \quad \hat L^V_t = \ell + \hat L^V_{t+1}, \] and hence \[ \hat L^V_t = (T-t+1)\ell. \] The unit procurement cost $p$ does not enter $\hat L^c_t$ because it does not depend on the stock level $s$; only the holding/backlog term $h$ contributes to the state-Lipschitz constant.

Substituting into the bound above, \[ α_t \le 2 \sum_{\tau=t}^{T} \bigl[ \ell δ_\tau + (T-\tau)\ell δ_\tau \bigr] = 2\ell \sum_{\tau=t}^{T} (T-\tau+1)δ_\tau. \] If the demand approximation error is time-homogeneous, $δ_\tau \le δ$ for all $\tau$, then this simplifies to \[ α_t \le 2\ell δ \sum_{\tau=t}^{T} (T-\tau+1) = \ell δ (T-t+1)(T-t+2). \]

4.5.2 Performance loss from certainty equivalent control

Certainty equivalence is the following design method: replace the random variables in a stochastic control problem by their conditional means, solve the resulting deterministic control problem, and use the resulting feedback policy in the original stochastic system. This is optimal for some special models, such as linear quadratic regulation, but not in general.

Consider a finite-horizon system with state space $\reals^n$, action space $\reals^m$, and dynamics \[\begin{equation}\label{eq:stochastic-CE} S_{t+1} = f_t(S_t,A_t) + N_t, \end{equation}\] where $\EXP[N_t]=0$. Suppose the per-step cost is $c_t(S_t,A_t)$ and does not depend directly on the noise. The certainty equivalent model replaces $\eqref{eq:stochastic-CE}$ by \[\begin{equation}\label{eq:deterministic-CE} S_{t+1} = f_t(S_t,A_t). \end{equation}\] Let $\ALPHABET M$ denote the stochastic model and $\widehat{\ALPHABET M}$ the deterministic model. The certainty equivalent policy is the optimal policy $\hat π^\star$ of $\widehat{\ALPHABET M}$, applied to the original stochastic model $\ALPHABET M$.

We use the Wasserstein bound in Corollary 4.1. The cost functions are the same in the two models, so $ε_t = 0$. To characterize $δ_t$, fix $(s,a)$ and let \[ X = f_t(s,a) + N_t, \quad Y = f_t(s,a). \] The Wasserstein distance between $P_t(\cdot \mid s,a)$ and $\hat P_t(\cdot \mid s,a)$ is $W_1(X,Y)$. From the coupling definition of Wasserstein distance, \[ W_1(X,Y) \le \EXP\bigl[\NORM{N_t}\bigr], \] and this bound does not depend on $(s,a)$. Thus we may take \[ δ_t = \EXP\bigl[\NORM{N_t}\bigr]. \]

If $\hat L^V_t$ denotes the Lipschitz bound for the value function of the deterministic model, then Corollary 4.1 gives \[\begin{equation}\label{eq:CE-bound} \NORM{V^\star_t - V^{\hat π^\star}_t} \le 2 \sum_{\tau=t}^{T} \EXP\bigl[\NORM{N_\tau}\bigr] \hat L^V_{\tau+1}. \end{equation}\] This bound quantifies the engineering intuition that certainty equivalent policies are good when the noise is small and the deterministic model has modest value-function Lipschitz constants.

In one dimension, this follows immediately from the CDF formula $W_1(X,Y)=\int_{-∞}^{∞} \ABS{F_X(x)-F_Y(x)}\,dx$.↩︎