Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Sequential Halving bad-final and last-optimal-elimination events

Definition
SequentialHalvingBadFinal

by Harry_Xu · Aug 2, 2026 · Mathlib 0df444a (Lean v4.33.1)

banditsbest-arm-identificationsequential-halving

IsSeqHalvingBadFinalRun records a complete Sequential Halving active-set chain that starts with at least one optimal arm and ends with no optimal arm. IsSeqHalvingLastOptimalEliminationAt records the phase-local transition at which the active set changes from containing an optimal arm to containing only suboptimal arms.

These predicates isolate the correct failure events when a bandit may have multiple optimal arms: eliminating one particular optimal arm is harmless if another optimal arm survives, whereas eliminating the last optimal arm is the event relevant to misidentification.

Formalization Note Optimality is expressed by zero gap and suboptimality by strictly positive gap.

Definition code
import Definitions.Def_SequentialHalving

open Finset

namespace BanditAlgorithm

/-- A complete Sequential Halving active-set chain which starts with at least
one optimal arm and ends with no optimal arm. -/
def IsSeqHalvingBadFinalRun (k n : ℕ) (ν : StochasticBandit k)
    (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 ∈ A 0, banditGap ν i = 0) ∧
    (∀ i ∈ A (Nat.clog 2 k), 0 < banditGap ν i)

/-- A complete Sequential Halving active-set chain in which phase `ℓ`
eliminates every optimal arm that was still active. -/
def IsSeqHalvingLastOptimalEliminationAt (k n : ℕ) (ν : StochasticBandit k)
    (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 ∈ A ℓ, banditGap ν i = 0) ∧
    (∀ i ∈ A (ℓ + 1), 0 < banditGap ν i)

end BanditAlgorithm
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 last-optimal formulation makes the proof valid with multiple optimal arms.

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