Lemma 5.1, p. 22 — NPG with softmax policies is soft policy iteration: π⁽ᵗ⁺¹⁾(a|s) = π⁽ᵗ⁾(a|s) exp(ηA⁽ᵗ⁾(s,a)/(1−γ))/Z_t(s)
ProvedPolicyGradTheory.NPG.npg_soft_policy_iterationThis is the policy form of Lemma 5.1 (NPG as soft policy iteration).
Let be a finite MDP with a nonempty action set, a start distribution from which every state is reachable, and a step size. Let be any run of the natural policy gradient updates (15) with softmax policies, from an arbitrary initial parameter , and write and . Then for every , every state and every action ,
The NPG step is thus a multiplicative-weights (exponentiated advantage) update at every state, independent of the state visitation distribution. This closed form is what drives the dimension-free rate of Theorem 5.3.
Formalization Note The page also states the parameter form . That clause is not stated: the pseudoinverse step is the minimum-norm solution, which differs from by a state-dependent offset, and the lemma's own proof (App. C.3, p. 70) ends with , . The policy form, which is invariant to the offset, is the statement used downstream. Reachability of every state is the standing restriction of §5.3 (footnote 6); the step size is unrestricted since the identity holds for every real .
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
/-- Lemma 5.1 (NPG as soft policy iteration; arXiv:1908.00261v5, p. 22), policy form: along any
run of the NPG updates (15) with softmax policies, from any start `θ^{(0)}`,
`π^{(t+1)}(a|s) = π^{(t)}(a|s) exp(η A^{(t)}(s,a)/(1−γ)) / Z_t(s)`. -/
theorem npg_soft_policy_iteration {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 γ ρ)
(η : ℝ) (θ : ℕ → EuclideanSpace ℝ (S × A)) (hrun : IsNPGRun P r γ ρ η θ) :
∀ (t : ℕ) (s : S) (a : A),
softmaxPolicy (θ (t + 1)) s a =
softmaxPolicy (θ t) s a *
Real.exp (η * PolicyGradTheory.ProjGA.advantage (softmaxPolicy (θ t)) P r γ s a / (1 - γ)) /
npgNormalizer P r γ η (θ t) s := by sorry
end PolicyGradTheory.NPG
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.