Lemma 8, p. 39 — Bernstein (Azuma–Hoeffding) bound ℙ[|Σ D_k| ≥ t] ≤ 2exp(−t²/(2Σσ_k²)) for sub-Gaussian martingale differences
ProvedMostlyExplorationFree.GreedyBandit.lemma_8concentration-inequalitymartingalep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sub-gaussian
Let be a filtration and real random variables with -measurable and conditionally -sub-Gaussian given :
(In particular is a martingale difference sequence.) Then for every ,
This concentration inequality for adaptively generated noise sums is what controls the least-squares error of an arm whose samples were selected by the algorithm itself.
Formalization Note The paper says " is -subgaussian" for a martingale difference sequence; the cited proof (Wainwright 2019, Theorem 2.3) uses the conditional form, which is stated here (with integrability of ). If , Lean's division by zero makes the right-hand side , which still bounds the probability.
Preamble
import Mathlib open MeasureTheory ProbabilityTheory
Formal statement
namespace MostlyExplorationFree.GreedyBandit
theorem lemma_8 {Ω : Type*} {mΩ : MeasurableSpace Ω} (P : Measure Ω) [IsProbabilityMeasure P]
(ℱ : Filtration ℕ mΩ) (D : ℕ → Ω → ℝ) (σk : ℕ → ℝ) (n : ℕ)
(hadapted : ∀ k ∈ Finset.Icc 1 n, StronglyMeasurable[ℱ k] (D k))
(hint : ∀ k ∈ Finset.Icc 1 n, ∀ τ : ℝ, Integrable (fun ω => Real.exp (τ * D k ω)) P)
(hsubG : ∀ k ∈ Finset.Icc 1 n, ∀ τ : ℝ,
condExp (ℱ (k - 1)) P (fun ω => Real.exp (τ * D k ω))
≤ᵐ[P] fun _ => Real.exp (σk k ^ 2 * τ ^ 2 / 2))
(t : ℝ) (ht : 0 < t) :
(P {ω | t ≤ |∑ k ∈ Finset.Icc 1 n, D k ω|}).toReal
≤ 2 * Real.exp (-(t ^ 2 / (2 * ∑ k ∈ Finset.Icc 1 n, σk k ^ 2))) := by sorry
end MostlyExplorationFree.GreedyBandit
Source
Bastani, Bayati & Khosravi, arXiv:1704.09011v8, p. 39, Lemma 8 (Bernstein Concentration; proof: Wainwright (2019), Theorem 2.3)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.