Corollary 5.7.1 — under D and D.2 with finite S and J* > −∞, ε-optimal policies exist
ProvedBertsekasShreve.Monotone.cor5_7_1_finite_state_eps_optimaldynamic-programmingepsilon-optimal-policyp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1uniform-decrease
In the abstract monotone dynamic programming model (state space , constraint sets , monotone mapping , terminal function , policy costs and optimal cost ), assume
- Assumption D: for all , ;
- Assumption D.2 holds for some scalar ;
- is a finite set;
- for all .
Then for every there exists an -optimal policy, i.e. a policy with
It is the counterpart under Assumption D of the existence of -optimal policies under Assumption I (Proposition 5.1 and Proposition 5.6(a)).
Formalization Note The model and the assumptions are the published MonotoneDP.Decrease definitions. Because is assumed, the book's general -optimality convention reduces to the displayed inequality; at states with the bound is .
Preamble
import Mathlib import Definitions.Def_MonotoneDP_Decrease_Model import Definitions.Def_MonotoneDP_Decrease_Assumptions
Formal statement
namespace BertsekasShreve.Monotone
/-- Bertsekas & Shreve (1996), p. 80, Corollary 5.7.1: let D and D.2 hold, let `S` be a finite set,
and let `J*(x) > −∞` for all `x ∈ S`. Then for every `ε > 0` there is a policy `π_ε` with
`J* ≤ J_{π_ε} ≤ J* + ε`. -/
theorem cor5_7_1_finite_state_eps_optimal {S C : Type*} [Finite S]
(m : MonotoneDP.Decrease.Model S C)
(hD : m.AssumptionD) (hD2 : ∃ α : ℝ, m.AssumptionD2 α) (hfin : ∀ x : S, ⊥ < m.Jstar x) :
∀ ε : ℝ, 0 < ε → ∃ π : m.Policy,
m.Jstar ≤ m.Jpi π ∧ m.Jpi π ≤ fun x => m.Jstar x + (ε : EReal) := by sorry
end BertsekasShreve.Monotone
Source
Bertsekas & Shreve, Stochastic Optimal Control: The Discrete-Time Case, Athena Scientific 1996, p. 80, Corollary 5.7.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.