Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

KL-UCB feasibility failure counts

Definition
klucbFeasibilityFailureCount

by Harry_Xu · Jul 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

banditskl-ucbprobability

Fix a Bernoulli bandit, an optimal arm aaa, a candidate suboptimal arm iii, and a tolerance ε>0\varepsilon>0ε>0. For every decision round rrr, let HrH_rHr​ be the history available before the arm at round rrr is selected, let Nj(r)N_j(r)Nj​(r) and μ^j(r)\widehat\mu_j(r)μ​j​(r) denote the pull count and empirical mean of arm jjj in HrH_rHr​, and put q=μ⋆−εq=\mu^\star-\varepsilonq=μ⋆−ε.

The definition returns two selected-round counts. The first counts rounds on which arm iii is selected and either initialization is incomplete or the optimal arm fails the one-sided KL feasibility test,

log⁡f(r+1)Na(r)<d‾ ⁣(μ^a(r),q).\frac{\log f(r+1)}{N_a(r)} < \overline d\!\left(\widehat\mu_a(r),q\right).Na​(r)logf(r+1)​<d(μ​a​(r),q).

The second counts initialized rounds on which arm iii is selected and that arm passes the corresponding threshold test,

d‾ ⁣(μ^i(r),q)≤log⁡f(r+1)Ni(r).\overline d\!\left(\widehat\mu_i(r),q\right) \le \frac{\log f(r+1)}{N_i(r)}.d(μ​i​(r),q)≤Ni​(r)logf(r+1)​.

Here d‾(p,q)=d(p,q)\overline d(p,q)=d(p,q)d(p,q)=d(p,q) when p≤qp\le qp≤q, and is zero otherwise. These are the two events used to charge selections of a suboptimal arm in the proof of the finite-time KL-UCB bound.

Formalization Note: A finite bandit history stores the selected arm and observed reward at each round. The prefix HrH_rHr​ excludes the round-rrr observation, matching the information available to the policy when it selects that round's arm. The two real-valued components are finite sums of indicator functions.

Definition code
import Definitions.Def_klucbTruncatedRelativeEntropy
import Definitions.Def_banditHistoryPrefix

/-!
Lattimore--Szepesvári, *Bandit Algorithms* (CUP 2020), proof of
Theorem 10.6, printed p. 139.

This version records the explicit one-sided KL feasibility tests appearing
in the book, rather than comparisons with the supremum-valued index.
-/

namespace BanditAlgorithm

/-- The two measurable selected-round counts in the proof of Theorem 10.6.
The first records incomplete initialization or failure of the optimal-arm
threshold test; the second records success of the selected arm's threshold
test after initialization. -/
noncomputable def klucbFeasibilityFailureCount {k n : ℕ}
    (ν : StochasticBandit k) (a i : Fin k) (ε : ℝ)
    (h : BanditHistory k n) : ℝ × ℝ :=
  let initialized := fun r : Fin n ↦
    ∀ j, armPullCount j (banditHistoryPrefixAt h r) ≠ 0
  let threshold := banditOptimalMean ν - ε
  let budget := fun (j : Fin k) (r : Fin n) ↦
    Real.log (klucbExploration (r.val + 1)) /
      armPullCount j (banditHistoryPrefixAt h r)
  let lowSelected := ∑ r : Fin n,
    if (h r).1 = i ∧
        (¬ initialized r ∨
          budget a r <
            klucbTruncatedRelativeEntropy
              (armEmpiricalMean a (banditHistoryPrefixAt h r))
              threshold) then (1 : ℝ) else 0
  let highSelected := ∑ r : Fin n,
    if initialized r ∧ (h r).1 = i ∧
        klucbTruncatedRelativeEntropy
            (armEmpiricalMean i (banditHistoryPrefixAt h r))
            threshold ≤
          budget i r then (1 : ℝ) else 0
  (lowSelected, highSelected)

end BanditAlgorithm
Source
Lattimore and Szepesvári, Bandit Algorithms (2020), Theorem 10.6 proof and Lemmas 10.7–10.8, printed pp. 139–140 (PDF pp. 128–129).

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