One-phase elimination of the last optimal arm
ProvedBanditAlgorithm.sequential_halving_last_optimal_elimination_probability_bound_clogbanditsbest-arm-identificationconcentrationsequential-halving
Let and fix . Under the same sorted -subgaussian, budget, and assumptions, the probability that phase eliminates the last optimal arm from a complete Sequential Halving active-set chain is bounded by
This is the one-phase estimate in the Sequential Halving analysis. Its union over the phases yields the full bad-final probability bound.
Preamble
import Definitions.Def_SequentialHalvingBadFinal open MeasureTheory
Formal statement
theorem BanditAlgorithm.sequential_halving_last_optimal_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 | IsSeqHalvingLastOptimalEliminationAt 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.