Equation (2.5), p. 8 — empirical gap lower tail
ProvedBanditCovariates.SE.bound_2_5multi-armed-banditp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1probabilitysuccessive-elimination
In the sorted arm model, let be a suboptimal arm with gap . Let be the difference of the empirical means of the best arm and arm after samples each. If , then
This lower-tail estimate controls failure to eliminate a sufficiently separated arm.
Formalization Note The printed phrase “for every ” needs the displayed threshold condition: a negative deviation size cannot be inserted into the stated Hoeffding bound. The proof uses the estimate where this condition holds. Rewards are bounded almost surely, and the published reward-stack model supplies independence.
Preamble
import Mathlib import Definitions.Def_BanditCovariates_SE_Setting
Formal statement
namespace BanditCovariates.SE
open MeasureTheory ProbabilityTheory
/-- Equation (2.5), p. 8, in the range where the displayed Hoeffding estimate applies. -/
theorem bound_2_5 {Ω : Type*} {m : MeasurableSpace Ω} (P : Measure Ω)
[IsProbabilityMeasure P] (K : ℕ) (hK : 1 ≤ K)
(Y : Fin (K + 1) → ℕ → Ω → ℝ) (f : Fin (K + 1) → ℝ)
(hmodel : RegretBandits.Stochastic.IsStochasticBandit P Y f)
(hbounded : ∀ i k, ∀ᵐ ω ∂P, Y i k ω ∈ Set.Icc (0 : ℝ) 1)
(hordered : Monotone f)
(hbest : ∀ i, i ≠ Fin.last K → f i < f (Fin.last K))
(i : Fin (K + 1)) (hi : i ≠ Fin.last K)
(T τ : ℕ) (hT : 1 ≤ T) (hτ : 1 ≤ τ) (γ : ℝ) (hγ : 1 ≤ γ)
(hthreshold : γ * U τ T ≤ gap f i) :
P.real {ω | estimatedGap Y i τ ω < γ * U τ T} ≤
Real.exp (-(τ : ℝ) * (gap f i - γ * U τ T) ^ 2 / 2) := by sorry
end BanditCovariates.SE
Source
Perchet, Rigollet, The multi-armed bandit problem with covariates, arXiv:1110.6084v3, p. 8, (2.5)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.