Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Sequential Halving optimal-arm elimination bound with LLL phases

Disproved
BanditAlgorithm.sequential_halving_failure_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⌉. Consider a kkk-armed 111-subgaussian bandit whose means are indexed in nonincreasing order, with budget n≥kLn\ge kLn≥kL, and let H2H_2H2​ satisfy i/Δi2≤H2i/\Delta_i^2\le H_2i/Δi2​≤H2​ for every suboptimal arm.

Under any bandit policy, the probability that the realized history contains a complete Sequential Halving active-set chain whose final active set has eliminated the optimal arm is at most

P(optimal arm eliminated)≤3Lexp⁡ ⁣(−n16H2L).\mathbb P(\text{optimal arm eliminated}) \le 3L\exp\!\left(-\frac{n}{16H_2L}\right).P(optimal arm eliminated)≤3Lexp(−16H2​Ln​).

This is the phase-elimination concentration core of Sequential Halving. It contains the probabilistic content of the fixed-budget guarantee while remaining independent of the recommendation rule.

Formalization Note A failure history is represented by IsSeqHalvingFailureRun, which records all phase cardinality, ranking, support, and equal-allocation invariants.

Preamble
import Definitions.Def_SequentialHalvingFailure

open MeasureTheory
Formal statement
theorem BanditAlgorithm.sequential_halving_failure_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 | IsSeqHalvingFailureRun k n 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), Exercise 33.8(b)–(f), printed pp. 419–420; this theorem is the direct general-k phase-count form with L = ceil(log₂ k).

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