Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

From the finite KL-UCB bound to the asymptotic constant

Proved
BanditAlgorithm.bandit_kl_ucb_finite_to_asymptotic

by Harry_Xu · Jul 29, 2026 · Mathlib c5ea003 (Lean v4.30.0)

asymptoticsbanditsprobability

This is the limiting argument that turns the finite-horizon KL-UCB estimate into its asymptotic regret guarantee.

Consider a finite Bernoulli bandit with means μi∈[0,1]\mu_i\in[0,1]μi​∈[0,1], optimal mean μ⋆\mu^\starμ⋆, gaps Δi=μ⋆−μi\Delta_i=\mu^\star-\mu_iΔi​=μ⋆−μi​, and a KL-UCB policy. Assume that for every horizon nnn and every positive arm-dependent pair ε1,i,ε2,i\varepsilon_{1,i},\varepsilon_{2,i}ε1,i​,ε2,i​ with ε1,i+ε2,i<Δi\varepsilon_{1,i}+\varepsilon_{2,i}<\Delta_iε1,i​+ε2,i​<Δi​, the standard finite-time bound of Theorem 10.6 holds. Then

lim sup⁡n→∞Rn(π,ν)log⁡n≤∑i:Δi>0Δid(μi,μ⋆).\limsup_{n\to\infty}\frac{R_n(\pi,\nu)}{\log n} \le \sum_{i:\Delta_i>0}\frac{\Delta_i}{d(\mu_i,\mu^\star)}.n→∞limsup​lognRn​(π,ν)​≤i:Δi​>0∑​d(μi​,μ⋆)Δi​​.

This theorem isolates the analytic passage from the non-asymptotic KL-UCB estimate to its optimal logarithmic leading constant.

Formalization Note The entire finite-horizon estimate is supplied as a hypothesis. The conclusion uses the extended-nonnegative-real limsup representation from the mission theorem.

Preamble
import Definitions.Def_bernoulliRelativeEntropy
import Definitions.Def_banditRegret

open MeasureTheory ProbabilityTheory Filter
Formal statement
theorem BanditAlgorithm.bandit_kl_ucb_finite_to_asymptotic
    {k : ℕ} (μvec : Fin k → ℝ)
    (hμ : ∀ i, μvec i ∈ Set.Icc (0 : ℝ) 1)
    (ν : StochasticBandit k) (hν : ν = bernoulliBandit μvec hμ)
    (π : BanditPolicy k) (hπ : IsKLUCBPolicy π)
    (hfinite :
      ∀ 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
Tor Lattimore and Csaba Szepesvári, Bandit Algorithms, Cambridge University Press, 2020, asymptotic claim of Theorem 10.6, printed p. 137; Exercise 10.2 and its hint, printed pp. 141–142: choose ε₁ and ε₂ to decrease slowly with n and use the first claim.

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