Lemma 2.1 (Weak Duality)
ProvedInfoRelax.IdealPenalty.lemma_2_1_weak_dualitydualitydynamic-programminginformation-relaxationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a nonanticipative policy, a dual feasible penalty, and a relaxation of . Assume that exists for every policy . Then
Any information relaxation combined with any dual feasible penalty therefore bounds the value of every nonanticipative policy, and hence the optimal value of the primal DP, from above. The statement holds for an arbitrary feasible set of action sequences and an arbitrary total reward.
Formalization Note The supremum is taken in the extended reals.
Preamble
import Mathlib import Definitions.Def_InfoRelax_IdealPenalty_Framework open MeasureTheory
Formal statement
namespace InfoRelax.IdealPenalty
/-- **Lemma 2.1 (Weak Duality)**, Brown, Smith & Sun (2010), Oper. Res., DOI
10.1287/opre.1090.0796, p. 3, eq. (4).
If `α_F ∈ 𝒜_𝔽` and `z ∈ 𝒵_𝔽` are primal and dual feasible and `𝔾` is a relaxation of `𝔽`, then
`𝔼[r(α_F)] ≤ sup_{α_G ∈ 𝒜_𝔾} 𝔼[r(α_G) − z(α_G)]`.
**Formalization Note.** General framework of §2.1–§2.2: any feasible set `A`, any total reward
`r`, any measurable action type. `hr` is the standing convention that `𝔼[r(α)]` exists for every
policy; the right side is the `EReal` supremum `dualBound`. -/
theorem lemma_2_1_weak_duality {Ω X : Type*} [mΩ : MeasurableSpace Ω] [MeasurableSpace X]
{T : ℕ} (μ : Measure Ω) [IsProbabilityMeasure μ] (A : Set (Fin (T + 1) → X))
(𝔽 𝔾 : Filtration (Fin (T + 1)) mΩ) (r : (Fin (T + 1) → X) → Ω → ℝ)
(hr : RewardIntegrable μ A r) (h𝔾 : IsRelaxation 𝔽 𝔾)
(α : Ω → Fin (T + 1) → X) (hα : α ∈ adaptedPolicies A 𝔽)
(z : (Fin (T + 1) → X) → Ω → ℝ) (hz : z ∈ dualFeasible μ A 𝔽) :
((∫ ω, r (α ω) ω ∂μ : ℝ) : EReal) ≤ dualBound μ A 𝔾 r z := 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. 3, Lemma 2.1, eq. (4)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.