Corollary 3.1, p. 6 — approximate value iteration with a nonexpansive M_F converges in max norm at the rate γ
ProvedStableFA.Discounted.corollary_3_1Let , , and be as in Theorem 3.1: a finite MDP on states with stochastic transition rows, discount , its parallel value backup operator , and a max-norm nonexpansion on . The approximate value iteration algorithm based on produces . There is a value function such that, from every initial guess , the iterates converge to at the geometric rate :
and in particular as .
The corollary turns the contraction of Theorem 3.1 into a quantitative convergence statement for the algorithm actually run in practice.
Formalization Note "Converges at the rate " is read as the geometric rate of the Contraction Mapping theorem (Theorem 2.1, p. 2): the error after steps is at most times the initial error, measured from the common limit (called Vinf in Lean). on Fin n → ℝ is the max norm; , so the case is trivial.
import Mathlib import Definitions.Def_BertsekasSSPModel import Definitions.Def_StableFA_Discounted_Setting open Filter Topology
namespace StableFA.Discounted
theorem corollary_3_1 {n : ℕ} {C : Type} [Fintype C] (M : BertsekasSSPModel n C)
(γ : ℝ) (hγ0 : 0 ≤ γ) (hγ1 : γ < 1)
(hp1 : ∀ i, ∀ u ∈ M.U i, ∑ j, M.p i u j = 1)
(MF : (Fin n → ℝ) → (Fin n → ℝ)) (hMF : ∀ Y Z : Fin n → ℝ, ‖MF Y - MF Z‖ ≤ ‖Y - Z‖) :
∃ Vinf : Fin n → ℝ,
(∀ V : Fin n → ℝ,
Tendsto (fun k => (MF ∘ BertsekasDiscountedBellmanOp M γ)^[k] V) atTop (𝓝 Vinf)) ∧
∀ (V : Fin n → ℝ) (k : ℕ),
‖(MF ∘ BertsekasDiscountedBellmanOp M γ)^[k] V - Vinf‖ ≤ γ ^ k * ‖V - Vinf‖ := by sorry
end StableFA.Discounted
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.