Mean of a hitting time is bounded by the sum of failure probabilities
ProvedBanditAlgorithm.hitting_time_lintegral_le_tsum_failurebanditssequential-analysis
Let be measurable events and let
be the first index from which belongs to all of them (with the value when no such index exists). Then
So is integrable as soon as the failure probabilities are summable against the index , which is what any geometric or polynomial-of-degree-below- concentration bound supplies. This is the layer-cake estimate combined with , and it is stated with no measurability assumption on itself: the bound is proved pointwise, , and monotonicity of the lower integral needs nothing of the smaller function.
The estimate is sharp in the only case that matters: if fails the events exactly on a finite set with largest element , then and the -th summand alone already contributes .
Preamble
import Mathlib.MeasureTheory.Integral.Lebesgue.Add import Mathlib.MeasureTheory.Measure.Typeclasses.Finite import Mathlib.Analysis.SpecificLimits.Normed open MeasureTheory ENNReal NNReal
Formal statement
theorem BanditAlgorithm.hitting_time_lintegral_le_tsum_failure {α : Type*}
[MeasurableSpace α] (G : ℕ → Set α) (hG : ∀ m, MeasurableSet (G m))
(μ : MeasureTheory.Measure α) :
∫⁻ ω, ((sInf {N : ℕ | ∀ n, N ≤ n → ω ∈ G n} : ℕ) : ℝ≥0∞) ∂μ
≤ ∑' m : ℕ, ((m : ℝ≥0∞) + 1) * μ (G m)ᶜ := by
sorrySource
Standard first-moment (layer-cake) estimate for the last failure time of a sequence of events; used here to supply the integrable random time in Garivier & Kaufmann, Optimal Best Arm Identification with Fixed Confidence, COLT 2016, Proposition 13.