Theorem 10 — and are contraction mappings
ProvedBoundedParamMDP.IntervalEval.theorem10_contractioncontractiondynamic-programmingmarkov-decision-processesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a bounded-parameter MDP with finite state set and finite nonempty action set , and let be a policy. Consider the lower- and upper-bound operators of interval policy evaluation, as maps on the space of value functions with the sup norm :
Theorem 10. Both and are contraction mappings: for each of them, , there is with
Together with Theorem 11 and the Banach fixed-point theorem, this gives the convergence of interval policy evaluation.
Formalization Note. The statement asserts the existence of a modulus, as the paper's notion of contraction mapping does; it does not fix the modulus to .
Preamble
import Mathlib import Definitions.Def_BoundedParamMDP_Optimal_MDP import Definitions.Def_BoundedParamMDP_Optimal_BMDP import Definitions.Def_BoundedParamMDP_IntervalEval_IntervalPolicyEvaluation
Formal statement
namespace BoundedParamMDP.IntervalEval
/-- Theorem 10 (Givan–Leach–Dean 2000, p. 21; restated p. 43): for any policy `π`, the
interval policy evaluation operators `IVI↓π` and `IVI↑π`, viewed as maps from value functions
to value functions, are contraction mappings for the sup norm. -/
theorem theorem10_contraction {Q A : Type*} [Fintype Q] [Fintype A] [Nonempty A]
(B : BoundedParamMDP.Optimal.BMDP Q A) (π : BoundedParamMDP.Optimal.Policy Q A) :
IsContraction (IVIlo B π) ∧ IsContraction (IVIhi B π) := by sorry
end BoundedParamMDP.IntervalEval
Source
Givan, Leach, Dean, Bounded-parameter Markov decision processes, Artificial Intelligence (2000), DOI 10.1016/S0004-3702(00)00047-3, manuscript of May 22, 2000, p. 21, Theorem 10 (restated with proof pp. 43–44)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.