Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 2.2 — Risk(T, ψ) ≥ ½ Σ_k E[‖Z‖ Σ_t (U_t′S^k_T)² + (T/‖Z‖)((Z − Ẑ_T)′S^k_T)²]

Proved
LinParamBandits.LowerBound.risk_decomposition

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

bayes-risklinear-banditlower-boundp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Work in the model of Section 2: arms on the unit sphere of Rr\mathbb R^rRr (r≥2r \ge 2r≥2), prior Z∼N(0,Ir/r)Z \sim N(0, I_r/r)Z∼N(0,Ir​/r), standard normal noise, and a fixed policy ψ\psiψ with arms U1,U2,…U_1, U_2, \dotsU1​,U2​,…. Let Z^T=E[Z∣HT]\widehat Z_T = \mathbb E[Z \mid H_T]ZT​=E[Z∣HT​], and let ST1,…,STr−1S^1_T, \dots, S^{r-1}_TST1​,…,STr−1​ be orthonormal vectors, orthogonal to Z^T\widehat Z_TZT​, each a measurable function of the history HTH_THT​.

Lemma 2.2 (Risk Decomposition). For any T≥1T \ge 1T≥1,

Risk(T,ψ)  ≥  12∑k=1r−1E[∥Z∥∑t=1T(Ut′STk)2+T∥Z∥{(Z−Z^T)′STk}2].\mathrm{Risk}(T, \psi) \;\ge\; \frac12 \sum_{k=1}^{r-1} \mathbb E\left[\|Z\| \sum_{t=1}^T \big(U_t' S^k_T\big)^2 + \frac{T}{\|Z\|}\Big\{\big(Z - \widehat Z_T\big)' S^k_T\Big\}^2\right].Risk(T,ψ)≥21​k=1∑r−1​E[∥Z∥t=1∑T​(Ut′​STk​)2+∥Z∥T​{(Z−ZT​)′STk​}2].

The first term inside the expectation measures how much the policy explored in the direction STkS^k_TSTk​, the second the squared estimation error in that direction; the lemma bounds the risk below by both.

Formalization Note The expectations on the right are lower Lebesgue integrals of nonnegative quantities, valued in [0,∞][0,\infty][0,∞]. On the event Z=0Z = 0Z=0, which has prior probability zero, Lean's convention T/0=0T/0 = 0T/0=0 applies. Orthogonality to Z^T\widehat Z_TZT​ is required almost surely, since Z^T\widehat Z_TZT​ is defined up to null sets; orthonormality is required for every history.

Preamble
import Mathlib
import Definitions.Def_LinParamBandits_LowerBound_Model

open MeasureTheory ProbabilityTheory
Formal statement
namespace LinParamBandits.LowerBound

/-- Lemma 2.2 (Risk Decomposition), Rusmevichientong, Tsitsiklis, arXiv:0812.3465v2, p. 9.
Standing assumptions of Sec. 2 (p. 9): arms on the unit sphere, prior `N(0, I_r/r)`; the vectors
`S k` (the paper's `S^1_T, …, S^{r-1}_T`) are orthonormal, orthogonal to `Ẑ_T`, and functions of
the history `H_T`. At `Z = 0` (prior probability zero) Lean's `T / 0 = 0`. -/
theorem risk_decomposition (r : ℕ) (hr : 2 ≤ r) (ψ : SpherePolicy r) (T : ℕ) (hT : 1 ≤ T)
    (S : Fin (r - 1) → History r T → Vec r)
    (hS_meas : ∀ k, Measurable (S k))
    (hS_orth : ∀ h, Orthonormal ℝ (fun k => S k h))
    (hS_perp : ∀ᵐ ω ∂(P r), ∀ k, inner ℝ (S k (hist ψ ω.1 ω.2 T)) (zhat ψ T ω) = 0) :
    2⁻¹ * ∑ k, ∫⁻ ω, ENNReal.ofReal
        (‖ω.1‖ * ∑ t ∈ Finset.range T, (inner ℝ (arm ψ ω.1 ω.2 t) (S k (hist ψ ω.1 ω.2 T))) ^ 2
          + (T : ℝ) / ‖ω.1‖ * (inner ℝ (ω.1 - zhat ψ T ω) (S k (hist ψ ω.1 ω.2 T))) ^ 2) ∂(P r)
      ≤ risk ψ T := by sorry

end LinParamBandits.LowerBound
Source
Rusmevichientong, Tsitsiklis, Linearly Parameterized Bandits, arXiv:0812.3465v2, Lemma 2.2, p. 9; standing assumptions of Sec. 2, p. 9
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