Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Algebraic summation of the reference-block error terms

Proved
G26G.ref_block_alg

by Canzhe Zhao · Nov 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

bandit-algorithmslinear-banditsonline-learning

This is a purely deterministic inequality that collects the error terms of the reference block bound.

Let d,u,nC,m0∈Nd,u,n_C,m_0\in\mathbb Nd,u,nC​,m0​∈N and C,ς,c0,τm,L∈RC,\varsigma,c_0,\tau_m,L\in\mathbb RC,ς,c0​,τm​,L∈R with ς>0\varsigma>0ς>0, c0≥0c_0\ge0c0​≥0, 1≤nC≤u1\le n_C\le u1≤nC​≤u, 0≤C≤nC0\le C\le n_C0≤C≤nC​, u+1≤4(m0+1)u+1\le4(m_0+1)u+1≤4(m0​+1), (m0+1)7/8≤τm(m_0+1)^{7/8}\le\tau_m(m0​+1)7/8≤τm​, 4nC(u+1)≤τm4\sqrt{n_C(u+1)}\le\tau_m4nC​(u+1)​≤τm​, τ2u:=tauB(nC(u+1),2u)≤(u+1)/4\tau_{2u}:=\mathrm{tauB}(\sqrt{n_C(u+1)},2u)\le(u+1)/4τ2u​:=tauB(nC​(u+1)​,2u)≤(u+1)/4, L≥1L\ge1L≥1,

L512(d+1)≤(4+c0)512(d+1) (512(d+1))!⋅6 (u+1),L≤(12+c0)u+1nC+1.L^{512(d+1)}\le(4+c_0)^{512(d+1)}\,(512(d+1))!\cdot6\,(u+1),\qquad L\le(12+c_0)\frac{u+1}{n_C+1}.L512(d+1)≤(4+c0​)512(d+1)(512(d+1))!⋅6(u+1),L≤(12+c0​)nC​+1u+1​.

Let P=4kP=4kP=4k, k=1024(d+1)k=1024(d+1)k=1024(d+1). Then the sum of the five error terms produced by the near-reference bound, the preparation bound (with ρ=τm(u+1)/(nC+1)\rho=\tau_m(u+1)/(n_C+1)ρ=τm​(u+1)/(nC​+1)), and the far-reference bound (with ε=ς/L1/8\varepsilon=\varsigma/L^{1/8}ε=ς/L1/8, ρ=2(u+1)2/(4τ2u)\rho=2(u+1)^2/(4\tau_{2u})ρ=2(u+1)2/(4τ2u​)) is at most

D(d,ς,c0)((nC+1u+1)4+1(u+1)4),D(d,\varsigma,c_0)\Big(\Big(\frac{n_C+1}{u+1}\Big)^4+\frac1{(u+1)^4}\Big),D(d,ς,c0​)((u+1nC​+1​)4+(u+1)41​),

where DDD is the explicit constant Dexpr d ς c₀.

This is the bookkeeping that turns the probabilistic decomposition of Lemma G.29 into its polynomial form (G.622).

Formalization Note The exact left-hand side is displayed in the formal statement; tauB z s =(s+1)7/8+4z=(s+1)^{7/8}+4z=(s+1)7/8+4z and root8 is the eighth root.

Preamble
import Mathlib
import Definitions.Def_IAFTRL_LinEnv
import Definitions.Def_IAFTRL_GIAFTRL
import Definitions.Def_IAFTRL_G26_body
import Definitions.Def_IAFTRL_G26_run
import Definitions.Def_IAFTRL_G26_window

open MeasureTheory ProbabilityTheory Set IAFTRL Matrix J11
open G26G
open G26 G26R
variable {d : ℕ} {𝒜 ℬ : Set (Fin d → ℝ)} {e : ℕ → Fin d → ℚ} {θ astar : Fin d → ℝ}
variable {Ω : Type*} [mΩ : MeasurableSpace Ω] {P : Measure Ω} [IsProbabilityMeasure P]
  {T : ℕ} {R : GRun d Ω}
Formal statement
theorem G26G.ref_block_alg {d u nC m0 : ℕ} {C sig c0 τm L : ℝ} (hsig : 0 < sig) (hc0 : 0 ≤ c0)
    (hnC1 : 1 ≤ nC) (hnu : nC ≤ u) (hC0 : 0 ≤ C) (hCn : C ≤ nC)
    (hu4 : (u : ℝ) + 1 ≤ 4 * ((m0 : ℝ) + 1))
    (hτm7 : root8 ((m0 : ℝ) + 1) ^ 7 ≤ τm) (hτmz : 4 * Real.sqrt ((nC : ℝ) * ((u : ℝ) + 1)) ≤ τm)
    (hτ2 : tauB (Real.sqrt ((nC : ℝ) * ((u : ℝ) + 1))) (2 * u) ≤ ((u : ℝ) + 1) / 4)
    (hL1 : 1 ≤ L)
    (hLq : L ^ (512 * (d + 1)) ≤
      ((4 + c0) ^ (512 * (d + 1)) * ((512 * (d + 1)).factorial : ℝ) * 6) * ((u : ℝ) + 1))
    (hL5 : L ≤ (12 + c0) * (((u : ℝ) + 1) / ((nC : ℝ) + 1))) :
    ∑ s ∈ Finset.Icc u (2 * u), cK d * ((s : ℝ) + 1) ^ (4 * kk d) /
          (((s : ℝ) + 2) ^ 4 / 2) ^ (4 * kk d) +
      (2 ^ (4 * kk d) * cK d * (((2 * u : ℕ) : ℝ) + 1) ^ (4 * kk d) /
          (τm * (((u : ℝ) + 1) / ((nC : ℝ) + 1))) ^ (4 * kk d) +
        2 ^ (4 * kk d) * 4 ^ d * ((τm * (((u : ℝ) + 1) / ((nC : ℝ) + 1))) / τm) ^ d /
          τm ^ (4 * kk d) *
          (Hneg (kk d) (16 * d + 1) (gB d) * (((2 * u : ℕ) : ℝ) + 1) ^ (3 * kk d) +
            ((((2 * u : ℕ) : ℝ) + 1) / ((nC : ℝ) + 1)) ^ (d + 2) *
              (2 ^ (4 * kk d) * (cK d * ((nC : ℝ) + 1) ^ (4 * kk d) + (2 * C) ^ (4 * kk d))))) +
      2 ^ (4 * kk d) * cK d * (((2 * u : ℕ) : ℝ) + 1) ^ (4 * kk d) /
        (2 * ((u : ℝ) + 1) ^ 2 / (4 * tauB (Real.sqrt ((nC : ℝ) * ((u : ℝ) + 1))) (2 * u))) ^
          (4 * kk d) +
      (2 * (4 * tauB (Real.sqrt ((nC : ℝ) * ((u : ℝ) + 1))) (2 * u))) ^ (4 * kk d) *
        ((2 * ((u : ℝ) + 1) ^ 2 / (4 * tauB (Real.sqrt ((nC : ℝ) * ((u : ℝ) + 1))) (2 * u))) /
          (4 * tauB (Real.sqrt ((nC : ℝ) * ((u : ℝ) + 1))) (2 * u))) ^ d *
        (2 ^ (4 * kk d) * (4 / (((u : ℝ) + 1) * (sig / root8 L))) ^ (4 * kk d)) ≤
      Dexpr d sig c0 * ((((nC : ℝ) + 1) / ((u : ℝ) + 1)) ^ 4 + 1 / ((u : ℝ) + 1) ^ 4) := by sorry
Source
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits: The Interplay of Information Acquisition, Corruption, and Geometry (STOC submission version; arXiv:2611.01299), Appendix G, proof of Lemma G.29, the summation leading to (G.621) (pp.185–186)

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