Theorem 4.1 (Derived MDP), p. 7 — T_M ∘ M_A is the parallel value backup operator of the derived MDP M′
ProvedStableFA.DerivedMDP.theorem_4_1Let be a finite Markov decision process with cost-free absorbing goal state and discount factor , whose parallel value backup operator is
and let be an averager with mapping . Let be the derived MDP with the same states, actions and discount, transition probabilities () and expected costs . Then
This holds for the discounted backup with every discount factor , and for the nondiscounted backup ().
This is the central observation of the report: approximate value iteration with an averager is exact value iteration on another Markov decision process, so its convergence is a question about .
Formalization Note The new process is the explicit derivedModel M A γ of the definitions file. The identity is algebraic and is stated for every real ; the paper's discount factors are special cases. The first conjunct uses BertsekasDiscountedBellmanOp, the second the nondiscounted BertsekasSSPBellmanOp with the model derivedModel M A 1. The goal is the implicit termination state, so no hypothesis is needed (the page's final display uses it silently).
import Mathlib import Definitions.Def_BertsekasSSPModel import Definitions.Def_StableFA_DerivedMDP_Setting
namespace StableFA.DerivedMDP
theorem theorem_4_1 {n : ℕ} {C : Type} [Fintype C]
(M : BertsekasSSPModel n C) (A : Averager n) :
(∀ γ : ℝ, BertsekasDiscountedBellmanOp (derivedModel M A γ) γ =
BertsekasDiscountedBellmanOp M γ ∘ A.apply) ∧
BertsekasSSPBellmanOp (derivedModel M A 1) = BertsekasSSPBellmanOp M ∘ A.apply := by sorry
end StableFA.DerivedMDP
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.