Proof of Theorem 4.2 — E[min{log T/Δ^u(Z), TΔ^u(Z)}] ≤ (M₀+1) log T + M₀ log² T
ProvedLinParamBandits.UEFinite.gap_min_expectation_boundbayes-riskdensityp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , let be a finite nonempty set of arms, , and . Let have a probability law on such that the law of consists of a point mass at and a density bounded above by on . Then for every the random variable is integrable and
Integrated against the prior, the per-arm term of the regret bound of Theorem 4.2 grows like ; this is what turns the regret bound into the Bayes risk bound.
Formalization Note On the event the minimum is read as (the paper's ); Lean's convention gives the same value. The density condition is written as: the law of restricted to is at most times Lebesgue measure. Assumption 1 and the policy play no role in this statement and are not assumed.
Preamble
import Mathlib import Definitions.Def_LinParamBandits_UEFinite_Model import Definitions.Def_LinParamBandits_UEFinite_UEPolicy
Formal statement
namespace LinParamBandits.UEFinite
open MeasureTheory ProbabilityTheory
theorem gap_min_expectation_bound
(r : ℕ) (hr : 2 ≤ r) (𝒰 : Set (LinParamBandits.LowerBound.Vec r)) (h𝒰fin : 𝒰.Finite) (h𝒰ne : 𝒰.Nonempty)
(u : LinParamBandits.LowerBound.Vec r) (hu : u ∈ 𝒰) (μ : Measure (LinParamBandits.LowerBound.Vec r)) (hμ : IsProbabilityMeasure μ)
(M₀ : ℝ) (hM₀ : 0 < M₀) (hdens : GapDensityLe 𝒰 μ M₀ u) (T : ℕ) (hT : r + 1 ≤ T) :
Integrable (fun z => min (Real.log T / gap 𝒰 u z) (T * gap 𝒰 u z)) μ ∧
∫ z, min (Real.log T / gap 𝒰 u z) (T * gap 𝒰 u z) ∂μ ≤
(M₀ + 1) * Real.log T + M₀ * Real.log T ^ 2 := by sorry
end LinParamBandits.UEFinite
Source
Rusmevichientong, Tsitsiklis, Linearly Parameterized Bandits, arXiv:0812.3465v2, proof of Theorem 4.2, pp. 22–23, display after 'From the regret bound, it suffices to show that for any u ∈ U_r'
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.