Theorem 3.1, p. 5 — a max-norm nonexpansion M_F is compatible with T_M, and M_F ∘ T_M has contraction factor γ
ProvedStableFA.Discounted.theorem_3_1Let be a finite MDP on states with stochastic transition rows and discount factor , and let be its parallel value backup operator,
Let be the mapping of a function approximator, and suppose is a nonexpansion in max norm, for all . Then
- is compatible with : for every initial guess the iterates converge; and
- has contraction factor : for all ,
Approximate value iteration alternates a backup with a fit; this theorem says that any fit that does not expand max-norm distances keeps the combined iteration a contraction.
Formalization Note is an arbitrary map on value functions Fin n → ℝ (not necessarily an averager). The page writes "Let " and ; since is the parallel value backup and acts on functions of the state, the composition only makes sense on value functions over the states, which is how it is stated here. on Fin n → ℝ is the max norm.
import Mathlib import Definitions.Def_BertsekasSSPModel import Definitions.Def_StableFA_Discounted_Setting open Filter Topology
namespace StableFA.Discounted
theorem theorem_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‖) :
Compatible MF (BertsekasDiscountedBellmanOp M γ) ∧
∀ V W : Fin n → ℝ,
‖MF (BertsekasDiscountedBellmanOp M γ V) - MF (BertsekasDiscountedBellmanOp M γ W)‖ ≤
γ * ‖V - W‖ := by sorry
end StableFA.Discounted
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.