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
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Setup and notation. Let be a probability space with standard Borel, filtration , dimension (no positivity assumed), action process , and noise process . Define pointwise in
Assertion. For regularization and confidence parameter (open interval),
where the probability is expressed as a real number.
Hypotheses.
- Predictability: is -measurable for every .
- Adaptedness: is -measurable for every .
- Conditional -sub-Gaussian noise: for every and every , -almost surely (through the regular conditional distribution given , with the requisite integrability); the variance proxy is the constant .
- (strict) and (both endpoints excluded).
- standard Borel, a probability measure.
Edge cases.
- The bad event uses a non-strict inequality with the quadratic form on the large side: it is the event that at some time the self-normalized quadratic form reaches or exceeds the threshold .
- The existential ranges over all , including , where , , the log-determinant term is , and the threshold — so can never witness the event.
- Since , each is positive definite, so the matrix inverse is the genuine inverse (no zero-matrix junk) and , making the logarithm's argument positive.
- is admitted (empty vectors, determinant , quadratic form ).
- No boundedness assumption is placed on the actions , and nothing ties the noise to any response variable in this statement.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).