Sequential Halving error bound on valid runs
OpenBanditAlgorithm.sequential_halving_run_error_probability_boundConsider a -armed -subgaussian bandit whose means are indexed in nonincreasing order, and a budget large enough that every phase of Sequential Halving samples every active arm at least once. Let be any common upper bound satisfying
for each suboptimal arm, with arm indices numbered from . For an arbitrary policy and recommendation rule, restrict attention to the histories that satisfy the complete deterministic Sequential Halving run invariant: the active sets halve with the prescribed cardinalities, every active arm receives the prescribed number of fresh phase samples, and survivors have empirical means at least those of eliminated arms. Then the probability of such a valid run ending with a suboptimal recommendation is at most
This is the concentration core of the fixed-budget Sequential Halving guarantee. Separating it from the policy-level theorem makes the result reusable for any implementation or tie-breaking rule whose realized histories satisfy the same run invariant.
Formalization Note The event explicitly includes IsSeqHalvingRun; no assumption is made here that the supplied policy produces valid runs almost surely.
import Mathlib.Analysis.SpecialFunctions.Log.Base import Definitions.Def_SequentialHalving open MeasureTheory
theorem BanditAlgorithm.sequential_halving_run_error_probability_bound {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 * Real.logb 2 k * Real.exp (-(n / (16 * H₂ * Real.logb 2 k))) := by
sorry