Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The DP operator TTT maps lower semianalytic functions to lower semianalytic functions

Open
BertsekasShreve.BorelFinite.T_lowerSemianalytic

by tianyipeng · Nov 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

bellman-operatordynamic-programminglower-semianalytic

Consider the finite horizon Borel model of Definition 8.1 (Borel spaces SSS, CCC, WWW, analytic constraint set Γ={(x,u)∣u∈U(x)}\Gamma=\{(x,u)\mid u\in U(x)\}Γ={(x,u)∣u∈U(x)}, Borel disturbance kernel p(dw∣x,u)p(dw\mid x,u)p(dw∣x,u), Borel system function fff, discount α>0\alpha>0α>0, one-stage cost ggg lower semianalytic on Γ\GammaΓ), with state transition kernel t(B∣x,u)=p({w∣f(x,u,w)∈B}∣x,u)t(B\mid x,u)=p(\{w\mid f(x,u,w)\in B\}\mid x,u)t(B∣x,u)=p({w∣f(x,u,w)∈B}∣x,u). For J:S→R∗J:S\to R^*J:S→R∗ let

T(J)(x)=inf⁡u∈U(x){g(x,u)+α∫SJ(x′) t(dx′∣x,u)},T(J)(x)=\inf_{u\in U(x)}\Big\{g(x,u)+\alpha\int_S J(x')\,t(dx'\mid x,u)\Big\},T(J)(x)=u∈U(x)inf​{g(x,u)+α∫S​J(x′)t(dx′∣x,u)},

where the integral is taken in the extended sense (43) of Chapter 7 (∫J=∫J+−∫J−\int J=\int J^+-\int J^-∫J=∫J+−∫J−, with ∞−∞=∞\infty-\infty=\infty∞−∞=∞) and the sum uses the convention (42) (∞−∞=∞\infty-\infty=\infty∞−∞=∞).

Claim (p. 196). If J:S→R∗J:S\to R^*J:S→R∗ is lower semianalytic, then T(J)T(J)T(J) is lower semianalytic.

The book justifies this in one sentence: "By Lemma 7.30(4) and Propositions 7.47 and 7.48, T(J)T(J)T(J) is lower semianalytic whenever JJJ is." Proposition 7.48 makes (x,u)↦∫J dt(⋅∣x,u)(x,u)\mapsto\int J\,dt(\cdot\mid x,u)(x,u)↦∫Jdt(⋅∣x,u) lower semianalytic, Lemma 7.30(4) handles the sum with ggg, and Proposition 7.47 handles the partial infimum over the analytic set Γ\GammaΓ.

Formalization note. "Lower semianalytic" is IsLowerSemianalyticOn Set.univ: SSS is analytic and {x∣J(x)<c}\{x\mid J(x)<c\}{x∣J(x)<c} is analytic for every real ccc. This fact is used, with J=Tk−1(J0)J=T^{k-1}(J_0)J=Tk−1(J0​), in the proof of Proposition 8.2 (to apply Lemma 8.2 / Proposition 7.50 to the iterates of the DP algorithm).

Preamble
import Mathlib
import Definitions.Def_BertsekasShreve_BorelFinite_Model
import Definitions.Def_BertsekasShreve_BorelFinite_Policy
import Definitions.Def_BertsekasShreve_BorelFinite_Operators
Formal statement
namespace BertsekasShreve.BorelFinite

/-- **p. 196** (text preceding Lemma 8.2). "By Lemma 7.30(4) and Propositions 7.47 and 7.48,
`T(J)` is lower semianalytic whenever `J` is." Here `T(J)(x) = inf_{u ∈ U(x)} {g(x,u) +
α ∫ J(x′) t(dx′|x,u)}` (Definition 8.5), with the integral in the extended sense (43) of
Chapter 7 and the sum taken with the convention (42). -/
theorem T_lowerSemianalytic {S C W : Type*}
    [TopologicalSpace S] [MeasurableSpace S] [BorelSpace S] [BertsekasShreve.AnalyticSelection.IsBorelSpace S] [Nonempty S]
    [TopologicalSpace C] [MeasurableSpace C] [BorelSpace C] [BertsekasShreve.AnalyticSelection.IsBorelSpace C] [Nonempty C]
    [TopologicalSpace W] [MeasurableSpace W] [BorelSpace W] [BertsekasShreve.AnalyticSelection.IsBorelSpace W] [Nonempty W]
    (M : Model S C W)
    (J : S → EReal) (hJ : IsLowerSemianalyticOn Set.univ J) :
    IsLowerSemianalyticOn Set.univ (T M J) := by sorry

end BertsekasShreve.BorelFinite
Source
Bertsekas & Shreve, Stochastic Optimal Control: The Discrete-Time Case, Athena Scientific 1996, p. 196 (paragraph after Definition 8.5 and before Lemma 8.2): "By Lemma 7.30(4) and Propositions 7.47 and 7.48, T(J) is lower semianalytic whenever J is."

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