6 Sample-path bounds
6.1 Motivation
In the previous lectures, we have obtained bounds on policy error, value error, and model approximation error in terms of the sup-norm. In this lecture, we will develop sample path based bounds which are tighter. For simplicity, we reuse some of the symbols from the previous lectures, but their meanings are different.
6.2 Model approximation (Take 3)
6.2.1 One step error propagation
Recall that the environment operator \(\ENV_t \colon \ALPHABET V \to \ALPHABET Q\) includes both the cost and the transition: \[ [\ENV_t v](s,a) = c_t(s,a) + \sum_{s' \in \ALPHABET S} P_t(s' \mid s,a) v(s'). \] Define the dynamics operator \(\DYNAMICS_t \colon \ALPHABET V \to \ALPHABET Q\) to be the transition part alone: \[ [\DYNAMICS_t v](s,a) = \sum_{s' \in \ALPHABET S} P_t(s' \mid s,a) v(s'). \] Thus \(\ENV_t v = c_t + \DYNAMICS_t v\). As before, the mismatch is \(\MISMATCH_t v = \ENV_t v - \hat \ENV_t v\).
Lemma 6.1 For any \(v, \hat v \in \ALPHABET V\), \[ \ENV_t v - \ENV_t \hat v = \DYNAMICS_t \bigl[ v - \hat v \bigr]. \]
The cost terms cancel: \[\begin{align*} \ENV_t v - \ENV_t \hat v &= \bigl(c_t + \DYNAMICS_t v\bigr) - \bigl(c_t + \DYNAMICS_t \hat v\bigr) = \DYNAMICS_t v - \DYNAMICS_t \hat v = \DYNAMICS_t \bigl[ v - \hat v \bigr], \end{align*}\] where the last step uses linearity of \(\DYNAMICS_t\).
Lemma 6.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 \[ q_t - \hat q_t = \MISMATCH_t \hat v_{t+1} + \bigl[ \ENV_t v_{t+1} - \ENV_t \hat v_{t+1} \bigr] = \MISMATCH_t \hat v_{t+1} + \DYNAMICS_t \bigl[ v_{t+1} - \hat v_{t+1} \bigr]. \]
Consider \[\begin{align*} q_t - \hat q_t &= \ENV_t v_{t+1} - \hat \ENV_t \hat v_{t+1} \\ &= \bigl[ \ENV_t \hat v_{t+1} - \hat \ENV_t \hat v_{t+1} \bigr] + \bigl[ \ENV_t v_{t+1} - \ENV_t \hat v_{t+1} \bigr] \\ &= \MISMATCH_t \hat v_{t+1} + \bigl[ \ENV_t v_{t+1} - \ENV_t \hat v_{t+1} \bigr] \\ &= \MISMATCH_t \hat v_{t+1} + \DYNAMICS_t \bigl[ v_{t+1} - \hat v_{t+1} \bigr], \end{align*}\] where the third equality uses the definition of \(\MISMATCH_t\) and the last equality uses Lemma 6.1.
6.2.2 Policy error
Proposition 6.1 (Policy error) For any policy \(π = (π_1, \dots, π_T)\), define the policy errors \[ α^π_t(s) \coloneqq V^π_t(s) - \hat V^π_t(s), \qquad β^π_t(s,a) \coloneqq Q^π_t(s,a) - \hat Q^π_t(s,a), \] with the convention \(α^π_{T+1} ≡ 0\). Then, for any \(t \in \{1,\dots,T\}\), \[\begin{align*} β^π_t &= \MISMATCH_t \hat V^π_{t+1} + \DYNAMICS_t α^π_{t+1}, \\ α^π_t &= \ALPHABET T^{π_t} β^π_t. \end{align*}\]
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 Lemma 6.2 with \(v_{t+1} = V^π_{t+1}\) and \(\hat v_{t+1} = \hat V^π_{t+1}\), \[ β^π_t = Q^π_t - \hat Q^π_t = \MISMATCH_t \hat V^π_{t+1} + \DYNAMICS_t α^π_{t+1}. \] Since \(\ALPHABET T^{π_t}\) is linear, \[ α^π_t = V^π_t - \hat V^π_t = \ALPHABET T^{π_t} Q^π_t - \ALPHABET T^{π_t} \hat Q^π_t = \ALPHABET T^{π_t} β^π_t. \]
6.2.3 Value error
Similar to the above, we can also compare the optimal value functions of the true and approximate models.
Proposition 6.2 (Value error) Define the value errors \[ α^\star_t(s) \coloneqq V^\star_t(s) - \hat V^\star_t(s), \qquad β^\star_t(s,a) \coloneqq Q^\star_t(s,a) - \hat Q^\star_t(s,a), \] with the convention \(α^\star_{T+1} ≡ 0\). Then, for any \(t \in \{1,\dots,T\}\), \[\begin{align*} β^\star_t &= \MISMATCH_t \hat V^\star_{t+1} + \DYNAMICS_t α^\star_{t+1}, \\ \ALPHABET T^{π^\star_t} β^\star_t &\le α^\star_t \le \ALPHABET T^{\hat π^\star_t} β^\star_t. \end{align*}\]
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 Lemma 6.2 with \(v_{t+1} = V^\star_{t+1}\) and \(\hat v_{t+1} = \hat V^\star_{t+1}\), \[ β^\star_t = Q^\star_t - \hat Q^\star_t = \MISMATCH_t \hat V^\star_{t+1} + \DYNAMICS_t α^\star_{t+1}. \]
The sandwich for \(α^\star_t\) uses the two optimality properties, one at a time.
Upper bound. By optimality of \(\hat π^\star_t\) on the approximate side, \(\hat V^\star_t = \ALPHABET T^{\hat π^\star_t} \hat Q^\star_t\), while on the true side \(V^\star_t = \ALPHABET T^\star Q^\star_t \le \ALPHABET T^{\hat π^\star_t} Q^\star_t\). Therefore \[ α^\star_t = V^\star_t - \hat V^\star_t \le \ALPHABET T^{\hat π^\star_t} Q^\star_t - \ALPHABET T^{\hat π^\star_t} \hat Q^\star_t = \ALPHABET T^{\hat π^\star_t} β^\star_t. \]
Lower bound. By optimality of \(π^\star_t\) on the true side, \(V^\star_t = \ALPHABET T^{π^\star_t} Q^\star_t\), while on the approximate side \(\hat V^\star_t = \ALPHABET T^\star \hat Q^\star_t \le \ALPHABET T^{π^\star_t} \hat Q^\star_t\). Therefore \[ α^\star_t = V^\star_t - \hat V^\star_t \ge \ALPHABET T^{π^\star_t} Q^\star_t - \ALPHABET T^{π^\star_t} \hat Q^\star_t = \ALPHABET T^{π^\star_t} β^\star_t. \]
Unfortunately, the result of Proposition 6.2 is uncomputable because we do not know the exact value of \(α^\star_t\). However, as we explain below, it can be used to obtain model approximation error bounds by upper and lower bounding \(\alpha^\star_t\).
6.2.4 Model approximation bounds
As in the sup-norm case, the key idea is that \[ 0 \le V^{\hat \pi^\star}_t - V^\star_t \le \bigl[\hat V^{\hat \pi^\star}_t - V^{\hat \pi^\star}_t \bigr] - \bigl[ V^\star_t - \hat V^\star_t \bigr]. \] So, we can take an upper bound on the first term and a lower bound on the second term to get a bound on the model error. We can get these (possibly loose) upper and lower bounds on \(α^{\hat π^\star}\) and \(α^\star\) by finding \((α^+, β^+)\) and \((α^-, β^-)\) that obey the same recursions but with inequalities instead of equalities.
Theorem 6.1 (Signed sample-path bound) Suppose that for each \(t \in \{1,\dots,T\}\) there exist functions \(α^+_t, α^-_t \colon \ALPHABET S \to \reals\) and \(β^+_t, β^-_t \colon \ALPHABET S \times \ALPHABET A \to \reals\) such that \[ β^-_T \le \MISMATCH_T \hat V^\star_{T+1} \le β^+_T, \] and for \(t < T\), \[\begin{align*} β^-_t &\le \MISMATCH_t \hat V^\star_{t+1} + \DYNAMICS_t α^-_{t+1}, \\ α^-_t &\le \ALPHABET T^{π^\star_t} β^-_t, \end{align*}\] and \[\begin{align*} β^+_t &\ge \MISMATCH_t \hat V^\star_{t+1} + \DYNAMICS_t α^+_{t+1}, \\ α^+_t &\ge \ALPHABET T^{\hat π^\star_t} β^+_t. \end{align*}\] Then, for all \(t\), \[ V^{\hat π^\star}_t - V^\star_t \le α^+_t - α^-_t. \]
The recursions for the upper bound and the lower bound are similar to the recursions for exact policy and value errors in Proposition 6.1 (specialized to \(\hat π^\star\)) and Proposition 6.2, with equalities replaced by inequalities. Therefore, a backward induction argument shows that \(α^+_t\) is an upper bound on \(α^{\hat π^\star}_t = V^{\hat π^\star}_t - \hat V^\star_t\) and \(α^-_t\) is a lower bound on \(α^\star_t = V^\star_t - \hat V^\star_t\). Combining the two inequalities then gives \[ V^{\hat π^\star}_t - V^\star_t = α^{\hat π^\star}_t - α^\star_t \le α^+_t - α^-_t. \]
A concrete construction that uses the best upper bound and relaxes the lower bound (so that we don’t need the knowledge of \(π^\star\)) is \[\begin{align*} α^+_t &= \ALPHABET T^{\hat π^\star_t}\bigl( \MISMATCH_t \hat V^\star_{t+1} + \DYNAMICS_t α^+_{t+1} \bigr), \\ α^-_t(s) &= \min_{a \in \ALPHABET C_t(s)} \Bigl[ \MISMATCH_t \hat V^\star_{t+1} + \DYNAMICS_t α^-_{t+1} \Bigr](s,a), \end{align*}\] where \(\ALPHABET C_t(s) \subseteq \ALPHABET A\) is any set guaranteed to contain \(π^\star_t(s)\) (for example \(\ALPHABET C_t(s) = \ALPHABET A\), in which case \(α^-_t = \ALPHABET T^\star\bigl(\MISMATCH_t \hat V^\star_{t+1} + \DYNAMICS_t α^-_{t+1}\bigr)\), or a structural candidate set that does not require computing \(π^\star\) explicitly). Theorem 6.1 then guarantees \[ V^{\hat π^\star}_t - V^\star_t \le α^+_t - α^-_t. \]
6.2.5 Symmetric bounds
The above bound requires separately keeping track of an upper and lower bound. We can get symmetric upper and lower bounds by taking absolute values.
Theorem 6.2 (Absolute-value sample-path bound) Suppose that for each \(t \in \{1,\dots,T\}\) there exist functions \(α^{\mathrm{abs}}_t \colon \ALPHABET S \to \reals_{\ge 0}\) and \(β^{\mathrm{abs}}_t \colon \ALPHABET S \times \ALPHABET A \to \reals_{\ge 0}\) such that \[ β^{\mathrm{abs}}_T \ge \ABS{\MISMATCH_T \hat V^\star_{T+1}}, \] and for \(t < T\), \[ β^{\mathrm{abs}}_t \ge \ABS{\MISMATCH_t \hat V^\star_{t+1}} + \DYNAMICS_t α^{\mathrm{abs}}_{t+1}, \] and for all \(t\), \[ α^{\mathrm{abs}}_t \ge \max\Bigl\{ \ALPHABET T^{π^\star_t} β^{\mathrm{abs}}_t,\; \ALPHABET T^{\hat π^\star_t} β^{\mathrm{abs}}_t \Bigr\}, \] where absolute values of \(Q\)-functions are pointwise. Then the policy \(\hat π^\star\) satisfies, for all \(t\), \[ \ABS{V^{\hat π^\star}_t - V^\star_t} \le 2 α^{\mathrm{abs}}_t. \]
Choose the upper and lower bounds \[ α^+_t = α^{\mathrm{abs}}_t, \quad α^-_t = -α^{\mathrm{abs}}_t, \quad β^+_t = β^{\mathrm{abs}}_t, \quad β^-_t = -β^{\mathrm{abs}}_t. \] These satisfy the hypotheses of Theorem 6.1, so \[ V^{\hat π^\star}_t - V^\star_t \le α^+_t - α^-_t = 2 α^{\mathrm{abs}}_t. \] For the matching lower side, optimality of \(V^\star\) yields \(V^{\hat π^\star}_t - V^\star_t \ge 0 \ge -2 α^{\mathrm{abs}}_t\) because \(α^{\mathrm{abs}}_t \ge 0\). Combining the two inequalities gives the claim.
A feasible (but state-independent) choice is \[ α^{\mathrm{abs}}_t \equiv \sum_{\tau=t}^{T} \NORM{\MISMATCH_\tau \hat V^\star_{\tau+1}}, \qquad β^{\mathrm{abs}}_t \equiv \NORM{\MISMATCH_t \hat V^\star_{t+1}} + \DYNAMICS_t α^{\mathrm{abs}}_{t+1}. \] For this choice, Theorem 6.2 recovers the factor-of-two model-approximation bound from the model-approximation lecture: \[ \NORM{V^{\hat π^\star}_t - V^\star_t} \le 2 \sum_{\tau=t}^{T} \NORM{\MISMATCH_\tau \hat V^\star_{\tau+1}}. \]
6.3 Computing the bounds
One difficulty in applying Theorem 6.1 is that the upper and lower bound recursions propagate with the true dynamics \(\DYNAMICS_t\). Moreover, computing the mismatch \(\MISMATCH_t \hat V^\star_{t+1}\) requires the true model.
In applications where \(P_t\) is unknown or inconvenient to evaluate, we can obtain coarser bounds that use only the approximate model, at the price of an additional IPM penalty. Write \(\hat \DYNAMICS_t\) for the dynamics operator of \(\widehat{\ALPHABET M}\), so \([\hat \DYNAMICS_t v](s,a) = \sum_{s'} \hat P_t(s'\mid s,a)\, v(s')\).
Let \(\def\F{\mathfrak{F}}\F\) be a (maximal) generator as in the model-approximation lecture, with IPM \(d_{\F}\) and Minkowski functional \(ρ_{\F}\). Suppose we are given \(ε^{+}_t, ε^{-}_t \in \ALPHABET Q\) with \[ ε^{-}_t \le c_t - \hat c_t \le ε^{+}_t, \] and define \(δ_t \in \ALPHABET Q\) by \[ δ_t(s,a) \coloneqq d_{\F}\bigl(P_t(\cdot \mid s,a), \hat P_t(\cdot \mid s,a)\bigr). \] (Here and below, products such as \(δ_t\, ρ_{\F}(v)\) are pointwise.) The defining IPM inequality then yields, for any \(v \colon \ALPHABET S \to \reals\), \[ \ABS{\DYNAMICS_t v - \hat \DYNAMICS_t v} \le δ_t\, ρ_{\F}(v), \] or equivalently \[ \hat \DYNAMICS_t v - δ_t\, ρ_{\F}(v) \le \DYNAMICS_t v \le \hat \DYNAMICS_t v + δ_t\, ρ_{\F}(v). \] Applying this to \(v = \hat V^\star_{t+1}\) and using \(\MISMATCH_t \hat V^\star_{t+1} = (c_t - \hat c_t) + (\DYNAMICS_t - \hat \DYNAMICS_t)\hat V^\star_{t+1}\) also bounds the one-step mismatch: \[ ε^{-}_t - δ_t\, ρ_{\F}(\hat V^\star_{t+1}) \le \MISMATCH_t \hat V^\star_{t+1} \le ε^{+}_t + δ_t\, ρ_{\F}(\hat V^\star_{t+1}). \]
Thus both the mismatch and the true dynamics can be replaced by approximate-model operators plus or minus an IPM correction. In particular, the recursions of Theorem 6.1 are implied by \[\begin{align*} β^-_t &\le ε^{-}_t - δ_t\, ρ_{\F}(\hat V^\star_{t+1}) + \hat \DYNAMICS_t α^-_{t+1} - δ_t\, ρ_{\F}(α^-_{t+1}), \\ α^-_t &\le \ALPHABET T^{π^\star_t} β^-_t, \end{align*}\] and \[\begin{align*} β^+_t &\ge ε^{+}_t + δ_t\, ρ_{\F}(\hat V^\star_{t+1}) + \hat \DYNAMICS_t α^+_{t+1} + δ_t\, ρ_{\F}(α^+_{t+1}), \\ α^+_t &\ge \ALPHABET T^{\hat π^\star_t} β^+_t. \end{align*}\] The resulting bounds are typically looser than those built from \(\DYNAMICS_t\), but they are computable from the approximate model together with model error \((ε^\pm_t,δ_t)\).
6.4 Model approximation with state abstraction (Take 4)
We now redo the sample-path bounds when the true model \(\ALPHABET M = \langle \ALPHABET S, \ALPHABET A, P, c, T \rangle\) and the approximate model \(\widehat {\ALPHABET M} = \langle \hat {\ALPHABET S}, \ALPHABET A, \hat P, \hat c, T \rangle\) live on different state spaces, related by a surjective abstraction \(φ \colon \ALPHABET S \to \hat {\ALPHABET S}\). As in the state-abstraction lecture, we lift any \(\hat f\) on \(\hat {\ALPHABET S}\) to \(\hat f \circ φ\) on \(\ALPHABET S\), write \(\hat π \circ φ\) for the lift of a policy \(\hat π\) on \(\widehat {\ALPHABET M}\), and use \((\hat q \circ φ)(s,a) \coloneqq \hat q(φ(s),a)\) for \(\hat q \in \hat {\ALPHABET Q}\).
The pointwise arguments carry over verbatim; the only change is that every comparison is between a function on \(\ALPHABET S\) and the lift of a function on \(\hat {\ALPHABET S}\). The details below are just for the sake of completeness.
6.4.1 One step error propagation
Since the two models have different state spaces, we use the mismatch operator \(\hat \MISMATCH_t \colon \hat {\ALPHABET V} \to \ALPHABET Q\) from the state-abstraction lecture: for \(\hat v \in \hat {\ALPHABET V}\), \[ \hat \MISMATCH_t \hat v = \ENV_t (\hat v \circ φ) - (\hat \ENV_t \hat v) \circ φ. \] The dynamics operator \(\DYNAMICS_t \colon \ALPHABET V \to \ALPHABET Q\) is that of the true model, exactly as before.
Lemma 6.3 (One step error propagation) Given \(v_{t+1} \in \ALPHABET V\) and \(\hat v_{t+1} \in \hat {\ALPHABET V}\), define \(q_t = \ENV_t v_{t+1}\) and \(\hat q_t = \hat \ENV_t \hat v_{t+1}\). Then \[ q_t - \hat q_t \circ φ = \hat \MISMATCH_t \hat v_{t+1} + \DYNAMICS_t \bigl[ v_{t+1} - \hat v_{t+1} \circ φ \bigr]. \]
Add and subtract \(\ENV_t(\hat v_{t+1} \circ φ)\): \[\begin{align*} q_t - \hat q_t \circ φ &= \bigl[ \ENV_t(\hat v_{t+1} \circ φ) - (\hat \ENV_t \hat v_{t+1}) \circ φ \bigr] + \bigl[ \ENV_t v_{t+1} - \ENV_t(\hat v_{t+1} \circ φ) \bigr] \\ &= \hat \MISMATCH_t \hat v_{t+1} + \DYNAMICS_t \bigl[ v_{t+1} - \hat v_{t+1} \circ φ \bigr], \end{align*}\] where the last step uses the definition of \(\hat \MISMATCH_t\) and Lemma 6.1.
6.4.2 Policy error
Proposition 6.3 (Policy error) For any policy \(\hat π = (\hat π_1, \dots, \hat π_T)\) on \(\widehat {\ALPHABET M}\), define the policy errors \[ α^{\hat π}_t(s) \coloneqq V^{\hat π \circ φ}_t(s) - \hat V^{\hat π}_t(φ(s)), \qquad β^{\hat π}_t(s,a) \coloneqq Q^{\hat π \circ φ}_t(s,a) - \hat Q^{\hat π}_t(φ(s),a), \] with the convention \(α^{\hat π}_{T+1} ≡ 0\). Then, for any \(t \in \{1,\dots,T\}\), \[\begin{align*} β^{\hat π}_t &= \hat \MISMATCH_t \hat V^{\hat π}_{t+1} + \DYNAMICS_t α^{\hat π}_{t+1}, \\ α^{\hat π}_t &= \ALPHABET T^{\hat π_t \circ φ} β^{\hat π}_t. \end{align*}\]
Recall that \(Q^{\hat π \circ φ}_t = \ENV_t V^{\hat π \circ φ}_{t+1}\) and \(\hat Q^{\hat π}_t = \hat \ENV_t \hat V^{\hat π}_{t+1}\). Applying Lemma 6.3 with \(v_{t+1} = V^{\hat π \circ φ}_{t+1}\) and \(\hat v_{t+1} = \hat V^{\hat π}_{t+1}\), \[ β^{\hat π}_t = Q^{\hat π \circ φ}_t - \hat Q^{\hat π}_t \circ φ = \hat \MISMATCH_t \hat V^{\hat π}_{t+1} + \DYNAMICS_t α^{\hat π}_{t+1}. \] Since \(V^{\hat π \circ φ}_t = \ALPHABET T^{\hat π_t \circ φ} Q^{\hat π \circ φ}_t\) and \(\hat V^{\hat π}_t \circ φ = \ALPHABET T^{\hat π_t \circ φ}(\hat Q^{\hat π}_t \circ φ)\), linearity of \(\ALPHABET T^{\hat π_t \circ φ}\) gives \[ α^{\hat π}_t = V^{\hat π \circ φ}_t - \hat V^{\hat π}_t \circ φ = \ALPHABET T^{\hat π_t \circ φ} β^{\hat π}_t. \]
6.4.3 Value error
Proposition 6.4 (Value error) Define the value errors \[ α^\star_t(s) \coloneqq V^\star_t(s) - \hat V^\star_t(φ(s)), \qquad β^\star_t(s,a) \coloneqq Q^\star_t(s,a) - \hat Q^\star_t(φ(s),a), \] with the convention \(α^\star_{T+1} ≡ 0\). Then, for any \(t \in \{1,\dots,T\}\), \[\begin{align*} β^\star_t &= \hat \MISMATCH_t \hat V^\star_{t+1} + \DYNAMICS_t α^\star_{t+1}, \\ \ALPHABET T^{π^\star_t} β^\star_t &\le α^\star_t \le \ALPHABET T^{\hat π^\star_t \circ φ} β^\star_t. \end{align*}\]
Applying Lemma 6.3 with \(v_{t+1} = V^\star_{t+1}\) and \(\hat v_{t+1} = \hat V^\star_{t+1}\) gives \(β^\star_t = \hat \MISMATCH_t \hat V^\star_{t+1} + \DYNAMICS_t α^\star_{t+1}\). For the sandwich we use the two optimality properties, one at a time.
Upper bound. By optimality of \(\hat π^\star_t\) on the approximate side, \(\hat V^\star_t \circ φ = \ALPHABET T^{\hat π^\star_t \circ φ}(\hat Q^\star_t \circ φ)\), while on the true side \(V^\star_t = \ALPHABET T^\star Q^\star_t \le \ALPHABET T^{\hat π^\star_t \circ φ} Q^\star_t\). Therefore \[ α^\star_t = V^\star_t - \hat V^\star_t \circ φ \le \ALPHABET T^{\hat π^\star_t \circ φ} β^\star_t. \]
Lower bound. By optimality of \(π^\star_t\) on the true side, \(V^\star_t = \ALPHABET T^{π^\star_t} Q^\star_t\), while on the approximate side \(\hat V^\star_t \circ φ = \ALPHABET T^\star(\hat Q^\star_t \circ φ) \le \ALPHABET T^{π^\star_t}(\hat Q^\star_t \circ φ)\). Therefore \[ α^\star_t = V^\star_t - \hat V^\star_t \circ φ \ge \ALPHABET T^{π^\star_t} β^\star_t. \]
6.4.4 Model approximation bounds
As in the MDP case, optimality of \(V^\star\) gives \(V^{\hat π^\star \circ φ}_t \ge V^\star_t\), and since \(\hat V^{\hat π^\star} = \hat V^\star\) (so \(\hat V^{\hat π^\star}_t \circ φ = \hat V^\star_t \circ φ\)), \[ 0 \le V^{\hat π^\star \circ φ}_t - V^\star_t = α^{\hat π^\star}_t - α^\star_t. \] As before, we bound the right-hand side by finding \((α^+, β^+)\) and \((α^-, β^-)\) that obey the same recursions with inequalities instead of equalities.
Theorem 6.3 (Signed sample-path bound) Suppose that for each \(t \in \{1,\dots,T\}\) there exist functions \(α^+_t, α^-_t \colon \ALPHABET S \to \reals\) and \(β^+_t, β^-_t \colon \ALPHABET S \times \ALPHABET A \to \reals\) such that \[ β^-_T \le \hat \MISMATCH_T \hat V^\star_{T+1} \le β^+_T, \] and for \(t < T\), \[\begin{align*} β^-_t &\le \hat \MISMATCH_t \hat V^\star_{t+1} + \DYNAMICS_t α^-_{t+1}, \\ α^-_t &\le \ALPHABET T^{π^\star_t} β^-_t, \end{align*}\] and \[\begin{align*} β^+_t &\ge \hat \MISMATCH_t \hat V^\star_{t+1} + \DYNAMICS_t α^+_{t+1}, \\ α^+_t &\ge \ALPHABET T^{\hat π^\star_t \circ φ} β^+_t. \end{align*}\] Then, for all \(t\), \[ V^{\hat π^\star \circ φ}_t - V^\star_t \le α^+_t - α^-_t. \]
As in Theorem 6.1, a backward induction with Proposition 6.3 (for \(\hat π^\star\)) and Proposition 6.4 shows that \(α^+_t\) upper-bounds \(α^{\hat π^\star}_t\) and \(α^-_t\) lower-bounds \(α^\star_t\). Combining the two, \[ V^{\hat π^\star \circ φ}_t - V^\star_t = α^{\hat π^\star}_t - α^\star_t \le α^+_t - α^-_t. \]
A concrete construction that uses the best upper bound and relaxes the lower bound (so that we don’t need the knowledge of \(π^\star\)) is \[\begin{align*} α^+_t &= \ALPHABET T^{\hat π^\star_t \circ φ}\bigl( \hat \MISMATCH_t \hat V^\star_{t+1} + \DYNAMICS_t α^+_{t+1} \bigr), \\ α^-_t(s) &= \min_{a \in \ALPHABET C_t(s)} \Bigl[ \hat \MISMATCH_t \hat V^\star_{t+1} + \DYNAMICS_t α^-_{t+1} \Bigr](s,a), \end{align*}\] where \(\ALPHABET C_t(s) \subseteq \ALPHABET A\) is any set guaranteed to contain \(π^\star_t(s)\) (for example \(\ALPHABET C_t(s) = \ALPHABET A\), in which case \(α^-_t = \ALPHABET T^\star\bigl(\hat \MISMATCH_t \hat V^\star_{t+1} + \DYNAMICS_t α^-_{t+1}\bigr)\)).
6.4.5 Symmetric bounds
Taking absolute values gives a symmetric bound, exactly as in Theorem 6.2.
Theorem 6.4 (Absolute-value sample-path bound) Suppose that for each \(t \in \{1,\dots,T\}\) there exist functions \(α^{\mathrm{abs}}_t \colon \ALPHABET S \to \reals_{\ge 0}\) and \(β^{\mathrm{abs}}_t \colon \ALPHABET S \times \ALPHABET A \to \reals_{\ge 0}\) such that \[ β^{\mathrm{abs}}_T \ge \ABS{\hat \MISMATCH_T \hat V^\star_{T+1}}, \] and for \(t < T\), \[ β^{\mathrm{abs}}_t \ge \ABS{\hat \MISMATCH_t \hat V^\star_{t+1}} + \DYNAMICS_t α^{\mathrm{abs}}_{t+1}, \] and for all \(t\), \[ α^{\mathrm{abs}}_t \ge \max\Bigl\{ \ALPHABET T^{π^\star_t} β^{\mathrm{abs}}_t,\; \ALPHABET T^{\hat π^\star_t \circ φ} β^{\mathrm{abs}}_t \Bigr\}, \] where absolute values of \(Q\)-functions are pointwise. Then the lifted policy \(\hat π^\star \circ φ\) satisfies, for all \(t\), \[ \ABS{V^{\hat π^\star \circ φ}_t - V^\star_t} \le 2 α^{\mathrm{abs}}_t. \]
The proof is identical to that of Theorem 6.2, with \(\hat π^\star_t\) replaced by \(\hat π^\star_t \circ φ\). As before, the state-independent choice \[ α^{\mathrm{abs}}_t \equiv \sum_{\tau=t}^{T} \NORM{\hat \MISMATCH_\tau \hat V^\star_{\tau+1}} \] recovers the factor-of-two model-approximation bound of the state-abstraction lecture.
6.4.6 Computing the bounds
As before, the bound of Theorem 6.3 is not directly computable: the recursions use the true dynamics \(\DYNAMICS_t\), and the mismatch \(\hat \MISMATCH_t \hat V^\star_{t+1}\) depends on the true model. We obtain coarser bounds that live entirely on \(\hat {\ALPHABET S}\). Write \(\hat \DYNAMICS_t \colon \hat {\ALPHABET V} \to \hat {\ALPHABET Q}\) for the dynamics of \(\widehat{\ALPHABET M}\).
Let \(\F\) be as above, and write \(P_{φ,t}\) for the pushed-forward kernel \[ P_{φ,t}(\hat s' \mid s,a) \coloneqq P_t\bigl(φ^{-1}(\hat s') \mid s,a\bigr). \] Suppose we are given \(\hat {\ALPHABET S}\)-measurable cost bounds \(\hat ε^{+}_t, \hat ε^{-}_t \in \hat {\ALPHABET Q}\) with \[ \hat ε^{-}_t \circ φ \le c_t - \hat c_t \circ φ \le \hat ε^{+}_t \circ φ, \] and a \(\hat {\ALPHABET S}\)-measurable transition discrepancy \(\hat δ_t \in \hat {\ALPHABET Q}\) with \[ d_{\F}\bigl(P_{φ,t}(\cdot \mid s,a), \hat P_t(\cdot \mid φ(s),a)\bigr) \le \hat δ_t\bigl(φ(s),a\bigr) \] for all \((s,a)\) (for example, take \(\hat δ_t(\hat s,a)\) to be the supremum of the IPM distance over the fiber \(φ^{-1}(\hat s)\)).
We also restrict the value bounds to be \(\hat {\ALPHABET S}\)-measurable: \(α^\pm_t = \hat α^\pm_t \circ φ\) and \(β^\pm_t = \hat β^\pm_t \circ φ\) for some \(\hat α^\pm_t \colon \hat {\ALPHABET S} \to \reals\) and \(\hat β^\pm_t \in \hat {\ALPHABET Q}\). For any such \(\hat α\), the IPM inequality between \(P_{φ,t}\) and \(\hat P_t\) gives \[ (\hat \DYNAMICS_t \hat α) \circ φ - (\hat δ_t\, ρ_{\F}(\hat α)) \circ φ \le \DYNAMICS_t(\hat α \circ φ) \le (\hat \DYNAMICS_t \hat α) \circ φ + (\hat δ_t\, ρ_{\F}(\hat α)) \circ φ. \] Applying this to \(\hat α = \hat V^\star_{t+1}\) and using the definition of \(\hat \MISMATCH_t\) bounds the mismatch by quantities on \(\hat {\ALPHABET S}\): \[ (\hat ε^{-}_t - \hat δ_t\, ρ_{\F}(\hat V^\star_{t+1})) \circ φ \le \hat \MISMATCH_t \hat V^\star_{t+1} \le (\hat ε^{+}_t + \hat δ_t\, ρ_{\F}(\hat V^\star_{t+1})) \circ φ. \]
Combining these estimates, the recursions of Theorem 6.3 are implied by the \(\hat {\ALPHABET S}\)-side inequalities \[\begin{align*} \hat β^-_t &\le \hat ε^{-}_t - \hat δ_t\, ρ_{\F}(\hat V^\star_{t+1}) + \hat \DYNAMICS_t \hat α^-_{t+1} - \hat δ_t\, ρ_{\F}(\hat α^-_{t+1}), \\ α^-_t &\le \ALPHABET T^{π^\star_t} β^-_t \end{align*}\] (or a minimum of \(β^-_t(s,\cdot)\) over a candidate set containing \(π^\star_t(s)\)), and \[\begin{align*} \hat β^+_t &\ge \hat ε^{+}_t + \hat δ_t\, ρ_{\F}(\hat V^\star_{t+1}) + \hat \DYNAMICS_t \hat α^+_{t+1} + \hat δ_t\, ρ_{\F}(\hat α^+_{t+1}), \\ \hat α^+_t &\ge \ALPHABET T^{\hat π^\star_t} \hat β^+_t. \end{align*}\] Lifting via \(α^\pm_t = \hat α^\pm_t \circ φ\) and \(β^\pm_t = \hat β^\pm_t \circ φ\) (and using \(\ALPHABET T^{\hat π^\star_t \circ φ}( \hat β^+_t \circ φ) = (\ALPHABET T^{\hat π^\star_t} \hat β^+_t)\circ φ\)) yields valid bounds for Theorem 6.3. The entire recursion is thus computable from the approximate model together with the \(\hat {\ALPHABET S}\)-measurable discrepancies \((\hat ε^\pm_t, \hat δ_t)\).
Notes
In this lecture, we adapt material from Bozkurt et al. (2026).