Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Sequential Halving error bound with L=⌈log⁡2k⌉L=\lceil\log_2 k\rceilL=⌈log2​k⌉ phases

Proved
BanditAlgorithm.sequential_halving_run_error_probability_bound_clog

by Harry_Xu · Aug 2, 2026 · Mathlib c5ea003 (Lean v4.30.0)

banditsbest-arm-identificationconcentrationsequential-halving

Let L=⌈log⁡2k⌉L=\lceil\log_2 k\rceilL=⌈log2​k⌉ be the number of phases used by Sequential Halving. Consider a kkk-armed 111-subgaussian bandit with arm means indexed in nonincreasing order, and assume n≥kLn\ge kLn≥kL. Let H2H_2H2​ satisfy i/Δi2≤H2i/\Delta_i^2\le H_2i/Δi2​≤H2​ for every suboptimal arm, with ranks numbered from 111.

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 LLL 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

P(valid run and suboptimal recommendation)≤3Lexp⁡ ⁣(−n16H2L).\mathbb P(\text{valid run and suboptimal recommendation}) \le 3L\exp\!\left(-\frac{n}{16H_2L}\right).P(valid run and suboptimal recommendation)≤3Lexp(−16H2​Ln​).

This is the direct general-kkk phase-count form of the Sequential Halving analysis. It isolates the concentration argument from implementation and tie-breaking details.

Formalization Note Here LLL is represented by Nat.clog 2 k, matching the number of phases in IsSeqHalvingRun.

Preamble
import Definitions.Def_SequentialHalving

open MeasureTheory
Formal statement
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
Source
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), Algorithm 22 and Exercise 33.8(c)–(f), printed pp. 412–413 and 419–420. The displayed L-bound is the direct general-k phase-count form of the exercise proof.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me