Theorem 3.2, p. 7 — the mapping of an averager is a max-norm nonexpansion, hence compatible with discounted value backups
ProvedStableFA.Discounted.theorem_3_2averagerfunction-approximationmax-normnonexpansionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1value-iteration
Let be an averager on states, with constants and nonnegative weights satisfying , and let be its mapping. Then:
- is a nonexpansion in the max norm: for all ,
- is compatible with the parallel value backup operator of every discounted finite MDP on the same states (discount , stochastic transition rows): for every initial guess the iterates converge.
The theorem singles out the averagers as a class of function approximators that cannot exaggerate differences between target value functions, and therefore can be combined with value iteration without risking divergence.
Formalization Note on Fin n → ℝ is the max norm. The MDP is BertsekasSSPModel with the stochastic-row hypothesis, any finite action type and any nonempty admissible action sets. The second part is stated for every such MDP, as on the page ("for any discounted MDP").
Preamble
import Mathlib import Definitions.Def_BertsekasSSPModel import Definitions.Def_StableFA_Discounted_Setting open Filter Topology
Formal statement
namespace StableFA.Discounted
theorem theorem_3_2 {n : ℕ} (A : Averager n) :
(∀ Y Z : Fin n → ℝ, ‖A.apply Y - A.apply Z‖ ≤ ‖Y - Z‖) ∧
∀ (C : Type) [Fintype C] (M : BertsekasSSPModel n C) (γ : ℝ), 0 ≤ γ → γ < 1 →
(∀ i, ∀ u ∈ M.U i, ∑ j, M.p i u j = 1) →
Compatible A.apply (BertsekasDiscountedBellmanOp M γ) := by sorry
end StableFA.Discounted
Source
Gordon, Stable Function Approximation in Dynamic Programming, Tech. Rep. CMU-CS-95-103, Carnegie Mellon University (1995), p. 7, Theorem 3.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.