BanditAlgorithm.bandit_subgaussian_maximal_inequality
Provedconcentrationmartingaleprobability
(Maximal concentration) Let be independent -subgaussian () random variables and . Then for any and ,
(via Doob's submartingale inequality applied to ).
Preamble
import Mathlib.Probability.Moments.SubGaussian open MeasureTheory ProbabilityTheory Real NNReal
Formal statement
theorem BanditAlgorithm.bandit_subgaussian_maximal_inequality
{Ω : Type} {mΩ : MeasurableSpace Ω} {P : Measure Ω} [IsProbabilityMeasure P]
{X : ℕ → Ω → ℝ} {σ : ℝ≥0} (hσ : 0 < σ)
(h_indep : iIndepFun X P)
(h_subG : ∀ i, HasSubgaussianMGF (X i) (σ ^ 2) P)
{n : ℕ} (hn : 0 < n) {ε : ℝ} (hε : 0 < ε) :
P.real {ω | ∃ t, 0 < t ∧ t ≤ n ∧ ε ≤ ∑ s ∈ Finset.range t, X s ω} ≤
exp (-ε ^ 2 / (2 * n * (σ : ℝ) ^ 2)) := by
sorry
Source
L&S Theorem 9.2, p.125