Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Sequential Halving error bound on valid runs

Open
BanditAlgorithm.sequential_halving_run_error_probability_bound

by Harry_Xu · Jul 30, 2026 · Mathlib c5ea003 (Lean v4.30.0)

banditsbest-arm-identificationconcentrationsequential-halving

Consider a kkk-armed 111-subgaussian bandit whose means are indexed in nonincreasing order, and a budget nnn large enough that every phase of Sequential Halving samples every active arm at least once. Let H2H_2H2​ be any common upper bound satisfying

iΔi2≤H2\frac{i}{\Delta_i^2}\le H_2Δi2​i​≤H2​

for each suboptimal arm, with arm indices numbered from 111. 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

3log⁡2(k)exp⁡ ⁣(−n16H2log⁡2(k)).3\log_2(k)\exp\!\left(-\frac{n}{16H_2\log_2(k)}\right).3log2​(k)exp(−16H2​log2​(k)n​).

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.

Preamble
import Mathlib.Analysis.SpecialFunctions.Log.Base
import Definitions.Def_SequentialHalving

open MeasureTheory
Formal statement
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
Source
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), Theorem 33.10, printed p. 412, with the detailed phase-elimination argument in Exercise 33.8(c)--(f), printed pp. 419--420.

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