When rewards are binary — a click or no click, a cure or no cure — the subgaussian machinery of Missions I–III is not tight: the variance of a Bernoulli arm degrades near the boundary of , and the correct exponential rate is governed by the binary relative entropy rather than a squared distance. Chapter 10 of Lattimore–Szepesvári develops Chernoff's tail bound in its information-theoretic form and the KL-UCB algorithm, whose upper confidence bounds are level sets of . The goal theorem shows KL-UCB attains
— asymptotic optimality with exactly the constant demanded by the lower bound of Mission VII, strictly improving subgaussian UCB on every Bernoulli instance.
theorem BanditAlgorithm.bandit_kl_ucb_regret_bound {k : ℕ} (μvec : Fin k → ℝ)
(hμ : ∀ i, μvec i ∈ Set.Icc (0 : ℝ) 1)
(ν : StochasticBandit k) (hν : ν = bernoulliBandit μvec hμ)
(π : BanditPolicy k) (hπ : IsKLUCBPolicy π) :
(∀ n : ℕ, ∀ ε₁ ε₂ : Fin k → ℝ,
(∀ i, 0 < banditGap ν i →
0 < ε₁ i ∧ 0 < ε₂ i ∧ ε₁ i + ε₂ i < banditGap ν i) →
banditRegret ν π n ≤
∑ i ∈ Finset.univ.filter (fun i ↦ 0 < banditGap ν i),
banditGap ν i *
(Real.log (klucbExploration n) /
bernoulliRelativeEntropy (banditArmMean ν i + ε₁ i)
(banditOptimalMean ν - ε₂ i) +
1 / (2 * ε₁ i ^ 2) + 2 / ε₂ i ^ 2)) ∧
atTop.limsup
(fun n : ℕ ↦ ENNReal.ofReal (banditRegret ν π n / Real.log n)) ≤
∑ i ∈ Finset.univ.filter (fun i ↦ 0 < banditGap ν i),
ENNReal.ofReal (banditGap ν i) /
ENNReal.ofReal
(bernoulliRelativeEntropy (banditArmMean ν i)
(banditOptimalMean ν)) := by
sorry
(KL-UCB regret bound, GOAL, L&S Theorem 10.6) If the reward in round is — i.e. the environment is bernoulliBandit for a mean vector — then the regret of Algorithm 8 (KL-UCB with ) satisfies, for every ,
for EVERY family with and at each suboptimal arm (-family encoding of the book's infimum), and furthermore
stated in (a zero/junk divergence contributes ), mirroring the liminf style of bandit_instance_dependent_lower_bound.
No open leaves. Every sub-goal is proved or awaiting decomposition.