Tail-sum formula for the expectation of an ℕ∞-valued random variable
ProvedBanditAlgorithm.lintegral_enat_eq_tsum_measure_ltmeasure-theorystopping-time
For an -valued measurable on a measure space , the tail-sum formula holds in :
Mathlib has this for -valued and for -valued random variables, but not for -valued ones, which is the type of a bandit stopping time (Definition 33.4 explicitly allows ). It is the tool that converts a family of round-by-round deviation bounds into a bound on , which is exactly how the sample-complexity half of Theorem 33.6 is proved.
Preamble
import Mathlib.MeasureTheory.Integral.Lebesgue.Add import Mathlib.Data.Real.ENatENNReal import Mathlib.MeasureTheory.Measure.Typeclasses.Probability open MeasureTheory ENNReal
Formal statement
theorem BanditAlgorithm.lintegral_enat_eq_tsum_measure_lt {Ω : Type*} [MeasurableSpace Ω]
(μ : MeasureTheory.Measure Ω) {τ : Ω → ℕ∞} (hτ : Measurable τ) :
∫⁻ ω, (τ ω : ENNReal) ∂μ = ∑' n : ℕ, μ {ω | (n : ℕ∞) < τ ω} := by
sorrySource
Standard layer-cake / Fubini-Tonelli argument; used in this form in Garivier & Kaufmann, COLT 2016, Proposition 13, and Lattimore & Szepesvari, Bandit Algorithms (CUP 2020), Section 33.2.2.