§2.3 — with the dual value functions equal the primal ones,
ProvedInfoRelax.IdealPenalty.dual_value_fn_eq_value_fnbellman-equationdualitydynamic-programminginformation-relaxationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Consider a recursive DP as in eq. (2) (natural filtration with , countable action set, nonempty feasible sets, bounded -measurable period rewards). Let be any relaxation of and take the generating functions built from the primal value functions of (2). Then for every and every action sequence,
where are the dual value functions of (10).
This identity is the core of Theorem 2.3: with the ideal generating functions the dual recursion reproduces the primal recursion, so the dual bound equals the primal value.
Formalization Note The equality is almost sure because conditional expectations are determined only almost everywhere. For both sides are .
Preamble
import Mathlib import Definitions.Def_InfoRelax_IdealPenalty_Framework import Definitions.Def_InfoRelax_IdealPenalty_RecursiveModel import Definitions.Def_InfoRelax_IdealPenalty_Penalty open MeasureTheory
Formal statement
namespace InfoRelax.IdealPenalty
/-- **§2.3, the induction before Theorem 2.3**, Brown, Smith & Sun (2010), Oper. Res., DOI
10.1287/opre.1090.0796, p. 5.
In the recursive setting, let `𝔾` be a relaxation of `𝔽` and take the generating functions
`w_t(a) = V_{t+1}(a_0, …, a_t)` from the primal value functions (2). Then the dual value functions
of (10) equal the primal value functions: `V^𝔾_t = V_t` for every `t = 0, …, T + 1` (and
trivially beyond), almost surely, for every action sequence.
**Formalization Note.** Equality is almost sure (`=ᵐ[μ]`) because conditional expectations are
determined only a.e. Pinned: countable action type with the discrete σ-algebra. -/
theorem dual_value_fn_eq_value_fn {Ω X : Type*} [mΩ : MeasurableSpace Ω] [MeasurableSpace X]
[DiscreteMeasurableSpace X] [Countable X] [DecidableEq X] {T : ℕ}
(μ : Measure Ω) [IsProbabilityMeasure μ] (M : RecursiveDP Ω X T) (hM : M.Valid)
(𝔾 : Filtration (Fin (T + 1)) mΩ) (h𝔾 : IsRelaxation M.𝔽 𝔾) :
∀ (t : ℕ) (a : Fin (T + 1) → X),
dualValueFn M μ 𝔾 (idealGen M μ) t a =ᵐ[μ] valueFn M μ t a := by sorry
end InfoRelax.IdealPenalty
Source
Brown, Smith & Sun, Information Relaxations and Duality in Stochastic Dynamic Programs, Oper. Res. (Articles in Advance, 2010), DOI 10.1287/opre.1090.0796, p. 5, §2.3, the paragraph before Theorem 2.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.