Lemma 9 — Freedman's inequality
ProvedTamingMonster.Regret.freedman_inequalityLet be real random variables on a probability space. Suppose that for every , almost surely and . Put
Then for every and every , with probability at least ,
This is the martingale concentration inequality behind the deviation bound for the inverse propensity estimates (Lemma 11); its strength is that it scales with the conditional variance rather than with the range .
Formalization Note The conditioning is on the natural σ-algebra (trivial for ). The paper allows , where the bound is ; Lean's convention would make that case false, so and are assumed. The variables are assumed measurable with and integrable (implicit in the paper; otherwise the conditional expectations are not defined). The conclusion is stated as "the failure event has (outer) probability at most ".
import Mathlib
namespace TamingMonster.Regret
open MeasureTheory
/-- Lemma 9 (Freedman's inequality, as quoted from Beygelzimer et al. 2011), p. 14.
`Xs 1, …, Xs T` are real random variables with `X_t ≤ R` and `E[X_t | X_1, …, X_{t−1}] = 0`;
`S = ∑_{t=1}^T X_t` and `V = ∑_{t=1}^T E[X_t² | X_1, …, X_{t−1}]`. For `δ ∈ (0,1)` and
`λ ∈ (0, 1/R]`, the event `S > (e − 2)λV + ln(1/δ)/λ` has probability at most `δ`.
The conditioning σ-algebra for round `t` is `σ(X_1, …, X_{t−1})` (trivial for `t = 1`). -/
theorem freedman_inequality {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω)
[IsProbabilityMeasure P] (Xs : ℕ → Ω → ℝ) (T : ℕ) (R : ℝ) (hR : 0 < R)
(hmeas : ∀ t, Measurable (Xs t))
(hint : ∀ t, Integrable (Xs t) P)
(hint2 : ∀ t, Integrable (fun ω => Xs t ω ^ 2) P)
(hle : ∀ t ∈ Finset.Icc 1 T, ∀ᵐ ω ∂P, Xs t ω ≤ R)
(hmart : ∀ t ∈ Finset.Icc 1 T,
condExp (⨆ i ∈ Finset.Icc 1 (t - 1), MeasurableSpace.comap (Xs i) inferInstance) P (Xs t)
=ᵐ[P] 0)
(δ lam : ℝ) (hδ0 : 0 < δ) (hδ1 : δ < 1) (hlam0 : 0 < lam) (hlam1 : lam ≤ 1 / R) :
P {ω | (Real.exp 1 - 2) * lam *
(∑ t ∈ Finset.Icc 1 T,
condExp (⨆ i ∈ Finset.Icc 1 (t - 1), MeasurableSpace.comap (Xs i) inferInstance) P
(fun ω' => Xs t ω' ^ 2) ω)
+ Real.log (1 / δ) / lam
< ∑ t ∈ Finset.Icc 1 T, Xs t ω} ≤ ENNReal.ofReal δ := by sorry
end TamingMonster.Regret
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.