Theorem 2.3 (The Ideal Penalty)
ProvedInfoRelax.IdealPenalty.theorem_2_3_ideal_penaltyConsider a dynamic program in recursive form: a natural filtration with , a countable action set, nonempty feasible-action sets , and bounded period rewards that are -measurable, with total reward and value functions given by (2). Let be a relaxation of and let be the penalty of Proposition 2.2 for the generating functions :
Then:
- is dual feasible, ;
- is optimal:
- if attains the supremum on the left of (11), then also attains the supremum on the right;
- if is the perfect-information relaxation ( for all ) and is an optimal policy, then almost surely.
The ideal penalty closes the duality gap for every information relaxation at once; in the perfect-information case it even removes all randomness from the penalized reward of an optimal policy. It is the target that practical penalties built from approximate value functions try to approximate.
Formalization Note and the value functions are definitions computed from the data of the DP, not variables constrained by hypotheses. Values are extended reals. The countable action set and bounded rewards are pinned regularity assumptions.
import Mathlib import Definitions.Def_InfoRelax_IdealPenalty_Framework import Definitions.Def_InfoRelax_IdealPenalty_RecursiveModel import Definitions.Def_InfoRelax_IdealPenalty_Penalty open MeasureTheory
namespace InfoRelax.IdealPenalty
/-- **Theorem 2.3 (The Ideal Penalty)**, Brown, Smith & Sun (2010), Oper. Res., DOI
10.1287/opre.1090.0796, p. 5, eq. (11).
In the recursive setting, let `𝔾` be a relaxation of `𝔽` and let `z⋆` be the penalty of
Proposition 2.2 for `w_t(a) = V_{t+1}(a_0, …, a_t)`. Then
1. `z⋆` is dual feasible;
2. `z⋆` is optimal: `sup_{α_F ∈ 𝒜_𝔽} 𝔼[r(α_F)] = sup_{α_G ∈ 𝒜_𝔾} 𝔼[r(α_G) − z⋆(α_G)]` (11);
3. if `α*_F ∈ 𝒜_𝔽` attains the primal supremum, it also attains the supremum on the right of (11);
4. if `𝔾` is the perfect-information relaxation and `α*_F ∈ 𝒜_𝔽` is optimal, then
`r(α*_F) − z⋆(α*_F) = 𝔼[r(α*_F)]` almost surely.
**Formalization Note.** `z⋆` is the def `idealPenalty`, built from the def `valueFn` (the
recursion (2)); nothing is a free variable. Values in `EReal`. Recursive setting
(`RecursiveDP.Valid`: `𝓕_0 = {∅, Ω}`, nonempty feasible sets depending on past actions,
`𝓕_t`-measurable bounded period rewards depending on `a_0, …, a_t`); pinned countable action type
with the discrete σ-algebra. "Perfect information" is `𝔾 = perfectInfo` (`𝒢_t = 𝓕` for all `t`). -/
theorem theorem_2_3_ideal_penalty {Ω 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.𝔽 𝔾) :
idealPenalty M μ 𝔾 ∈ dualFeasible μ M.A M.𝔽 ∧
primalValue μ M.A M.𝔽 M.r = dualBound μ M.A 𝔾 M.r (idealPenalty M μ 𝔾) ∧
(∀ α ∈ adaptedPolicies M.A M.𝔽,
((∫ ω, M.r (α ω) ω ∂μ : ℝ) : EReal) = primalValue μ M.A M.𝔽 M.r →
((∫ ω, (M.r (α ω) ω - idealPenalty M μ 𝔾 (α ω) ω) ∂μ : ℝ) : EReal) =
dualBound μ M.A 𝔾 M.r (idealPenalty M μ 𝔾)) ∧
(𝔾 = perfectInfo →
∀ α ∈ adaptedPolicies M.A M.𝔽,
((∫ ω, M.r (α ω) ω ∂μ : ℝ) : EReal) = primalValue μ M.A M.𝔽 M.r →
∀ᵐ ω ∂μ, M.r (α ω) ω - idealPenalty M μ 𝔾 (α ω) ω = ∫ ω', M.r (α ω') ω' ∂μ) := by sorry
end InfoRelax.IdealPenalty
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.