(25), p. 39 — comparator transfer term bounded by Q-prediction loss
ProvedPolicyGradTheory.QNPG.transfer_term_boundcomparator-measurep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1q-npgtransfer-error
Fix a comparator policy π⋆, a starting distribution ρ, log-linear features φ, a parameter θ, and any weight vector w. Under , the comparator-weighted discrepancy between advantage and the log-policy score obeys
This controls the transfer component of the regret error by a prediction loss under the comparator's states.
Formalization Note The paper displays this inequality for its exact minimizer ; the displayed derivation uses no minimizing property, so this statement allows any w.
Preamble
import Mathlib import Definitions.Def_PolicyGradTheory_QNPG_Setting
Formal statement
namespace PolicyGradTheory.QNPG
open FoundationsML.ReinforcementLearning
/-- Inequality (25), proof of Theorem 6.1, p. 39. The displayed proof
uses no minimizing property of its weight vector. -/
theorem transfer_term_bound {S A : Type} [Fintype S] [DecidableEq S]
[Fintype A] [DecidableEq A] [Nonempty A] {d : ℕ}
(P : S → A → S → ℝ) (r : S → A → ℝ) (γ : ℝ)
(hM : PolicyGradTheory.ProjGA.IsFiniteMDP P r γ)
(ρ : S → ℝ) (hρ : PolicyGradTheory.ProjGA.IsDist ρ)
(πstar : S → A → ℝ) (hπstar : IsPolicy πstar)
(φ : S → A → EuclideanSpace ℝ (Fin d))
(θ w : EuclideanSpace ℝ (Fin d)) :
(∑ s : S, PolicyGradTheory.ProjGA.visitation πstar P γ ρ s *
∑ a : A, πstar s a *
(PolicyGradTheory.ProjGA.advantage (logLinearPolicy φ θ) P r γ s a -
inner ℝ w (gradient (fun x => Real.log (logLinearPolicy φ x s a)) θ))) ≤
2 * Real.sqrt ((Fintype.card A : ℝ) *
qLoss P r γ φ w θ (dstar P γ ρ πstar)) := by sorry
end PolicyGradTheory.QNPG
Source
arXiv:1908.00261v5, (25), proof of Theorem 6.1, p. 39
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.