Lemma B.4 — martingale inequality for x′M_t
ProvedLinParamBandits.UEGeneral.martingale_ineqConsider a run of the UE policy under Assumption 1 and let . For every , every and every ,
Here , so .
This is the one-direction form of the large deviation inequality for adaptive least squares; Lemma B.5 extends it to all directions at once.
Formalization Note The statement is about a run of the UE policy (IsUE) under Assumption 1 (Assumption1) on a compact nonempty arm set , , with noise laws given by a Markov kernel (the law of is for every ). "" is the law histMeasure ν z ψ t of the history with the parameter fixed to ; is ψ.act t h. is Cmat, the inverse of the design matrix , which is positive definite on every history that starts with (all histories of a UE run, since ). The probability is taken given , for every (the paper applies the lemma in this conditional form in the proof of Theorem B.2; the unconditional form follows for every prior). Corrected slip: the page states the lemma for ; its proof uses , which needs the initial arms, and . At the threshold is () and the printed claim fails for continuous noise. The statement is made for .
import Mathlib import Definitions.Def_LinParamBandits_UEGeneral_Model import Definitions.Def_LinParamBandits_UEGeneral_UEPolicy
namespace LinParamBandits.UEGeneral
open MeasureTheory ProbabilityTheory
/-- Lemma B.4 (p. 30): martingale inequality, stated for `t ≥ r` (the printed `t ≥ 1` is a
slip, see the Formalization Note) and given `Z = z`. -/
theorem martingale_ineq {r : ℕ} (hr : 2 ≤ r) {𝒰 : Set (LinParamBandits.LowerBound.Vec r)} (h𝒰c : IsCompact 𝒰) (h𝒰n : 𝒰.Nonempty)
{ν : Kernel (LinParamBandits.LowerBound.Vec r) ℝ} [IsMarkovKernel ν] {b : Fin r → LinParamBandits.LowerBound.Vec r} {σ₀ ubar lam0 : ℝ}
(hA : Assumption1 𝒰 ν b σ₀ ubar lam0) {ψ : Policy r} (hψ : IsUE 𝒰 b σ₀ ubar lam0 ψ)
(x z : LinParamBandits.LowerBound.Vec r) (t : ℕ) (ht : r ≤ t) (ζ : ℝ) (hζ : Real.sqrt 2 ≤ ζ) :
histMeasure ν z ψ t
{h | ζ * kappa0 ubar lam0 * σ₀ * Real.sqrt (Real.log t) *
wnorm (design (armsOf h)) x < |inner ℝ x (Mvec z h)|} =
histMeasure ν z ψ t
{h | ζ ^ 2 * kappa0 ubar lam0 ^ 2 * σ₀ ^ 2 * Real.log t *
quadForm (design (armsOf h)) x < inner ℝ x (Mvec z h) ^ 2} ∧
histMeasure ν z ψ t
{h | ζ ^ 2 * kappa0 ubar lam0 ^ 2 * σ₀ ^ 2 * Real.log t *
quadForm (design (armsOf h)) x < inner ℝ x (Mvec z h) ^ 2} ≤
ENNReal.ofReal (Real.exp (-ζ ^ 2 / 2)) := by sorry
end LinParamBandits.UEGeneral
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.