Theorem 5(a) — the robust Bellman operator L_D maps V into V and is a λ-contraction
ProvedRobustDP.Discounted.theorem5a_contractioncontractiondynamic-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1robust-optimization
Let be a discounted ambiguous MDP and let be any nonempty set of deterministic Markov decision rules. Then maps bounded functions to bounded functions, and for all bounded ,
Since , is a contraction of the Banach space ; this is the input to the Banach fixed point argument of Theorem 5(b).
Formalization Note is an arbitrary nonempty set of rules, as on the page ("Let be any subset"); nonemptiness excludes the empty supremum. is the supremum norm.
Preamble
import Mathlib import Definitions.Def_RobustDP_Discounted_Model import Definitions.Def_RobustDP_Discounted_Value import Definitions.Def_RobustDP_Discounted_Bellman
Formal statement
namespace RobustDP.Discounted
theorem theorem5a_contraction {S A : Type*} [Countable S] [Countable A] (M : Model S A)
(D : Set (DecisionRule M)) (hD : D.Nonempty) (U W : S → ℝ) (hU : IsBounded U)
(hW : IsBounded W) :
IsBounded (L M D U) ∧
supNorm (fun s => L M D U s - L M D W s) ≤ M.lam * supNorm (fun s => U s - W s) := by sorry
end RobustDP.Discounted
Source
Iyengar, Robust dynamic programming, CORC Tech Report TR-2002-07 (rev. May 4, 2004), p. 9, Theorem 5(a), eq. (23)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.