Optimal-arm elimination in one Sequential Halving phase
DefinitionSequentialHalvingPhaseEliminationbanditsbest-arm-identificationsequential-halving
A history exhibits elimination at phase when it admits a complete Sequential Halving active-set chain in which the first arm (Lean index ) is active at the beginning of phase and absent at the beginning of phase .
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 BanditAlgorithmSource
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), Algorithm 22 and Exercise 33.8(c)–(e), printed pp. 412–413 and 419–420.