9 Certainty equivalence in POMDPs
9.1 Classical certainty equivalence
In linear-quadratic-Gaussian (LQG) control with output feedback, the optimal control law has the following structure. The optimal action at each time is obtained by evaluating the optimal state-feedback policy of the fully observed stochastic LQG system at the MMSE state estimate: if \(\hat π^\star\) is optimal for that fully observed problem and \(σ_t(h_t) = \EXP[S_t \mid H_t = h_t]\) is the MMSE estimate, then \[ π_t(h_t) = \hat π^\star_t\bigl(σ_t(h_t)\bigr). \]
The comparison model \(\ALPHABET M\) is fully observed but still stochastic. One does not replace process noise by its mean and then solve a deterministic open-loop problem. (That different idea is sometimes also called certainty equivalence in stochastic control; we do not treat that idea here.)
In LQG this construction is optimal. Outside LQG, composing a fully observed optimal policy with a state estimate is a heuristic. In the rest of this lecture, we make that heuristic quantitative for finite POMDPs.
9.2 Generalized CE for finite POMDPs
Fix a finite-horizon POMDP with finite spaces \(\ALPHABET S\), \(\ALPHABET A\), \(\ALPHABET Y\), history \(H_t = (Y_{1:t}, A_{1:t-1})\), and additive costs \(C_t = c_t(S_t, A_t)\). Write \(V^π_t(h_t)\) and \(V^\star_t(h_t)\) for the history value of a policy \(π\) and for the optimal history value, as in lecture 7.
Let \(\ALPHABET M\) be the associated fully observed MDP \[ \ALPHABET M = \bigl\langle \ALPHABET S, \ALPHABET A, P, c, T \bigr\rangle, \] in which the controller sees \(S_t\) at time \(t\) and \(P_t(\cdot \mid s, a)\) is the state transition kernel of the POMDP. Let \(\hat π^\star = (\hat π^\star_1,\dots,\hat π^\star_T)\) denote the optimal policy of the MDP and \(\{\hat V^\star_t\}_{t=1}^T\) be the corresponding optimal value function.
Consider an arbitrary sequence of estimators \(σ_t \colon \ALPHABET H_t \to \ALPHABET S\) that generate a state estimate from the history. For example, this could be the conditional mean, MAP estimate, the last observation, and so on. Write \(\hat S_t = σ_t(H_t)\) for the resulting estimate. The certainty equivalent policy generated by \(\{σ_t\}\) is \[ π^{\mathrm{CE}}_t(h_t) = \hat π^\star_t\bigl(σ_t(h_t)\bigr). \] In words: pretend the estimate is the true state, and play the optimal fully observed action. In the language of lecture 8 this is exactly the lifted AIS policy \(π_t = \hat π^\star_t \circ σ_t\). We are interested in quantifying the sub-optimality gap of this policy.
9.2.1 Quality of estimation
Let \(\ALPHABET S\) be a metric space with a metric \(d_{\ALPHABET S}\). Define the conditional estimation error \[\begin{equation}\label{eq:ce-eta-local} η_t(h_t) \coloneqq \EXP\bigl[ d_{\ALPHABET S}\bigl(S_t, σ_t(h_t)\bigr) \bigm| H_t = h_t \bigr], \end{equation}\] with the convention \(η_{T+1} \equiv 0\). By the belief lemma of lecture 7 (Lemma 7.2), the conditional law of \(S_t\) given \(h_t\) does not depend on the control policy, so \(η_t(h_t)\) is a property of the observation model and the estimator alone.
9.3 Smoothness assumption
Assume the cost and dynamics of \(\ALPHABET M\) are Lipschitz in the state: there exist constants \(L^c_t, L^P_t \ge 0\) such that for all \(s,\tilde s \in \ALPHABET S\) and \(a \in \ALPHABET A\), \[\begin{align} \ABS{c_t(s,a) - c_t(\tilde s,a)} &\le L^c_t\, d_{\ALPHABET S}(s,\tilde s), \label{eq:ce-Lip-c} \\ W_1\bigl( P_t(\cdot \mid s,a),\, P_t(\cdot \mid \tilde s,a) \bigr) &\le L^P_t\, d_{\ALPHABET S}(s,\tilde s). \label{eq:ce-Lip-P} \end{align}\] As in Theorem 3.3, \[ \operatorname{Lip}(\hat V^\star_t) \le L^c_t + L^P_t\, \operatorname{Lip}(\hat V^\star_{t+1}), \] with \(\operatorname{Lip}(\hat V^\star_{T+1}) = 0\). Thus Lipschitz constants of \(\hat V^\star\) are controlled by \(\{L^c_t, L^P_t\}\) alone.
9.4 Main insight: the CE generator is an AIS
Certainty equivalence is an AIS policy for a concrete generator whose pointwise errors are linear in \(η_t(h_t)\). The approximate MDP is exactly the fully observed model \(\ALPHABET M\), and the lifted AIS policy is \(π^{\mathrm{CE}} = \hat π^\star \circ σ\).
Theorem 9.1 (CE as an AIS) Under \(\eqref{eq:ce-Lip-c}\)–\(\eqref{eq:ce-Lip-P}\), the compression \(σ_t\) with cost approximators \(\hat c_t = c_t\) and dynamics approximators \(\hat P_t = P_t\) (the dynamics of \(\ALPHABET M\)) are an AIS generator with tolerances \[ ε_t(h_t) = L^c_t\, η_t(h_t), \qquad δ_t(h_t, a_t) = L^P_t\, η_t(h_t) + \EXP\bigl[ η_{t+1}(H_{t+1}) \bigm| h_t, a_t \bigr]. \] Consequently \(π^{\mathrm{CE}}\) is the lifted AIS policy for this generator, with approximate optimal value functions \(\{\hat V^\star_t\}\).
The theorem is proved by the next two lemmas: Lemma 9.1 is pointwise (AP1) and Lemma 9.2 is pointwise (AP2). The policy gap is deferred to the next section (sample-path envelopes of lecture 8), rather than the uniform form of Theorem 8.1.
9.4.1 (AP1): cost approximation
Lemma 9.1 (Cost approximation for CE) For every history \(h_t\) and action \(a_t\), \[ \ABS{ \EXP\bigl[ c_t(S_t, a_t) \bigm| H_t = h_t,\, A_t = a_t \bigr] - c_t\bigl(σ_t(h_t), a_t\bigr) } \le L^c_t\, η_t(h_t) = ε_t(h_t). \]
Write \(\hat s_t = σ_t(h_t)\). By the triangle inequality and \(\eqref{eq:ce-Lip-c}\), \[\begin{align*} \ABS{ \EXP\bigl[ c_t(S_t, a_t) \bigm| h_t \bigr] - c_t(\hat s_t, a_t) } &\le \EXP\bigl[ \ABS{c_t(S_t, a_t) - c_t(\hat s_t, a_t)} \bigm| h_t \bigr] \\ &\le L^c_t\, \EXP\bigl[ d_{\ALPHABET S}(S_t, \hat s_t) \bigm| h_t \bigr] \\ &= L^c_t\, η_t(h_t), \end{align*}\] where the last step is \(\eqref{eq:ce-eta-local}\).
9.4.2 (AP2): dynamics approximation
Lemma 9.2 (Dynamics approximation for CE) For every history \(h_t\) and action \(a_t\), writing \[ μ_t(\,\cdot\,) = \PR\bigl( \hat S_{t+1} \in \cdot \bigm| H_t = h_t,\, A_t = a_t \bigr), \quad ν_t(\,\cdot\,) = P_t\bigl(\cdot \bigm| σ_t(h_t), a_t\bigr) \] as in Definition 8.1, we have \[ W_1(μ_t, ν_t) \le L^P_t\, η_t(h_t) + \EXP\bigl[ η_{t+1}(H_{t+1}) \bigm| h_t, a_t \bigr] = δ_t(h_t, a_t). \]
Write \(\hat s_t = σ_t(h_t)\) and let \[ \tilde μ_t(\cdot \mid h_t, a_t) = \PR\bigl( S_{t+1} \in \cdot \bigm| h_t, a_t \bigr) = \sum_{s \in \ALPHABET S} P_t(\cdot \mid s, a_t)\, b_t[h_t](s) \] be the predictive law of the true next state. By the triangle inequality for \(W_1\), \[ W_1(μ_t, ν_t) \le W_1(μ_t, \tilde μ_t) + W_1(\tilde μ_t, ν_t). \]
Estimate versus true next state. Coupling \((\hat S_{t+1}, S_{t+1})\) under the joint conditional law given \((h_t, a_t)\) and using the tower property with \(\eqref{eq:ce-eta-local}\), \[\begin{align*} W_1(μ_t, \tilde μ_t) &\le \EXP\bigl[ d_{\ALPHABET S}\bigl(\hat S_{t+1}, S_{t+1}\bigr) \bigm| h_t, a_t \bigr] \\ &= \EXP\Bigl[ \EXP\bigl[ d_{\ALPHABET S}\bigl(σ_{t+1}(H_{t+1}), S_{t+1}\bigr) \bigm| H_{t+1} \bigr] \Bigm| h_t, a_t \Bigr] \\ &= \EXP\bigl[ η_{t+1}(H_{t+1}) \bigm| h_t, a_t \bigr]. \end{align*}\]
Dynamics Lipschitz under current error. Convexity of \(W_1\) and \(\eqref{eq:ce-Lip-P}\) give \[\begin{align*} W_1(\tilde μ_t, ν_t) &\le \sum_{s} b_t[h_t](s)\, W_1\bigl( P_t(\cdot \mid s, a_t),\, P_t(\cdot \mid \hat s_t, a_t) \bigr) \\ &\le L^P_t\, \EXP\bigl[ d_{\ALPHABET S}(S_t, \hat s_t) \bigm| h_t \bigr] \\ &= L^P_t\, η_t(h_t). \end{align*}\] Adding the two estimates yields the claim.
Together, Lemma 9.1 and Lemma 9.2 establish Theorem 9.1: the CE generator meets the stated pointwise \((ε_t,δ_t)\) tolerances, so \(π^{\mathrm{CE}} = \hat π^\star \circ σ\) is the corresponding lifted AIS policy.
9.5 Sample-path sub-optimality of CE
We view the history-based MDP as the true model, \(\ALPHABET M\) as the abstract model, and \(σ_t\) as the abstraction. Absolute-value envelopes (Theorem 6.4) give a history-dependent gap; signed envelopes (Theorem 6.3) are available when mismatches are one-sided.
A convenient explicit upper bound is \[\begin{equation}\label{eq:ce-alpha-local} α_t(h_t) = \sum_{τ=t}^{T} \EXP\Bigl[ ε_τ(H_τ) + δ_τ(H_τ, A_τ)\, \operatorname{Lip}(\hat V^\star_{τ+1}) \Bigm| H_t = h_t \Bigr], \end{equation}\] where \(ε_τ(H_τ) = L^c_τ η_τ(H_τ)\) and \(δ_τ(H_τ, A_τ)\) is as in Theorem 9.1, and we use \(\hat V^\star_{T+1} = 0\) (hence \(\operatorname{Lip}(\hat V^\star_{T+1}) = 0\)), so the \(τ=T\) dynamics term vanishes. (If an action-free upper bound is preferred, replace \(δ_τ(H_τ,A_τ)\) by \[ \bar δ_τ(H_τ) = L^P_τ\, η_τ(H_τ) + \sup_{a \in \ALPHABET A} \EXP\bigl[ η_{τ+1}(H_{τ+1}) \bigm| H_τ, a \bigr] \] before taking the conditional expectation.)
Theorem 9.2 (Sub-optimality of certainty equivalence (sample-path)) Under \(\eqref{eq:ce-Lip-c}\)–\(\eqref{eq:ce-Lip-P}\), the certainty equivalent policy \(π^{\mathrm{CE}}\) satisfies \[ V^{π^{\mathrm{CE}}}_t(h_t) - V^\star_t(h_t) \le 2 α_t(h_t) \] for every history \(h_t\), where \(α_t(h_t)\) is given by \(\eqref{eq:ce-alpha-local}\) (or any absolute envelope from Theorem 6.4 driven by the pointwise mismatches of Theorem 9.1).
Lemma 9.1 and Lemma 9.2 bound the pointwise mismatch of the history-based MDP against \(\ALPHABET M\) at \((h_t,a_t)\) by \[ \ABS{\bigl[\hat\MISMATCH_t \hat V^\star_{t+1}\bigr](h_t,a_t)} \le ε_t(h_t) + δ_t(h_t,a_t)\, \operatorname{Lip}(\hat V^\star_{t+1}). \] Theorem 6.4 then yields \(V^{\hat π^\star \circ σ}_t(h_t) - V^\star_t(h_t) \le 2 α_t(h_t)\) for any absolute envelope that upper-bounds those one-step terms; \(π^{\mathrm{CE}} = \hat π^\star \circ σ\) and optimality of \(V^\star\) give the claim. Unfolding the envelope recursion produces \(\eqref{eq:ce-alpha-local}\).
Sub-optimality scales with the local estimation error \(\{η_t(h_t)\}\), amplified by the Lipschitz constants of \(\ALPHABET M\). Histories with accurate estimates pay a small gap; histories with poor estimates pay more. Signed envelopes replace the factor two by \(α^+_t(h_t) - α^-_t(h_t)\) when the CE mismatch is one-sided (lecture 8).
9.6 Corollary: uniform / sup-norm bound
Collapsing history dependence by a supremum recovers the classical scalar statement. Define \[\begin{align} η_t &\coloneqq \sup_{h_t \in \ALPHABET H_t} η_t(h_t) = \NORM{η_t(\,\cdot\,)}_∞, \label{eq:ce-eta} \\ ε_t &\coloneqq L^c_t\, η_t, \label{eq:ce-eps-unif} \\ δ_t &\coloneqq L^P_t\, η_t + η_{t+1}, \label{eq:ce-delta-unif} \end{align}\] and the uniform aggregate \[\begin{equation}\label{eq:ce-alpha-unif} α_t^{\mathrm{unif}} = \sum_{τ=t}^{T} \bigl[ ε_τ + δ_τ\, \operatorname{Lip}(\hat V^\star_{τ+1}) \bigr]. \end{equation}\] For every \((h_t,a_t)\) one has \(ε_t(h_t) \le ε_t\) and \(δ_t(h_t,a_t) \le δ_t\), so \(α_t(h_t) \le α_t^{\mathrm{unif}}\).
Corollary 9.1 (Uniform sub-optimality of certainty equivalence) Under \(\eqref{eq:ce-Lip-c}\)–\(\eqref{eq:ce-Lip-P}\), for every history \(h_t\), \[ V^{π^{\mathrm{CE}}}_t(h_t) - V^\star_t(h_t) \le 2 α_t^{\mathrm{unif}}. \]
The constant envelopes \(α_t(\,\cdot\,) \equiv α_t^{\mathrm{unif}}\) are feasible for Theorem 9.2, since \(ε_τ(h_τ) \le ε_τ\) and \(δ_τ(h_τ,a_τ) \le δ_τ\) for all histories and actions. Alternatively, the same scalars \((ε_t,δ_t)\) are uniform AIS tolerances in the sense of Definition 8.1, and Theorem 8.1 / Corollary 8.1 (with \(ρ_{\mathfrak F} = \operatorname{Lip}\)) give the identical bound. Either route is a corollary of the history-local development: one takes \(\sup_{h_t}\) after the pointwise (AP1)/(AP2) estimates.
If estimation quality is essentially constant across histories (e.g. uniform bounded observation noise below), \(α_t(h_t)\) and \(α_t^{\mathrm{unif}}\) coincide up to the usual upper bounds, and Corollary 9.1 is the readable statement. When quality varies (erasures, intermittent degradation), Theorem 9.2 is strictly sharper on good histories.
9.7 Example: bounded observation noise
Example 9.1 (Bounded observation noise) Suppose \(\ALPHABET Y = \ALPHABET S\) and the observation always lands within radius \(r\) of the state: \[ d_{\ALPHABET S}(Y_t, S_t) \le r \qquad\text{for all realizations.} \] Take the estimator to be the last observation, \(σ_t(h_t) = y_t\). Then \[ η_t(h_t) = \EXP\bigl[ d_{\ALPHABET S}(S_t, y_t) \bigm| h_t \bigr] \le r \] for every history, so \(η_t \le r\) as well. Under the Lipschitz assumption \(\eqref{eq:ce-Lip-c}\)–\(\eqref{eq:ce-Lip-P}\), \[ ε_t(h_t) \le r L^c_t, \qquad δ_t(h_t, a_t) \le r\bigl(1 + L^P_t\bigr), \] and likewise \(ε_t \le r L^c_t\), \(δ_t \le r(1 + L^P_t)\). Theorem 9.2 and Corollary 9.1 therefore both yield \[ V^{π^{\mathrm{CE}}}_t(h_t) - V^\star_t(h_t) \le 2 r\, L^{\ALPHABET M}_t, \] where \[ L^{\ALPHABET M}_t \coloneqq \sum_{τ=t}^{T} \Bigl( L^c_τ + \bigl(1 + L^P_τ\bigr)\, \operatorname{Lip}(\hat V^\star_{τ+1}) \Bigr) \] depends only on the smoothness of \(\ALPHABET M\) (with \(\hat V^\star_{T+1} = 0\)). As \(r \to 0\) (vanishing observation noise), the CE policy with \(σ_t(h_t) = y_t\) approaches optimality at a linear rate in \(r\).
The same argument applies when observations are usually accurate but occasionally degraded. Suppose \(d_{\ALPHABET S}(Y_t, S_t) \le r\) on a “good” event and \(d_{\ALPHABET S}(Y_t, S_t) \le R\) otherwise. Then \(η_t(h_t) \le r\) on good histories and \(η_t(h_t) \le R\) on bad ones, so \(α_t(h_t)\) tracks the realized degradation through the conditional expectations in \(δ_t\) and in \(\eqref{eq:ce-alpha-local}\). This is the same mechanism as the packet-drop signed envelopes in lecture 8.
9.8 Example: learning / adaptive control
Example 9.2 (Learning with unknown parameters) Consider a parameterized fully observed MDP \(\ALPHABET M_X(θ)\) with state space \(\ALPHABET X\), action space \(\ALPHABET A\), time-invariant dynamics \(P_{X,θ}\), and time-invariant per-step cost \(c_θ\), where the unknown parameter \(θ \in Θ\) is drawn from a known prior, independent of the process noise. The controller observes the physical state and past actions (and, typically, realized costs), but not \(θ\).
This is a POMDP with joint state \(S_t = (X_t, θ)\). We assume that \(\ALPHABET X\) and \(Θ\) are metric spaces with metrics \(d_{\ALPHABET X}\) and \(d_Θ\), and define the metric on the product space as \[ d_{\ALPHABET S}\bigl((x,θ), (x',θ')\bigr) = d_{\ALPHABET X}(x,x') + d_Θ(θ,θ'). \] The associated fully observed model \(\ALPHABET M\) has state \((X_t, θ)\); its optimal policy \(\hat π^\star\) depends on both. Equivalently, \(\hat π^\star_t(x,θ)\) is the optimal policy of \(\ALPHABET M_X(θ)\) evaluated at \(x\).
Assume joint Lipschitz continuity in \((x,θ)\): there exist \(L^c, L^P \ge 0\) such that for all \(x,x' \in \ALPHABET X\), \(θ,θ' \in Θ\), and \(a \in \ALPHABET A\), \[\begin{align*} \ABS{c_θ(x,a) - c_{θ'}(x',a)} &\le L^c \bigl( d_{\ALPHABET X}(x,x') + d_Θ(θ,θ') \bigr), \\ W_1\bigl( P_{X,θ}(\cdot \mid x,a),\, P_{X,θ'}(\cdot \mid x',a) \bigr) &\le L^P \bigl( d_{\ALPHABET X}(x,x') + d_Θ(θ,θ') \bigr). \end{align*}\]
Take the estimator \(σ_t(h_t) = (x_t, \hat θ_t)\), where \(\hat θ_t\) is any estimate of \(θ\) from \(h_t\) (for example the MMSE estimate \(\EXP[θ \mid h_t]\)). The certainty equivalent policy is \[ π^{\mathrm{CE}}_t(h_t) = \hat π^\star_t\bigl(x_t, \hat θ_t\bigr). \] Because \(X_t\) is observed perfectly, \[ η_t(h_t) = \EXP\bigl[ d_Θ(θ, \hat θ_t) \bigm| H_t = h_t \bigr]. \] Under the Lipschitz assumption above, Theorem 9.1 specializes to \[ ε_t(h_t) = L^c\, η_t(h_t), \qquad δ_t(h_t, a_t) = L^P\, η_t(h_t) + \EXP\bigl[ η_{t+1}(H_{t+1}) \bigm| h_t, a_t \bigr], \] and Theorem 9.2 yields \[ V^{π^{\mathrm{CE}}}_t(h_t) - V^\star_t(h_t) \le 2 α_t(h_t) \] with \(α_t\) as in \(\eqref{eq:ce-alpha-local}\). The gap is therefore controlled by the local quality of parameter estimation along the realized history. If \(η_t(h_t)\) decays sufficiently fast (for example exponentially in \(t\)), the resulting upper bound remains useful even as \(T \to ∞\).
9.9 Some remarks
9.9.1 When CE is the wrong structure
Certainty equivalence is not appropriate for every POMDP. If the action set includes a costly sensing action that reveals the state, a CE policy never chooses to sense: its action is always \(\hat π^\star_t(\hat s_t)\) for the fully observed MDP \(\ALPHABET M\), which has no reason to pay for information it already treats as free and perfect.
This is exactly the tension in the when-to-observe example of lecture 7. There the optimal policy sometimes pays \(λ\) to reset the belief to a point mass. A CE rule with \(σ_t\) equal to the last observation (or any estimator that ignores the option value of sensing) will not reproduce that tradeoff. The AIS bound remains valid, but \(η_t(h_t)\) need not be small for such an estimator, and a different structured policy (one that occasionally senses) can do better.
9.9.2 CE with state abstraction
The same argument applies with a state abstraction \(φ \colon \ALPHABET S \to \hat{\ALPHABET S}\): estimate \(φ(S_t)\), solve the abstract MDP \(\widehat{\ALPHABET M}\) from lecture 5, and play \(\hat π^\star_t(σ_t(h_t))\). Abstraction error and filter error add inside an effective \(η_t(h_t)\); the sample-path AIS envelopes again supply the gap, and taking \(\sup_{h_t}\) recovers a uniform corollary. We do not derive the details here.
Notes
The generalized CE principle and the examples follow Bozkurt et al. (2025). The policy-gap step uses the sample-path AIS envelopes of lecture 8 (Beyond sup-norm; Theorem 6.4), based on Subramanian et al. (2022) and Bozkurt et al. (2026); the uniform corollary also matches Theorem 8.1.