Ville's inequality for nonnegative supermartingales
ProvedBanditAlgorithm.nonnegative_supermartingale_villebandit-algorithmsmartingalesprobability
Let be a real-valued supermartingale on a probability space, adapted to a discrete-time filtration. Assume that almost surely for every and that almost surely. Then, for every ,
This is Ville's inequality, or the maximal inequality for nonnegative supermartingales. Its time-uniform form is the probability-theoretic step that turns the mixture supermartingale in the self-normalized concentration argument into a bound valid simultaneously at every time.
Formalization Note Nonnegativity and the initial bound are stated almost surely, matching the measure-theoretic definition of a supermartingale.
Preamble
import Mathlib.Probability.Martingale.OptionalStopping import Mathlib.MeasureTheory.Integral.Bochner.Basic open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.nonnegative_supermartingale_ville
{Ω : Type} {mΩ : MeasurableSpace Ω}
{P : Measure Ω} [IsProbabilityMeasure P]
(ℱ : Filtration ℕ mΩ) (f : ℕ → Ω → ℝ)
(hf : Supermartingale f ℱ P)
(hnonneg : ∀ t : ℕ, 0 ≤ᵐ[P] f t)
(h0 : ∀ᵐ ω ∂P, f 0 ω ≤ 1)
{δ : ℝ} (hδ : δ ∈ Set.Ioo (0 : ℝ) 1) :
P.real {ω | ∃ t : ℕ, 1 / δ ≤ f t ω} ≤ δ := by
sorry
Source
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), printed p. 51, Theorem 3.9 (Maximal inequality), used in the proof of Theorem 20.4 on printed p. 260, Eq. (20.7).