Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Optimal-arm elimination in one Sequential Halving phase

Definition
SequentialHalvingPhaseElimination

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

banditsbest-arm-identificationsequential-halving

A history exhibits elimination at phase ℓ\ellℓ when it admits a complete Sequential Halving active-set chain in which the first arm (Lean index 000) is active at the beginning of phase ℓ\ellℓ and absent at the beginning of phase ℓ+1\ell+1ℓ+1.

The predicate records the phase-local failure event used in the proof of the Sequential Halving error bound, including the full run invariants needed to interpret the active sets and fresh empirical means.

Formalization Note The distinguished arm is quantified with natural-number index zero, so the definition remains well-typed for every natural-number arm count.

Definition code
import Definitions.Def_SequentialHalvingFailure

open Finset

namespace BanditAlgorithm

/-- A complete Sequential Halving active-set chain in which arm `0` is present
at the start of phase `ℓ` and absent immediately after that phase. -/
def IsSeqHalvingEliminationAt (k n : ℕ) (h : BanditHistory k n) (ℓ : ℕ) : Prop :=
  ∃ A : ℕ → Finset (Fin k),
    A 0 = Finset.univ ∧
    (∀ s < Nat.clog 2 k,
      A (s + 1) ⊆ A s ∧
      (A (s + 1)).card = ((A s).card + 1) / 2 ∧
      (∀ i ∈ A (s + 1), ∀ j ∈ A s \ A (s + 1),
        seqHalvingPhaseMean h s j ≤ seqHalvingPhaseMean h s i) ∧
      (∀ t ∈ seqHalvingPhase k n s, (h t).1 ∈ A s) ∧
      (∀ i ∈ A s,
        ((seqHalvingPhase k n s).filter (fun t ↦ (h t).1 = i)).card =
          seqHalvingPulls k n s)) ∧
    ∃ i₀ : Fin k, (i₀ : ℕ) = 0 ∧ i₀ ∈ A ℓ ∧ i₀ ∉ A (ℓ + 1)

end BanditAlgorithm
Source
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), Algorithm 22 and Exercise 33.8(c)–(e), printed pp. 412–413 and 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