Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 4.2 — E[min{log T/Δ^u(Z), TΔ^u(Z)}] ≤ (M₀+1) log T + M₀ log² T

Proved
LinParamBandits.UEFinite.gap_min_expectation_bound

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

bayes-riskdensityp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let r≥2r \ge 2r≥2, let Ur⊂Rr\mathcal U_r \subset \mathbb R^rUr​⊂Rr be a finite nonempty set of arms, u∈Uru \in \mathcal U_ru∈Ur​, and Δu(z)=max⁡v∈Urv′z−u′z\Delta^u(z) = \max_{v \in \mathcal U_r} v'z - u'zΔu(z)=maxv∈Ur​​v′z−u′z. Let ZZZ have a probability law μ\muμ on Rr\mathbb R^rRr such that the law of Δu(Z)\Delta^u(Z)Δu(Z) consists of a point mass at 000 and a density bounded above by M0>0M_0 > 0M0​>0 on R+\mathbb R_+R+​. Then for every T≥r+1T \ge r + 1T≥r+1 the random variable min⁡{log⁡T/Δu(Z),TΔu(Z)}\min\{\log T/\Delta^u(Z), T\Delta^u(Z)\}min{logT/Δu(Z),TΔu(Z)} is integrable and

E[min⁡{log⁡TΔu(Z),TΔu(Z)}]≤(M0+1)log⁡T+M0log⁡2T.\mathbb E\Big[\min\Big\{\frac{\log T}{\Delta^u(Z)}, T\Delta^u(Z)\Big\}\Big] \le (M_0 + 1)\log T + M_0\log^2 T.E[min{Δu(Z)logT​,TΔu(Z)}]≤(M0​+1)logT+M0​log2T.

Integrated against the prior, the per-arm term of the regret bound of Theorem 4.2 grows like log⁡2T\log^2 Tlog2T; this is what turns the log⁡T\log TlogT regret bound into the ∣Ur∣2log⁡2T|\mathcal U_r|^2\log^2 T∣Ur​∣2log2T Bayes risk bound.

Formalization Note On the event Δu(Z)=0\Delta^u(Z) = 0Δu(Z)=0 the minimum is read as 000 (the paper's min⁡{log⁡T/0,0}\min\{\log T/0, 0\}min{logT/0,0}); Lean's convention x/0=0x/0 = 0x/0=0 gives the same value. The density condition is written as: the law of Δu(Z)\Delta^u(Z)Δu(Z) restricted to (0,∞)(0, \infty)(0,∞) is at most M0M_0M0​ times Lebesgue measure. Assumption 1 and the policy play no role in this statement and are not assumed.

Preamble
import Mathlib
import Definitions.Def_LinParamBandits_UEFinite_Model
import Definitions.Def_LinParamBandits_UEFinite_UEPolicy
Formal statement
namespace LinParamBandits.UEFinite

open MeasureTheory ProbabilityTheory

theorem gap_min_expectation_bound
    (r : ℕ) (hr : 2 ≤ r) (𝒰 : Set (LinParamBandits.LowerBound.Vec r)) (h𝒰fin : 𝒰.Finite) (h𝒰ne : 𝒰.Nonempty)
    (u : LinParamBandits.LowerBound.Vec r) (hu : u ∈ 𝒰) (μ : Measure (LinParamBandits.LowerBound.Vec r)) (hμ : IsProbabilityMeasure μ)
    (M₀ : ℝ) (hM₀ : 0 < M₀) (hdens : GapDensityLe 𝒰 μ M₀ u) (T : ℕ) (hT : r + 1 ≤ T) :
    Integrable (fun z => min (Real.log T / gap 𝒰 u z) (T * gap 𝒰 u z)) μ ∧
    ∫ z, min (Real.log T / gap 𝒰 u z) (T * gap 𝒰 u z) ∂μ ≤
      (M₀ + 1) * Real.log T + M₀ * Real.log T ^ 2 := by sorry

end LinParamBandits.UEFinite
Source
Rusmevichientong, Tsitsiklis, Linearly Parameterized Bandits, arXiv:0812.3465v2, proof of Theorem 4.2, pp. 22–23, display after 'From the regret bound, it suffices to show that for any u ∈ U_r'
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

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