BanditAlgorithm.self_normalized_martingale_bound
Provedconcentrationlinear-banditsprobabilityself-normalized
(Self-normalized bound, method of mixtures, GOAL; L&S Theorem 20.4) With the setup above (-measurable actions , -measurable conditionally 1-subgaussian noise ), let
Then for all and ,
uniformly over all times (the is inside a single event).
Preamble
import Mathlib.Probability.Moments.SubGaussian import Mathlib.Probability.Martingale.Basic import Mathlib.Analysis.SpecialFunctions.Log.Basic import Definitions.Def_SelfNormalizedProcess open MeasureTheory ProbabilityTheory Matrix
Formal statement
theorem BanditAlgorithm.self_normalized_martingale_bound
{Ω : Type} {mΩ : MeasurableSpace Ω} [StandardBorelSpace Ω]
{P : Measure Ω} [IsProbabilityMeasure P]
{d : ℕ} (ℱ : Filtration ℕ mΩ)
(A : ℕ → Ω → Fin d → ℝ) (η : ℕ → Ω → ℝ)
(hA : ∀ t : ℕ, Measurable[ℱ t] (A (t + 1)))
(hη : ∀ t : ℕ, Measurable[ℱ (t + 1)] (η (t + 1)))
(hsg : ∀ t : ℕ, HasCondSubgaussianMGF (ℱ t) (ℱ.le t) (η (t + 1)) 1 P)
{lam : ℝ} (hlam : 0 < lam) {δ : ℝ} (hδ : δ ∈ Set.Ioo (0 : ℝ) 1) :
P.real {ω | ∃ t : ℕ,
2 * Real.log (1 / δ)
+ Real.log ((regularizedDesignMatrix d lam A t ω).det / lam ^ d)
≤ selfNormalizedSum d η A t ω ⬝ᵥ
(regularizedDesignMatrix d lam A t ω)⁻¹ *ᵥ
selfNormalizedSum d η A t ω} ≤ δ := by
sorry
Source
L&S Theorem 20.4, p.260
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.