Lemma D.3, p. 74 — smoothness of the direct parameterization: ‖∇_πV^π(s₀) − ∇_πV^{π′}(s₀)‖₂ ≤ (2γ|A|/(1−γ)³)‖π − π′‖₂
ProvedPolicyGradTheory.ProjGA.direct_smoothnessdirect-parameterizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1policy-gradientsmoothness
Let be a finite discounted MDP with rewards in and . Under the direct parameterization, write for the gradient of , the value from the start state .
Lemma (smoothness for direct parameterization). For every start state and all policies ,
So , and hence for every start distribution , is -smooth on the policy simplex with . This constant fixes the step size of Theorem 4.1 and enters its iteration bound.
Formalization Note The value from is the objective with the point mass at as start distribution. As everywhere in Appendix D, range over policies; the gradients are the full Euclidean gradients on EuclideanSpace ℝ (S × A).
Preamble
import Mathlib import Definitions.Def_PolicyGradTheory_ProjGA_MDP import Definitions.Def_PolicyGradTheory_ProjGA_Algorithm open FoundationsML.ReinforcementLearning
Formal statement
namespace PolicyGradTheory.ProjGA
/-- Lemma D.3 (smoothness for direct parameterization), arXiv:1908.00261v5, p. 74: for all
starting states `s₀` and all policies `π, π'`,
`‖∇_π V^π(s₀) − ∇_π V^{π'}(s₀)‖₂ ≤ (2γ|A|/(1−γ)³) ‖π − π'‖₂`. -/
theorem direct_smoothness {S A : Type*} [Fintype S] [DecidableEq S] [Fintype A] [DecidableEq A]
(P : S → A → S → ℝ) (r : S → A → ℝ) (γ : ℝ) (hM : IsFiniteMDP P r γ) :
∀ (s₀ : S), ∀ π ∈ simplexSet S A, ∀ π' ∈ simplexSet S A,
‖gradient (directValue P r γ (fun x => if x = s₀ then 1 else 0)) π -
gradient (directValue P r γ (fun x => if x = s₀ then 1 else 0)) π'‖ ≤
2 * γ * (Fintype.card A : ℝ) / (1 - γ) ^ 3 * ‖π - π'‖ := by sorry
end PolicyGradTheory.ProjGA
Source
arXiv:1908.00261v5, Lemma D.3, p. 74 (uses Lemma D.2, pp. 71–74)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.