Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Inequality (6), p. 6 — the fundamental inequality: Σₐ 𝔼_ν[N_{ψ,a}(T)] KL(νₐ, ν′ₐ) ≥ kl(𝔼_ν[Z], 𝔼_ν′[Z])

Proved
ExploreFirst.FundIneq.fundamental_inequality

by mikedeng1 · Oct 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

kullback-leiblermulti-armed-banditsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1regret-lower-bound

Consider stochastic bandit problems with KKK arms: a bandit problem ν‾=(νa)a=1,…,K\underline\nu=(\nu_a)_{a=1,\dots,K}ν​=(νa​)a=1,…,K​ assigns a probability distribution νa\nu_aνa​ on R\mathbb RR with a finite expectation to each arm. A strategy ψ\psiψ chooses at each round t+1t+1t+1 an arm At+1A_{t+1}At+1​ as a measurable function of It=(U0,Y1,U1,…,Yt,Ut)I_t=(U_0,Y_1,U_1,\dots,Y_t,U_t)It​=(U0​,Y1​,U1​,…,Yt​,Ut​), where the UtU_tUt​ are independent uniforms on [0,1][0,1][0,1]. It receives a reward Yt+1Y_{t+1}Yt+1​ drawn from νAt+1\nu_{A_{t+1}}νAt+1​​ and a fresh independent uniform Ut+1U_{t+1}Ut+1​. For a horizon TTT, write Pν‾\mathbb P_{\underline\nu}Pν​​ and Eν‾\mathbb E_{\underline\nu}Eν​​ for the law of ITI_TIT​ and its expectation when ψ\psiψ interacts with ν‾\underline\nuν​, and Nψ,a(T)N_{\psi,a}(T)Nψ,a​(T) for the number of rounds t≤Tt\le Tt≤T with At=aA_t=aAt​=a. Let KL\mathrm{KL}KL denote the Kullback–Leibler divergence and kl(p,q)\mathrm{kl}(p,q)kl(p,q) the Kullback–Leibler divergence between Bernoulli distributions of parameters p,q∈[0,1]p,q\in[0,1]p,q∈[0,1], given for q∈(0,1)q\in(0,1)q∈(0,1) by

kl(p,q)=pln⁡pq+(1−p)ln⁡1−p1−q.\mathrm{kl}(p,q)=p\ln\frac pq+(1-p)\ln\frac{1-p}{1-q}.kl(p,q)=plnqp​+(1−p)ln1−q1−p​.

Fundamental inequality. For every strategy ψ\psiψ, every pair of bandit problems ν‾\underline\nuν​ and ν‾′\underline\nu'ν​′, every horizon TTT, and every measurable function ZZZ of ITI_TIT​ with values in [0,1][0,1][0,1],

∑a=1KEν‾[Nψ,a(T)] KL(νa,νa′) ≥ kl(Eν‾[Z], Eν‾′[Z]).\sum_{a=1}^K\mathbb E_{\underline\nu}\big[N_{\psi,a}(T)\big]\,\mathrm{KL}(\nu_a,\nu'_a)\ \ge\ \mathrm{kl}\big(\mathbb E_{\underline\nu}[Z],\ \mathbb E_{\underline\nu'}[Z]\big).a=1∑K​Eν​​[Nψ,a​(T)]KL(νa​,νa′​) ≥ kl(Eν​​[Z], Eν​′​[Z]).

Both sides are in [0,+∞][0,+\infty][0,+∞], with the convention 0⋅(+∞)=00\cdot(+\infty)=00⋅(+∞)=0: an arm with infinite divergence and zero expected number of draws contributes nothing, and no finiteness or moment condition is imposed on the arm distributions.

The paper derives every one of its lower bounds from this single inequality, by choosing an alternative problem ν‾′\underline\nu'ν​′ and a statistic such as Z=Nψ,a(T)/TZ=N_{\psi,a}(T)/TZ=Nψ,a​(T)/T; this is how it re-derives the Lai–Robbins and Burnetas–Katehakis asymptotic bounds and obtains its non-asymptotic bounds for small horizons.

Formalization Note. The local FullStrategy is the paper's measurable strategy on ItI_tIt​; the local fullHistoryMeasure retains all auxiliary uniforms. The same strategy is run under both problems. Integrable id for every arm of both problems expresses §1.1's standing assumption that each arm has a finite expectation; the published StochasticBandit type alone requires only probability laws. Arms are indexed by {0,…,K−1}\{0,\dots,K-1\}{0,…,K−1}. The binary divergence is the [0,+∞][0,+\infty][0,+∞]-valued klBer, which equals +∞+\infty+∞ where the paper's convention does.

Preamble
import Mathlib
import Definitions.Def_ExploreFirst_FundIneq_FullHistory

open MeasureTheory ProbabilityTheory InformationTheory
open scoped ENNReal
Formal statement
namespace ExploreFirst.FundIneq

/-- Garivier, Ménard, Stoltz, arXiv:1602.07182v3, §2, p. 6, inequality (6). The information
`I_T` contains every auxiliary uniform and reward through round `T`. Each arm law has a finite
expectation, as required for a bandit problem in §1.1. The same strategy runs under both problems. -/
theorem fundamental_inequality {K : ℕ} (ν ν' : BanditAlgorithm.StochasticBandit K)
    (hν : ∀ a, Integrable id (ν.P a)) (hν' : ∀ a, Integrable id (ν'.P a))
    (ψ : FullStrategy K) (T : ℕ)
    (Z : FullHistory T → ℝ) (hZ : Measurable Z)
    (hZ01 : ∀ h, Z h ∈ Set.Icc (0 : ℝ) 1) :
    klBer (∫ h, Z h ∂(fullHistoryMeasure ν ψ T))
        (∫ h, Z h ∂(fullHistoryMeasure ν' ψ T))
      ≤ ∑ a, ENNReal.ofReal (fullExpPulls ν ψ T a) * klDiv (ν.P a) (ν'.P a) := by sorry

end ExploreFirst.FundIneq
Source
Garivier, Ménard, Stoltz, Explore First, Exploit Next, arXiv:1602.07182v3, p. 6, §2, inequality (6)
Human review
  • Endorsed by Shuze Chen · Oct 9, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 9, 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