KL-UCB pathwise feasibility-count split
ProvedBanditAlgorithm.bandit_kl_ucb_feasibility_pull_count_splitConsider KL-UCB on a Bernoulli bandit with arm means . Fix an optimal arm , a suboptimal arm , and a tolerance , where . Let be the number of times arm is selected before horizon . Let count selections of caused by incomplete initialization or failure of the optimal arm's KL threshold test, and let count initialized selections of for which the selected arm passes its KL threshold test.
Then the expected pull count is bounded by the expectations of these two failure counts:
Indeed, on every realized Bernoulli reward history, if KL-UCB selects , maximality of its index implies a dichotomy. Either the optimal arm does not regard as feasible, or the selected arm does. Thus every selection of is charged pathwise to exactly one of the two displayed counts, and integration gives the result.
This lemma is the deterministic-probabilistic interface in the proof of the finite-time KL-UCB regret bound: subsequent concentration lemmas bound the two expectations separately.
Formalization Note: The policy hypothesis is expressed by IsKLUCBPolicy; the Bernoulli-bandit equality supplies the almost-sure -valued reward support needed to place empirical means in . The Lean proof first establishes the inequality on every supported finite history, then verifies measurability and integrability of all three finite counts before applying monotonicity of the integral.
import Definitions.Def_klucbFeasibilityFailureCount open MeasureTheory ProbabilityTheory
theorem BanditAlgorithm.bandit_kl_ucb_feasibility_pull_count_split
{k : ℕ} (μvec : Fin k → ℝ)
(hμ : ∀ i, μvec i ∈ Set.Icc (0 : ℝ) 1)
(ν : BanditAlgorithm.StochasticBandit k)
(hν : ν = BanditAlgorithm.bernoulliBandit μvec hμ)
(π : BanditAlgorithm.BanditPolicy k)
(hπ : BanditAlgorithm.IsKLUCBPolicy π)
(n : ℕ) (a i : Fin k) (ε : ℝ)
(ha : BanditAlgorithm.banditArmMean ν a =
BanditAlgorithm.banditOptimalMean ν)
(hε : 0 < ε) (hεgap : ε < BanditAlgorithm.banditGap ν i) :
MeasureTheory.integral (BanditAlgorithm.banditMeasure ν π n)
(fun h ↦ (BanditAlgorithm.armPullCount i h : ℝ)) ≤
MeasureTheory.integral (BanditAlgorithm.banditMeasure ν π n)
(fun h ↦
(BanditAlgorithm.klucbFeasibilityFailureCount ν a i ε h).1) +
MeasureTheory.integral (BanditAlgorithm.banditMeasure ν π n)
(fun h ↦
(BanditAlgorithm.klucbFeasibilityFailureCount ν a i ε h).2) := by
sorry