§2, p. 3 — the Bellman operator T is a λ-contraction of (ℝⁿ, ‖·‖∞)
ProvedAccelVI.LowerBound.bellman_contractionbellman-operatorcontractionmarkov-decision-processp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite MDP with a nonempty action set, in which each is a probability distribution over next states and , and let be its Bellman operator (2.1). Then for all ,
This is the basic contraction property on which value iteration and all the inequalities of §3 rest.
Formalization Note. is Mathlib's sup norm on S → ℝ. The state set may be any finite type; for an empty state set both sides are .
Preamble
import Mathlib import Definitions.Def_AccelVI_LowerBound_Setting
Formal statement
namespace AccelVI.LowerBound
theorem bellman_contraction {S A : Type*} [Fintype S] [DecidableEq S] [Fintype A] [Nonempty A]
(M : MDP S A) (hM : M.Valid) (v w : S → ℝ) :
‖bellman M v - bellman M w‖ ≤ M.lam * ‖v - w‖ := by sorry
end AccelVI.LowerBound
Source
Goyal & Grand-Clément, A First-Order Approach to Accelerated Value Iteration, arXiv:1905.09963v7, p. 3, §2, sentence after (2.1)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.