Sequential Halving optimal-arm elimination bound with phases
DisprovedBanditAlgorithm.sequential_halving_failure_probability_bound_clogbanditsbest-arm-identificationconcentrationsequential-halving
Let . Consider a -armed -subgaussian bandit whose means are indexed in nonincreasing order, with budget , and let satisfy for every suboptimal arm.
Under any bandit policy, the probability that the realized history contains a complete Sequential Halving active-set chain whose final active set has eliminated the optimal arm is at most
This is the phase-elimination concentration core of Sequential Halving. It contains the probabilistic content of the fixed-budget guarantee while remaining independent of the recommendation rule.
Formalization Note A failure history is represented by IsSeqHalvingFailureRun, which records all phase cardinality, ranking, support, and equal-allocation invariants.
Preamble
import Definitions.Def_SequentialHalvingFailure open MeasureTheory
Formal statement
theorem BanditAlgorithm.sequential_halving_failure_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) :
(banditMeasure ν π n).real {h | IsSeqHalvingFailureRun k n h} ≤
3 * (Nat.clog 2 k : ℝ) *
Real.exp (-(n / (16 * H₂ * (Nat.clog 2 k : ℝ)))) := by
sorrySource
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), Exercise 33.8(b)–(f), printed pp. 419–420; this theorem is the direct general-k phase-count form with L = ceil(log₂ k).