§4, p. 10 — if all policies are proper, the partition S_1, S_2, … by distance from the goal is exhaustive
ProvedStableFA.DerivedMDP.partition_exhaustivep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1partitionproper-policystochastic-shortest-path
Let be a finite nondiscounted Markov decision process with cost-free absorbing goal state in which every policy is proper. Define the layers , and, for ,
Then every state lies in some layer: for every non-goal state there is an index with .
The report attributes this to Bertsekas and Tsitsiklis [BT89]. It makes the layer index , the "distance from the goal", well defined, and with it the notion of a self-weighted averager.
Formalization Note "All policies proper" quantifies over stationary policies (functions from states to admissible actions, p. 3). The goal state lies in by definition, so only non-goal states are quantified.
Preamble
import Mathlib import Definitions.Def_BertsekasSSPModel import Definitions.Def_StableFA_DerivedMDP_Setting
Formal statement
namespace StableFA.DerivedMDP
theorem partition_exhaustive {n : ℕ} {C : Type} [Fintype C]
(M : BertsekasSSPModel n C)
(hproper : ∀ μ : Fin n → C, (∀ i, μ i ∈ M.U i) → IsProper M μ) :
∀ i : Fin n, ∃ k : ℕ, some i ∈ layer M k := by sorry
end StableFA.DerivedMDP
Source
Gordon, Stable Function Approximation in Dynamic Programming, Tech. Rep. CMU-CS-95-103, Carnegie Mellon University (1995), p. 10, §4, "Bertsekas and Tsitsiklis show that this partitioning is exhaustive"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.