Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Proposition 6.2, p. 100 — θᵢ = Δeᵢ: regret Δ(1 − πᵢ) and D²_H(Mᵢ(π), Rad(0)) ≤ ¾Δ²πᵢ², the regret and information properties with uᵢ(π) = πᵢ, vᵢ(π) = πᵢ²

Proved
StatComplexityDM.LinearLB.ball_family_hard

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

decision-estimation-coefficienthard-familylinear-banditsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1

Let Bd\mathbb{B}^dBd be the Euclidean unit ball of Rd\mathbb{R}^dRd, let θ↦πθ\theta \mapsto \pi_\thetaθ↦πθ​ be a maximizer selector for the linear mean reward fθ(π)=⟨θ,π⟩f^\theta(\pi) = \langle \theta, \pi\ranglefθ(π)=⟨θ,π⟩ over the ball, let Δ∈[0,1]\Delta \in [0, 1]Δ∈[0,1] and i∈{1,…,d}i \in \{1, \dots, d\}i∈{1,…,d}. Put θi=Δ⋅ei\theta_i = \Delta \cdot e_iθi​=Δ⋅ei​, Mi(π)=Rad(⟨θi,π⟩)M_i(\pi) = \mathrm{Rad}(\langle \theta_i, \pi\rangle)Mi​(π)=Rad(⟨θi​,π⟩), and let M‾(π)=Rad(0)\overline{M}(\pi) = \mathrm{Rad}(0)M(π)=Rad(0) be the model with parameter 000. Then for every π∈Bd\pi \in \mathbb{B}^dπ∈Bd:

  1. (regret property, ui(π)=πiu_i(\pi) = \pi_iui​(π)=πi​)
fMi(πMi)−fMi(π)=⟨θi,ei−π⟩=Δ (1−πi);f^{M_i}(\pi_{M_i}) - f^{M_i}(\pi) = \langle \theta_i, e_i - \pi\rangle = \Delta\,(1 - \pi_i);fMi​(πMi​​)−fMi​(π)=⟨θi​,ei​−π⟩=Δ(1−πi​);
  1. (information property, vi(π)=πi2v_i(\pi) = \pi_i^2vi​(π)=πi2​)
DH2(Mi(π),M‾(π))≤34Δ2πi2.D^2_{\mathrm{H}}\bigl(M_i(\pi), \overline{M}(\pi)\bigr) \le \tfrac34 \Delta^2 \pi_i^2 .DH2​(Mi​(π),M(π))≤43​Δ2πi2​.

Together with the sum bounds ∑iπi≤d/2\sum_i \pi_i \le d/2∑i​πi​≤d/2 and ∑iπi2≤1\sum_i \pi_i^2 \le 1∑i​πi2​≤1 (for d≥4d \ge 4d≥4), this makes {M1,…,Md}\{M_1, \dots, M_d\}{M1​,…,Md​} a (Δ,34Δ2,0)(\Delta, \tfrac34\Delta^2, 0)(Δ,43​Δ2,0)-family with respect to M‾\overline{M}M, the construction behind the lower bound d/(12γ)d/(12\gamma)d/(12γ) of Proposition 6.2.

Formalization Note A parameter θi\theta_iθi​ is passed as a point of the ball whose underlying vector equals Δei\Delta e_iΔei​. The first identity uses that the selector attains ⟨θi,πθi⟩=Δ\langle\theta_i,\pi_{\theta_i}\rangle = \Delta⟨θi​,πθi​​⟩=Δ, which follows from the maximizer hypothesis. Here uiu_iui​ takes negative values, so the family satisfies Definition 5.1 only without its range conditions (see the restated Lemma 5.1 of this mission).

Preamble
import Mathlib
import Definitions.Def_StatComplexityDM_LinearLB_Setting
Formal statement
namespace StatComplexityDM.LinearLB

/-- Proof of Proposition 6.2 (arXiv:2112.13487v3, p. 100): the models `M_i(π) = Rad(⟨θ_i, π⟩)`,
`θ_i = Δ·e_i`, satisfy the regret property with `u_i(π) = π_i` and the information property with
`v_i(π) = π_i²` and constant `¾Δ²`, with respect to `M̄ = Rad(0)`. -/
theorem ball_family_hard (d : ℕ) (piStar : Ball d → Ball d)
    (hpiStar : IsBallArgmax piStar) (Δ : ℝ) (hΔ0 : 0 ≤ Δ) (hΔ1 : Δ ≤ 1)
    (i : Fin d) (θ : Ball d)
    (hθ : (θ : EuclideanSpace ℝ (Fin d)) = Δ • EuclideanSpace.single i 1) :
    ∀ π : Ball d,
      gapLin piStar θ π = Δ * (1 - (π : EuclideanSpace ℝ (Fin d)) i) ∧
      hellLin θ (ballZero d) π ≤ 3 / 4 * Δ ^ 2 * ((π : EuclideanSpace ℝ (Fin d)) i) ^ 2 := by sorry

end StatComplexityDM.LinearLB
Source
arXiv:2112.13487v3, proof of Proposition 6.2, App. E.1.1, p. 100
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