Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Stopped change-of-measure inequality for best-arm identification

Proved
BanditAlgorithm.best_arm_identification_stopping_change_of_measure

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

banditsbest-arm-identificationinformation-theorylower-boundsstopping-times

Let (π,τ,ψ)(\pi,\tau,\psi)(π,τ,ψ) be a best-arm-identification strategy that is sound at confidence δ∈(0,1)\delta\in(0,1)δ∈(0,1) on an environment class E\mathcal EE. Fix ν∈E\nu\in\mathcal Eν∈E and an alternative ν′∈Ealt(ν)\nu'\in\mathcal E_{\mathrm{alt}}(\nu)ν′∈Ealt​(ν) whose optimal arms are disjoint from those of ν\nuν. Assume the expected stopping time under ν\nuν is finite. If Ti(τ)T_i(\tau)Ti​(τ) denotes the number of pulls of arm iii strictly before the stopping time, then

log⁡ ⁣14δ≤∑i=1kEν,π[Ti(τ)] D(νi∥νi′).\log\!\frac{1}{4\delta} \le \sum_{i=1}^k \mathbb E_{\nu,\pi}[T_i(\tau)]\, D(\nu_i\Vert\nu_i').log4δ1​≤i=1∑k​Eν,π​[Ti​(τ)]D(νi​∥νi′​).

The inequality is understood in [0,∞][0,\infty][0,∞], so it also covers singular arm laws. This is the stopped-experiment information constraint used in every fixed-confidence best-arm-identification lower bound.

Formalization Note The stopped pull count is represented directly as the infinite sum of the indicators 1{t<τ,At=i}\mathbf 1\{t<\tau, A_t=i\}1{t<τ,At​=i} on the canonical infinite trajectory.

Preamble
import Definitions.Def_BanditTrajectory

open MeasureTheory ProbabilityTheory InformationTheory ENNReal
Formal statement
theorem BanditAlgorithm.best_arm_identification_stopping_change_of_measure {k : ℕ}
    (𝓔 : Set (StochasticBandit k)) (δ : ℝ) (hδ : δ ∈ Set.Ioo (0 : ℝ) 1)
    (π : BanditPolicy k) (τ : (ℕ → Fin k × ℝ) → ℕ∞)
    (ψ : (ℕ → Fin k × ℝ) → Fin k)
    (hτ : IsBanditStoppingTime τ) (hψ : Measurable[hτ.measurableSpace] ψ)
    (hsound : IsSoundBAI δ π τ ψ 𝓔)
    (ν ν' : StochasticBandit k) (hν : ν ∈ 𝓔)
    (hν' : ν' ∈ baiAlternatives 𝓔 ν)
    (hfinite : ∫⁻ ω, (τ ω : ℝ≥0∞) ∂banditTrajMeasure ν π < ⊤) :
    ENNReal.ofReal (Real.log (1 / (4 * δ))) ≤
      ∑ i, (∫⁻ ω, ∑' t : ℕ,
          if (t : ℕ∞) < τ ω ∧ (ω t).1 = i then (1 : ℝ≥0∞) else 0
        ∂banditTrajMeasure ν π) * klDiv (ν.P i) (ν'.P i) := by
  sorry
Source
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), Theorem 33.5 proof, printed p. 407, Eqs. (33.5)–(33.6), using the stopping-time version of Lemma 15.1 requested in Exercise 15.7, printed p. 211.

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