Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Sequential Halving failure run

Definition
SequentialHalvingFailure

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

banditsbest-arm-identificationsequential-halving

A history is a Sequential Halving failure run when there is a complete active-set chain satisfying Algorithm 22—correct initial set, halving cardinalities, survivor empirical-mean ordering, phase support, and equal phase pull counts—but the final active set omits arm 111 (represented by index 000 in Lean).

This predicate isolates the algorithmic failure event used in the phase-elimination proof of the fixed-budget guarantee. It is independent of the recommendation rule, so it can be reused for different Sequential Halving implementations and tie-breaking conventions.

Formalization Note The distinguished arm is quantified together with the condition that its natural-number index is zero. This keeps the definition well-typed even when the arm type is empty.

Definition code
import Definitions.Def_SequentialHalving

open Finset

namespace BanditAlgorithm

/-- A Sequential Halving active-set chain whose final set omits arm `0`, the
optimal arm when means are indexed in nonincreasing order.  The existential
`i₀` plus `(i₀ : ℕ) = 0` keeps the definition meaningful also at `k = 0`. -/
def IsSeqHalvingFailureRun (k n : ℕ) (h : BanditHistory k n) : Prop :=
  ∃ A : ℕ → Finset (Fin k),
    A 0 = Finset.univ ∧
    (∀ ℓ < Nat.clog 2 k,
      A (ℓ + 1) ⊆ A ℓ ∧
      (A (ℓ + 1)).card = ((A ℓ).card + 1) / 2 ∧
      (∀ i ∈ A (ℓ + 1), ∀ j ∈ A ℓ \ A (ℓ + 1),
        seqHalvingPhaseMean h ℓ j ≤ seqHalvingPhaseMean h ℓ i) ∧
      (∀ t ∈ seqHalvingPhase k n ℓ, (h t).1 ∈ A ℓ) ∧
      (∀ i ∈ A ℓ,
        ((seqHalvingPhase k n ℓ).filter (fun t ↦ (h t).1 = i)).card =
          seqHalvingPulls k n ℓ)) ∧
    ∃ i₀ : Fin k, (i₀ : ℕ) = 0 ∧ i₀ ∉ A (Nat.clog 2 k)

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