Lemma 20.2: fixed-direction exponential supermartingale
ProvedBanditAlgorithm.linear_bandit_fixed_direction_supermartingalebandit-algorithmsconcentrationmartingalesprobability
On a standard Borel probability space with a discrete-time filtration , let be -measurable and let be -measurable and conditionally -subgaussian given . Define
For every and every fixed , the process
is a nonnegative supermartingale, and .
This fixed-direction exponential supermartingale is the basic concentration object used by the method of mixtures. Integrating it over directions produces the mixture process underlying the self-normalized martingale bound.
Formalization Note Conditional subgaussianity is represented by Mathlib's HasCondSubgaussianMGF; the theorem permits predictable, random, and unbounded actions.
Preamble
import Mathlib.Probability.Moments.SubGaussian import Mathlib.Probability.Martingale.Basic import Definitions.Def_SelfNormalizedProcess open MeasureTheory ProbabilityTheory Matrix
Formal statement
theorem BanditAlgorithm.linear_bandit_fixed_direction_supermartingale
{Ω : Type} {mΩ : MeasurableSpace Ω} [StandardBorelSpace Ω]
{P : Measure Ω} [IsProbabilityMeasure P]
{d : ℕ} (ℱ : Filtration ℕ mΩ)
(A : ℕ → Ω → Fin d → ℝ) (η : ℕ → Ω → ℝ)
(hA : ∀ t : ℕ, Measurable[ℱ t] (A (t + 1)))
(hη : ∀ t : ℕ, Measurable[ℱ (t + 1)] (η (t + 1)))
(hsg : ∀ t : ℕ, HasCondSubgaussianMGF (ℱ t) (ℱ.le t) (η (t + 1)) 1 P)
{lam : ℝ} (hlam : 0 ≤ lam) (x : Fin d → ℝ) :
Supermartingale (selfNormalizedProcess d lam η A x) ℱ P ∧
∀ ω : Ω, selfNormalizedProcess d lam η A x 0 ω ≤ 1 := by
sorry
Source
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), printed pp. 257-258, Lemma 20.2 and its proof.