4 Model approximation

4.1 Motivation

There are many instances where approximate models are used. For example, with a large state space one often builds a simulation model and computes a policy from that simulator (say, by dynamic programming or reinforcement learning). The simulator is typically only an approximation of the real system. The practical question is: if we take the policy that is optimal for the simulator and use it in the real world, how much performance do we lose?

The same pattern appears when \((P,c)\) are estimated from data, or when a detailed physical model is replaced by a coarser one. In all of these cases we have a true model and an approximate model, and we want quantitative error bounds.

Formally, 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)\) may be time varying. Write \(\widehat {\ALPHABET M} = \langle \ALPHABET S, \ALPHABET A, \hat P, \hat c, T \rangle\) for the approximate MDP. Let \(\{V^\star_t\}_{t=1}^T\) and \(\{\hat V^\star_t\}_{t =1}^T\) be the optimal value functions of \(\ALPHABET M\) and \(\widehat {\ALPHABET M}\), and let \(π^\star\) and \(\hat π^\star\) be corresponding optimal policies. We write \(\ENV_t\) and \(\hat \ENV_t\) for the environment operators of the two models.

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)\)?

We will characterize these bounds in the sup-norm: for any \(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 the same questions with finer metrics.

4.2 Operator notation (recall)

In the previous lecture we factored the Bellman operators as \[ \BELLMAN^π_t = \ALPHABET T^π \circ \ENV_t, \quad \text{and}\quad \BELLMAN^\star_t = \ALPHABET T^\star \circ \ENV_t, \] where \(\ENV_t \colon \ALPHABET V \to \ALPHABET Q\) is the environment operator \[ [\ENV_t v](s,a) = c_t(s,a) + \sum_{s' \in \ALPHABET S} P_t(s'|s,a) v(s'), \] and \(\ALPHABET T^π\), \(\ALPHABET T^\star\) are the (model-independent) action selection operators \[ [\ALPHABET T^π q](s) = q(s, π(s)), \qquad [\ALPHABET T^\star q](s) = \min_{a \in \ALPHABET A} q(s, a), \] with the usual extension of \(\ALPHABET T^π\) to randomized policies. We also write \(π \in \GREEDY q\) when \(π(s) \in \arg\min_a q(s,a)\).

The corresponding dynamic programs are \[ 0 ≡ V^\star_{T+1} \xrightarrow{\ENV_T} Q^\star_T \xrightarrow{\ALPHABET T^\star} V^\star_T \xrightarrow{\ENV_{T-1}} Q^\star_{T-1} \cdots \xrightarrow{\ALPHABET T^\star} V^\star_1 \] and likewise \(V^π_{T+1} \xrightarrow{\ENV} Q^π \xrightarrow{\ALPHABET T^π} V^π \cdots\) for policy evaluation. A policy \(π^\star\) is optimal if and only if \(π^\star_t \in \GREEDY Q^\star_t\) for all \(t\).

The point of the split for this lecture is that \(\ENV_t\) depends on the model \((P_t,c_t)\), while \(\ALPHABET T^π\) and \(\ALPHABET T^\star\) do not. Model approximation perturbs only the environment operators: we write \(\hat \ENV_t\) for the approximate model \(\widehat{\ALPHABET M}\).

4.2.1 Non-expansion in the sup-norm

In addition to the span and Lipschitz properties derived in the previous lecture, the same operators are non-expansions in the sup-norm. This is the basic contraction property we need for approximation error bounds.

Lemma 4.1 (Non-expansion properties) The operators \(\ENV_t\), \(\hat \ENV_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{\ENV_t v - \ENV_t \hat v} \le \NORM{v - \hat v}. \] The same bound holds with \(\ENV_t\) replaced by \(\hat \ENV_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{[\ENV_t v](s,a) - [\ENV_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.

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 = \ENV_t v - \hat \ENV_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 = \ENV_t v_{t+1}\) and \(\hat q_t = \hat \ENV_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{\ENV_t v_{t+1} - \hat \ENV_t \hat v_{t+1} } \\ &\stackrel{(a)}\le \NORM{\ENV_t v_{t+1} - \hat \ENV_t v_{t+1} } + \NORM{\hat \ENV_t v_{t+1} - \hat \ENV_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 \ENV_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{\ENV_t v_{t+1} - \hat \ENV_t \hat v_{t+1} } \\ &\stackrel{(c)}\le \NORM{\ENV_t \hat v_{t+1} - \hat \ENV_t \hat v_{t+1} } + \NORM{\ENV_t v_{t+1} - \ENV_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 \(\ENV_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 = \ENV_t V^π_{t+1}, \quad \hat Q^π_t = \hat \ENV_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 = \ENV_t V^\star_{t+1}, \quad \hat Q^\star_t = \hat \ENV_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 action selection 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} \ENV_t V^{\hat π^\star}_{t+1} - \ALPHABET T^{\hat π^\star} \hat \ENV_t \hat V^\star_{t+1}} \\ &\le \NORM{\ENV_t V^{\hat π^\star}_{t+1} - \hat \ENV_t \hat V^\star_{t+1}} \\ &\le \NORM{\ENV_t V^{\hat π^\star}_{t+1} - \ENV_t V^\star_{t+1}} + \NORM{\ENV_t V^\star_{t+1} - \hat \ENV_t V^\star_{t+1}} + \NORM{\hat \ENV_t V^\star_{t+1} - \hat \ENV_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 bounds in Theorem 4.3 still involve \(ρ_{\F}(\hat V^\star_{\tau+1})\) or \(ρ_{\F}(V^\star_{\tau+1})\). Using Theorem 3.2 from the properties of value functions lecture, we can upper-bound \(\SPAN(V^\star_t)\) (and likewise \(\SPAN(\hat V^\star_t)\)) in an instance-independent manner. Combined with ?prp-TV-span-bound, this yields fully explicit total-variation error bounds that depend only on the cost spans, the contraction factors, and the model distances \((ε_τ,δ_τ)\). An analogous role is played by the Lipschitz recursion of Theorem 3.3 for Wasserstein distance.

Corollary 4.1 (Instance-independent model approximation bounds)

Total variation. Recall that \(ρ_{\mathrm{TV}}(v) \le \tfrac12 \SPAN(v)\). Let \(λ_t\) and \(\hat λ_t\) be the contraction factors of \(\ALPHABET M\) and \(\widehat{\ALPHABET M}\), and suppose \(\hat λ \ge \hat λ_t\) (where \(\hat λ_t\) is the contraction factor in model \(\widehat{\ALPHABET M}\)). \[ α_t \le 2 \sum_{\tau=t}^{T} ε_\tau + \sum_{\tau=t}^{T} δ_\tau \sum_{k=\tau+1}^{T} \hat λ^{\,k-\tau-1}\, \SPAN(\hat c_k). \]
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.3 in the properties of value functions 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 Theorem 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\).↩︎