§7.3.1, p. 88 — the future state distribution dominates the start distribution:
ProvedSampleComplexityRL.CPI.future_dist_ge_startdynamic-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1reinforcement-learning
Let and be finite nonempty sets, a transition kernel on , , a stationary policy and a distribution on . Let be the horizon time and the discounted future state distribution. Then for every state ,
The future distribution keeps a contribution from the starting distribution. This converts a guarantee on future advantages, which weight states by , into information about states weighted by .
Formalization Note The point of the statement is pointwise domination by the time- term of the series; no reward function enters.
Preamble
import Mathlib import Definitions.Def_FoundationsML_ReinforcementLearning_IsTransitionKernel import Definitions.Def_FoundationsML_ReinforcementLearning_IsPolicy import Definitions.Def_ApproxOptRL_Shared_Model import Definitions.Def_ApproxOptRL_CPI_PolicyAdvantage import Definitions.Def_SampleComplexityRL_CPI_ExactCPI open ApproxOptRL.Shared ApproxOptRL.CPI FoundationsML.ReinforcementLearning
Formal statement
namespace SampleComplexityRL.CPI
/-- Kakade 2003, §7.3.1, p. 88: the future state distribution dominates the start distribution,
`d_{π,μ} ≥ μ/H` with `H = 1/(1 − γ)`, i.e. `d_{π,μ}(s) ≥ (1 − γ) μ(s)` for every state `s`. -/
theorem future_dist_ge_start {S A : Type} [Fintype S] [DecidableEq S] [Fintype A]
[Nonempty S] [Nonempty A]
(P : S → A → S → ℝ) (hP : IsTransitionKernel P)
(γ : ℝ) (hγ0 : 0 ≤ γ) (hγ1 : γ < 1)
(π : S → A → ℝ) (hπ : IsPolicy π)
(μ : S → ℝ) (hμ : IsStateDist μ) :
∀ s : S, μ s / horizon γ ≤ futureStateDist P γ π μ s := by sorry
end SampleComplexityRL.CPI
Source
Kakade, On the Sample Complexity of Reinforcement Learning, PhD thesis, University College London, 2003, p. 88, Section 7.3.1 (the fact d_{π,μ} ≥ μ/H)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.