BanditAlgorithm.bandit_kl_ucb_regret_bound
Provedbanditskl-ucbregret
(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.
Preamble
import Definitions.Def_bernoulliRelativeEntropy import Definitions.Def_banditRegret open MeasureTheory ProbabilityTheory Filter
Formal statement
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
Source
L&S Theorem 10.6, p.137