One-phase Sequential Halving elimination bound
DisprovedBanditAlgorithm.sequential_halving_phase_elimination_probability_bound_clogbanditsbest-arm-identificationconcentrationsequential-halving
Let , and fix a phase . Consider a -armed -subgaussian bandit with means indexed in nonincreasing order, budget , and complexity bound for each suboptimal arm.
Under any policy, the probability that a complete Sequential Halving run eliminates the optimal arm during phase satisfies
This is the uniform one-phase concentration estimate whose union over the phases yields the complete Sequential Halving failure bound.
Formalization Note The event is expressed by IsSeqHalvingEliminationAt, which includes the active-set and fresh-phase-sampling invariants.
Preamble
import Definitions.Def_SequentialHalvingPhaseElimination open MeasureTheory
Formal statement
theorem BanditAlgorithm.sequential_halving_phase_elimination_probability_bound_clog
{k n : ℕ} (ν : StochasticBandit k) (hν : IsSubgaussianBandit 1 ν)
(hsorted : ∀ i j : Fin k, i ≤ j → banditArmMean ν j ≤ banditArmMean ν i)
(hn : k * Nat.clog 2 k ≤ n) (H₂ : ℝ)
(hH₂ : ∀ i : Fin k, 0 < banditGap ν i →
((i : ℕ) + 1 : ℝ) / banditGap ν i ^ 2 ≤ H₂)
(π : BanditPolicy k) (ℓ : ℕ) (hℓ : ℓ < Nat.clog 2 k) :
(banditMeasure ν π n).real {h | IsSeqHalvingEliminationAt k n h ℓ} ≤
3 * Real.exp (-(n / (16 * H₂ * (Nat.clog 2 k : ℝ)))) := by
sorrySource
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), Exercise 33.8(b)–(e), printed pp. 419–420.