BanditAlgorithm.linear_bandit_mixture_supermartingale
Proved(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.
import Mathlib.Probability.Moments.SubGaussian import Mathlib.Probability.Martingale.Basic import Definitions.Def_SelfNormalizedProcess open MeasureTheory ProbabilityTheory Matrix
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
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Setup and notation. Let be a probability space with a standard Borel space, equipped with a filtration (each ). Given a dimension (no positivity assumed), an action process , a noise process , and , define pointwise
for , and, for a probability measure on , the mixture (a Bochner integral). Note identically. "Supermartingale with respect to and " means: each time-slice is -measurable and -integrable, and -a.s. for all .
Assertion (a conjunction of four claims):
- For every : the process is a supermartingale with respect to and , and for every (pointwise, not a.s.).
- The mixture is a supermartingale with respect to and .
- for every .
- If , then for every .
Hypotheses.
- Predictability of actions: for every , is -measurable (in particular is -measurable).
- Adaptedness of noise: for every , is -measurable.
- Conditional -sub-Gaussian noise: for every and every , -almost surely , together with the accompanying integrability of ; this is formulated through the regular conditional probability distribution given , with the variance proxy fixed to the constant (not a free parameter).
- (weak inequality; is allowed).
- is a probability measure on .
- Integrability of the mixture: for every and every (pointwise in , not merely a.e.), the map is -integrable.
- is a standard Borel space and is a probability measure.
Edge cases.
- The index- entries never appear; sums run over .
- is admitted (then is the empty vector, the quadratic form is , and ).
- The supermartingale conclusions include, as part of the claim, adaptedness and -integrability of every and of every .
- The time-zero bounds in claims 1, 3, 4 hold for all , and claim 4 is an equality (which forces the exponent to vanish when , so ).
Confirmed by the mission captain (proposal self-audit).