policy_gradient_finite_horizon
Provedalgebraalgebraic-geometrycalculusmdpopen-problempolicy-gradientreinforcement-learningtopology
The finite-horizon policy gradient theorem (Sutton, McAllester, Singh, Mansour 1999; finite-horizon, finite-state/action, scalar-parameter form). For a finite MDP with transition kernel , reward , policy differentiable in a scalar parameter , start state , and horizon :
where is the time- state visitation probability and the -steps-remaining action value. Proof: induction on , unrolling pg_bellman_step; the inner term becomes the slice of the sum via the first-step recursion for . Note no probability axioms on are needed for the identity itself; they make and probabilistically meaningful but the algebra holds regardless.
Preamble
import Definitions.Def_pg_mdp_core import Mathlib.Analysis.Calculus.Deriv.Basic import Mathlib.Analysis.Calculus.Deriv.Add import Mathlib.Analysis.Calculus.Deriv.Mul import Mathlib.Analysis.SpecialFunctions.Log.Deriv import Mathlib.Data.Fintype.BigOperators import Mathlib.Data.Real.Basic
Formal statement
theorem policy_gradient_finite_horizon {S A : Type} [Fintype S] [Fintype A] [DecidableEq S]
(P : S → A → S → ℝ) (r : S → A → ℝ) (π : ℝ → S → A → ℝ) (θ : ℝ)
(hdiff : ∀ s a, DifferentiableAt ℝ (fun θ' => π θ' s a) θ)
(T : ℕ) (s₀ : S) :
deriv (fun θ' => pgValue P r π T θ' s₀) θ
= ∑ t ∈ Finset.range T, ∑ s : S, pgRho P π t s₀ θ s
* ∑ a : A, pgQ P r π (T - 1 - t) θ s a * deriv (fun θ' => π θ' s a) θ := by sorrySource
R. Sutton, D. McAllester, S. Singh, Y. Mansour. Policy Gradient Methods for Reinforcement Learning with Function Approximation. NeurIPS 1999.