BanditAlgorithm.subgaussian_sample_mean_confidence_bound
Proved(Confidence form — L&S Eqs. (5.6)-(5.7)) Under the same hypotheses, let . With probability at least ,
stated as
This is the exact deviation bound the UCB index of Chapter 7 is built from.
import Mathlib.Probability.Moments.SubGaussian open MeasureTheory ProbabilityTheory Real NNReal
theorem BanditAlgorithm.subgaussian_sample_mean_confidence_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δ : δ ∈ Set.Ioo (0 : ℝ) 1) :
P.real {ω | (∑ i, X i ω) / n + Real.sqrt (2 * (σ : ℝ) ^ 2 * log (1 / δ) / n) ≤ m} ≤ δ := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Setting. Identical to the tail-bound item: Ω an arbitrary type with a σ-algebra and a probability measure P; n a natural number with 0 < n; X a family of n real-valued functions on Ω; m an arbitrary real number; σ a nonnegative real with 0 < σ. The hypotheses are the same two:
- the centered family ω ↦ Xᵢ(ω) − m (i = 0, …, n−1) is mutually independent under P;
- each centered function ω ↦ Xᵢ(ω) − m has sub-Gaussian MGF with variance proxy σ² under P (for every real t, exp(t·(Xᵢ − m)) is integrable and E[exp(t·(Xᵢ − m))] ≤ exp(σ²·t²/2)).
Additionally, δ is a real number lying in the open interval (0, 1): 0 < δ and δ < 1, both strict.
Claim. Writing A(ω) = (∑ᵢ Xᵢ(ω))/n for the sample mean and w = √(2·σ²·log(1/δ)/n) for the confidence width, the theorem asserts the single inequality
P{ω : A(ω) + w ≤ m} ≤ δ.
In words: the probability of the event "the sample mean plus the width √(2σ²·log(1/δ)/n) is still at most m" is at most δ. This is a one-sided statement only (it says nothing about the event A(ω) − w ≥ m or about two-sided coverage).
Edge cases and conventions. Since 0 < δ < 1 strictly, 1/δ > 1 and log(1/δ) > 0, so the radicand is positive and the square root is genuine (no junk-value branch of √ is engaged). The event uses a non-strict ≤. As before, m is just a real parameter constrained only through the hypotheses, and no separate measurability of the Xᵢ is assumed.
Confirmed by the mission captain (proposal self-audit).