Theorem B.1 — Chernoff inequality for uncertainty ellipsoids with finitely many arms
ProvedLinParamBandits.UEGeneral.chernoff_finite_armsConsider a run of the UE policy under Assumption 1, and suppose the set of arms is finite, with elements. Then for every , all and every ,
and
This extends the Chernoff inequality to least squares estimates built from adaptively chosen arms; together with Theorem B.2 it controls the uncertainty radius in Lemma B.6.
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 paper states the result "under Assumption 1"; finiteness of is the hypothesis of the theorem's title (p. 30: for infinitely many arms the bound is vacuous).
import Mathlib import Definitions.Def_LinParamBandits_UEGeneral_Model import Definitions.Def_LinParamBandits_UEGeneral_UEPolicy
namespace LinParamBandits.UEGeneral
open MeasureTheory ProbabilityTheory
/-- Theorem B.1 (p. 29): Chernoff inequality for uncertainty ellipsoids with finitely many arms. -/
theorem chernoff_finite_arms {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 ψ)
(hfin : 𝒰.Finite) (t : ℕ) (ht : r ≤ t) (x z : LinParamBandits.LowerBound.Vec r) (ζ : ℝ) (hζ : 0 < ζ) :
histMeasure ν z ψ t
{h | ζ * σ₀ * wnorm (Cmat (armsOf h)) x < inner ℝ x (Zhat h - z)} ≤
ENNReal.ofReal ((t : ℝ) ^ (5 * 𝒰.ncard) * Real.exp (-ζ ^ 2 / 2)) ∧
histMeasure ν z ψ t
{h | ζ * σ₀ * wnorm (Cmat (armsOf h)) (ψ.act t h - x) <
inner ℝ (ψ.act t h - x) (Zhat h - z)} ≤
ENNReal.ofReal ((t : ℝ) ^ (5 * 𝒰.ncard) * Real.exp (-ζ ^ 2 / 2)) := by sorry
end LinParamBandits.UEGeneral
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.