Lemma 6 — Hoeffding bounds on binomial cdfs, (10) and (11)
ProvedAgrawalGoyalTS.TwoArmed.binom_cdf_hoeffdingbinomial-distributionconcentrationp2o-batch-pfp1bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a natural number, and , and let for real . Then
These are the concentration estimates used in the proofs of Lemmas 2 and 3.
Preamble
import Mathlib import Definitions.Def_AgrawalGoyalTS_TwoArmed_BetaBinomial
Formal statement
namespace AgrawalGoyalTS.TwoArmed
/-- Lemma 6 (p. 13), (10) and (11): for every natural `n`, `p ∈ [0,1]` and `δ ≥ 0`,
`F^B_{n,p}(np - nδ) ≤ e^{-2nδ²}`, `1 - F^B_{n,p}(np + nδ) ≤ e^{-2nδ²}` and
`1 - F^B_{n+1,p}(np + nδ) ≤ e^{4δ} / e^{2nδ²}`. -/
theorem binom_cdf_hoeffding (n : ℕ) (p : ℝ) (hp0 : 0 ≤ p) (hp1 : p ≤ 1)
(δ : ℝ) (hδ : 0 ≤ δ) :
binomCDF n p ((n : ℝ) * p - (n : ℝ) * δ) ≤ Real.exp (-2 * (n : ℝ) * δ ^ 2) ∧
1 - binomCDF n p ((n : ℝ) * p + (n : ℝ) * δ) ≤ Real.exp (-2 * (n : ℝ) * δ ^ 2) ∧
1 - binomCDF (n + 1) p ((n : ℝ) * p + (n : ℝ) * δ) ≤
Real.exp (4 * δ) / Real.exp (2 * (n : ℝ) * δ ^ 2) := by sorry
end AgrawalGoyalTS.TwoArmed
Source
Agrawal and Goyal, Analysis of Thompson Sampling for the Multi-armed Bandit Problem, arXiv:1111.1797v3, p. 13, Lemma 6, Eqs. (10)–(11)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.