Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

BanditAlgorithm.bandit_kl_ucb_regret_bound

Proved

by Shuze Chen · Jul 26, 2026 · Mathlib 0df444a (Lean v4.33.1)

banditskl-ucbregret

(KL-UCB regret bound, GOAL, L&S Theorem 10.6) If the reward in round ttt is Xt∼B(μAt)X_t \sim \mathcal{B}(\mu_{A_t})Xt​∼B(μAt​​) — i.e. the environment is bernoulliBandit for a mean vector μ∈[0,1]k\mu \in [0,1]^kμ∈[0,1]k — then the regret of Algorithm 8 (KL-UCB with f(t)=1+tlog⁡2tf(t) = 1+t\log^2 tf(t)=1+tlog2t) satisfies, for every nnn,

Rn≤∑i:Δi>0Δi(log⁡f(n)d(μi+ε1i, μ∗−ε2i)+12(ε1i)2+2(ε2i)2)R_n \le \sum_{i:\Delta_i>0} \Delta_i\left(\frac{\log f(n)}{d(\mu_i+\varepsilon_1^i,\ \mu^*-\varepsilon_2^i)} + \frac{1}{2(\varepsilon_1^i)^2} + \frac{2}{(\varepsilon_2^i)^2}\right)Rn​≤i:Δi​>0∑​Δi​(d(μi​+ε1i​, μ∗−ε2i​)logf(n)​+2(ε1i​)21​+(ε2i​)22​)

for EVERY family ε1,ε2\varepsilon_1, \varepsilon_2ε1​,ε2​ with ε1i,ε2i>0\varepsilon_1^i, \varepsilon_2^i > 0ε1i​,ε2i​>0 and ε1i+ε2i∈(0,Δi)\varepsilon_1^i + \varepsilon_2^i \in (0, \Delta_i)ε1i​+ε2i​∈(0,Δi​) at each suboptimal arm (∀\forall∀-family encoding of the book's infimum), and furthermore

lim sup⁡n→∞Rnlog⁡n≤∑i:Δi>0Δid(μi,μ∗),\limsup_{n\to\infty} \frac{R_n}{\log n} \le \sum_{i:\Delta_i>0} \frac{\Delta_i}{d(\mu_i, \mu^*)},n→∞limsup​lognRn​​≤i:Δi​>0∑​d(μi​,μ∗)Δi​​,

stated in R‾≥0\overline{\mathbb{R}}_{\ge 0}R≥0​ (a zero/junk divergence contributes ∞\infty∞), 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

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me