BanditAlgorithm.subgaussian_sample_mean_confidence_bound
Provedbanditsconcentrationconfidenceprobability
(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.
Preamble
import Mathlib.Probability.Moments.SubGaussian open MeasureTheory ProbabilityTheory Real NNReal
Formal statement
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
Source
L&S Eqs. (5.6)-(5.7), p.78