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 model operator \(\MODEL_t \colon \ALPHABET V \to \ALPHABET Q\) includes both the cost and the transition: \[ [\MODEL_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 \(\MODEL_t v = c_t + \DYNAMICS_t v\). As before, the mismatch is \(\MISMATCH_t v = \MODEL_t v - \hat \MODEL_t v\).
Lemma 6.1 For any \(v, \hat v \in \ALPHABET V\), \[ \MODEL_t v - \MODEL_t \hat v = \DYNAMICS_t \bigl[ v - \hat v \bigr]. \]
The cost terms cancel: \[\begin{align*} \MODEL_t v - \MODEL_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 = \MODEL_t v_{t+1}\) and \(\hat q_t = \hat \MODEL_t \hat v_{t+1}\). Then \[ q_t - \hat q_t = \MISMATCH_t \hat v_{t+1} + \bigl[ \MODEL_t v_{t+1} - \MODEL_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 &= \MODEL_t v_{t+1} - \hat \MODEL_t \hat v_{t+1} \\ &= \bigl[ \MODEL_t \hat v_{t+1} - \hat \MODEL_t \hat v_{t+1} \bigr] + \bigl[ \MODEL_t v_{t+1} - \MODEL_t \hat v_{t+1} \bigr] \\ &= \MISMATCH_t \hat v_{t+1} + \bigl[ \MODEL_t v_{t+1} - \MODEL_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\}\) and all \((s,a) \in \ALPHABET S \times \ALPHABET A\), \[\begin{align*} β^π_t &= Δ^π_t + \DYNAMICS_t α^π_{t+1}, \\ α^π_t(s) &= β^π_t\bigl(s, π_t(s)\bigr), \end{align*}\] where \[ Δ^π_t \coloneqq \MISMATCH_t \hat V^π_{t+1}. \]
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 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 = Δ^π_t + \DYNAMICS_t α^π_{t+1}. \] Evaluating at \(a = π_t(s)\) and using that \(π_t\) is deterministic, \[ α^π_t(s) = V^π_t(s) - \hat V^π_t(s) = Q^π_t\bigl(s, π_t(s)\bigr) - \hat Q^π_t\bigl(s, π_t(s)\bigr) = β^π_t\bigl(s, π_t(s)\bigr). \]
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\}\) and all \((s,a) \in \ALPHABET S \times \ALPHABET A\), \[\begin{align*} β^\star_t &= Δ^\star_t + \DYNAMICS_t α^\star_{t+1}, \\ β^\star_t\bigl(s, π^\star_t(s)\bigr) &\le α^\star_t(s) \le β^\star_t\bigl(s, \hat π^\star_t(s)\bigr), \end{align*}\] where \[ Δ^\star_t \coloneqq \MISMATCH_t \hat V^\star_{t+1}. \]
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 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 = Δ^\star_t + \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(s) = \hat Q^\star_t\bigl(s, \hat π^\star_t(s)\bigr)\), while on the true side \(V^\star_t(s) = \inf_{a} Q^\star_t(s,a) \le Q^\star_t\bigl(s, \hat π^\star_t(s)\bigr)\). Therefore \[ α^\star_t(s) = V^\star_t(s) - \hat V^\star_t(s) \le Q^\star_t\bigl(s, \hat π^\star_t(s)\bigr) - \hat Q^\star_t\bigl(s, \hat π^\star_t(s)\bigr) = β^\star_t\bigl(s, \hat π^\star_t(s)\bigr). \]
Lower bound. By optimality of \(π^\star_t\) on the true side, \(V^\star_t(s) = Q^\star_t\bigl(s, π^\star_t(s)\bigr)\), while on the approximate side \(\hat V^\star_t(s) = \inf_{a} \hat Q^\star_t(s,a) \le \hat Q^\star_t\bigl(s, π^\star_t(s)\bigr)\). Therefore \[ α^\star_t(s) = V^\star_t(s) - \hat V^\star_t(s) \ge Q^\star_t\bigl(s, π^\star_t(s)\bigr) - \hat Q^\star_t\bigl(s, π^\star_t(s)\bigr) = β^\star_t\bigl(s, π^\star_t(s)\bigr). \]
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(s,a) \le Δ^\star_T(s,a) \le β^+_T(s,a), \] and for \(t < T\), \[\begin{align*} β^-_t(s,a) &\le Δ^\star_t(s,a) + \sum_{s'} α^-_{t+1}(s') P_t(s' \mid s,a), \\ α^-_t(s) &\le β^-_t\bigl(s, π^\star_t(s)\bigr), \end{align*}\] and \[\begin{align*} β^+_t(s,a) &\ge Δ^\star_t(s,a) + \sum_{s'} α^+_{t+1}(s') P_t(s' \mid s,a), \\ α^+_t(s) &\ge β^+_t\bigl(s, \hat π^\star_t(s)\bigr), \end{align*}\] where \(Δ^\star_t\) is as in Proposition 6.2. Then, for all \(t\) and \(s\), \[ V^{\hat π^\star}_t(s) - V^\star_t(s) \le α^+_t(s) - α^-_t(s). \]
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(s) - V^\star_t(s) = α^{\hat π^\star}_t(s) - α^\star_t(s) \le α^+_t(s) - α^-_t(s). \]
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(s) &= Δ^\star_t\bigl(s, \hat π^\star_t(s)\bigr) + \sum_{s'} α^+_{t+1}(s') P_t\bigl(s' \mid s, \hat π^\star_t(s)\bigr), \\ α^-_t(s) &= \min_{a \in \ALPHABET C_t(s)} \Bigl[ Δ^\star_t(s,a) + \sum_{s'} α^-_{t+1}(s') P_t(s' \mid s,a) \Bigr], \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\), or a structural candidate set that does not require computing \(π^\star\) explicitly). Theorem 6.1 then guarantees \[ V^{\hat π^\star}_t(s) - V^\star_t(s) \le α^+_t(s) - α^-_t(s). \]
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(s,a) \ge \ABS{Δ^\star_T(s,a)}, \] and for \(t < T\), \[ β^{\mathrm{abs}}_t(s,a) \ge \ABS{Δ^\star_t(s,a)} + \sum_{s' \in \ALPHABET S} α^{\mathrm{abs}}_{t+1}(s') P_t(s' \mid s,a), \] and for all \(t\), \[ α^{\mathrm{abs}}_t(s) \ge \max\Bigl\{ β^{\mathrm{abs}}_t\bigl(s, π^\star_t(s)\bigr),\; β^{\mathrm{abs}}_t\bigl(s, \hat π^\star_t(s)\bigr) \Bigr\}, \] where \(Δ^\star_t\) is as in Proposition 6.2. Then the policy \(\hat π^\star\) satisfies, for all \(t\) and \(s\), \[ \ABS{V^{\hat π^\star}_t(s) - V^\star_t(s)} \le 2 α^{\mathrm{abs}}_t(s). \]
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(s) - V^\star_t(s) \le α^+_t(s) - α^-_t(s) = 2 α^{\mathrm{abs}}_t(s). \] For the matching lower side, optimality of \(V^\star\) yields \(V^{\hat π^\star}_t(s) - V^\star_t(s) \ge 0 \ge -2 α^{\mathrm{abs}}_t(s)\) because \(α^{\mathrm{abs}}_t \ge 0\). Combining the two inequalities gives the claim.
A feasible (but state-independent) choice is \[ α^{\mathrm{abs}}_t(s) \equiv \sum_{\tau=t}^{T} \NORM{\MISMATCH_\tau \hat V^\star_{\tau+1}}, \qquad β^{\mathrm{abs}}_t(s,a) \equiv \NORM{\MISMATCH_t \hat V^\star_{t+1}} + \sum_{s'} α^{\mathrm{abs}}_{t+1}(s') P_t(s' \mid s,a). \] 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 kernel \(P_t\). Moreover, computing the mismatch \(Δ^\star_t = \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.
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 have bounds on the per-step cost difference \[ ε^{-}_t(s,a) \le c_t(s,a) - \hat c_t(s,a) \le ε^{+}_t(s,a). \] Define \[ δ_t(s,a) \coloneqq d_{\F}\bigl(P_t(\cdot \mid s,a), \hat P_t(\cdot \mid s,a)\bigr). \] The defining IPM inequality then yields, for any \(v \colon \ALPHABET S \to \reals\), \[ \ABS{ \sum_{s'} v(s') P_t(s' \mid s,a) - \sum_{s'} v(s') \hat P_t(s' \mid s,a) } \le δ_t(s,a)\, ρ_{\F}(v). \] Equivalently, \[ \sum_{s'} v(s') \hat P_t(s' \mid s,a) - δ_t(s,a)\, ρ_{\F}(v) \le \sum_{s'} v(s') P_t(s' \mid s,a) \le \sum_{s'} v(s') \hat P_t(s' \mid s,a) + δ_t(s,a)\, ρ_{\F}(v). \] Applying this to \(v = \hat V^\star_{t+1}\) and using the definition of \(\MISMATCH_t\) also bounds the one-step mismatch: \[ ε^{-}_t(s,a) - δ_t(s,a)\, ρ_{\F}(\hat V^\star_{t+1}) \le Δ^\star_t(s,a) \le ε^{+}_t(s,a) + δ_t(s,a)\, ρ_{\F}(\hat V^\star_{t+1}). \]
Thus both the mismatch and any average with respect to the true dynamics can be replaced by approximate-model quantities plus or minus an IPM correction. In particular, the lower recursion of Theorem 6.1 is implied by \[ β^-_t(s,a) \le ε^{-}_t(s,a) - δ_t(s,a)\, ρ_{\F}(\hat V^\star_{t+1}) + \sum_{s'} α^-_{t+1}(s') \hat P_t(s' \mid s,a) - δ_t(s,a)\, ρ_{\F}(α^-_{t+1}), \] and the upper recursion is implied by \[ β^+_t(s,a) \ge ε^{+}_t(s,a) + δ_t(s,a)\, ρ_{\F}(\hat V^\star_{t+1}) + \sum_{s'} α^+_{t+1}(s') \hat P_t(s' \mid s,a) + δ_t(s,a)\, ρ_{\F}(α^+_{t+1}). \] The resulting bounds are typically looser than those built from \(P_t\), but they are computable from the approximate model together with model error \((ε_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 = \MODEL_t (\hat v \circ φ) - (\hat \MODEL_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 = \MODEL_t v_{t+1}\) and \(\hat q_t = \hat \MODEL_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 \(\MODEL_t(\hat v_{t+1} \circ φ)\): \[\begin{align*} q_t - \hat q_t \circ φ &= \bigl[ \MODEL_t(\hat v_{t+1} \circ φ) - (\hat \MODEL_t \hat v_{t+1}) \circ φ \bigr] + \bigl[ \MODEL_t v_{t+1} - \MODEL_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\}\) and all \((s,a) \in \ALPHABET S \times \ALPHABET A\), \[\begin{align*} β^{\hat π}_t &= Δ^{\hat π}_t + \DYNAMICS_t α^{\hat π}_{t+1}, \\ α^{\hat π}_t(s) &= β^{\hat π}_t\bigl(s, \hat π_t(φ(s))\bigr), \end{align*}\] where \[ Δ^{\hat π}_t \coloneqq \hat \MISMATCH_t \hat V^{\hat π}_{t+1}. \]
Recall that \(Q^{\hat π \circ φ}_t = \MODEL_t V^{\hat π \circ φ}_{t+1}\) and \(\hat Q^{\hat π}_t = \hat \MODEL_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 π}_t + \DYNAMICS_t α^{\hat π}_{t+1}. \] Since the lifted policy takes action \(\hat π_t(φ(s))\) at state \(s\), evaluating at \(a = \hat π_t(φ(s))\) gives \(V^{\hat π \circ φ}_t(s) = Q^{\hat π \circ φ}_t\bigl(s, \hat π_t(φ(s))\bigr)\) and \(\hat V^{\hat π}_t(φ(s)) = \hat Q^{\hat π}_t\bigl(φ(s), \hat π_t(φ(s))\bigr)\), so \(α^{\hat π}_t(s) = β^{\hat π}_t\bigl(s, \hat π_t(φ(s))\bigr)\).
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\}\) and all \((s,a) \in \ALPHABET S \times \ALPHABET A\), \[\begin{align*} β^\star_t &= Δ^\star_t + \DYNAMICS_t α^\star_{t+1}, \\ β^\star_t\bigl(s, π^\star_t(s)\bigr) &\le α^\star_t(s) \le β^\star_t\bigl(s, \hat π^\star_t(φ(s))\bigr), \end{align*}\] where \[ Δ^\star_t \coloneqq \hat \MISMATCH_t \hat V^\star_{t+1}. \]
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 = Δ^\star_t + \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(φ(s)) = \hat Q^\star_t\bigl(φ(s), \hat π^\star_t(φ(s))\bigr)\), while on the true side \(V^\star_t(s) = \inf_a Q^\star_t(s,a) \le Q^\star_t\bigl(s, \hat π^\star_t(φ(s))\bigr)\). Therefore \(α^\star_t(s) \le β^\star_t\bigl(s, \hat π^\star_t(φ(s))\bigr)\).
Lower bound. By optimality of \(π^\star_t\) on the true side, \(V^\star_t(s) = Q^\star_t\bigl(s, π^\star_t(s)\bigr)\), while on the approximate side \(\hat V^\star_t(φ(s)) = \inf_a \hat Q^\star_t(φ(s),a) \le \hat Q^\star_t\bigl(φ(s), π^\star_t(s)\bigr)\). Therefore \(α^\star_t(s) \ge β^\star_t\bigl(s, π^\star_t(s)\bigr)\).
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(s) - V^\star_t(s) = α^{\hat π^\star}_t(s) - α^\star_t(s). \] 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(s,a) \le Δ^\star_T(s,a) \le β^+_T(s,a), \] and for \(t < T\), \[\begin{align*} β^-_t(s,a) &\le Δ^\star_t(s,a) + \sum_{s'} α^-_{t+1}(s') P_t(s' \mid s,a), \\ α^-_t(s) &\le β^-_t\bigl(s, π^\star_t(s)\bigr), \end{align*}\] and \[\begin{align*} β^+_t(s,a) &\ge Δ^\star_t(s,a) + \sum_{s'} α^+_{t+1}(s') P_t(s' \mid s,a), \\ α^+_t(s) &\ge β^+_t\bigl(s, \hat π^\star_t(φ(s))\bigr), \end{align*}\] where \(Δ^\star_t\) is as in Proposition 6.4. Then, for all \(t\) and \(s\), \[ V^{\hat π^\star \circ φ}_t(s) - V^\star_t(s) \le α^+_t(s) - α^-_t(s). \]
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(s) - V^\star_t(s) = α^{\hat π^\star}_t(s) - α^\star_t(s) \le α^+_t(s) - α^-_t(s). \]
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(s) &= Δ^\star_t\bigl(s, \hat π^\star_t(φ(s))\bigr) + \sum_{s'} α^+_{t+1}(s') P_t\bigl(s' \mid s, \hat π^\star_t(φ(s))\bigr), \\ α^-_t(s) &= \min_{a \in \ALPHABET C_t(s)} \Bigl[ Δ^\star_t(s,a) + \sum_{s'} α^-_{t+1}(s') P_t(s' \mid s,a) \Bigr], \end{align*}\] where \(\ALPHABET C_t(s) \subseteq \ALPHABET A\) is any set guaranteed to contain \(π^\star_t(s)\).
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(s,a) \ge \ABS{Δ^\star_T(s,a)}, \] and for \(t < T\), \[ β^{\mathrm{abs}}_t(s,a) \ge \ABS{Δ^\star_t(s,a)} + \sum_{s' \in \ALPHABET S} α^{\mathrm{abs}}_{t+1}(s') P_t(s' \mid s,a), \] and for all \(t\), \[ α^{\mathrm{abs}}_t(s) \ge \max\Bigl\{ β^{\mathrm{abs}}_t\bigl(s, π^\star_t(s)\bigr),\; β^{\mathrm{abs}}_t\bigl(s, \hat π^\star_t(φ(s))\bigr) \Bigr\}, \] where \(Δ^\star_t\) is as in Proposition 6.4. Then the lifted policy \(\hat π^\star \circ φ\) satisfies, for all \(t\) and \(s\), \[ \ABS{V^{\hat π^\star \circ φ}_t(s) - V^\star_t(s)} \le 2 α^{\mathrm{abs}}_t(s). \]
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(s) \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 kernel \(P_t\), and the mismatch \(Δ^\star_t = \hat \MISMATCH_t \hat V^\star_{t+1}\) depends on the true model. We obtain coarser bounds that live entirely on \(\hat {\ALPHABET S}\).
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}\) such that for all \((s,a)\), \[ \hat ε^{-}_t\bigl(φ(s),a\bigr) \le c_t(s,a) - \hat c_t\bigl(φ(s),a\bigr) \le \hat ε^{+}_t\bigl(φ(s),a\bigr). \] Similarly, suppose we have a \(\hat {\ALPHABET S}\)-measurable transition discrepancy \(\hat δ_t \in \hat {\ALPHABET Q}\) such that for all \((s,a)\), \[ 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 example, one may 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(s,a) = \hat β^\pm_t(φ(s),a)\) for some \(\hat α^\pm_t \colon \hat {\ALPHABET S} \to \reals\) and \(\hat β^\pm_t \in \hat {\ALPHABET Q}\). Then, for any such \(\hat α\), \[ \sum_{s'} (\hat α \circ φ)(s') P_t(s' \mid s,a) = \sum_{\hat s'} \hat α(\hat s') P_{φ,t}(\hat s' \mid s,a), \] and the IPM inequality gives \[ \sum_{\hat s'} \hat α(\hat s') \hat P_t(\hat s' \mid φ(s),a) - \hat δ_t\bigl(φ(s),a\bigr)\, ρ_{\F}(\hat α) \le \sum_{s'} (\hat α \circ φ)(s') P_t(s' \mid s,a) \le \sum_{\hat s'} \hat α(\hat s') \hat P_t(\hat s' \mid φ(s),a) + \hat δ_t\bigl(φ(s),a\bigr)\, ρ_{\F}(\hat α). \] 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\bigl(φ(s),a\bigr) - \hat δ_t\bigl(φ(s),a\bigr)\, ρ_{\F}(\hat V^\star_{t+1}) \le Δ^\star_t(s,a) \le \hat ε^{+}_t\bigl(φ(s),a\bigr) + \hat δ_t\bigl(φ(s),a\bigr)\, ρ_{\F}(\hat V^\star_{t+1}). \]
Combining these estimates, the lower recursion of Theorem 6.3 is implied by the \(\hat {\ALPHABET S}\)-side inequality \[ \hat β^-_t(\hat s,a) \le \hat ε^{-}_t(\hat s,a) - \hat δ_t(\hat s,a)\, ρ_{\F}(\hat V^\star_{t+1}) + \sum_{\hat s'} \hat α^-_{t+1}(\hat s') \hat P_t(\hat s' \mid \hat s,a) - \hat δ_t(\hat s,a)\, ρ_{\F}(\hat α^-_{t+1}), \] and the upper recursion is implied by \[ \hat β^+_t(\hat s,a) \ge \hat ε^{+}_t(\hat s,a) + \hat δ_t(\hat s,a)\, ρ_{\F}(\hat V^\star_{t+1}) + \sum_{\hat s'} \hat α^+_{t+1}(\hat s') \hat P_t(\hat s' \mid \hat s,a) + \hat δ_t(\hat s,a)\, ρ_{\F}(\hat α^+_{t+1}). \] The corresponding anchors are \(\hat α^-_t(\hat s) \le \hat β^-_t\bigl(\hat s, π^\star_t(s)\bigr)\) for some \(s \in φ^{-1}(\hat s)\) (or a minimum over a candidate set), and \(\hat α^+_t(\hat s) \ge \hat β^+_t\bigl(\hat s, \hat π^\star_t(\hat s)\bigr)\). Lifting back via \(α^\pm_t = \hat α^\pm_t \circ φ\) and \(β^\pm_t(s,a) = \hat β^\pm_t(φ(s),a)\) 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
The material for this lecture is adapted from Bozkurt et al. (2026).