Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Lemma 2.5, p. 12 — given HTH_THT​, (Z−Z^T)′STk∼N(0,Θ)(Z-\widehat Z_T)'S^k_T \sim N(0,\Theta)(Z−ZT​)′STk​∼N(0,Θ), so Pr⁡{Γ≥ηΘ∣HT}=2(1−Φ(η))\Pr\{\Gamma\ge\eta\Theta\mid H_T\}=2(1-\Phi(\sqrt\eta))Pr{Γ≥ηΘ∣HT​}=2(1−Φ(η​))

Open
LinParamBandits.LowerBound.posterior_direction_tail

by tianyipeng · Nov 5, 2026 · Mathlib 0df444a (Lean v4.33.1)

bayes-riskgaussian-posteriorlinear-banditlower-bound

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), i.i.d. standard normal noise, a fixed deterministic policy ψ\psiψ), with Z^T=E[Z∣HT]\widehat Z_T=\mathbb E[Z\mid H_T]ZT​=E[Z∣HT​] and vectors ST1,…,STr−1S^1_T,\dots,S^{r-1}_TST1​,…,STr−1​ as in Lemma 2.2 (orthonormal, orthogonal to Z^T\widehat Z_TZT​, measurable functions of HTH_THT​). Fix kkk and put

Γ={(Z−Z^T)′STk}2,Θ=E[Γ∣HT].\Gamma=\Big\{\big(Z-\widehat Z_T\big)'S^k_T\Big\}^2,\qquad \Theta=\mathbb E\big[\Gamma\mid H_T\big].Γ={(Z−ZT​)′STk​}2,Θ=E[Γ∣HT​].

Claim (proof of Lemma 2.5, p. 12). Conditioned on HTH_THT​, (Z−Z^T)′STk(Z-\widehat Z_T)'S^k_T(Z−ZT​)′STk​ is normally distributed with mean zero and variance Θ\ThetaΘ. Consequently, for every η≥0\eta\ge 0η≥0, with probability one,

Pr⁡{Γ≥η Θ ∣ HT}  =  2(1−Φ(η)),\Pr\big\{\Gamma\ge\eta\,\Theta\ \big|\ H_T\big\}\;=\;2\big(1-\Phi(\sqrt\eta)\big),Pr{Γ≥ηΘ ​ HT​}=2(1−Φ(η​)),

where Φ\PhiΦ is the standard normal distribution function.

This is the step of the paper's proof of Lemma 2.5 that uses the Gaussian posterior: given the history, ZZZ is Gaussian (the prior is Gaussian and the observations are linear in ZZZ with Gaussian noise, the design being a deterministic function of past observations), so its projection on the history-measurable unit vector STkS^k_TSTk​, centred at its conditional mean, is a centred normal with variance Θ\ThetaΘ.

Formalization Note The conditional probability is Mathlib's conditional expectation of the indicator of {ηΘ≤Γ}\{\eta\Theta\le\Gamma\}{ηΘ≤Γ} with respect to the σ-algebra generated by HTH_THT​ under the joint law of (Z,η)(Z,\eta)(Z,η); Θ\ThetaΘ is likewise Mathlib's conditional expectation. Φ(x)\Phi(x)Φ(x) is cdf (gaussianReal 0 1) x. The identity holds almost surely, which does not depend on the versions chosen. The standing assumptions of Lemma 2.2 are kept as hypotheses for uniformity with Lemmas 2.2, 2.3 and 2.5 (orthonormality guarantees STk≠0S^k_T\neq 0STk​=0, which is needed; η≥0\eta\ge0η≥0 is needed for η\sqrt\etaη​ to be meaningful).

Preamble
import Mathlib
import Definitions.Def_LinParamBandits_LowerBound_Model

open MeasureTheory ProbabilityTheory
Formal statement
namespace LinParamBandits.LowerBound

/-- Proof of Lemma 2.5, Rusmevichientong, Tsitsiklis, arXiv:0812.3465v2, p. 12: conditioned on
`H_T`, `(Z − Ẑ_T)′ S^k_T` is normal with mean zero and variance `Θ = E[Γ | H_T]`, where
`Γ = ((Z − Ẑ_T)′ S^k_T)²`; hence `Pr{Γ ≥ η Θ | H_T} = 2 (1 − Φ(√η))` almost surely.
Standing assumptions of Sec. 2 (p. 9) as in Lemma 2.2. -/
theorem posterior_direction_tail (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)
    (k : Fin (r - 1)) (η : ℝ) (hη : 0 ≤ η) :
    ∀ᵐ ω ∂(P r),
      ((P r)[{ω' : Ω r | η * ((P r)[fun ω'' : Ω r =>
              (inner ℝ (ω''.1 - zhat ψ T ω'') (S k (hist ψ ω''.1 ω''.2 T))) ^ 2 | histSigma ψ T]) ω'
            ≤ (inner ℝ (ω'.1 - zhat ψ T ω') (S k (hist ψ ω'.1 ω'.2 T))) ^ 2}.indicator
          (fun _ => (1 : ℝ)) | histSigma ψ T]) ω
        = 2 * (1 - cdf (gaussianReal 0 1) (Real.sqrt η)) := by sorry

end LinParamBandits.LowerBound
Source
Rusmevichientong, Tsitsiklis, Linearly Parameterized Bandits, arXiv:0812.3465v2, proof of Lemma 2.5, p. 12 (display defining Pr{Γ ≥ ηΘ | H_T} = 2(1 − Φ(√η)))

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