Theorem B.2 — Chernoff inequality for uncertainty ellipsoids with infinitely many arms
ProvedLinParamBandits.UEGeneral.chernoff_infinite_armsConsider a run of the UE policy under Assumption 1, on an arbitrary compact set of arms. For every , all and every ,
and
Unlike Theorem B.1, the bound does not depend on the number of arms, so it applies to infinite arm sets; it is the second input of 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 ). is a real power.
import Mathlib import Definitions.Def_LinParamBandits_UEGeneral_Model import Definitions.Def_LinParamBandits_UEGeneral_UEPolicy
namespace LinParamBandits.UEGeneral
open MeasureTheory ProbabilityTheory
/-- Theorem B.2 (p. 30): Chernoff inequality for uncertainty ellipsoids with infinitely many
arms. -/
theorem chernoff_infinite_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 ψ)
(t : ℕ) (ht : r ≤ t) (x z : LinParamBandits.LowerBound.Vec r) (ζ : ℝ) (hζ : 2 ≤ ζ) :
histMeasure ν z ψ t
{h | ζ * kappa0 ubar lam0 * σ₀ * Real.sqrt (Real.log t) * wnorm (Cmat (armsOf h)) x <
inner ℝ x (Zhat h - z)} ≤
ENNReal.ofReal ((t : ℝ) ^ ((r : ℝ) * kappa0 ubar lam0 ^ 2) * Real.exp (-ζ ^ 2 / 4)) ∧
histMeasure ν z ψ t
{h | ζ * kappa0 ubar lam0 * σ₀ * Real.sqrt (Real.log t) *
wnorm (Cmat (armsOf h)) (ψ.act t h - x) < inner ℝ (ψ.act t h - x) (Zhat h - z)} ≤
ENNReal.ofReal ((t : ℝ) ^ ((r : ℝ) * kappa0 ubar lam0 ^ 2) * Real.exp (-ζ ^ 2 / 4)) := by sorry
end LinParamBandits.UEGeneral
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.