Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemmas C.31, C.33, C.28 (v1) — stopped negative moments and the window failure probability

Proved
IAFTRL.lemma_C_37_window

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

bandit-algorithmslinear-banditsonline-learning

Throughout, the processes satisfy the full-history scalar difference interface of Lemma C.34 (bundled as C37.Iface). There are KKK actions with a distinguished action a∗a^*a∗ and gaps Δ(a∗)=0\Delta(a^*)=0Δ(a∗)=0, Δ0≤Δ(a)≤2\Delta_0\le\Delta(a)\le 2Δ0​≤Δ(a)≤2. The processes satisfy X0,a=0X_{0,a}=0X0,a​=0, Xt+1,a=Xt,a+Dt,aX_{t+1,a}=X_{t,a}+D_{t,a}Xt+1,a​=Xt,a​+Dt,a​ and Dt,a∗=0D_{t,a^*}=0Dt,a∗​=0, and E[Dt,a∣Ft]=Δ(a)+et,a\mathbb E[D_{t,a}\mid\mathcal F_t]=\Delta(a)+e_{t,a}E[Dt,a​∣Ft​]=Δ(a)+et,a​ with ∣et,a∣≤2κt|e_{t,a}|\le2\kappa_t∣et,a​∣≤2κt​, κt∈[0,2]\kappa_t\in[0,2]κt​∈[0,2] and ∑t<Tκt≤C\sum_{t<T}\kappa_t\le C∑t<T​κt​≤C. The increments obey ∣Dt,a∣≤2βt+1+(Zt,a+Zt,a∗)/B|D_{t,a}|\le 2\beta_{t+1}+(Z_{t,a}+Z_{t,a^*})/B∣Dt,a​∣≤2βt+1​+(Zt,a​+Zt,a∗​)/B and E[Dt,a2∣Ft]≤4βt+1+2(Zt,a2+Zt,a∗2)/(B(t+1))\mathbb E[D_{t,a}^2\mid\mathcal F_t]\le 4\beta_{t+1}+2(Z_{t,a}^2+Z_{t,a^*}^2)/(B(t+1))E[Dt,a2​∣Ft​]≤4βt+1​+2(Zt,a2​+Zt,a∗2​)/(B(t+1)), where Zt,a=Xt,a−min⁡bXt,bZ_{t,a}=X_{t,a}-\min_bX_{t,b}Zt,a​=Xt,a​−minb​Xt,b​. Here P=2⌈256+log⁡(2K)⌉P=2\lceil256+\log(2K)\rceilP=2⌈256+log(2K)⌉, B=224PB=2^{24}PB=224P, k=K1/Pk=K^{1/P}k=K1/P, ν=3P/4\nu=3P/4ν=3P/4, and n=t+1n=t+1n=t+1 is the paper's round.

Let bj=C−∑s<jκsb_j=C-\sum_{s<j}\kappa_sbj​=C−∑s<j​κs​ be the remaining budget and Fj=∑a(2bj−Xj,a)+PF_j=\sum_a(2b_j-X_{j,a})_+^PFj​=∑a​(2bj​−Xj,a​)+P​ the power sum of negative parts of the budget-shifted differences. Fix a start time t0t_0t0​ with n0=t0+1n_0=t_0+1n0​=t0​+1, n0P/4≥HGn_0^{P/4}\ge H_Gn0P/4​≥HG​ and C≤n0C\le n_0C≤n0​, a window [m,t][m,t][m,t] with t0≤m≤t<Tt_0\le m\le t<Tt0​≤m≤t<T, and a level L≥0L\ge0L≥0. Then

L⋅P(∃ j∈[m,t]: Fj>L)≤H0 nν+(64 n0)P(nn0)q,L\cdot\mathbb P\bigl(\exists\,j\in[m,t]:\ F_j>L\bigr)\le H_0\,n^\nu+(64\,n_0)^P\Bigl(\frac n{n_0}\Bigr)^{q},L⋅P(∃j∈[m,t]: Fj​>L)≤H0​nν+(64n0​)P(n0​n​)q,

where H0H_0H0​ and q=⌈v⌉q=\lceil v\rceilq=⌈v⌉ are the negative-moment constants (Definition C.32, with v=6P2k2/B+P/4096v=6P^2k^2/B+P/4096v=6P2k2/B+P/4096).

The bound combines the shifted negative-moment recursion E[Ft+1∣Ft]≤(1+v/n)Ft+J0nν−1\mathbb E[F_{t+1}\mid\mathcal F_t]\le(1+v/n)F_t+J_0n^{\nu-1}E[Ft+1​∣Ft​]≤(1+v/n)Ft​+J0​nν−1, its initialization E[Fn0]≤(64n0)P\mathbb E[F_{n_0}]\le(64n_0)^PE[Fn0​​]≤(64n0​)P, and the stopped process of Lemma C.28. It is the window-failure input of Lemma C.26.

Formalization Note The left side is L E[1−σt+1]L\,\mathbb E[1-\sigma_{t+1}]LE[1−σt+1​], where σs\sigma_sσs​ is the indicator of {Fj≤L, m≤j<s}\{F_j\le L,\ m\le j<s\}{Fj​≤L, m≤j<s} (C37.sv).

Preamble
import Mathlib
import Definitions.Def_IAFTRL_beta
import Definitions.Def_IAFTRL_Bc
import Definitions.Def_IAFTRL_C37_scalar
Formal statement
namespace IAFTRL

open MeasureTheory

/-- **Window failure probability via stopped negative moments.** Zhao–Tan, *Best-of-Both-Worlds FTRL
for Linear Bandits*, arXiv:2611.01299v1, Lemmas C.31, C.33 and C.28 ((C.193)–(C.194)), for the abstract
interface `C37.Iface`: with `F_j = Σ_a (2b_j − X_{j,a})_+^P` (`b_j = C − Σ_{s<j} κ_s`), a start time
`t₀` after the burn-in with `C ≤ t₀ + 1`, a window `[m, t]` with `t₀ ≤ m`, and any level `L ≥ 0`,
`L · P(∃ j ∈ [m, t], F_j > L) ≤ H_0 n^ν + (64 n₀)^P (n/n₀)^q` where `n = t + 1`, `n₀ = t₀ + 1`. -/
theorem lemma_C_37_window {d K : ℕ} {jstar : Fin K} {Δ : Fin K → ℝ} {Δ₀ : ℝ} {Ω : Type*}
    [mΩ : MeasurableSpace Ω] {μ : Measure Ω} [IsProbabilityMeasure μ] {F : ℕ → MeasurableSpace Ω}
    {T : ℕ} {C : ℝ} {X D e : ℕ → Fin K → Ω → ℝ} {κ : ℕ → Ω → ℝ}
    (I : C37.Iface d K jstar Δ Δ₀ μ F T C X D e κ) (t0 m t : ℕ) (L : ℝ)
    (hL : 0 ≤ L) (ht0m : t0 ≤ m) (hmt : m ≤ t) (htT : t ≤ T)
    (hburn : C37.HG d K ≤ ((t0 : ℝ) + 1) ^ ((C37.Pord K : ℝ) / 4)) (hCn : C ≤ (t0 : ℝ) + 1) :
    L * ∫ ω, (1 - C37.sv C κ X m L (t + 1) ω) ∂μ ≤ C37.HN d K * ((t : ℝ) + 1) ^ C37.nuP K +
      (64 * ((t0 : ℝ) + 1)) ^ C37.Pord K * (((t : ℝ) + 1) / ((t0 : ℝ) + 1)) ^ C37.qN K := by sorry

end IAFTRL
Source
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits, arXiv:2611.01299v1, Lemma C.31 (C.206)–(C.209), Lemma C.33 (C.210)–(C.222), Lemma C.28 (C.193)–(C.194), pp.80–86

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