Sequential Halving error bound with phases
ProvedBanditAlgorithm.sequential_halving_run_error_probability_bound_clogLet be the number of phases used by Sequential Halving. Consider a -armed -subgaussian bandit with arm means indexed in nonincreasing order, and assume . Let satisfy for every suboptimal arm, with ranks numbered from .
For any policy and recommendation rule, restrict to histories satisfying the full deterministic Sequential Halving run invariant: the active set is halved in each of the phases, each active arm receives the prescribed number of fresh samples, and each survivor has phase empirical mean at least that of every eliminated arm. Then
This is the direct general- phase-count form of the Sequential Halving analysis. It isolates the concentration argument from implementation and tie-breaking details.
Formalization Note Here is represented by Nat.clog 2 k, matching the number of phases in IsSeqHalvingRun.
import Definitions.Def_SequentialHalving open MeasureTheory
theorem BanditAlgorithm.sequential_halving_run_error_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) (rec : BanditHistory k n → Fin k) :
(banditMeasure ν π n).real
{h | IsSeqHalvingRun k n h (rec h) ∧ 0 < banditGap ν (rec h)} ≤
3 * (Nat.clog 2 k : ℝ) *
Real.exp (-(n / (16 * H₂ * (Nat.clog 2 k : ℝ)))) := by
sorry