Lemma B.5 — M_tM_t′ ≤ ζ²κ₀²σ₀²(log t)C_t^{-1} with high probability
ProvedLinParamBandits.UEGeneral.martingale_loewnerConsider a run of the UE policy under Assumption 1. For every and every ,
where means that is positive semidefinite and .
The matrix inequality controls in all directions simultaneously; it is the step from Lemma B.4 to Theorem B.2.
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 form used in the proof of Theorem B.2). The Loewner order is Matrix.PosSemidef of the difference; is vecMulVec M M. When the right-hand side is negative the bound is trivial, as on the page.
import Mathlib import Definitions.Def_LinParamBandits_UEGeneral_Model import Definitions.Def_LinParamBandits_UEGeneral_UEPolicy
namespace LinParamBandits.UEGeneral
open MeasureTheory ProbabilityTheory
/-- Lemma B.5 (p. 32): `M_t M_t′ ≤ ζ² κ₀² σ₀² (log t) C_t^{-1}` in the Loewner order with
probability at least `1 − t^{r κ₀²} e^{−ζ²/4}`, given `Z = z`. -/
theorem martingale_loewner {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 ψ)
(z : LinParamBandits.LowerBound.Vec r) (t : ℕ) (ht : r ≤ t) (ζ : ℝ) (hζ : 2 ≤ ζ) :
ENNReal.ofReal (1 - (t : ℝ) ^ ((r : ℝ) * kappa0 ubar lam0 ^ 2) * Real.exp (-ζ ^ 2 / 4)) ≤
histMeasure ν z ψ t
{h | ((ζ ^ 2 * kappa0 ubar lam0 ^ 2 * σ₀ ^ 2 * Real.log t) • design (armsOf h) -
Matrix.vecMulVec (Mvec z h).ofLp (Mvec z h).ofLp).PosSemidef} := by sorry
end LinParamBandits.UEGeneral
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.