Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 4.2 — Regret(z,T,UE) = Σ_u Δ^u(z) E[N^u(z,T) | Z = z]

Proved
LinParamBandits.UEFinite.regret_eq_sum_gap_pulls

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

linear-banditp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1regret

Consider the linearly parameterized bandit of Rusmevichientong and Tsitsiklis under Assumption 1, with a finite nonempty set of arms Ur⊂Rr\mathcal U_r \subset \mathbb R^rUr​⊂Rr (r≥2r \ge 2r≥2), run by the Uncertainty Ellipsoid policy. For every horizon TTT and every z∈Rrz \in \mathbb R^rz∈Rr,

Regret(z,T,UE)=∑u∈UrΔu(z) E[Nu(z,T) ∣ Z=z],\mathrm{Regret}(z, T, \mathrm{UE}) = \sum_{u \in \mathcal U_r}\Delta^u(z)\,\mathbb E\big[N^u(z, T) \,\big|\, Z = z\big],Regret(z,T,UE)=u∈Ur​∑​Δu(z)E[Nu(z,T)​Z=z],

where Δ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 is the gap of arm uuu and Nu(z,T)N^u(z, T)Nu(z,T) the number of periods among the first TTT in which arm uuu is played.

This regret decomposition turns the regret, a sum over periods, into a sum over arms, so that a bound on the number of pulls of each suboptimal arm becomes a regret bound.

Formalization Note The regret is defined as Tmax⁡vv′z−E[∑t≤TUt′z∣Z=z]T\max_v v'z - \mathbb E[\sum_{t\le T} U_t'z \mid Z = z]Tmaxv​v′z−E[∑t≤T​Ut′​z∣Z=z]. The identity holds for every horizon; the paper writes it inside the proof of Theorem 4.2, where T≥r+1T \ge r + 1T≥r+1.

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

open MeasureTheory ProbabilityTheory

theorem regret_eq_sum_gap_pulls
    (σ₀ ū lam₀ : ℝ) (hσ₀ : 0 < σ₀) (hū : 0 < ū) (hlam₀ : 0 < lam₀)
    (r : ℕ) (hr : 2 ≤ r) (𝒰 : Set (LinParamBandits.LowerBound.Vec r)) (h𝒰fin : 𝒰.Finite) (h𝒰ne : 𝒰.Nonempty)
    (ν : Kernel (LinParamBandits.LowerBound.Vec r) ℝ) (hν : IsMarkovKernel ν) (hnoise : NoiseAssumption 𝒰 ν σ₀)
    (b : Fin r → LinParamBandits.LowerBound.Vec r) (harms : ArmAssumption 𝒰 b ū lam₀)
    (ψ : LinParamBandits.UEGeneral.Policy r) (hψ : IsUE 𝒰 b σ₀ ū lam₀ ψ)
    (T : ℕ) (z : LinParamBandits.LowerBound.Vec r) :
    Regret 𝒰 ν ψ z T =
      ∑ u ∈ h𝒰fin.toFinset, gap 𝒰 u z * ∫ h, (pullCount u h : ℝ) ∂(LinParamBandits.UEGeneral.histMeasure ν z ψ T) := by sorry

end LinParamBandits.UEFinite
Source
Rusmevichientong, Tsitsiklis, Linearly Parameterized Bandits, arXiv:0812.3465v2, proof of Theorem 4.2, p. 22, first line of the display after 'because'
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