Sequential Halving optimized rank-tail probability bound
ProvedBanditAlgorithm.sequential_halving_rank_tail_average_bound_clog_minbanditsconcentrationpure-explorationsequential-halving
Let , be the active-arm count, , and . If for every positive gap, then some cutoff makes the rank-tail average, capped by the trivial probability bound , satisfy
The optimized cutoff absorbs the floor in ; the cap by is essential in the small-exponent regime, where the desired right-hand side is already at least one.
Preamble
import Definitions.Def_SequentialHalving open MeasureTheory
Formal statement
theorem BanditAlgorithm.sequential_halving_rank_tail_average_bound_clog_min
{k n : ℕ} (gap : Fin k → ℝ)
(hn : k * Nat.clog 2 k ≤ n) (H₂ : ℝ)
(hH₂ : ∀ i : Fin k, 0 < gap i →
((i : ℕ) + 1 : ℝ) / gap i ^ 2 ≤ H₂)
(ℓ : ℕ) (hℓ : ℓ < Nat.clog 2 k) :
∃ threshold : ℕ, threshold < BanditAlgorithm.seqHalvingCount k (ℓ + 1) ∧
min 1 ((∑ i : Fin k,
if threshold ≤ (i : ℕ) ∧ 0 < gap i then
Real.exp (-(BanditAlgorithm.seqHalvingPulls k n ℓ : ℝ) * gap i ^ 2 / 4)
else 0) /
((BanditAlgorithm.seqHalvingCount k (ℓ + 1) - threshold : ℕ) : ℝ)) ≤
3 * Real.exp (-(n / (16 * H₂ * (Nat.clog 2 k : ℝ)))) := by
sorrySource
Lattimore and Szepesvari, Bandit Algorithms (2020), Theorem 33.10 p. 412 and Exercise 33.8(c)-(e) pp. 419-420; floor-aware analytic bridge for Algorithm 22 line 4.