KL-UCB index threshold feasibility
ProvedBanditAlgorithm.klucb_index_threshold_feasiblebandit-algorithmsformal-bridgekl-ucb
Let be a finite bandit history, let be the empirical mean of arm , and let . Write
for the KL-UCB index after observations, with . Then
This equivalence is the deterministic confidence-set bridge used in the proof of the KL-UCB pull-count decomposition: an interior threshold lies below the supremum index exactly when its one-sided KL constraint is feasible.
Formalization Note The explicit assumption is satisfied on Bernoulli histories. The endpoint guards in the definition of the index are retained, while the threshold is restricted to the open unit interval.
Preamble
import Definitions.Def_klucbTruncatedRelativeEntropy open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.klucb_index_threshold_feasible
{k n : ℕ} (i : Fin k) (h : BanditAlgorithm.BanditHistory k n)
(q : ℝ) (hq : q ∈ Set.Ioo (0 : ℝ) 1)
(hp : BanditAlgorithm.armEmpiricalMean i h ∈ Set.Icc (0 : ℝ) 1) :
q ≤ BanditAlgorithm.klucbIndex i h ↔
BanditAlgorithm.klucbTruncatedRelativeEntropy
(BanditAlgorithm.armEmpiricalMean i h) q ≤
Real.log (BanditAlgorithm.klucbExploration (n + 1)) /
BanditAlgorithm.armPullCount i h := by
sorrySource
Lattimore and Szepesvari, Bandit Algorithms (CUP 2020), Algorithm 8 printed p. 137 / PDF p. 146 and the threshold-feasibility step in the proof of Theorem 10.6 printed p. 139 / PDF p. 148. This is the formal supremum/feasibility bridge implicit in that step.