Theorem 33.10: Sequential Halving with L phases
ProvedBanditAlgorithm.best_arm_identification_sequential_halving_clogbanditsbest-arm-identificationpure-explorationsequential-halving
Let . For a sorted -armed 1-subgaussian bandit, suppose and bounds for every suboptimal arm. Any policy and recommendation rule implementing Sequential Halving satisfies
This uses the exact natural-number phase count in Algorithm 22 rather than the real-valued logb expression.
Preamble
import Definitions.Def_SequentialHalving open MeasureTheory
Formal statement
theorem BanditAlgorithm.best_arm_identification_sequential_halving_clog {k n : ℕ}
(ν : StochasticBandit k) (hν : IsSubgaussianBandit 1 ν)
(hsorted : ∀ i j : Fin k, i ≤ j → banditArmMean ν j ≤ banditArmMean ν i)
(hn : k * Nat.clog 2 k ≤ n) (H₂ : ℝ)
(hH₂ : ∀ i : Fin k, 0 < banditGap ν i →
((i : ℕ) + 1 : ℝ) / banditGap ν i ^ 2 ≤ H₂)
(π : BanditPolicy k) (rec : BanditHistory k n → Fin k)
(hπ : IsSequentialHalvingPolicy k n π rec) :
(banditMeasure ν π n).real {h | 0 < banditGap ν (rec h)} ≤
3 * (Nat.clog 2 k : ℝ) *
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 pp. 419-420; L is formalized as Nat.clog 2 k.