Proof of Theorem 4.2 — Regret(z,T,UE) = Σ_u Δ^u(z) E[N^u(z,T) | Z = z]
ProvedLinParamBandits.UEFinite.regret_eq_sum_gap_pullslinear-banditp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1regret
Consider the linearly parameterized bandit of Rusmevichientong and Tsitsiklis under Assumption 1, with a finite nonempty set of arms (), run by the Uncertainty Ellipsoid policy. For every horizon and every ,
where is the gap of arm and the number of periods among the first in which arm is played.
This regret decomposition turns the regret, a sum over periods, into a sum over arms, so that a bound on the number of pulls of each suboptimal arm becomes a regret bound.
Formalization Note The regret is defined as . The identity holds for every horizon; the paper writes it inside the proof of Theorem 4.2, where .
Preamble
import Mathlib import Definitions.Def_LinParamBandits_UEFinite_Model import Definitions.Def_LinParamBandits_UEFinite_UEPolicy
Formal statement
namespace LinParamBandits.UEFinite
open MeasureTheory ProbabilityTheory
theorem regret_eq_sum_gap_pulls
(σ₀ ū lam₀ : ℝ) (hσ₀ : 0 < σ₀) (hū : 0 < ū) (hlam₀ : 0 < lam₀)
(r : ℕ) (hr : 2 ≤ r) (𝒰 : Set (LinParamBandits.LowerBound.Vec r)) (h𝒰fin : 𝒰.Finite) (h𝒰ne : 𝒰.Nonempty)
(ν : Kernel (LinParamBandits.LowerBound.Vec r) ℝ) (hν : IsMarkovKernel ν) (hnoise : NoiseAssumption 𝒰 ν σ₀)
(b : Fin r → LinParamBandits.LowerBound.Vec r) (harms : ArmAssumption 𝒰 b ū lam₀)
(ψ : LinParamBandits.UEGeneral.Policy r) (hψ : IsUE 𝒰 b σ₀ ū lam₀ ψ)
(T : ℕ) (z : LinParamBandits.LowerBound.Vec r) :
Regret 𝒰 ν ψ z T =
∑ u ∈ h𝒰fin.toFinset, gap 𝒰 u z * ∫ h, (pullCount u h : ℝ) ∂(LinParamBandits.UEGeneral.histMeasure ν z ψ T) := by sorry
end LinParamBandits.UEFinite
Source
Rusmevichientong, Tsitsiklis, Linearly Parameterized Bandits, arXiv:0812.3465v2, proof of Theorem 4.2, p. 22, first line of the display after 'because'
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.