Lemma B.7 — instantaneous regret bound
ProvedLinParamBandits.UEGeneral.inst_regret_boundConsider a run of the UE policy under Assumption 1 and let be the instantaneous regret in period given . For all and ,
The instantaneous regret is thus, outside an event of probability , at most twice the uncertainty radius of the arm played; this is the basis of the regret decomposition, Lemma B.8.
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 instRegret 𝒰 z (ψ.act t h).
import Mathlib import Definitions.Def_LinParamBandits_UEGeneral_Model import Definitions.Def_LinParamBandits_UEGeneral_UEPolicy
namespace LinParamBandits.UEGeneral
open MeasureTheory ProbabilityTheory
/-- Lemma B.7 (p. 35): instantaneous regret bound. -/
theorem inst_regret_bound {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) :
histMeasure ν z ψ t
{h | 2 * radiusFactor 𝒰 σ₀ ubar lam0 t * wnorm (Cmat (armsOf h)) (ψ.act t h) <
instRegret 𝒰 z (ψ.act t h)} ≤
ENNReal.ofReal (1 / (t : ℝ) ^ 2) := by sorry
end LinParamBandits.UEGeneral
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.