Corollary 5.3.1 — under D and D.2 with finite S and J* > −∞, J* = T(J*) and J* is the largest such J ≤ J₀
ProvedBertsekasShreve.Monotone.cor5_3_1_finite_state_bellmandynamic-programmingoptimality-equationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1uniform-decrease
In the abstract monotone dynamic programming model (state space , constraint sets , monotone mapping , terminal function , operator , policy costs and optimal cost ), assume
- Assumption D: for all , ;
- Assumption D.2: for some , for all , , , ;
- is a finite set;
- for all .
Then
Furthermore, if satisfies and , then .
This is the version of Proposition 5.3 in which the continuity Assumption D.1 is replaced by D.2 together with finiteness of the state space and finiteness from below of .
Formalization Note The model and the assumptions D, D.2 are the published MonotoneDP.Decrease definitions; finiteness of is [Finite S].
Preamble
import Mathlib import Definitions.Def_MonotoneDP_Decrease_Model import Definitions.Def_MonotoneDP_Decrease_Assumptions
Formal statement
namespace BertsekasShreve.Monotone
/-- Bertsekas & Shreve (1996), p. 76, Corollary 5.3.1: let D and D.2 hold, let `S` be a finite set,
and let `J*(x) > −∞` for all `x ∈ S`. Then `J* = T(J*)`; furthermore every `J' ∈ F` with
`J' ≤ J₀` and `J' ≤ T(J')` satisfies `J' ≤ J*`. -/
theorem cor5_3_1_finite_state_bellman {S C : Type*} [Finite S]
(m : MonotoneDP.Decrease.Model S C)
(hD : m.AssumptionD) (hD2 : ∃ α : ℝ, m.AssumptionD2 α) (hfin : ∀ x : S, ⊥ < m.Jstar x) :
m.Jstar = m.T m.Jstar ∧
∀ J' : S → EReal, J' ≤ m.Jbar → J' ≤ m.T J' → J' ≤ m.Jstar := by sorry
end BertsekasShreve.Monotone
Source
Bertsekas & Shreve, Stochastic Optimal Control: The Discrete-Time Case, Athena Scientific 1996, p. 76, Corollary 5.3.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.