(3.6), p. 6 — ‖(I − T)(v) − (I − T)(w)‖∞ ≤ (1 + λ)‖v − w‖∞
ProvedAccelVI.LowerBound.eq_3_6bellman-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 and , and let be its Bellman operator (2.1). Writing , for all ,
This is the analogue of the Lipschitz continuity of a gradient, with constant . Taking gives , the last step of the proof of Theorem 6.3.
Formalization Note. is Mathlib's sup norm on S → ℝ.
Preamble
import Mathlib import Definitions.Def_AccelVI_LowerBound_Setting
Formal statement
namespace AccelVI.LowerBound
theorem eq_3_6 {S A : Type*} [Fintype S] [DecidableEq S] [Fintype A] [Nonempty A]
(M : MDP S A) (hM : M.Valid) (v w : S → ℝ) :
‖(v - bellman M v) - (w - bellman M w)‖ ≤ (1 + 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. 6, display (3.6)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.