§5.3, proof of Theorem 5.3, p. 24 — NPG improves every state: V⁽ᵗ⁺¹⁾(s) ≥ V⁽ᵗ⁾(s) for all s
ProvedPolicyGradTheory.NPG.npg_value_monotonenatural-policy-gradientp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1policy-improvementsoftmax-policy
This is the monotonicity claim used in the proof of Theorem 5.3 (" for all states by Lemma 5.2").
Let be a finite MDP with a nonempty action set, a start distribution from which every state is reachable, and . Let be any run of the natural policy gradient updates (15) with softmax policies and the value of . Then for every and every state ,
State-wise monotonicity lets the proof of Theorem 5.3 replace the average of the values by the last one.
Formalization Note Reachability of every state from is the standing restriction of §5.3 (footnote 6). The run may start from any .
Preamble
import Mathlib import Definitions.Def_PolicyGradTheory_ProjGA_MDP import Definitions.Def_PolicyGradTheory_NPG_Algorithm import Definitions.Def_FoundationsML_ReinforcementLearning_IsOptimalPolicy open FoundationsML.ReinforcementLearning
Formal statement
namespace PolicyGradTheory.NPG
/-- §5.3, proof of Theorem 5.3 (arXiv:1908.00261v5, p. 24): the NPG iterates improve at every
state, `V^{(t+1)}(s) ≥ V^{(t)}(s)` for all states `s`. -/
theorem npg_value_monotone {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)) (hrun : IsNPGRun P r γ ρ η θ) :
∀ (t : ℕ) (s : S),
PolicyValue (softmaxPolicy (θ t)) P r γ s ≤
PolicyValue (softmaxPolicy (θ (t + 1))) P r γ s := by sorry
end PolicyGradTheory.NPG
Source
arXiv:1908.00261v5, §5.3, proof of Theorem 5.3, p. 24
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.