Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Corollary B.1, p. 26 — Bernstein for bounded martingale differences: |Mₙ| ≤ 2√(Vₙ ln(n/δ)) + 3K ln(n/δ)

Proved
OptimisticPSRL.Concentration.corollaryB1_bernstein

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

bernstein-inequalityconcentrationmartingalep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1probability

Let (Ω,F,P)(\Omega,\mathcal F,\mathbb P)(Ω,F,P) be a probability space with a filtration (Fi)i≥0(\mathcal F_i)_{i\ge0}(Fi​)i≥0​, and let Z1,…,ZnZ_1,\dots,Z_nZ1​,…,Zn​ be a bounded martingale difference sequence: ZiZ_iZi​ is Fi\mathcal F_iFi​-measurable, ∣Zi∣≤K|Z_i|\le K∣Zi​∣≤K and E[Zi∣Fi−1]=0\mathbb E[Z_i\mid\mathcal F_{i-1}]=0E[Zi​∣Fi−1​]=0. Put

Mn=∑i=1nZi,Vn=∑i=1nE[Zi2∣Fi−1].M_n=\sum_{i=1}^nZ_i,\qquad V_n=\sum_{i=1}^n\mathbb E\big[Z_i^2\mid\mathcal F_{i-1}\big].Mn​=i=1∑n​Zi​,Vn​=i=1∑n​E[Zi2​∣Fi−1​].

If n≥96n\ge96n≥96 and δ∈(0,1)\delta\in(0,1)δ∈(0,1), then with probability greater than 1−δ1-\delta1−δ,

∣Mn∣≤2Vnln⁡nδ+3Kln⁡nδ.|M_n|\le2\sqrt{V_n\ln\frac n\delta}+3K\ln\frac n\delta .∣Mn​∣≤2Vn​lnδn​​+3Klnδn​.

This is a Bernstein inequality with the random predictable variance VnV_nVn​ in place of a deterministic variance bound, at the price of ln⁡(n/δ)\ln(n/\delta)ln(n/δ) instead of ln⁡(1/δ)\ln(1/\delta)ln(1/δ). Agrawal and Jia derive it from a result of Seldin et al. (2012) and use it to prove Proposition 5.2.

Formalization Note Indices are shifted: ZiZ_iZi​ is Z i for i=1,…,ni=1,\dots,ni=1,…,n, measurable for ℱ i, with conditional expectation taken given ℱ (i-1). The bound ∣Zi∣≤K|Z_i|\le K∣Zi​∣≤K is required almost surely. "With probability greater than 1−δ1-\delta1−δ" is the strict inequality 1−δ<P(⋅)1-\delta<\mathbb P(\cdot)1−δ<P(⋅), as printed.

Preamble
import Mathlib
Formal statement
namespace OptimisticPSRL.Concentration

open MeasureTheory

/-- **Corollary B.1** (Agrawal–Jia, arXiv:1705.07041v3, p. 26). Let `Z_1, …, Z_n` be a
martingale difference sequence for the filtration `ℱ` (`Z_i` is `ℱ_i`-measurable and
`E[Z_i | ℱ_{i−1}] = 0`) with `|Z_i| ≤ K`, `M_n = ∑_{i=1}^n Z_i` and
`V_n = ∑_{i=1}^n E[Z_i² | ℱ_{i−1}]`. For `n ≥ 96` and `δ ∈ (0, 1)`, with probability greater
than `1 − δ`, `|M_n| ≤ 2 √(V_n ln(n/δ)) + 3K ln(n/δ)`. -/
theorem corollaryB1_bernstein {Ω : Type*} {m0 : MeasurableSpace Ω} (μ : Measure Ω)
    [IsProbabilityMeasure μ] (ℱ : Filtration ℕ m0) (Z : ℕ → Ω → ℝ) (K : ℝ) (n : ℕ) (δ : ℝ)
    (hmeas : ∀ i < n, StronglyMeasurable[ℱ (i + 1)] (Z (i + 1)))
    (hbdd : ∀ i < n, ∀ᵐ ω ∂μ, |Z (i + 1) ω| ≤ K)
    (hmds : ∀ i < n, μ[Z (i + 1) | ℱ i] =ᵐ[μ] 0)
    (hn : 96 ≤ n) (hδ0 : 0 < δ) (hδ1 : δ < 1) :
    ENNReal.ofReal (1 - δ) <
      μ {ω | |∑ i ∈ Finset.range n, Z (i + 1) ω| ≤
        2 * Real.sqrt ((∑ i ∈ Finset.range n, (μ[fun ω' => Z (i + 1) ω' ^ 2 | ℱ i]) ω) *
            Real.log (n / δ)) +
          3 * K * Real.log (n / δ)} := by sorry

end OptimisticPSRL.Concentration
Source
Agrawal & Jia, Posterior sampling for reinforcement learning: worst-case regret bounds, arXiv:1705.07041v3, p. 26, Appendix B, Corollary B.1 (setting from Fact 3)
Human review
  • Endorsed by Shuze Chen · Oct 15, 2026

    Confirmed by the moderator at approval.

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