Theorem 6.1, p. 29 — agnostic Q-NPG bound from transfer error, excess risk and conditioning
ProvedPolicyGradTheory.QNPG.qnpg_agnostic_boundFix finite state and action sets, a discounted MDP with rewards in [0,1], a start distribution ρ, a state-action fitting distribution ν, and any comparator policy π⋆. Let πθ be the log-linear class with feature norms at most B. Q-NPG starts from and updates with random directions in the radius-W ball and step size . At each , let be an exact radius-W minimizer of the Q-prediction loss under the on-policy measure .
Suppose the relative covariance bound with constant κ holds between and ν. Suppose the expected excess risk is at most εstat and the expected transfer loss is at most εbias at every . Then
The result guarantees competition with an arbitrary comparison policy; optimality of π⋆ is not assumed.
Formalization Note The finite setting and reward range come from §3. Nonempty A and positive B, W and T make the uniform policy, step size and minimum well-defined. Random directions and exact minimizers are measurable, which makes these bounded-loss expectations integrable. κ is a nonnegative quadratic-form upper bound, which includes the finite coefficient of Assumption 6.2. The minimum is taken separately for each random run before expectation.
import Mathlib import Definitions.Def_PolicyGradTheory_QNPG_Setting
namespace PolicyGradTheory.QNPG
open FoundationsML.ReinforcementLearning MeasureTheory
/-- Theorem 6.1, p. 29: agnostic Q-NPG for a log-linear policy class. -/
theorem qnpg_agnostic_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 ρ)
(ν : S × A → ℝ) (hν : PolicyGradTheory.ProjGA.IsDist ν)
(πstar : S → A → ℝ) (hπstar : IsPolicy πstar)
(φ : S → A → EuclideanSpace ℝ (Fin d))
(B : ℝ) (hB : 0 < B) (hφ : ∀ s a, ‖φ s a‖ ≤ B)
(W : ℝ) (hW : 0 < W)
(κ : ℝ) (hκnonneg : 0 ≤ κ)
(hκ : ∀ v, quadForm φ (dstar P γ ρ πstar) v ≤ κ * quadForm φ ν v)
(T : ℕ) (hT : 0 < T)
(η : ℝ) (hη : η = Real.sqrt (2 * Real.log (Fintype.card A : ℝ) /
(B ^ 2 * W ^ 2 * T)))
{Ω : Type*} [MeasurableSpace Ω] (ℙ : Measure Ω) [IsProbabilityMeasure ℙ]
(w wstar : ℕ → Ω → EuclideanSpace ℝ (Fin d))
(hwm : ∀ t < T, Measurable (w t))
(hwstarm : ∀ t < T, Measurable (wstar t))
(hwW : ∀ t < T, ∀ ω, ‖w t ω‖ ≤ W)
(hwstar : ∀ t < T, ∀ ω,
‖wstar t ω‖ ≤ W ∧
∀ v, ‖v‖ ≤ W →
qLoss P r γ φ (wstar t ω) (qnpgParams η w t ω)
(onPolicyMeasure (logLinearPolicy φ (qnpgParams η w t ω)) P γ ν) ≤
qLoss P r γ φ v (qnpgParams η w t ω)
(onPolicyMeasure (logLinearPolicy φ (qnpgParams η w t ω)) P γ ν))
(εstat εbias : ℝ)
(hstat : ∀ t < T,
(∫ ω, (qLoss P r γ φ (w t ω) (qnpgParams η w t ω)
(onPolicyMeasure (logLinearPolicy φ (qnpgParams η w t ω)) P γ ν) -
qLoss P r γ φ (wstar t ω) (qnpgParams η w t ω)
(onPolicyMeasure (logLinearPolicy φ (qnpgParams η w t ω)) P γ ν)) ∂ℙ) ≤ εstat)
(hbias : ∀ t < T,
(∫ ω, qLoss P r γ φ (wstar t ω) (qnpgParams η w t ω)
(dstar P γ ρ πstar) ∂ℙ) ≤ εbias) :
(∫ ω, (Finset.range T).inf' (Finset.nonempty_range_iff.mpr (Nat.ne_of_gt hT))
(fun t => PolicyGradTheory.ProjGA.valueAt πstar P r γ ρ -
PolicyGradTheory.ProjGA.valueAt (logLinearPolicy φ (qnpgParams η w t ω)) P r γ ρ) ∂ℙ) ≤
B * W / (1 - γ) * Real.sqrt (2 * Real.log (Fintype.card A : ℝ) / T) +
Real.sqrt (4 * (Fintype.card A : ℝ) * κ * εstat / (1 - γ) ^ 3) +
Real.sqrt (4 * (Fintype.card A : ℝ) * εbias) / (1 - γ) := by sorry
end PolicyGradTheory.QNPG
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.