8 Approximate Information States
8.1 Motivation
In the previous lecture, we showed that a partially observed problem admits a dynamic programming decomposition once an information state is available (Theorem 7.2).
In many practical scenarios, however, an exact information state is difficult to use, especially when the model is being learned. Useful exact compressions are rare. In a standard POMDP the natural information state is the belief \(b_t = \PR(S_t \mid H_t) \in Δ(\ALPHABET S)\), which is continuous and still hard to plan on; under learning one may not know the dynamics needed to run a Bayes filter to update the beliefs.
In this lecture, we characterize the features required of an information state in approximate form, and then use the model-approximation / state-abstraction results of Lecture 5 to quantify the error incurred when planning with an approximate information state (AIS). The starting point is that \(\{H_t\}\) itself forms a history-based MDP. An AIS is then a (time-varying) state abstraction of that MDP, so the mismatch / IPM bounds of Lecture 5 apply with \(\ALPHABET S_t = \ALPHABET H_t\).
8.2 The history-based MDP
We use the finite-horizon partially observed model of Lecture 7. Observations and actions generate the history \[ H_t = (Y_{1:t}, A_{1:t-1}), \] which updates as \[ H_{t+1} = (H_t, A_t, Y_{t+1}). \] A policy is a sequence \(π = (π_1,\dots,π_T)\) with \(A_t = π_t(H_t)\). With additive costs \(C(O_T) = \sum_{t=1}^T C_t\), the history DP of Theorem 7.1 is \[\begin{align*} Q^\star_t(h_t, a_t) &= \EXP\bigl[ C_t + V^\star_{t+1}(H_{t+1}) \bigm| H_t = h_t,\, A_t = a_t \bigr], \\ V^\star_t(h_t) &= \min_{a_t \in \ALPHABET A} Q^\star_t(h_t, a_t), \end{align*}\] with \(V^\star_{T+1} \equiv 0\).
This recursion is exactly the MDP dynamic program on the growing state space \(\{\ALPHABET H_t\}_{t=1}^T\): the next history is a controlled Markov kernel on \(\ALPHABET H_{t+1}\), and the per-step cost is the conditional expectation \(\EXP[C_t \mid H_t, A_t]\). Call this the history-based MDP.
An exact information state \(\{σ_t\}\) (Theorem 7.2) is an exact state abstraction of that MDP: properties (P1)–(P2) say that costs and next-summary laws factor through \(Z_t = σ_t(H_t)\), so the mismatch of Lecture 5 is identically zero. Approximate information states relax the same two properties.
8.3 Recall: state abstraction
We briefly recall the Lecture 5 dictionary; details and proofs live in the state-abstraction lecture.
Given a surjection \(φ \colon \ALPHABET S \to \hat{\ALPHABET S}\), lift any function \(\hat f\) on the abstract space by \(\hat f \circ φ\). Lifting is non-expansive (Lemma 5.1). For models \(\ALPHABET M\) and \(\widehat{\ALPHABET M}\) on different state spaces, the mismatch operator is \[ \hat\MISMATCH_t \hat v = \ENV_t(\hat v \circ φ) - (\hat\ENV_t \hat v) \circ φ. \] One-step, policy, and value errors are controlled by \(\NORM{\hat\MISMATCH_t \hat v}\) (Proposition 5.2). Let \(\def\F{\mathfrak{F}}\F\) be an IPM function class as in Lectures 3–5, with distance \(d_{\F}\) and Minkowski functional \(ρ_{\F}\). When the approximation is measured by \(d_{\F}\), \[ \NORM{\hat\MISMATCH_t \hat v} \le ε_{φ,t} + \hat δ_{φ,t}\, ρ_{\F}(\hat v) \] (Lemma 5.3), and the lifted abstract-optimal policy is within a factor-two sum of those one-step errors (Theorem 5.2).
Nothing in those theorems required \(\ALPHABET S\) to be a “physical” state. They apply equally with \(\ALPHABET S_t = \ALPHABET H_t\) and a time-dependent abstraction \(\hat σ_t\) (finite horizon makes time dependence harmless).
8.4 Approximate information state
Fix Banach spaces \(\{\ALPHABET Z_t\}_{t=1}^T\), a function class \(\F\), and tolerances \(\{(ε_t,δ_t)\}_{t=1}^T\).
Definition 8.1 (Approximate information state generator) A collection \(\{\hat σ_t, \hat c_t, \hat P_t\}_{t=1}^T\), with \[ \hat σ_t \colon \ALPHABET H_t \to \ALPHABET Z_t, \quad \hat c_t \colon \ALPHABET Z_t \times \ALPHABET A \to \reals, \quad \hat P_t \colon \ALPHABET Z_t \times \ALPHABET A \to Δ(\ALPHABET Z_{t+1}), \] is an \(\{(ε_t,δ_t)\}\)-AIS generator if \(Z_t = \hat σ_t(H_t)\) satisfies the following for every policy \(π\), every history \(h_t\), and every action \(a_t\):
(AP1) Approximate cost evaluation. \[ \ABS{ \EXP^π[C_t \mid H_t = h_t,\, A_t = a_t] - \hat c_t\bigl(\hat σ_t(h_t), a_t\bigr) } \le ε_t, \] where \(\hat c_t\bigl(\hat σ_t(h_t), a_t\bigr)\) does not depend on \(π\).
(AP2) Approximate self-prediction. Writing \[ μ^π_t(\,\cdot\,) = \PR^π\bigl(Z_{t+1} \in \cdot \bigm| H_t = h_t,\, A_t = a_t\bigr), \quad ν_t(\,\cdot\,) = \hat P_t\bigl(\,\cdot \mid \hat σ_t(h_t), a_t\bigr), \] we have \(d_{\F}(μ^π_t, ν_t) \le δ_t\), where \(ν_t\) does not depend on \(π\).
We often say that “\(\{Z_t\}_{t \ge 1}\) is an \((ε,δ)\)-AIS” when the generators are clear from context.
In general Borel models one also requires measurable optimal selectors for the approximate MDP on \(\ALPHABET Z_t\). For finite \(\ALPHABET Z_t\) and \(\ALPHABET A\) this is automatic, so we omit a separate measurable-selection hypothesis in this lecture and in Lecture 9.
8.4.1 AIS as state abstraction of the history-based MDP
Set \(φ = \hat σ_t\) (time-dependent) and take the abstract model \[ \widehat{\ALPHABET M}_t = \bigl\langle \ALPHABET Z_t,\, \ALPHABET A,\, \hat P_t,\, \hat c_t \bigr\rangle. \] Then (AP1)–(AP2) are exactly the cost and pushed-forward transition errors of an \((ε_t,δ_t)\)-approximation of the history-based MDP. Consequently Lemma 5.3 gives \[ \NORM{\hat\MISMATCH_t \hat v} \le ε_t + δ_t\, ρ_{\F}(\hat v) \] for every abstract continuation \(\hat v\).
8.4.2 Alternative characterization (AP2a)+(AP2b)
As with exact information states, (AP2) can be replaced by a deterministic update plus approximate observation prediction.
(AP2a) State-like update. There exist maps \(\hat φ_t\) such that \[ Z_{t+1} = \hat φ_t\bigl(Z_t, A_t, Y_{t+1}\bigr). \]
(AP2b) Approximate observation prediction. There exist measurable observation prediction kernels \(\{\hat P^Y_t \colon \ALPHABET Z_t \times \ALPHABET A \to Δ(\ALPHABET Y)\}\) such that for every policy \(π\), every history \(h_t\), and every action \(a_t\), writing \[ μ^{Y,π}_t(\,\cdot\,) = \PR^π\bigl(Y_{t+1} \in \cdot \bigm| H_t = h_t,\, A_t = a_t\bigr), \quad ν^Y_t(\,\cdot\,) = \hat P^Y_t\bigl(\,\cdot \mid \hat σ_t(h_t), a_t\bigr), \] we have \[ d_{\F}\bigl(μ^{Y,π}_t,\, ν^Y_t\bigr) \le \frac{δ_t}{κ_{\F}(\hat φ_t)}, \] where \(κ_{\F}(\hat φ_t)\) is defined as \[ κ_{\F}(\hat φ_t) = \sup_{h_t \in \ALPHABET H_t,\, a_t \in \ALPHABET A} κ_{\F}\bigl(\hat φ_t(\hat σ_t(h_t), a_t, \cdot)\bigr). \] Note that for the total variation distance \(κ_{\F}(\hat φ_t) = 1\); for the Kantorovich distance \(κ_{\F}(\hat φ_t)\) is equal to the Lipschitz uniform bound on the Lipschitz constant of \(\hat φ_t\) with respect to \(y_t\). Finally, \(ν^Y_t\) (equivalently \(\hat P^Y_t(\,\cdot \mid \hat σ_t(h_t), a_t)\)) does not depend on \(π\).
Proposition 8.1 ((AP2a) and (AP2b) imply (AP2)) If \((\hat σ_t, \hat c_t, \hat φ_t, \hat P^Y_t)\) satisfy (AP1), (AP2a), and (AP2b), then the pushforward kernel \[ \hat P_t(B \mid z, a) = \int \IND\bigl\{\hat φ_t(z, a, y) \in B\bigr\}\, \hat P^Y_t(dy \mid z, a) \] satisfies (AP2) with the same \(δ_t\). Thus \(\{(\hat σ_t, \hat c_t, \hat φ_t, \hat P^Y_t)\}\) is an AIS generator in the sense of (AP1)–(AP2).
Fix a policy \(π\), a history \(h_t\), and an action \(a_t\), and write \(z_t = \hat σ_t(h_t)\). By the law of total probability and (AP2a), the measures \(μ^π_t\) and \(ν_t\) in (AP2) are the pushforwards of \(μ^{Y,π}_t\) and \(ν^Y_t\) under \(y \mapsto \hat φ_t(z_t, a_t, y)\): \[\begin{align*} μ^π_t(B) &= \int \IND\bigl\{\hat φ_t(z_t, a_t, y) \in B\bigr\}\, μ^{Y,π}_t(dy), \\ ν_t(B) &= \int \IND\bigl\{\hat φ_t(z_t, a_t, y) \in B\bigr\}\, ν^Y_t(dy). \end{align*}\] Thus, for any real-valued function \(f\) on \(\ALPHABET Z_{t+1}\), \[\begin{align*} \int f\, dμ^π_t &= \int f\bigl(\hat φ_t(z_t, a_t, y)\bigr)\, μ^{Y,π}_t(dy), \\ \int f\, dν_t &= \int f\bigl(\hat φ_t(z_t, a_t, y)\bigr)\, ν^Y_t(dy). \end{align*}\] Therefore, for every \(f \in \F\), \[\begin{align*} \ABS{\int f\, dμ^π_t - \int f\, dν_t} &= \ABS{ \int f\bigl(\hat φ_t(z_t, a_t, y)\bigr)\, μ^{Y,π}_t(dy) - \int f\bigl(\hat φ_t(z_t, a_t, y)\bigr)\, ν^Y_t(dy) } \\ &\le κ_{\F}\bigl(\hat φ_t(z_t, a_t, \cdot)\bigr)\, d_{\F}(μ^{Y,π}_t, ν^Y_t), \end{align*}\] where the inequality is the contraction property of IPMs used to define \(κ_{\F}\) above. Taking the supremum over \(f \in \F\) and using the definition of \(κ_{\F}(\hat φ_t)\) together with (AP2b) yields \[ d_{\F}(μ^π_t, ν_t) \le κ_{\F}(\hat φ_t)\, d_{\F}(μ^{Y,π}_t, ν^Y_t) \le κ_{\F}(\hat φ_t) \cdot \frac{δ_t}{κ_{\F}(\hat φ_t)} = δ_t, \] which is (AP2).
This matches the (P2a)/(P2b) pattern of Lecture 7 (Proposition 7.1), with IPM slack in the observation channel.
8.5 Approximate DP and guarantees
Given an AIS generator, define the abstract Bellman recursion by \(\hat V^\star_{T+1} \equiv 0\) and, for \(t = T,\dots,1\), \[\begin{align} \hat Q^\star_t(z, a) &= \hat c_t(z, a) + \EXP_{\hat P_t}\bigl[\hat V^\star_{t+1}(Z_{t+1}) \bigm| Z_t = z,\, A_t = a\bigr], \label{eq:ais-Qt} \\ \hat V^\star_t(z) &= \min_{a \in \ALPHABET A} \hat Q^\star_t(z, a). \label{eq:ais-Vt} \end{align}\] Let \(\hat π^\star_t(z) \in \arg\min_a \hat Q^\star_t(z, a)\), and lift to histories by \(π_t = \hat π^\star_t \circ \hat σ_t\).
As in Lecture 5, the one-step discrepancy between the history-based MDP and the abstract model is measured by the mismatch operator with \(φ = \hat σ_t\): \[ \hat\MISMATCH_t \hat v = \ENV_t(\hat v \circ \hat σ_t) - (\hat\ENV_t \hat v) \circ \hat σ_t. \]
Theorem 8.1 (Approximate DP for an AIS) Suppose \(\{\hat σ_t, \hat c_t, \hat P_t\}\) is an AIS generator, and define \((\hat Q^\star_t, \hat V^\star_t)\) by \(\eqref{eq:ais-Qt}\)–\(\eqref{eq:ais-Vt}\). Set \(α_{T+1} = 0\) and \[ α_t = \sum_{\tau=t}^{T} \NORM{\hat\MISMATCH_τ \hat V^\star_{τ+1}}, \qquad t = T,\dots,1. \] Then, for every history \(h_t\) and action \(a_t\):
Value error. \[ \ABS{Q^\star_t(h_t,a_t) - \hat Q^\star_t\bigl(\hat σ_t(h_t), a_t\bigr)} \le α_t, \qquad \ABS{V^\star_t(h_t) - \hat V^\star_t\bigl(\hat σ_t(h_t)\bigr)} \le α_t. \]
Model approximation error. The lifted greedy policy \(π_t = \hat π^\star_t \circ \hat σ_t\) is \(2α_t\)-optimal: for every history \(h_t\) and action \(a_t\), \[ 0 \le Q^π_t(h_t,a_t) - Q^\star_t(h_t,a_t) \le 2α_t, \qquad 0 \le V^π_t(h_t) - V^\star_t(h_t) \le 2α_t. \]
This is Proposition 5.2 and Theorem 5.1 specialized to the history-based MDP with \(φ_t = \hat σ_t\) (and with the \(\hat V^\star\)-sided choice of one-step error).
The AIS axioms control the mismatch through the IPM bound of Lecture 5.
Corollary 8.1 (IPM form) If \(\{\hat σ_t, \hat c_t, \hat P_t\}\) is an \(\{(ε_t,δ_t)\}\)-AIS generator, then Lemma 5.3 gives \[ \NORM{\hat\MISMATCH_t \hat V^\star_{t+1}} \le ε_t + δ_t\, ρ_{\F}(\hat V^\star_{t+1}). \] Consequently the envelopes of Theorem 8.1 satisfy \[ α_t \le \sum_{\tau=t}^{T} \bigl( ε_τ + ρ_{\F}(\hat V^\star_{τ+1})\, δ_τ \bigr), \] or, recursively, \(α_{T+1} = 0\) and \[ α_t \le ε_t + ρ_{\F}(\hat V^\star_{t+1})\, δ_t + α_{t+1}. \]
8.6 Other generalizations
8.6.1 Stochastic AIS
So far the compression \(\hat σ_t \colon \ALPHABET H_t \to \ALPHABET Z_t\) has been deterministic. In applications (especially when learning a discrete code by stochastic gradient methods) it is convenient to allow a randomized compression: given \(H_t = h_t\), one draws \(Z_t\) from a kernel \(\hat σ_t(\,\cdot \mid h_t) \in Δ(\ALPHABET Z_t)\).
This does not require a separate theory. Realize the randomization by an auxiliary primitive random variable \(θ_t\) (independent of the system noise, with a known law), and write \[ Z_t = \tilde σ_t(H_t, θ_t) \] for a deterministic map \(\tilde σ_t\). Then \((H_t, θ_t)\) is just a larger history, and \(\tilde σ_t\) is an ordinary (deterministic) AIS compression of that history. The approximate cost \(\hat c_t\) and kernel \(\hat P_t\) are unchanged. All results of this lecture—mismatch bounds, Theorem 8.1, and Corollary 8.1—apply verbatim to \(\tilde σ_t\), and taking the expectation over \(θ_t\) recovers the statements for the original randomized compression.
8.6.2 Observation compression
In applications with high-dimensional sensors (e.g. video), one may first compress the observation alphabet by a fixed map \(q \colon \ALPHABET Y \to \hat{\ALPHABET Y}\) and work with the compressed observations \(\hat Y_t = q(Y_t)\). The corresponding compressed histories are \[ \hat H_t = (\hat Y_{1:t}, A_{1:t-1}). \] An AIS for the compressed history process is exactly an AIS in the sense of this lecture, applied to the partially observed system whose observations are \(\hat Y_t\) rather than \(Y_t\). The axioms (AP1)–(AP2), the mismatch operator, and the guarantees of Theorem 8.1 / Corollary 8.1 carry over unchanged; only the underlying observation channel has been replaced by \(q\).
8.6.3 Action compression
Suppose the planner is restricted to a quantized action set \(\hat{\ALPHABET A} \subset \ALPHABET A\), with a quantizer \(ψ \colon \ALPHABET A \to \hat{\ALPHABET A}\). The abstract model is then defined only for actions in \(\hat{\ALPHABET A}\): \(\hat c_t \colon \ALPHABET Z_t \times \hat{\ALPHABET A} \to \reals\) and \(\hat P_t \colon \ALPHABET Z_t \times \hat{\ALPHABET A} \to Δ(\ALPHABET Z_{t+1})\). The AIS axioms are restated by comparing the true action \(a_t\) on the left-hand side to its quantized version \(ψ(a_t)\) on the right-hand side.
(AP1) Approximate cost evaluation. For every policy \(π\), every history \(h_t\), and every action \(a_t \in \ALPHABET A\), \[ \ABS{ \EXP^π[C_t \mid H_t = h_t,\, A_t = a_t] - \hat c_t\bigl(\hat σ_t(h_t), ψ(a_t)\bigr) } \le ε_t, \] where \(\hat c_t\bigl(\hat σ_t(h_t), ψ(a_t)\bigr)\) does not depend on \(π\).
(AP2) Approximate self-prediction. Writing \[ μ^π_t(\,\cdot\,) = \PR^π\bigl(Z_{t+1} \in \cdot \bigm| H_t = h_t,\, A_t = a_t\bigr), \quad ν_t(\,\cdot\,) = \hat P_t\bigl(\,\cdot \mid \hat σ_t(h_t), ψ(a_t)\bigr), \] we have \(d_{\F}(μ^π_t, ν_t) \le δ_t\), where \(ν_t\) does not depend on \(π\).
The abstract DP is the usual Bellman recursion, but the \(\min\) (and the greedy policy \(\hat π^\star_t\)) run only over \(\hat{\ALPHABET A}\). Because \(\hat{\ALPHABET A} \subset \ALPHABET A\), a policy valued in \(\hat{\ALPHABET A}\) can be executed directly in the true model. The mismatch / IPM argument is the same as before; the policy gap improves from \(2α_t\) to \(α_t\) in the perfectly observed special case with \(\hat σ_t = \mathrm{id}\) and \((\hat c_t,\hat P_t) = (c_t,P_t)\) restricted to \(\hat{\ALPHABET A}\) (Subramanian et al. 2022 Cor. 19).
8.7 Beyond sup-norm bounds
The bound in Theorem 8.1 depends on the history only through the scalar \[ α_t = \sum_{\tau=t}^{T} \NORM{\hat\MISMATCH_τ \hat V^\star_{τ+1}}, \] and gives \(V^π_t - V^\star_t \le 2α_t\). This is the Lecture 5 abstraction argument (Theorem 5.1, Proposition 5.2) with \(\ALPHABET S_t = \ALPHABET H_t\) and \(φ_t = \hat σ_t\). The IPM form Corollary 8.1 is what Subramanian et al. (2022) uses.
In Lecture 6 we obtained tighter bounds by working with the pointwise mismatch \(\hat\MISMATCH_t \hat V^\star_{t+1}\) rather than its sup-norm. The signed envelopes \(α^\pm_t\), \(β^\pm_t\) give lower and upper bounds on \(V^{\hat π^\star \circ \hat σ}_t - V^\star_t\) (Theorem 6.1 when the two models share a state space; Theorem 6.3 when they are related by a lift \(φ\)). Taking absolute values recovers a pathwise bound that is never worse than the uniform sum in Theorem 8.1 (Theorem 6.4).
8.7.1 Sample-path bounds for AIS
An AIS is a state abstraction of the history-based MDP, so the same results apply with \[ \text{history-based MDP} \leftrightarrow \ALPHABET M, \quad \text{AIS abstract MDP} \leftrightarrow \widehat{\ALPHABET M}, \quad \hat σ_t \leftrightarrow φ_t. \] In particular, Lemma 6.3 through Theorem 6.3 give pathwise envelopes for \[ V^{\hat π^\star \circ \hat σ}_t(h_t) - V^\star_t(h_t) \] (and the corresponding \(Q\)-gaps). The one-step terms are the signed mismatches \(\hat\MISMATCH_t \hat V^\star_{t+1}\); the \((ε_t,δ_t)\) bounds from Corollary 8.1 still control their size via Lemma 5.3 (or the signed IPM corrections in Lecture 6).
The AIS axioms (AP1)–(AP2) do not change. What changes is how the mismatch is turned into a bound on \(V^π - V^\star\): pointwise rather than through the sup-norm. We do not restate the Lecture 6 recursions here; Theorem 8.1 remains the default statement for this lecture. A worked packet-drop channel with signed envelopes is in Proposition 8.2 below.
8.8 Examples
8.8.1 Exact information state
If \(\{σ_t\}\) is an exact information state and we take \(\hat σ_t = σ_t\), \(\hat c_t(z,a) = \EXP[C_t \mid Z_t = z, A_t = a]\), and \(\hat P_t\) equal to the true conditional law of \(Z_{t+1}\), then \(\NORM{\hat\MISMATCH_t \hat V^\star_{t+1}} = 0\) for all \(t\). Theorem 8.1 collapses to Theorem 7.2: \(α_t = 0\) and the lifted greedy policy is optimal.
8.8.2 MDP state abstraction
Suppose \(Y_t = S_t\) (perfect observation) with cost \(C_t = c_t(S_t, A_t)\), and let \(φ \colon \ALPHABET S \to \hat{\ALPHABET S}\) be a state abstraction with approximate model \((\hat P_t, \hat c_t)\) as in Lecture 5. Set \[ \hat σ_t(H_t) = φ(S_t). \] Then \((\hat σ_t, \hat c_t, \hat P_t)\) is an AIS of the history-based MDP, with the same \((ε_{φ,t}, \hat δ_{φ,t})\) as in Definition 5.1. State quantization in Lecture 5 is the special case where \(φ\) maps each cell to a representative. Thus Lecture 5 is AIS with identity compression of observations and nontrivial compression of the physical state.
8.8.3 Belief compression in POMDPs
Consider a standard POMDP. Quantize the beliefs using a quantization function \(φ\) such that \(d_{\rm TV}(b, φ(b)) \le r\) for all \(b \in Δ(\ALPHABET S)\). A concrete construction using type-lattice quantization is presented in Reznik (2011).
Take the approximate cost \[ \hat c_t(\hat b, a) = \sum_{s \in \ALPHABET S} \hat b(s)\, c_t(s,a), \] and approximate next-belief kernel equal to the Bayes update started from \(\hat b\) (followed by re-quantization). It can be shown than for this model (see Subramanian et al. (2022), Appendix C) \[ ε_t \le r \SPAN(c_t), \quad δ_t \le 3r. \] Then Corollary 8.1 gives an approximation bound for using the quantized beliefs.
8.8.4 Observations over a packet-drop channel
Model and AIS generator. Consider a finite-horizon POMDP in which the controller observes the state through an i.i.d. packet-drop channel: with probability \(p \in [0,1]\), independently of the past, \[ Y_t = \begin{cases} \mathfrak{E}, & \text{packet drop}, \\ S_t, & \text{otherwise}, \end{cases} \] where \(\mathfrak{E}\) is an erasure symbol. The observation channel itself is uncontrolled (no action enters the law of \(Y_t\) given \(S_t\)). The per-step cost is the conditional expectation \(c_t(h_t,a_t) = \int k_t(s,a_t)\, P(ds \mid h_t)\) of a bounded primitive state-action cost \(0 \le k_t(s,a) \le k_{\max}\).
Take the AIS generator with \(\ALPHABET Z_t = \ALPHABET S\), \[ \hat σ_t(y_{1:t}, a_{1:t-1}) = \begin{cases} y_t, & y_t \ne \mathfrak{E}, \\ s_{\mathrm{nom}}, & y_t = \mathfrak{E}, \end{cases} \] for a fixed nominal state \(s_{\mathrm{nom}} \in \ALPHABET S\), approximate cost \(\hat c_t(s,a) = k_t(s,a)\), and approximate transition \(\hat P_t = P_{S,t}\) equal to the true state kernel. Write \(d_t(h_t) \coloneqq \mathbf{1}_{\{y_t = \mathfrak{E}\}}\) for the drop indicator.
This is an abstract-model situation: the history-based MDP is \(\ALPHABET M\), the AIS MDP on \(\ALPHABET S\) is \(\widehat{\ALPHABET M}\), and \(φ_t = \hat σ_t\). On a non-drop, \(\hat σ_t(h_t) = S_t\) and the immediate cost matches. On a drop, \(\hat σ_t(h_t) = s_{\mathrm{nom}}\) and \(\hat c_t(s_{\mathrm{nom}},a) = k_t(s_{\mathrm{nom}},a)\), while the true conditional cost still lies in \([0,k_{\max}]\), so \[ -k_t(s_{\mathrm{nom}},a) \le c_t(h_t,a) - \hat c_t(s_{\mathrm{nom}},a) \le k_{\max} - k_t(s_{\mathrm{nom}},a). \] We choose total variation as the IPM as in the properties lecture (\(d_{\mathrm{TV}} = \NORM{\,\cdot\,}_1\), \(ρ_{\F}(v) = \tfrac12 \SPAN(v)\)). Take the (conservative) transition discrepancy \(\hat δ_t = 2\, d_t\), which yields an IPM correction \(\hat δ_t\, ρ_{\F}(\hat V^\star_{t+1}) = \SPAN(\hat V^\star_{t+1})\, d_t\) on each side; non-drop transition error of order \(p\) is absorbed into the backward recursion through the next drop indicator.
Signed envelopes. Apply the computable upper bounds from Lecture 6 with the action-dependent cost mismatches \[\begin{align*} \hat ε^+_t(h_t,a) &= \bigl(k_{\max} - k_t(s_{\mathrm{nom}},a)\bigr)\, d_t(h_t), \qquad \hat ε^-_t(h_t,a) = -k_t(s_{\mathrm{nom}},a)\, d_t(h_t), \end{align*}\] and \[\begin{align*} \hat δ_t\, ρ_{\F}(\hat V^\star_{t+1}) &= ω_t\, d_t, \qquad ω_t \coloneqq \SPAN(\hat V^\star_{t+1}), \end{align*}\] with \(ω_T \coloneqq 0\). For every \(a\), the width \(\hat ε^+_t(h_t,a) - \hat ε^-_t(h_t,a) = k_{\max}\, d_t(h_t)\) is action-independent. To obtain history envelopes that depend on \(h_t\) only through \(d_t\), replace the \(a\)-dependent bounds by the worst-case (over \(a\)) upper bounds \[ \underline{k}_t \coloneqq \min_{a \in \ALPHABET A} k_t(s_{\mathrm{nom}},a), \qquad \overline{k}_t \coloneqq \max_{a \in \ALPHABET A} k_t(s_{\mathrm{nom}},a), \] so that \[ \hat ε^+_t = \bigl(k_{\max} - \underline{k}_t\bigr)\, d_t, \qquad \hat ε^-_t = -\overline{k}_t\, d_t \] dominate the pointwise formulas for every \(a\). Because the drop channel is uncontrolled, once \(α^\pm_{t+1}\) depend on the history only through \(d_{t+1}\), the conditional expectation \(\DYNAMICS_t α^\pm_{t+1}\) is action-independent. The concrete construction after Theorem 6.3 therefore collapses to \[\begin{align*} α^+_T &= \bigl(k_{\max} - \underline{k}_T\bigr)\, d_T, \qquad α^-_T = -\overline{k}_T\, d_T, \end{align*}\] and for \(t < T\), \[\begin{align*} α^+_t &= \bigl(k_{\max} - \underline{k}_t + ω_t\bigr)\, d_t + \int α^+_{t+1}(h_t, a_t, y_{t+1})\, P(dy_{t+1} \mid h_t, a_t), \\ α^-_t &= \bigl(-\overline{k}_t - ω_t\bigr)\, d_t + \int α^-_{t+1}(h_t, a_t, y_{t+1})\, P(dy_{t+1} \mid h_t, a_t). \end{align*}\]
Proposition 8.2 (Packet-drop signed sample-path bound) The envelopes above satisfy the hypotheses of Theorem 6.3. Consequently the lifted AIS policy \(π_t = \hat π^\star_t \circ \hat σ_t\) obeys, for every \(t\) and every history \(h_t\), \[ V^π_t(h_t) - V^\star_t(h_t) \le α^+_t(h_t) - α^-_t(h_t). \] Moreover \(α^\pm_t\) admit the closed forms \[ α^+_t = ξ^+_t + \bigl(k_{\max} - \underline{k}_t + ω_t\bigr)\, d_t, \qquad α^-_t = ξ^-_t + \bigl(-\overline{k}_t - ω_t\bigr)\, d_t, \] where \(ξ^\pm_{T} = 0\), \(ξ^+_{T-1} = p(k_{\max} - \underline{k}_T)\), \(ξ^-_{T-1} = -p\,\overline{k}_T\), and for \(t < T-1\), \[\begin{align*} ξ^+_t &= ξ^+_{t+1} + p\bigl(k_{\max} - \underline{k}_{t+1} + ω_{t+1}\bigr), \\ ξ^-_t &= ξ^-_{t+1} + p\bigl(-\overline{k}_{t+1} - ω_{t+1}\bigr). \end{align*}\] In particular the gap \(\varphi_t \coloneqq α^+_t - α^-_t\) is \[ \varphi_t = ζ_t + \bigl(k_{\max} - \underline{k}_t + \overline{k}_t + 2ω_t\bigr)\, d_t, \] with \(ζ_T = 0\), \(ζ_{T-1} = p\bigl(k_{\max} - \underline{k}_T + \overline{k}_T\bigr)\), and for \(t < T-1\), \[ ζ_t = ζ_{t+1} + p\bigl(k_{\max} - \underline{k}_{t+1} + \overline{k}_{t+1} + 2ω_{t+1}\bigr). \] When \(k_t(s_{\mathrm{nom}},\,\cdot\,)\) does not depend on \(a\), one has \(\underline{k}_t = \overline{k}_t\) and the drop coefficient in \(\varphi_t\) simplifies to \(k_{\max} + 2ω_t\).
On a drop, the pointwise cost bounds and the TV correction give, for every \(a\), \[ -k_t(s_{\mathrm{nom}},a) - ω_t \le \bigl[\hat\MISMATCH_t \hat V^\star_{t+1}\bigr](h_t,a) \le k_{\max} - k_t(s_{\mathrm{nom}},a) + ω_t. \] The worst-case upper bounds \(\hat ε^\pm_t\) above dominate these for all \(a\), and yield the action-free one-step interval \(\bigl[-\overline{k}_t - ω_t,\, k_{\max} - \underline{k}_t + ω_t\bigr]\) on a drop. On a non-drop the same upper bounds are zero (under the discrepancy choice above). Substituting into the concrete \(α^\pm\) construction of Theorem 6.3 yields the displayed recursion. The ansatz that \(α^\pm_t\) depends on \(h_t\) only through \(d_t\) is preserved backward because \[ \int α^\pm_{t+1}\, P(dy_{t+1} \mid h_t, a_t) = ξ^\pm_{t+1} + p \cdot (\text{drop coefficient at } t+1), \] independently of \((h_t,a_t)\) and of whether \(d_t = 1\). The constants \(ξ^\pm_t\) are exactly those drop contributions. Subtracting the two envelopes produces \(\varphi_t = ζ_t + (k_{\max} - \underline{k}_t + \overline{k}_t + 2ω_t)\, d_t\) with the claimed recursion for \(ζ_t\). Theorem 6.3 then gives \(V^π_t - V^\star_t \le \varphi_t\).
Averaging at time \(1\) over \(H_1 = Y_1\) produces the performance bound \[ \EXP\bigl[V^π_1(H_1)\bigr] - \EXP\bigl[V^\star_1(H_1)\bigr] \le ζ_1 + p\bigl(k_{\max} - \underline{k}_1 + \overline{k}_1 + 2\,\SPAN(\hat V^\star_2)\bigr). \] Both this expectation and the pointwise gap \(\varphi_t\) vanish as \(p \to 0\).
The classical uniform (history-independent) AIS bound of Theorem 8.1 yields a constant \(\bar α_t\) that does not tend to \(0\) as \(p \to 0\), since it must cover the worst-case drop at every time. The sample-path envelopes repair that defect.
Notes
In this lecture, we follow Subramanian et al. (2022) for finite-horizon AIS. Belief compression and \(ε\)-sufficient statistics are as in §3.3, building on François-Lavet et al. (2019) and type-lattice quantization Reznik (2011). Sample-path refinements of the AIS value / policy gaps follow by specializing Lecture 6 (Take 4) to the history-based MDP with \(φ_t = \hat σ_t\) (Bozkurt et al. 2026).