Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

BanditAlgorithm.bandit_kl_ucb_regret_bound

Proved

by Shuze Chen · Jul 26, 2026 · Mathlib c5ea003 (Lean v4.30.0)

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
Read-back

What the Lean code literally says, in plain math · claude-fable-5

Setup and notation. Let

d(p,q)=p log⁡pq+(1−p) log⁡1−p1−qd(p,q)=p\,\log\frac{p}{q}+(1-p)\,\log\frac{1-p}{1-q}d(p,q)=plogqp​+(1−p)log1−q1−p​

with the real conventions (division by 000 gives 000; log⁡\loglog of a nonpositive number is 000; so ddd is finite everywhere). Fix (μi0)i<k(\mu^{0}_i)_{i<k}(μi0​)i<k​ with each μi0∈[0,1]\mu^{0}_i\in[0,1]μi0​∈[0,1], and let ν\nuν be a kkk-armed bandit hypothesized to equal the Bernoulli bandit of this vector: arm iii's distribution is μi0 δ1+(1−μi0) δ0\mu^{0}_i\,\delta_1+(1-\mu^{0}_i)\,\delta_0μi0​δ1​+(1−μi0​)δ0​ on R\mathbb{R}R. Write μi=∫x dνi\mu_i=\int x\,d\nu_iμi​=∫xdνi​ for the (Bochner-integral) mean of arm iii's distribution, μ∗=sup⁡iμi\mu^{*}=\sup_i\mu_iμ∗=supi​μi​, Δi=μ∗−μi\Delta_i=\mu^{*}-\mu_iΔi​=μ∗−μi​. Pn\mathbb{P}^{n}Pn is the canonical history measure of ν\nuν and a policy π\piπ (built from the empty history by repeatedly drawing an arm from the policy kernel and a reward from that arm), and Rn=nμ∗−∫(∑t<nXt)dPnR_n=n\mu^{*}-\int\bigl(\sum_{t<n}X_t\bigr)d\mathbb{P}^{n}Rn​=nμ∗−∫(∑t<n​Xt​)dPn is the expected regret (integral =0=0=0 by convention if not integrable). The schedule is f(t)=1+t(log⁡t)2f(t)=1+t(\log t)^2f(t)=1+t(logt)2 (log⁡0=0\log 0=0log0=0, f(0)=f(1)=1f(0)=f(1)=1f(0)=f(1)=1). The index of arm iii at a length-mmm history hhh is

γi(h)=sup⁡{μ′∈[0,1] ∣ d(μ^i(h),μ′)≤log⁡f(m+1)Ti(h), (μ′=0⇒μ^i(h)=0), (μ′=1⇒μ^i(h)=1)}\gamma_i(h)=\sup\Bigl\{\mu'\in[0,1]\ \Bigm|\ d(\hat\mu_i(h),\mu')\le\tfrac{\log f(m+1)}{T_i(h)},\ (\mu'=0\Rightarrow\hat\mu_i(h)=0),\ (\mu'=1\Rightarrow\hat\mu_i(h)=1)\Bigr\}γi​(h)=sup{μ′∈[0,1] ​ d(μ^​i​(h),μ′)≤Ti​(h)logf(m+1)​, (μ′=0⇒μ^​i​(h)=0), (μ′=1⇒μ^​i​(h)=1)}

(sup⁡∅=0\sup\varnothing=0sup∅=0; TiT_iTi​, μ^i\hat\mu_iμ^​i​ = pull count and empirical mean with x/0=0x/0=0x/0=0), and the policy property assumed of π\piπ is: at every history of every length there is an arm aaa selected with probability one, unpulled if any arm is unpulled, and non-strictly maximizing γ\gammaγ over all arms if every arm has been pulled. Write (x)+=max⁡(x,0)(x)^{+}=\max(x,0)(x)+=max(x,0) viewed in [0,∞][0,\infty][0,∞].

Assertion (a conjunction). (1) Finite-horizon bound: for every horizon nnn and all real families (ε1,i)(\varepsilon_{1,i})(ε1,i​), (ε2,i)(\varepsilon_{2,i})(ε2,i​) satisfying the hypothesis below,

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

(2) Asymptotic bound:

lim sup⁡n→∞(Rnlog⁡n) ⁣+ ≤ ∑i: Δi>0(Δi)+(d(μi,μ∗))+in [0,∞],\limsup_{n\to\infty}\Bigl(\frac{R_n}{\log n}\Bigr)^{\!+}\ \le\ \sum_{i:\,\Delta_i>0}\frac{(\Delta_i)^{+}}{\bigl(d(\mu_i,\mu^{*})\bigr)^{+}}\qquad\text{in }[0,\infty],n→∞limsup​(lognRn​​)+ ≤ i:Δi​>0∑​(d(μi​,μ∗))+(Δi​)+​in [0,∞],

where the division on the right is the extended one: x/0=∞x/0=\inftyx/0=∞ for x≠0x\neq0x=0, x/∞=0x/\infty=0x/∞=0, and 0/0=00/0=00/0=0.

Hypotheses.

  • Each μi0∈[0,1]\mu^{0}_i\in[0,1]μi0​∈[0,1], and ν\nuν equals the Bernoulli bandit of (μi0)(\mu^{0}_i)(μi0​).
  • π\piπ satisfies the index-policy property above.
  • In part (1) only: for every arm iii with Δi>0\Delta_i>0Δi​>0, ε1,i>0\varepsilon_{1,i}>0ε1,i​>0, ε2,i>0\varepsilon_{2,i}>0ε2,i​>0, and ε1,i+ε2,i<Δi\varepsilon_{1,i}+\varepsilon_{2,i}<\Delta_iε1,i​+ε2,i​<Δi​ (strict). At arms with Δi≤0\Delta_i\le 0Δi​≤0 both families are unconstrained.

Edge cases.

  • In (1) the denominator d(μi+ε1,i,μ∗−ε2,i)d(\mu_i+\varepsilon_{1,i},\mu^{*}-\varepsilon_{2,i})d(μi​+ε1,i​,μ∗−ε2,i​) is a real number; if it equals 000, the real convention makes that fraction 000 and the term degenerates to Δi(12ε1,i2+2ε2,i2)\Delta_i\bigl(\tfrac{1}{2\varepsilon_{1,i}^2}+\tfrac{2}{\varepsilon_{2,i}^2}\bigr)Δi​(2ε1,i2​1​+ε2,i2​2​).
  • In (2), for an arm with Δi>0\Delta_i>0Δi​>0 but d(μi,μ∗)≤0d(\mu_i,\mu^{*})\le 0d(μi​,μ∗)≤0, the truncated denominator is 000 and the term is ∞\infty∞, so the right side is ∞\infty∞ and the inequality is trivially satisfied.
  • For n∈{0,1}n\in\{0,1\}n∈{0,1}: f(n)=1f(n)=1f(n)=1 so log⁡f(n)=0\log f(n)=0logf(n)=0 in (1); in (2), log⁡n=0\log n=0logn=0 so those terms are the truncation of Rn/0=0R_n/0=0Rn​/0=0.
  • Negative values of Rn/log⁡nR_n/\log nRn​/logn truncate to 000 before the limsup.
  • For k=0k=0k=0 the policy property is unsatisfiable, so both parts hold vacuously; RnR_nRn​ carries the usual conventions (supremum μ∗\mu^{*}μ∗, defaulting integral).
Human review
  • Endorsed by Community (Bot) · Jul 26, 2026

  • Endorsed by Shuze Chen · Jul 26, 2026

    Confirmed by the mission captain (proposal self-audit).

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