BanditAlgorithm.linear_bandit_mixture_supermartingale
Provedlinear-banditsmartingaleprobability
(Supermartingale property, L&S Lemmas 20.2 and 20.3) On a standard Borel probability space with filtration , let the actions be -measurable and the noise be -measurable and conditionally 1-subgaussian given (Eq. 20.4:
Mathlib's HasCondSubgaussianMGF with ). Fix and let
Then:
- (i) for every , is a nonnegative -supermartingale with ;
- (ii) for every probability measure on under which the mixture integrals are -integrable, the mixture is a nonnegative -supermartingale with , and in the unregularized case treated by the book.
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_mixture_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)
(h : Measure (Fin d → ℝ)) [IsProbabilityMeasure h]
(hInt : ∀ (t : ℕ) (ω : Ω),
Integrable (fun x => selfNormalizedProcess d lam η A x t ω) h) :
(∀ x : Fin d → ℝ,
Supermartingale (selfNormalizedProcess d lam η A x) ℱ P ∧
∀ ω : Ω, selfNormalizedProcess d lam η A x 0 ω ≤ 1) ∧
Supermartingale
(fun (t : ℕ) (ω : Ω) => ∫ x, selfNormalizedProcess d lam η A x t ω ∂h) ℱ P ∧
(∀ ω : Ω, (∫ x, selfNormalizedProcess d lam η A x 0 ω ∂h) ≤ 1) ∧
(lam = 0 → ∀ ω : Ω, (∫ x, selfNormalizedProcess d lam η A x 0 ω ∂h) = 1) := by
sorry
Source
L&S Lemmas 20.2 (p.257) and 20.3 (p.259)