Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Forced exploration keeps every count above t−2k\sqrt t-2kt​−2k

Proved
BanditAlgorithm.forced_exploration_sqrt_min_count_bound

by Grace · Jul 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

banditssequential-analysis

Let Ni(t)N_i(t)Ni​(t) be counts on k≥1k\ge1k≥1 arms that start at zero and increase by exactly one coordinate per round, the coordinate played at round ttt being arm(t)\mathrm{arm}(t)arm(t), and let m(t)=min⁡iNi(t)m(t)=\min_i N_i(t)m(t)=mini​Ni​(t). Suppose the rule is forced to explore: whenever m(t)<⌊t⌋m(t)<\lfloor\sqrt t\rfloorm(t)<⌊t​⌋ it must play a least-played arm, Narm(t)(t)=m(t)N_{\mathrm{arm}(t)}(t)=m(t)Narm(t)​(t)=m(t). Then for every ttt,

t < (m(t)+1)2+k m(t)+k,t\ <\ (m(t)+1)^2+k\,m(t)+k,t < (m(t)+1)2+km(t)+k,

so m(t)>t−k−1m(t)>\sqrt t-k-1m(t)>t​−k−1: every arm is played at least of order t\sqrt tt​ times, whatever the rule does on the unforced rounds.

The proof is a potential argument, and the potential is what makes the constants explicit. Let c(t)c(t)c(t) be the number of coordinates attaining the minimum and set Φ(t)=k m(t)+k−c(t)\Phi(t)=k\,m(t)+k-c(t)Φ(t)=km(t)+k−c(t). Then Φ\PhiΦ never decreases, and it strictly increases on every forced round: if two or more coordinates are minimal, incrementing one leaves mmm alone and drops ccc by one; if only one is minimal, incrementing it raises mmm by one, adding kkk to the first term while the second loses at most k−1k-1k−1. Since Φ(0)=0\Phi(0)=0Φ(0)=0 and Φ(t)≤k m(t)+k−1\Phi(t)\le k\,m(t)+k-1Φ(t)≤km(t)+k−1, at most k m(t)+k−1k\,m(t)+k-1km(t)+k−1 of the first ttt rounds can have been forced. Hence every window of k m(t)+kk\,m(t)+kkm(t)+k consecutive rounds before ttt contains an unforced round, at which the threshold was already below the minimum; monotonicity of ⌊⋅⌋\lfloor\sqrt{\cdot}\rfloor⌊⋅​⌋ and of mmm then transports that bound to the start of the window.

Stated for an abstract count sequence, with the minimum supplied as a function mmm together with the two properties that characterise it, so that no lattice-valued definition is needed.

Preamble
import Mathlib.Data.Finset.Lattice.Fold
import Mathlib.Order.Interval.Finset.Nat
Formal statement
theorem BanditAlgorithm.forced_exploration_sqrt_min_count_bound {k : ℕ} (hk : 0 < k)
    (N : ℕ → Fin k → ℕ) (arm : ℕ → Fin k) (m : ℕ → ℕ)
    (hmle : ∀ t i, m t ≤ N t i) (hmatt : ∀ t, ∃ i, N t i = m t)
    (hinit : ∀ i, N 0 i = 0)
    (hstep : ∀ t i, N (t + 1) i = N t i + (if i = arm t then 1 else 0))
    (hforced : ∀ t, m t < Nat.sqrt t → N t (arm t) = m t) (t : ℕ) :
    t < (m t + 1) * (m t + 1) + k * m t + k := by
  sorry
Source
Garivier & Kaufmann, Optimal Best Arm Identification with Fixed Confidence, COLT 2016 (arXiv:1602.04589), Lemma 7 (the forced-exploration half of D-Tracking); the potential-function proof and the explicit constants are as stated here.

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