Finite-horizon regret bound for KL-UCB
ProvedBanditAlgorithm.bandit_kl_ucb_finite_regret_boundThis is the finite-horizon 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. Let be any policy satisfying the KL-UCB selection rule with exploration function . For every horizon and every pair of arm-dependent tolerances satisfying on each suboptimal arm,
This estimate is the non-asymptotic part of the KL-UCB analysis and isolates the contribution of every suboptimal arm, making it reusable in finite-time regret arguments.
Formalization Note The bandit is explicitly identified with the Bernoulli bandit determined by the supplied mean vector. The tolerances are represented as functions on the finite arm type, and the sum is restricted to arms with strictly positive gap.
import Definitions.Def_bernoulliRelativeEntropy import Definitions.Def_banditRegret open MeasureTheory ProbabilityTheory Filter
theorem BanditAlgorithm.bandit_kl_ucb_finite_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) := by
sorry