Corollary 4.1, p. 11 — all policies proper and A self-weighted ⇒ T_M and M_A are compatible and approximate value iteration converges
ProvedStableFA.DerivedMDP.corollary_4_1Let be a finite nondiscounted Markov decision process with a cost-free absorbing goal state, in which every policy is proper. Let be an averager that is self-weighted for , let be the parallel value backup operator of (which sets ) and the mapping of . Then:
- and are compatible: for every initial guess the iterates converge;
- approximate value iteration based on converges when applied to : for every initial guess the iterates converge.
This is the report's convergence guarantee for nondiscounted problems. An averager need not be a nonexpansion in the weighted max norm in which contracts, and approximate value iteration can diverge (Figure 4); self-weighting rules that out.
Formalization Note "Compatible" follows the definition on p. 5: Compatible MF T iterates MF ∘ T, so part 1 is Compatible A.apply (BertsekasSSPBellmanOp M). The approximate value iteration sequence of p. 10 interleaves the two orders, ; part 2 states the convergence of , the other order. The goal is the implicit termination state of BertsekasSSPModel; its value is . "All policies proper" quantifies over stationary policies (p. 3). The hypotheses are about and only; nothing is assumed about the derived MDP.
import Mathlib import Definitions.Def_BertsekasSSPModel import Definitions.Def_StableFA_DerivedMDP_Setting
namespace StableFA.DerivedMDP
theorem corollary_4_1 {n : ℕ} {C : Type} [Fintype C]
(M : BertsekasSSPModel n C) (A : Averager n)
(hproper : ∀ μ : Fin n → C, (∀ i, μ i ∈ M.U i) → IsProper M μ)
(hself : SelfWeighted M A) :
StableFA.Discounted.Compatible A.apply (BertsekasSSPBellmanOp M) ∧
StableFA.Discounted.Compatible (BertsekasSSPBellmanOp M) A.apply := by sorry
end StableFA.DerivedMDP
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.