Lemma D.1, p. 26 — Σ_{i≤t} φ_i^⊤ Λ_t^{-1} φ_i ≤ d for Λ_t = λI + Σ_{i≤t} φ_i φ_i^⊤, λ > 0
ProvedLinearMDPRL.Linear.lemma_D_1gram-matrixlinear-algebrap2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1ridge-regression
Let , let , and let . Then
This trace bound controls the self-normalized size of the regression data and is used to bound the weights of Algorithm 1 (Lemma B.2).
Preamble
import Mathlib
Formal statement
namespace LinearMDPRL.Linear
open Matrix
/-- **Lemma D.1** (arXiv:1907.05388v2, p. 26). Let `Λ_t = λI + Σ_{i=1}^t φ_i φ_i^⊤` with
`φ_i ∈ ℝ^d` and `λ > 0`. Then `Σ_{i=1}^t φ_i^⊤ (Λ_t)^{-1} φ_i ≤ d`. -/
theorem lemma_D_1 (d t : ℕ) (lam : ℝ) (hlam : 0 < lam) (φ : ℕ → Fin d → ℝ) :
∑ i ∈ Finset.Icc 1 t,
φ i ⬝ᵥ ((lam • (1 : Matrix (Fin d) (Fin d) ℝ) +
∑ j ∈ Finset.Icc 1 t, vecMulVec (φ j) (φ j))⁻¹ *ᵥ φ i) ≤ d := by sorry
end LinearMDPRL.Linear
Source
Jin, Yang, Wang, Jordan, arXiv:1907.05388v2, Lemma D.1, p. 26
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.