Sequential Halving optimized rank-tail average bound
DisprovedBanditAlgorithm.sequential_halving_rank_tail_average_bound_clogbanditsconcentrationpure-explorationsequential-halving
Let , let be the deterministic number of active arms in phase , let , and let . Suppose positive gaps satisfy . Then there is a rank cutoff such that the average of the one-arm tails above obeys
The cutoff is optimized rather than fixed at one quarter; this is what absorbs the natural-number floor in while retaining the book constant .
Preamble
import Definitions.Def_SequentialHalving open MeasureTheory
Formal statement
theorem BanditAlgorithm.sequential_halving_rank_tail_average_bound_clog
{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) ∧
(∑ 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.