Sequential Halving failure run
DefinitionSequentialHalvingFailureA 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 (represented by index 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.
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