Lemma B.8 — regret decomposition
ProvedLinParamBandits.UEGeneral.regret_decompositionConsider a run of the UE policy under Assumption 1. For all and ,
The first term covers the initialization periods and the rare periods in which Lemma B.7's event fails; the second reduces the regret to the growth of the weighted arm norms, bounded in Lemmas B.10 and B.11.
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 expectation on the right is the Bochner integral over histMeasure ν z ψ T of , written with potential (armSeq h) t; the integrand is nonnegative and bounded on the support, and a junk value would only make the bound harder.
import Mathlib import Definitions.Def_LinParamBandits_UEGeneral_Model import Definitions.Def_LinParamBandits_UEGeneral_UEPolicy
namespace LinParamBandits.UEGeneral
open MeasureTheory ProbabilityTheory
/-- Lemma B.8 (p. 36): regret decomposition. -/
theorem regret_decomposition {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 + 1 ≤ T) (z : LinParamBandits.LowerBound.Vec r) :
regret ν 𝒰 ψ z T ≤
2 * ubar * ((r : ℝ) + 2) * ‖z‖ +
2 * alpha σ₀ ubar lam0 * Real.sqrt r * Real.log T * Real.sqrt T *
∫ h, Real.sqrt (∑ t ∈ Finset.Ico r T, potential (armSeq h) t)
∂(histMeasure ν z ψ T) := by sorry
end LinParamBandits.UEGeneral
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.