Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 6.3(a) — a uniformly NNN-stage optimal policy exists iff the DP infima are attained

Proved
BertsekasShreve.Generalized.prop6_3a_uniform_optimal_iff_attained

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

dynamic-programmingfinite-horizonp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1

Consider the generalized abstract model of Section 6.1 under conditions A.1–A.4 and the exact selection assumption, and let NNN be a positive integer. There exists a uniformly NNN-stage optimal policy in Π~\tilde\PiΠ~ if and only if the infimum in

Tk+1(J0)(x)=inf⁡u∈U(x)H[x,u,Tk(J0)]T^{k+1}(J_0)(x)=\inf_{u\in U(x)}H[x,u,T^k(J_0)]Tk+1(J0​)(x)=u∈U(x)inf​H[x,u,Tk(J0​)]

is attained (by some u∈U(x)u\in U(x)u∈U(x)) for each x∈Sx\in Sx∈S and k=0,1,…,N−1k=0,1,\dots,N-1k=0,1,…,N−1.

The exact selection assumption is what allows pointwise minimizers to be assembled into a selector in the restricted class M~\tilde MM~.

Preamble
import Mathlib
import Definitions.Def_BertsekasShreve_Generalized_Model
import Definitions.Def_BertsekasShreve_Generalized_Assumptions
import Definitions.Def_BertsekasShreve_Generalized_Optimality
Formal statement
namespace BertsekasShreve.Generalized

open Filter Topology

/-- Proposition 6.3(a), p. 96. Under A.1–A.4 and the exact selection assumption, a uniformly
`N`-stage optimal policy exists if and only if the infimum in
`T^{k+1}(J₀)(x) = inf_{u ∈ U(x)} H[x, u, T^k(J₀)]` is attained for each `x ∈ S` and
`k = 0, 1, …, N − 1`. `N` is a positive integer (p. 28). -/
theorem prop6_3a_uniform_optimal_iff_attained {S C : Type*} (P : Model S C)
    (hA1 : P.A1) (hA2 : P.A2) (hA3 : P.A3) (hA4 : P.A4) (hES : P.ExactSelection)
    (N : ℕ) (hN : 0 < N) :
    (∃ π : P.Policy, P.IsUniformlyNStageOptimal N π) ↔
      ∀ x, ∀ k, k < N → ∃ u ∈ P.U x, P.H x u (P.T^[k] P.J0) = P.T^[k + 1] P.J0 x := by sorry

end BertsekasShreve.Generalized
Source
Bertsekas & Shreve, Stochastic Optimal Control: The Discrete-Time Case, Athena Scientific 1996, p. 96, Proposition 6.3(a)
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 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