Theorem 7.3.1 — advantages at most ε/H under ν give
ProvedSampleComplexityRL.CPI.mu_optimalityConsider a finite MDP with nonempty state set , nonempty action set , transition kernel , rewards and discount , with normalized values and advantages . Let and let be a class of stationary policies. For a state distribution and a policy write , and let be the discounted future state distribution of started at .
Let be a stationary policy and a distribution such that
Then for every policy and every state ,
A policy whose average advantages under are small competes with every policy of the class whose future state distribution is close to . With this is the guarantee that motivates the output condition of conservative policy iteration.
Formalization Note The hypothesis is on the advantage of Definition 7.1.1, weighted by , and not on the future advantage. The policy need not belong to , and is any real number.
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
namespace SampleComplexityRL.CPI
/-- **Theorem 7.3.1** (Kakade 2003, p. 89). Let `Pi` be a class of stationary policies. If `π`
is a policy such that, for the distribution `ν` and every `h ∈ Pi`, `A_π(ν, h) ≤ ε/H`, then for
every `π' ∈ Pi` and every start state `s₀`,
`V_π(s₀) ≥ V_{π'}(s₀) − ε − H ‖d_{π',s₀} − ν‖₁`.
Normalized discounted values; `H = 1/(1 − γ)`; `A_π(ν, h)` is the advantage of Definition 7.1.1
(state weights `ν`, not the future distribution). -/
theorem mu_optimality {S A : Type} [Fintype S] [DecidableEq S] [Fintype A]
[Nonempty S] [Nonempty A]
(P : S → A → S → ℝ) (hP : IsTransitionKernel P)
(r : S → A → ℝ) (hr : ∀ s a, 0 ≤ r s a ∧ r s a ≤ 1)
(γ : ℝ) (hγ0 : 0 ≤ γ) (hγ1 : γ < 1)
(Pi : Set (S → A → ℝ)) (hPi : ∀ h ∈ Pi, IsPolicy h)
(π : S → A → ℝ) (hπ : IsPolicy π)
(ν : S → ℝ) (hν : IsStateDist ν) (ε : ℝ)
(hadv : ∀ h ∈ Pi, distAdvantage P r γ π ν h ≤ ε / horizon γ) :
∀ π' ∈ Pi, ∀ s₀ : S,
value P r γ π' s₀ - ε - horizon γ * l1Dist (futureStateDist P γ π' (pointMass s₀)) ν ≤
value P r γ π s₀ := by sorry
end SampleComplexityRL.CPI
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.