Theorem 6.2, p. 12 — iteration of T_M ∘ M_A converges to V₀ with ‖V₀ − V*‖ ≤ 2γε/(1 − γ)
ProvedStableFA.Discounted.theorem_6_2Let be a finite Markov decision process on states with nonempty finite action sets , expected costs , stochastic transition probabilities and discount factor . Let be its parallel value backup operator,
and let be the optimal value function, i.e. the fixed point . Let be an averager with mapping , let be any fixed point of , and put , where is the max norm. Then there is a value function such that, from every initial guess , the iterates converge to , and
So if the averager can represent some function within of the optimal value function, approximate value iteration through it converges, from any start, to a value function whose error is of order ; as the bound vanishes. Here denotes the limit of the iteration, not its starting point.
Formalization Note is taken as a hypothesis, the fixed point of . This is licensed by the last clause of Theorem 2.2 (p. 4: "The fixed point of each of these operators is the optimal value function for the MDP"), which is the content of the published, proved theorem BertsekasDP.discounted_main_theorem (existence, uniqueness and optimality of the fixed point for ; for the fixed point is , plainly optimal). The page says "with discount factor "; the theorem sits in the paper's discounted discussion (§6.1: "If we are trying to solve a discounted MDP") and its proof uses that is a -contraction, so is assumed. The MDP is BertsekasSSPModel plus the stochastic-row hypothesis; action sets may depend on the state, which harmlessly generalizes the paper's single action set. The averager acts on whole value functions (Fin n → ℝ), the sampled approximator being the special case of zero weights outside the sample. The iterated map is (fit, then back up), as on the page. 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_6_2 {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)
(A : Averager n) (Vstar VA : Fin n → ℝ) (ε : ℝ)
(hV : BertsekasDiscountedBellmanOp M γ Vstar = Vstar)
(hVA : A.apply VA = VA) (hε : ‖VA - Vstar‖ = ε) :
∃ V₀ : Fin n → ℝ,
(∀ V : Fin n → ℝ,
Tendsto (fun k => (BertsekasDiscountedBellmanOp M γ ∘ A.apply)^[k] V) atTop (𝓝 V₀)) ∧
‖V₀ - Vstar‖ ≤ 2 * γ * ε / (1 - γ) := by sorry
end StableFA.Discounted
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.