Theorem 4.1 — UE regret ≤ a₄r‖z‖ + a₅r√T log^{3/2} T and Risk ≤ a₄r E‖Z‖ + a₅r√T log^{3/2} T
ProvedLinParamBandits.UEGeneral.ue_regret_bound_generalTheorem 4.1 (Bounds for General Compact Sets of Arms). For all constants there are constants , depending only on , with the following property. For every dimension , every compact nonempty set of arms , every noise model and arms satisfying Assumption 1 with these constants, every run of the Uncertainty Ellipsoid policy, and every horizon :
- for every ,
- for every prior distribution of with , the regret is integrable in and
The UE policy thus comes within a factor of the lower bound of Theorem 2.1, for any compact set of arms, without knowing the horizon .
Formalization Note The quantifier order is the paper's: are chosen after and before , the arm set, the noise kernel, the arms , the UE run, and . Finite arm sets are included. is the real power Real.log T ^ (3/2 : ℝ), with since . The prior is a probability measure on ; is stated as integrability of (the bound mentions ), and integrability of is part of the conclusion, so the risk is never a junk value. The noise is independent of , so the risk is the integral over the prior of the regret given .
import Mathlib import Definitions.Def_LinParamBandits_UEGeneral_Model import Definitions.Def_LinParamBandits_UEGeneral_UEPolicy
namespace LinParamBandits.UEGeneral
open MeasureTheory ProbabilityTheory
/-- Theorem 4.1 (p. 21): bounds for general compact sets of arms. The constants `a₄, a₅`
depend only on `σ₀, ū, λ₀`: they are chosen before `r`, the arm set, the noise, the UE run,
`T` and `z`. -/
theorem ue_regret_bound_general :
∀ σ₀ ubar lam0 : ℝ, 0 < σ₀ → 0 < ubar → 0 < lam0 →
∃ a₄ a₅ : ℝ, 0 < a₄ ∧ 0 < a₅ ∧
∀ (r : ℕ), 2 ≤ r →
∀ (𝒰 : Set (LinParamBandits.LowerBound.Vec r)), IsCompact 𝒰 → 𝒰.Nonempty →
∀ (ν : Kernel (LinParamBandits.LowerBound.Vec r) ℝ), IsMarkovKernel ν →
∀ (b : Fin r → LinParamBandits.LowerBound.Vec r), Assumption1 𝒰 ν b σ₀ ubar lam0 →
∀ (ψ : Policy r), IsUE 𝒰 b σ₀ ubar lam0 ψ →
∀ (T : ℕ), r + 1 ≤ T →
(∀ z : LinParamBandits.LowerBound.Vec r,
regret ν 𝒰 ψ z T ≤
a₄ * r * ‖z‖ + a₅ * r * Real.sqrt T * Real.log T ^ (3 / 2 : ℝ)) ∧
(∀ μ : Measure (LinParamBandits.LowerBound.Vec r), IsProbabilityMeasure μ → Integrable (fun z => ‖z‖) μ →
Integrable (fun z => regret ν 𝒰 ψ z T) μ ∧
risk ν 𝒰 ψ μ T ≤
a₄ * r * (∫ z, ‖z‖ ∂μ) + a₅ * r * Real.sqrt T * Real.log T ^ (3 / 2 : ℝ)) := by sorry
end LinParamBandits.UEGeneral
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.