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).
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.