Corollary D.1, p. 56 — deviation bounds 6/(Nℓ²), 4/(Nℓ²), 3/(Nℓ²) for the mean of geometric variables with μ ≤ 1
ProvedMNLBandit.UCB.corollary_D_1chernoff-boundconcentration-inequalitygeometric-distributionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let () be i.i.d. geometric random variables with parameter , , let and . Let be integers and write . If , then
Here and are free parameters: in the paper's application is the number of products and the epoch index, and the bounds are summed over the at most possible sample sizes in the proof of Lemma A.2.
Formalization Note. The page says "for all " for the first two bounds; the third is stated for all in the same way. The sample is the product of copies of Mathlib's geometricMeasure p.
Preamble
import Mathlib
Formal statement
namespace MNLBandit.UCB
open MeasureTheory ProbabilityTheory
theorem corollary_D_1 (n : ℕ) (hn : 1 ≤ n) (N ℓ : ℕ) (hN : 1 ≤ N) (hℓ : 1 ≤ ℓ)
(p : unitInterval) (hp : p ≠ 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 : ℝ)
let lg : ℝ := Real.log (Real.sqrt N * ℓ + 1)
μ ≤ 1 →
P {x | |Xbar x - μ| > Real.sqrt (48 * Xbar x * lg / n) + 48 * lg / n} ≤
ENNReal.ofReal (6 / (N * ℓ ^ 2)) ∧
P {x | |Xbar x - μ| ≥ Real.sqrt (24 * μ * lg / n) + 48 * lg / n} ≤
ENNReal.ofReal (4 / (N * ℓ ^ 2)) ∧
P {x | Xbar x ≥ 3 * μ / 2 + 48 * lg / n} ≤ ENNReal.ofReal (3 / (N * ℓ ^ 2)) := by sorry
end MNLBandit.UCB
Source
Agrawal, Avadhanula, Goyal, Zeevi, MNL-Bandit: A Dynamic Learning Approach to Assortment Selection, arXiv:1706.03880v2, p. 56, Corollary D.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.