Lemma B.3 — exponential inequality for ratios (De la Peña, Klass and Lai 2004)
ProvedLinParamBandits.UEGeneral.exp_ineq_ratiosconcentrationmartingalep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1self-normalized
Let and be random variables on a probability space such that almost surely and
Then for all and ,
This self-normalized tail bound is quoted by the paper from Corollary 2.2 of De la Peña, Klass and Lai (2004); it is the probabilistic input of the martingale inequality, Lemma B.4.
Formalization Note The expectation in the hypothesis is a lower Lebesgue integral of the nonnegative integrand, so the hypothesis cannot hold by a junk value of a non-integrable Bochner integral. and are measurable (they are random variables).
Preamble
import Mathlib
Formal statement
namespace LinParamBandits.UEGeneral
open MeasureTheory ProbabilityTheory
/-- Lemma B.3 (p. 30; De la Peña, Klass and Lai 2004, Corollary 2.2): exponential inequality
for ratios. -/
theorem exp_ineq_ratios {Ω : Type*} [MeasurableSpace Ω] {P : Measure Ω} [IsProbabilityMeasure P]
{A B : Ω → ℝ} (hA : Measurable A) (hB : Measurable B) (hB0 : ∀ᵐ ω ∂P, 0 ≤ B ω)
(hexp : ∀ γ : ℝ,
∫⁻ ω, ENNReal.ofReal (Real.exp (γ * A ω - γ ^ 2 * B ω ^ 2 / 2)) ∂P ≤ 1)
(ζ : ℝ) (hζ : Real.sqrt 2 ≤ ζ) (y : ℝ) (hy : 0 < y) :
P {ω | ζ * Real.sqrt ((B ω ^ 2 + y) * (1 + 1 / 2 * Real.log (1 + B ω ^ 2 / y))) ≤ |A ω|} ≤
ENNReal.ofReal (Real.exp (-ζ ^ 2 / 2)) := by sorry
end LinParamBandits.UEGeneral
Source
Rusmevichientong, Tsitsiklis, Linearly Parameterized Bandits, arXiv:0812.3465v2, Lemma B.3, p. 30 (citing De la Peña, Klass, Lai 2004, Ann. Probab. 32, Corollary 2.2, p. 1908)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.