The separation theorem — certainty equivalence for linear-quadratic control with imperfect state information — is one of the celebrated structural results of stochastic control: the optimal controller splits into a least-squares estimator and the deterministic LQR actuator, designed independently. It underlies every LQG autopilot and Kalman-filter-based regulator. Section 5.2 of Bertsekas, Dynamic Programming and Optimal Control, Vol. I (3rd ed., 2005) proves it from the DP algorithm over information vectors, with Lemma 5.2.1 supplying the key fact that the estimation error is beyond the controller's influence. No formal analogue exists in Mathlib.
Linear dynamics and measurements
with quadratic cost , , . The initial state and the zero-mean disturbances/noises are independent with finite ranges; independence is structural — the sample space is the product of an initial-state coordinate and per-stage noise coordinates (BertsekasLQGModel, BertsekasLQGSample, BertsekasLQGProb). A policy maps the realized measurement history to ; the closed-loop process is BertsekasLQGTraj, the expected cost BertsekasLQGCost. The estimator is an explicit conditional average (BertsekasCondExpVec, BertsekasLQGEstimate); the gains come from the time-varying Riccati recursion (BertsekasLQGRiccati, BertsekasLQGGain).
— BertsekasDP.lqg_certainty_equivalence (goal). Milestone: Lemma 5.2.1 in pointwise form — the error is the same under any two policies, outcome by outcome (lqg_estimation_error_policy_independent).
This is the theorem that justifies designing estimator and controller separately — remove it and the entire LQG methodology loses its warrant. The formalization also yields the first machine-checked instance of the informational decomposition (control-dependent part + policy-independent error) that recurs throughout imperfect-information control. Notably the result needs no Gaussian assumption — only zero mean and independence — and the finite-support model makes that generality exact. The result is classical (Joseph–Tou 1961, Gunckel–Franklin 1963; the book's §5.2); the formal proof is new.
The heart is Lemma 5.2.1: showing the estimation error coincides, sample by sample, with the error of the control-free system — which requires proving that the observation-history σ-events under any policy coincide with those of the control-free system (controls are determined by the history, so they shift observations by a known amount). Then the DP argument over information histories must carry the quadratic decomposition through the backward recursion. Bookkeeping over histories-as-lists is the main formal burden; probability theory stays finite.
Finite-support randomness (all expectations are finite sums); conditional expectation with the explicit junk value 0 on zero-probability events — the goal's hypothesis is accordingly restricted to outcomes of positive probability. Policies are functions of the measurement list only (equivalent to the book's information vector for deterministic policies, since past controls are recoverable from past measurements). Matrices are time-varying; positive definiteness of makes every matrix inverse in the gains genuine. Measurement noise covariance is not assumed positive definite — the estimator is the abstract conditional expectation, not the Kalman filter (whose recursive form, §5.2.1, would be a natural follow-up mission).
namespace BertsekasDP
theorem lqg_certainty_equivalence {n m q : ℕ} {Ω₀ ΩW ΩV : Type}
[Fintype Ω₀] [Fintype ΩW] [Fintype ΩV]
(M : BertsekasLQGModel n m q Ω₀ ΩW ΩV)
(πstar : List (Fin q → ℝ) → Fin m → ℝ)
(hstar : ∀ k < M.N, ∀ ω : BertsekasLQGSample M,
BertsekasLQGProb M ω ≠ 0 →
πstar ((BertsekasLQGTraj M πstar k ω).2) =
BertsekasLQGGain M k *ᵥ BertsekasLQGEstimate M πstar k ω) :
∀ π : List (Fin q → ℝ) → Fin m → ℝ,
BertsekasLQGCost M πstar ≤ BertsekasLQGCost M π := by sorry
end BertsekasDPThe separation theorem / certainty equivalence principle (Bertsekas, Vol. I, §5.2). Consider the linear-quadratic problem with imperfect state information: dynamics , measurements , quadratic cost with and , and independent finitely supported zero-mean disturbances. Let be the gain matrices of the corresponding deterministic linear-quadratic problem, and let be the least-squares estimate of the state given the measurement history .
Suppose a policy satisfies, along its own closed-loop trajectories and at every stage ,
Then is optimal:
The optimal controller therefore separates into two independently designed parts: an estimator, which produces and is the solution of a pure estimation problem in which no control takes place, and an actuator, which multiplies that estimate by the gain that would be used if the state were observed exactly. Remove this theorem and the entire LQG design methodology — Kalman filter feeding an LQR gain — loses its warrant. Notably no Gaussian assumption is required: independence and zero mean suffice.
Formalization Note The hypothesis is imposed only on outcomes of positive probability, where the conditional expectation is genuine rather than the junk value ; on measurement histories that never occur, the policy is unconstrained and does not affect the cost. The competitor class is all functions from measurement lists to controls, with no linearity or measurability restriction. The inequality is not strict.
No open leaves. Every sub-goal is proved or awaiting decomposition.