Ville's maximal inequality for a bandit exponential weight
ProvedBanditAlgorithm.bandit_ville_maximal_inequalityVille's maximal inequality in the canonical bandit model. Let be a nonnegative process on length- histories with unit mass, , satisfying the martingale property in its integrated form
for every measurable on length- histories. Then for every level ,
The point is the absence of any union over rounds: a fixed-round Chernoff bound controls for each separately, and unioning costs a factor growing with the horizon, whereas the maximal inequality is uniform in at no cost. This is what makes the time-uniform threshold of Lattimore--Szepesv'ari Lemma 33.7 achievable at all — a union over rounds would force a threshold linear in .
The martingale hypothesis is stated in integrated form rather than as because that is exactly what the one-step exponential tilt identity of the canonical model supplies; the two are equivalent here, and no conditional expectations are needed anywhere. The proof is optional stopping arranged so that only the one-step identity is used: writing for "no crossing up to ", the induction hypothesis is advanced by splitting at the level of and recombining, which is legitimate precisely because is a function of the length- history.
import Definitions.Def_TrackAndStop import Definitions.Def_GaussianBandit import Mathlib.MeasureTheory.Measure.Prod open MeasureTheory ProbabilityTheory Real NNReal ENNReal
theorem BanditAlgorithm.bandit_ville_maximal_inequality {k : ℕ}
(P : MeasureTheory.Measure (ℕ → Fin k × ℝ))
(W : (n : ℕ) → BanditAlgorithm.BanditHistory k n → ENNReal)
(hmeas : ∀ n, Measurable (W n))
(hinit : ∫⁻ ω, W 0 (BanditAlgorithm.banditTrajPrefix k 0 ω) ∂P = 1)
(hstep : ∀ (n : ℕ) (F : BanditAlgorithm.BanditHistory k n → ENNReal), Measurable F →
∫⁻ ω, F (BanditAlgorithm.banditTrajPrefix k n ω)
* W (n + 1) (BanditAlgorithm.banditTrajPrefix k (n + 1) ω) ∂P
= ∫⁻ ω, F (BanditAlgorithm.banditTrajPrefix k n ω)
* W n (BanditAlgorithm.banditTrajPrefix k n ω) ∂P)
(c : ENNReal) :
c * P {ω : ℕ → Fin k × ℝ |
∃ i : ℕ, c ≤ W i (BanditAlgorithm.banditTrajPrefix k i ω)} ≤ 1 := by
sorry