Theorem 5.3, p. 22 — NPG with softmax policies from θ⁽⁰⁾ = 0: V⁽ᵀ⁾(ρ) ≥ V*(ρ) − log|A|/(ηT) − 1/((1−γ)²T)
ProvedPolicyGradTheory.NPG.npg_global_convergenceThis is Theorem 5.3 (global convergence for natural policy gradient).
Let be a finite MDP with state set , nonempty action set , rewards in and . Let be a start distribution from which every state is reachable, and let be an optimal policy, with . Fix a step size , and run the natural policy gradient updates (15) with softmax policies, using , from :
Then for every ,
The bound does not depend on the number of states or on any distribution mismatch coefficient, although is not concave. It is the paper's headline rate for exact natural policy gradient.
Formalization Note is the value of the softmax policy after updates. is the natural logarithm. is given as a policy satisfying the published IsOptimalPolicy (its value dominates every policy's at every state). Two standing assumptions of the page are explicit binders: (implicit on the page, since is nonempty), and reachability of every state from (§5.3, footnote 6). The Moore–Penrose pseudoinverse is the published predicate VectorSpaceOpt.IsPseudoinverse.
import Mathlib import Definitions.Def_PolicyGradTheory_ProjGA_MDP import Definitions.Def_PolicyGradTheory_NPG_Algorithm import Definitions.Def_FoundationsML_ReinforcementLearning_IsOptimalPolicy open FoundationsML.ReinforcementLearning
namespace PolicyGradTheory.NPG
/-- Theorem 5.3 (global convergence for NPG; arXiv:1908.00261v5, p. 22): running the NPG
updates (15) with `ρ ∈ ∆(S)`, `θ^{(0)} = 0` and a fixed `η > 0`, for all `T > 0`,
`V^{(T)}(ρ) ≥ V^⋆(ρ) − log|A|/(ηT) − 1/((1−γ)²T)`. -/
theorem npg_global_convergence {S A : Type*} [Fintype S] [DecidableEq S] [Fintype A] [DecidableEq A]
(P : S → A → S → ℝ) (r : S → A → ℝ) (γ : ℝ) (hM : PolicyGradTheory.ProjGA.IsFiniteMDP P r γ)
[Nonempty A] (ρ : S → ℝ) (hρ : PolicyGradTheory.ProjGA.IsDist ρ) (hreach : AllReachable P γ ρ)
(η : ℝ) (hη : 0 < η) (θ : ℕ → EuclideanSpace ℝ (S × A)) (hθ0 : θ 0 = 0)
(hrun : IsNPGRun P r γ ρ η θ)
(πstar : S → A → ℝ) (hπstar : IsPolicy πstar) (hopt : IsOptimalPolicy πstar P r γ) :
∀ T : ℕ, 0 < T →
PolicyGradTheory.ProjGA.valueAt πstar P r γ ρ - Real.log (Fintype.card A : ℝ) / (η * T) -
1 / ((1 - γ) ^ 2 * T) ≤
PolicyGradTheory.ProjGA.valueAt (softmaxPolicy (θ T)) P r γ ρ := by sorry
end PolicyGradTheory.NPG
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.