Theorem 5, pp. 50–51 — multiplicative Chernoff bounds for the mean of n i.i.d. geometric variables
ProvedMNLBandit.UCB.theorem_5chernoff-boundconcentration-inequalitygeometric-distributionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let () be i.i.d. geometric random variables with parameter , i.e. for , and let . For every :
- (upper tail)
- (lower tail)
The two cases overlap at , where both bounds hold. These are the paper's extension of the multiplicative Chernoff–Hoeffding bounds to unbounded (geometric) variables; they drive the concentration of the epoch averages in Lemma A.2.
Formalization Note. The sample is the product measure of copies of Mathlib's geometricMeasure p, whose mass at is , exactly the paper's convention. The paper leaves the range of implicit in three of the four cases; is required (for the first bound fails). For the lower-tail event is empty.
Preamble
import Mathlib
Formal statement
namespace MNLBandit.UCB
open MeasureTheory ProbabilityTheory
theorem theorem_5 (n : ℕ) (hn : 1 ≤ n) (p : unitInterval) (hp : p ≠ 0) (δ : ℝ) (hδ : 0 < δ) :
let μ : ℝ := (1 - (p : ℝ)) / (p : ℝ)
let P : Measure (Fin n → ℕ) := Measure.pi (fun _ : Fin n => geometricMeasure p)
let Xbar : (Fin n → ℕ) → ℝ := fun x => (∑ k, (x k : ℝ)) / (n : ℝ)
(μ ≤ 1 → P {x | Xbar x > (1 + δ) * μ} ≤
ENNReal.ofReal (Real.exp (-((n : ℝ) * μ * δ ^ 2) / (2 * (1 + δ) * (1 + μ) ^ 2)))) ∧
(1 ≤ μ → δ < 1 → P {x | Xbar x > (1 + δ) * μ} ≤
ENNReal.ofReal (Real.exp (-((n : ℝ) * δ ^ 2 * μ ^ 2 / (6 * (1 + μ) ^ 2))
* (3 - 2 * δ * μ / (1 + μ))))) ∧
(μ ≤ 1 → P {x | Xbar x < (1 - δ) * μ} ≤
ENNReal.ofReal (Real.exp (-((n : ℝ) * δ ^ 2 * μ / (6 * (1 + μ) ^ 2))
* (3 - 2 * δ * μ / (1 + μ))))) ∧
(1 ≤ μ → P {x | Xbar x < (1 - δ) * μ} ≤
ENNReal.ofReal (Real.exp (-((n : ℝ) * δ ^ 2 * μ ^ 2) / (2 * (1 + μ) ^ 2)))) := by sorry
end MNLBandit.UCB
Source
Agrawal, Avadhanula, Goyal, Zeevi, MNL-Bandit: A Dynamic Learning Approach to Assortment Selection, arXiv:1706.03880v2, pp. 50–51, Theorem 5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.