Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§2.1 — the initial value V0V_0V0​ of the recursion (2) equals the primal value (1)

Proved
InfoRelax.IdealPenalty.value_zero_eq_primal

by mikedeng1 · Oct 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

bellman-equationdynamic-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Consider a dynamic program in recursive form: a natural filtration F\mathbb FF with F0={∅,Ω}\mathcal F_0=\{\emptyset,\Omega\}F0​={∅,Ω}, a countable action set XXX, nonempty feasible-action sets At(a0,…,at−1)A_t(a_0,\dots,a_{t-1})At​(a0​,…,at−1​), and bounded period rewards rt(a0,…,at)r_t(a_0,\dots,a_t)rt​(a0​,…,at​) that are Ft\mathcal F_tFt​-measurable. Let VtV_tVt​ be the value functions of the Bellman recursion (2), with VT+1=0V_{T+1}=0VT+1​=0. Then, almost surely,

V0=sup⁡α∈AFE[r(α)],V_0=\sup_{\alpha\in\mathcal A_{\mathbb F}}\mathbb E[r(\alpha)],V0​=α∈AF​sup​E[r(α)],

the optimal value of the primal DP (1) over all nonanticipative policies.

This identity is what makes the recursion (2) a solution method for (1); it holds whether or not the suprema in (2) are attained.

Formalization Note V0(a)V_0(a)V0​(a) does not depend on aaa; the statement quantifies over all action sequences. The comparison is made in the extended reals, where the primal value is defined. The countable action set is a pinned regularity assumption that makes the supremum in (2) measurable.

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.1, the claim after eq. (2)**, Brown, Smith & Sun (2010), Oper. Res., DOI
10.1287/opre.1090.0796, p. 3: "The final value `V_0` is equal to the optimal value of (1)."

In the recursive setting (`RecursiveDP.Valid`: `𝓕_0 = {∅, Ω}`, nonempty feasible sets depending on
past actions, `𝓕_t`-measurable bounded period rewards depending on `a_0, …, a_t`), the value
function `V_0` of the recursion (2) equals, almost surely and for every `a`, the primal value
`sup_{α ∈ 𝒜_𝔽} 𝔼[r(α)]` of (1).

**Formalization Note.** `V_0(a)` does not depend on `a` (it is a function of no actions); the
statement quantifies over all `a`. The claim holds whether or not the suprema in (2) are
attained. Pinned: countable action type with the discrete σ-algebra. The comparison is in
`EReal`, where the primal value lives. -/
theorem value_zero_eq_primal {Ω X : Type*} [mΩ : MeasurableSpace Ω] [MeasurableSpace X]
    [DiscreteMeasurableSpace X] [Countable X] [DecidableEq X] {T : ℕ}
    (μ : Measure Ω) [IsProbabilityMeasure μ] (M : RecursiveDP Ω X T) (hM : M.Valid) :
    ∀ a : Fin (T + 1) → X, ∀ᵐ ω ∂μ,
      ((valueFn M μ 0 a ω : ℝ) : EReal) = primalValue μ M.A M.𝔽 M.r := 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, §2.1, the paragraph after eq. (2): "The final value V_0 is equal to the optimal value of (1)."
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 8, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me