Eq. (2.3) — Cramér–Chernoff bound
ProvedRegretBandits.Stochastic.cramer_chernoffConsider a stochastic bandit whose reward distributions satisfy the moment condition (2.2) with a convex function , and let . Let be the sample mean of the first rewards of arm . Then for every ,
with .
This concentration inequality is what makes an upper confidence bound on at level ; the UCB analysis applies it with a union bound over the number of pulls.
Formalization Note. Two conventions the book leaves implicit are stated. (i) : for the printed inequality is false (with it would bound a probability close to by ). (ii) for . Condition (2.2) constrains only on , while takes the supremum over all . Without (ii), with large satisfies (2.2) for rewards and has , which makes (2.3) false for small . Every used in the book is even and satisfies (ii). Under (ii) the supremum may be taken over . is computed in the extended reals and the right side is the extended exponential.
import Mathlib import Definitions.Def_RegretBandits_Stochastic_model
namespace RegretBandits.Stochastic
open MeasureTheory
/-- Eq. (2.3) of Bubeck and Cesa-Bianchi (arXiv:1204.5721v2, p. 10): if the rewards satisfy
(2.2) with a convex `ψ` (which is not below `ψ 0` on `(-∞, 0]`), then for every arm `i`, every
number of pulls `s ≥ 1` and every `ε ≥ 0`,
`ℙ(μ_i - μ̂_{i,s} > ε) ≤ e^{-s ψ*(ε)}`, with `e^{-∞} = 0`. -/
theorem cramer_chernoff {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω)
[IsProbabilityMeasure P] {K : ℕ} (X : Fin K → ℕ → Ω → ℝ) (μ : Fin K → ℝ)
(hX : IsStochasticBandit P X μ) (ψ : ℝ → ℝ) (hψ : SatisfiesMomentCondition P ψ X μ)
(hψneg : ∀ l : ℝ, l ≤ 0 → ψ 0 ≤ ψ l) (i : Fin K) (s : ℕ) (hs : 1 ≤ s) (ε : ℝ)
(hε : 0 ≤ ε) :
P {ω | ε < μ i - sampleMean X i s ω} ≤
EReal.exp (-((s : ℝ) : EReal) * legendreFenchel ψ ε) := by sorry
end RegretBandits.Stochastic
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.