Asymptotic regret bound for KL-UCB
ProvedBanditAlgorithm.bandit_kl_ucb_asymptotic_regret_boundbanditsinformation-theoryprobability
This is the asymptotic regret guarantee for KL-UCB on a Bernoulli bandit.
Consider a stochastic bandit with finitely many Bernoulli arms. Arm has mean ; write , , and
for the binary relative entropy. If satisfies the KL-UCB selection rule with exploration function , then
The bound gives the optimal problem-dependent logarithmic rate for KL-UCB and is the asymptotic conclusion of the standard finite-time analysis.
Formalization Note The formal statement takes the limsup in the extended nonnegative reals after applying the nonnegative-real embedding to normalized regret. The bandit is explicitly identified with the Bernoulli bandit determined by the supplied mean vector.
Preamble
import Definitions.Def_bernoulliRelativeEntropy import Definitions.Def_banditRegret open MeasureTheory ProbabilityTheory Filter
Formal statement
theorem BanditAlgorithm.bandit_kl_ucb_asymptotic_regret_bound
{k : ℕ} (μvec : Fin k → ℝ)
(hμ : ∀ i, μvec i ∈ Set.Icc (0 : ℝ) 1)
(ν : StochasticBandit k) (hν : ν = bernoulliBandit μvec hμ)
(π : BanditPolicy k) (hπ : IsKLUCBPolicy π) :
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
sorrySource
Tor Lattimore and Csaba Szepesvári, Bandit Algorithms, Cambridge University Press, 2020, Theorem 10.6, printed p. 137; asymptotic derivation assigned as Exercise 10.2 with hint on printed pp. 141–142.