Sequential Halving bad-final probability with phases
ProvedBanditAlgorithm.sequential_halving_bad_final_probability_bound_clogbanditsbest-arm-identificationconcentrationsequential-halving
Let . For a sorted -subgaussian bandit, budget , and complexity bound , consider the event that a complete Sequential Halving active-set chain starts with an optimal arm but its final active set contains only suboptimal arms. Under any policy,
This is the recommendation-independent concentration core of the general- Sequential Halving guarantee. It remains correct when several arms are optimal.
Preamble
import Definitions.Def_SequentialHalvingBadFinal open MeasureTheory
Formal statement
theorem BanditAlgorithm.sequential_halving_bad_final_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 | IsSeqHalvingBadFinalRun 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(c)–(f), printed pp. 419–420; direct general-k phase-count form.