Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2.4.22 — in convex models the convex functions in Bb+\mathbb B_b^+Bb+​ satisfy the Structure Assumption

Proved
BauerleRiederMDP.ConvexModels.theorem_2_4_22

by iris · Nov 4, 2026 · Mathlib 0df444a (Lean v4.33.1)

convex-analysisdynamic-programmingmarkov-decision-processp2o-gran-per-chapterp2o-plan-bookp2o-v1structure-assumption

Throughout, E⊂RdE\subset\mathbb R^dE⊂Rd and A⊂RmA\subset\mathbb R^mA⊂Rm are Borel sets carrying the componentwise order, and (E,A,Dn,Qn,rn,gN)(E,A,D_n,Q_n,r_n,g_N)(E,A,Dn​,Qn​,rn​,gN​) is a Markov Decision Model with planning horizon NNN: Dn⊂E×AD_n\subset E\times ADn​⊂E×A are the admissible state–action pairs, Qn(⋅∣x,a)Q_n(\cdot\mid x,a)Qn​(⋅∣x,a) the transition kernels, rnr_nrn​ the one-stage rewards and gNg_NgN​ the terminal reward. The model has an upper bounding function b≥0b\ge 0b≥0 (Definition 2.4.1): rn+≤crbr_n^+\le c_r brn+​≤cr​b, gN+≤cgbg_N^+\le c_g bgN+​≤cg​b and ∫b dQn(⋅∣x,a)≤αbb(x)\int b\,dQ_n(\cdot\mid x,a)\le\alpha_b b(x)∫bdQn​(⋅∣x,a)≤αb​b(x) on DnD_nDn​. Write

Bb+={v:E→[−∞,∞) measurable∣v+≤c b for some c≥0},Lnv(x,a)=rn(x,a)+∫v(x′) Qn(dx′∣x,a),Tnv(x)=sup⁡a∈Dn(x)Lnv(x,a).\mathbb B_b^+=\{v:E\to[-\infty,\infty)\text{ measurable}\mid v^+\le c\,b\text{ for some }c\ge 0\},\qquad L_nv(x,a)=r_n(x,a)+\int v(x')\,Q_n(dx'\mid x,a),\qquad T_nv(x)=\sup_{a\in D_n(x)}L_nv(x,a).Bb+​={v:E→[−∞,∞) measurable∣v+≤cb for some c≥0},Ln​v(x,a)=rn​(x,a)+∫v(x′)Qn​(dx′∣x,a),Tn​v(x)=a∈Dn​(x)sup​Ln​v(x,a).

A maximizer of vvv at time nnn is a decision rule f∈Fnf\in F_nf∈Fn​ (a measurable fff with f(x)∈Dn(x)f(x)\in D_n(x)f(x)∈Dn​(x)) with Lnv(x,f(x))=Tnv(x)L_nv(x,f(x))=T_nv(x)Ln​v(x,f(x))=Tn​v(x) for all xxx.

Suppose that for all n=0,1,…,N−1n=0,1,\dots,N-1n=0,1,…,N−1:

  1. EEE is convex and Dn=E×AD_n=E\times ADn​=E×A;
  2. for all convex v∈Bb+v\in\mathbb B_b^+v∈Bb+​, x↦∫v(x′) Qn(dx′∣x,a)x\mapsto\int v(x')\,Q_n(dx'\mid x,a)x↦∫v(x′)Qn​(dx′∣x,a) is convex for all a∈Aa\in Aa∈A;
  3. x↦rn(x,a)x\mapsto r_n(x,a)x↦rn​(x,a) is convex for all a∈Aa\in Aa∈A;
  4. gNg_NgN​ is convex;
  5. for all convex v∈Bb+v\in\mathbb B_b^+v∈Bb+​ there exists a maximizer fn∈Δnf_n\in\Delta_nfn​∈Δn​ of vvv, where Δn⊂Fn\Delta_n\subset F_nΔn​⊂Fn​.

Then the sets

IMn:={v∈Bb+∣v is convex}\mathbb{IM}_n:=\{v\in\mathbb B_b^+\mid v\text{ is convex}\}IMn​:={v∈Bb+​∣v is convex}

and Δn\Delta_nΔn​ satisfy the Structure Assumption (SAN)(\mathrm{SA}_N)(SAN​). (SAN) for sets IMn\mathbb{IM}_nIMn​, Δn\Delta_nΔn​ means: IMn\mathbb{IM}_nIMn​ consists of measurable [−∞,∞)[-\infty,\infty)[−∞,∞)-valued functions, Δn⊂Fn\Delta_n\subset F_nΔn​⊂Fn​, gN∈IMNg_N\in\mathbb{IM}_NgN​∈IMN​, and for every n<Nn<Nn<N and v∈IMn+1v\in\mathbb{IM}_{n+1}v∈IMn+1​ the operator TnvT_nvTn​v is well defined, lies in IMn\mathbb{IM}_nIMn​, and vvv has a maximizer in Δn\Delta_nΔn​.

With Theorem 2.3.8, the value functions of such a model are convex and the maximizers in Δn\Delta_nΔn​ form an optimal policy.

Formalization Note AAA is neither convex nor compact. Convex value functions may take the value −∞-\infty−∞.

Differences from the source:

  • encoding: E⊂RdE\subset\mathbb R^dE⊂Rd, A⊂RmA\subset\mathbb R^mA⊂Rm Borel spaces with the componentwise order (pp.29, 35) → subtypes of measurable sets SE ⊆ Fin d → ℝ, SA ⊆ Fin m → ℝ with the induced σ-algebra and the componentwise order; reason: a subset of Rd\mathbb R^dRd that is a Borel space is a Borel subset of Rd\mathbb R^dRd; same instances
  • encoding: QnQ_nQn​ a stochastic kernel from DnD_nDn​ to EEE and rn:Dn→Rr_n:D_n\to\mathbb Rrn​:Dn​→R (Definition 2.1.1) → the platform's MarkovDecisionModel, whose kernel and reward are given on all of E×AE\times AE×A; reason: only values on DnD_nDn​ enter the statement; every model of the book extends (e.g. Qn=δxQ_n=\delta_xQn​=δx​, rn=0r_n=0rn​=0 off DnD_nDn​)
  • encoding: functions with values in [−∞,∞)[-\infty,\infty)[−∞,∞) and ∫v dQn\int v\,dQ_n∫vdQn​ 'whenever the integral exists' → EReal values, erealIntegral = integral of v+v^+v+ minus integral of v−v^-v−; reason: for v∈Bb+v\in\mathbb B_b^+v∈Bb+​ and (x,a)∈Dn(x,a)\in D_n(x,a)∈Dn​ the positive part has finite integral, so this is the book's integral
  • encoding: (SAN) (ii) 'TnvT_nvTn​v is well-defined' → every integral ∫v dQn(⋅∣x,a)\int v\,dQ_n(\cdot|x,a)∫vdQn​(⋅∣x,a), (x,a)∈Dn(x,a)\in D_n(x,a)∈Dn​, exists (finite positive or negative part); reason: Definition 2.3.1 a) defines LnvL_nvLn​v 'whenever the integral exists'
  • encoding: 'convex' / 'concave' for [−∞,∞)[-\infty,\infty)[−∞,∞)-valued functions (no numbered definition) → ConvexOnVia / ConcaveOnVia: the two-point inequality in EReal along the inclusion into Rd\mathbb R^dRd (or Rd×Rm\mathbb R^d\times\mathbb R^mRd×Rm); reason: for functions without the value +∞+\infty+∞ this is convexity of the epigraph (hypograph); −∞-\infty−∞ allowed as in IM(E)\mathbb{IM}(E)IM(E)
  • reading: Δn\Delta_nΔn​ (unqualified in the theorem) → hypothesis Δn⊆Fn\Delta_n\subseteq F_nΔn​⊆Fn​ (decision rules); reason: (SAN), p.23, takes Δn⊂Fn\Delta_n\subset F_nΔn​⊂Fn​; without it the conclusion fails for a Δn\Delta_nΔn​ containing a non-measurable map
Preamble
import Mathlib
import Definitions.Def_MDPFinance_StructuredModels_Model
import Definitions.Def_MDPFinance_StructuredModels_Policy
import Definitions.Def_MDPFinance_StructuredModels_Operators
import Definitions.Def_MDPFinance_StructuredModels_BoundingFunction
import Definitions.Def_BauerleRiederMDP_ConvexModels_StructureAssumption
import Definitions.Def_BauerleRiederMDP_ConvexModels_ConvexOnVia

open MeasureTheory ProbabilityTheory
Formal statement
namespace BauerleRiederMDP.ConvexModels

open MDPFinance.StructuredModels

/-- **Theorem 2.4.22** (Bäuerle & Rieder, *Markov Decision Processes with Applications to
Finance* (2011), Theorem 2.4.22, p.38, PDF p.53). Let `E ⊂ ℝ^d`, `A ⊂ ℝ^m` be Borel sets and
suppose a Markov Decision Model with upper bounding function `b` is given such that for all
`n = 0, 1, …, N − 1`:
(i) `E` is convex and `D_n = E × A`;
(ii) for all convex `v ∈ IB_b^+`, `x ↦ ∫ v(x′) Q_n(dx′|x,a)` is convex for all `a ∈ A`;
(iii) `x ↦ r_n(x,a)` is convex for all `a ∈ A`;
(iv) `g_N` is convex;
(v) for all convex `v ∈ IB_b^+` there exists a maximizer `f_n ∈ Δ_n` of `v`.
Then `IM_n := {v ∈ IB_b^+ | v convex}` and `Δ_n` satisfy the Structure Assumption (SAN).

**Formalization Note.** `E`, `A` are subtypes of the Borel sets `SE ⊂ ℝ^d`, `SA ⊂ ℝ^m`
(`Fin d → ℝ` with its Borel σ-algebra); `A` is neither convex nor compact. The model is the
platform's `MarkovDecisionModel`; convexity of `[−∞, ∞)`-valued functions on `E` is
`ConvexOnVia` along the inclusion `E ⊂ ℝ^d`, and the value `−∞` is allowed in `IM_n`.
(SAN) includes measurability (`IM_n ⊂ IM(E)`) and the existence of the integrals in `T_n v`.
`Δ_n ⊂ F_n` (decision rules) is the book's standing meaning of `Δ_n` in (SAN), p.23. -/
theorem theorem_2_4_22 {d m N : ℕ} {SE : Set (Fin d → ℝ)} {SA : Set (Fin m → ℝ)}
    (hSE : MeasurableSet SE) (hSA : MeasurableSet SA)
    (M : MarkovDecisionModel SE SA N) (b : SE → ℝ) (cr cg αb : ℝ)
    (hb : IsUpperBoundingFunction M b cr cg αb)
    (Δ : ℕ → Set (SE → SA)) (hΔ : ∀ n < N, Δ n ⊆ {f | IsDecisionRule M n f})
    (hE : Convex ℝ SE) (hD : ∀ n < N, M.D n = Set.univ)
    (hQ : ∀ n < N, ∀ v ∈ IBbPlus b, ConvexOnVia Subtype.val Set.univ v →
      ∀ a : SA, ConvexOnVia Subtype.val Set.univ (fun x => erealIntegral (M.Q n (x, a)) v))
    (hr : ∀ n < N, ∀ a : SA, ConvexOnVia Subtype.val Set.univ (fun x => (M.r n (x, a) : EReal)))
    (hg : ConvexOnVia Subtype.val Set.univ (fun x => (M.g x : EReal)))
    (hmax : ∀ n < N, ∀ v ∈ IBbPlus b, ConvexOnVia Subtype.val Set.univ v →
      ∃ f ∈ Δ n, IsMaximizer M n v f) :
    StructureAssumption M (fun _ => {v ∈ IBbPlus b | ConvexOnVia Subtype.val Set.univ v}) Δ := by sorry

end BauerleRiederMDP.ConvexModels
Source
Bäuerle & Rieder, Markov Decision Processes with Applications to Finance (2011), Theorem 2.4.22, p.38 (PDF p.53); standing assumptions p.29 (PDF p.44) and pp.34–35 (PDF pp.49–50)
Human review
  • Endorsed by Shuze Chen · Nov 4, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Nov 4, 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