Theorem 2.2, first clause, p. 4 — the discounted parallel value backup is a γ-contraction in max norm
ProvedStableFA.Discounted.theorem_2_2_contractionLet be a finite Markov decision process with states , admissible action sets (finite and nonempty), expected one-step costs and transition probabilities with for every admissible action . Let be the discount factor. The parallel value iteration operator maps a value function to
Then is a contraction in the max norm with contraction factor : for all ,
This is the basic fact behind the convergence of value iteration in discounted problems, and the starting point of every stability and error bound for approximate value iteration in this mission.
Formalization Note The MDP is the published BertsekasSSPModel, whose rows are only substochastic; the hypothesis makes it Gordon's (stochastic) MDP. on Fin n → ℝ is the max norm. Action sets may differ between states, which harmlessly generalizes the paper's single action set . This item is the first sentence of Theorem 2.2 only; the nondiscounted clause and the identification of the fixed point with the optimal value function are not part of it.
import Mathlib import Definitions.Def_BertsekasSSPModel import Definitions.Def_StableFA_Discounted_Setting open Filter Topology
namespace StableFA.Discounted
theorem theorem_2_2_contraction {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) :
∀ V W : Fin n → ℝ,
‖BertsekasDiscountedBellmanOp M γ V - BertsekasDiscountedBellmanOp M γ W‖ ≤
γ * ‖V - W‖ := by sorry
end StableFA.Discounted
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.