(3.5), p. 6 — (1 − λ)‖v − w‖∞ ≤ ‖(I − T)(v) − (I − T)(w)‖∞
ProvedAccelVI.LowerBound.eq_3_5bellman-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 for the residual map of strong monotonicity of a gradient, with constant . In the lower-bound proof it turns a lower bound on into one on the residual.
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_5 {S A : Type*} [Fintype S] [DecidableEq S] [Fintype A] [Nonempty A]
(M : MDP S A) (hM : M.Valid) (v w : S → ℝ) :
(1 - M.lam) * ‖v - w‖ ≤ ‖(v - bellman M v) - (w - bellman M 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.5)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.