BanditAlgorithm.subgaussian_sample_mean_tail_bound
Provedbanditsconcentrationhoeffdingprobability
(Hoeffding-type bound, GOAL — L&S Corollary 5.5) Assume are independent, -subgaussian random variables for (with ), and let
be the sample mean. Then for any ,
(Here -subgaussian means Mathlib's HasSubgaussianMGF with variance proxy .)
Preamble
import Mathlib.Probability.Moments.SubGaussian open MeasureTheory ProbabilityTheory Real NNReal
Formal statement
theorem BanditAlgorithm.subgaussian_sample_mean_tail_bound
{Ω : Type} {mΩ : MeasurableSpace Ω} {P : Measure Ω} [IsProbabilityMeasure P]
{n : ℕ} (hn : 0 < n) {X : Fin n → Ω → ℝ} {m : ℝ} {σ : ℝ≥0} (hσ : 0 < σ)
(h_indep : iIndepFun (fun i ω ↦ X i ω - m) P)
(h_subG : ∀ i, HasSubgaussianMGF (fun ω ↦ X i ω - m) (σ ^ 2) P)
{ε : ℝ} (hε : 0 ≤ ε) :
P.real {ω | m + ε ≤ (∑ i, X i ω) / n} ≤
exp (-((n : ℝ) * ε ^ 2) / (2 * (σ : ℝ) ^ 2)) ∧
P.real {ω | (∑ i, X i ω) / n ≤ m - ε} ≤
exp (-((n : ℝ) * ε ^ 2) / (2 * (σ : ℝ) ^ 2)) := by
sorry
Source
L&S Corollary 5.5, p.78
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.