Lemma B.6 — large deviation inequalities for the uncertainty radius
ProvedLinParamBandits.UEGeneral.radius_large_deviationConsider a run of the UE policy under Assumption 1 and let . For every arm and every ,
and for every ,
The lemma explains the choice of and of the uncertainty radius: the probability of overestimating an arm's reward by more than its radius is at most , which is summable over .
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 width, equal to for an infinite arm set; radiusFactor 𝒰 σ₀ ubar lam0 t is .
import Mathlib import Definitions.Def_LinParamBandits_UEGeneral_Model import Definitions.Def_LinParamBandits_UEGeneral_UEPolicy
namespace LinParamBandits.UEGeneral
open MeasureTheory ProbabilityTheory
/-- Lemma B.6 (p. 34): large deviation inequalities for the uncertainty radius. -/
theorem radius_large_deviation {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) (z : LinParamBandits.LowerBound.Vec r) :
(∀ u ∈ 𝒰, histMeasure ν z ψ t
{h | radius 𝒰 σ₀ ubar lam0 h u < inner ℝ u (Zhat h - z)} ≤
ENNReal.ofReal (1 / (t : ℝ) ^ 2)) ∧
(∀ x : LinParamBandits.LowerBound.Vec r, histMeasure ν z ψ t
{h | radiusFactor 𝒰 σ₀ ubar lam0 t * wnorm (Cmat (armsOf h)) (ψ.act t h - x) <
inner ℝ (ψ.act t h - x) (Zhat h - z)} ≤
ENNReal.ofReal (1 / (t : ℝ) ^ 2)) := by sorry
end LinParamBandits.UEGeneral
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.