Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Preparation before a reference block: probability that the remaining-budget field crosses its buffer

Proved
G26G.Sharp.prep_prob

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

bandit-algorithmslinear-banditsonline-learning

Setting. A⊆Rd\mathcal A\subseteq\mathbb R^dA⊆Rd is a compact action set spanning Rd\mathbb R^dRd, B⊆A\mathcal B\subseteq\mathcal AB⊆A is a compact generator (A⊆K:=Conv⁡B\mathcal A\subseteq\mathcal K:=\operatorname{Conv}\mathcal BA⊆K:=ConvB), e:N→Qde:\mathbb N\to\mathbb Q^de:N→Qd is the direction enumeration, and RRR is a GIA-FTRL run of TTT rounds (IsGIAFTRLRun) with cumulative loss estimate Sn=∑j<nθ^jS_n=\sum_{j<n}\hat\theta_jSn​=∑j<n​θ^j​, run filtration (Gn)(\mathcal G_n)(Gn​), learning rate βn=16d+n\beta_n=16d+\sqrt nβn​=16d+n​ (gbeta) and magnitude constant B=236(d+1)B=2^{36}(d+1)B=236(d+1) (gB). The filtration used below is Fn=Gn\mathcal F_n=\mathcal G_nFn​=Gn​ for n<Tn<Tn<T and FT=F\mathcal F_T=\mathcal FFT​=F (Fx). The standing hypotheses Sharp hold: A\mathcal AA lies in the unit ball, k=dim⁡K≥1k=\dim\mathcal K\ge1k=dimK≥1, ∥θ∥A≤1\|\theta\|_{\mathcal A}\le1∥θ∥A​≤1, a∗∈Aa^*\in\mathcal Aa∗∈A is the unique minimizer of a↦a⊤θa\mapsto a^\top\thetaa↦a⊤θ on A\mathcal AA, and the instance is sharp with modulus ς>0\varsigma>0ς>0 (H.sig): Δ(a)=(a−a∗)⊤θ≥ς∥a−a∗∥S\Delta(a)=(a-a^*)^\top\theta\ge\varsigma\|a-a^*\|_{\mathcal S}Δ(a)=(a−a∗)⊤θ≥ς∥a−a∗∥S​ on K\mathcal KK. The corruption is bounded by CCC: ∑t<T∥θt−θ∥A≤C\sum_{t<T}\|\theta_t-\theta\|_{\mathcal A}\le C∑t<T​∥θt​−θ∥A​≤C a.s. (IsCorruptedG). The projective body is Uθ={Δ(a)−1(a−a∗):a∈K∖{a∗}}‾U_\theta=\overline{\{\Delta(a)^{-1}(a-a^*):a\in\mathcal K\setminus\{a^*\}\}}Uθ​={Δ(a)−1(a−a∗):a∈K∖{a∗}}​ and the cone body is Dθ={λu:λ∈[0,1],u∈Uθ}D_\theta=\{\lambda u:\lambda\in[0,1],u\in U_\theta\}Dθ​={λu:λ∈[0,1],u∈Uθ​}; Λ=ς−1\Lambda=\varsigma^{-1}Λ=ς−1, An=∑j<n∥θj−θ∥AA_n=\sum_{j<n}\|\theta_j-\theta\|_{\mathcal A}An​=∑j<n​∥θj​−θ∥A​, and j∗j^*j∗ is the index of a∗a^*a∗ among the reference atoms (js).

Let C≥0C\ge0C≥0, let τ\tauτ be nondecreasing, m0≤nC≤N≤Tm_0\le n_C\le N\le Tm0​≤nC​≤N≤T, τm0≥1\tau_{m_0}\ge1τm0​​≥1, and ρ≥max⁡{τm0,4C}\rho\ge\max\{\tau_{m_0},4C\}ρ≥max{τm0​​,4C}. Write P=4kP=4kP=4k with k=1024(d+1)k=1024(d+1)k=1024(d+1) (kk d), cKc_KcK​ (cK d) for the absolute-envelope constant, and INWI^W_NINW​ for the event that the remaining-budget field WWW of Lemma G.30 satisfies max⁡K(−Wj)≤τj\max_{\mathcal K}(-W_j)\le\tau_jmaxK​(−Wj​)≤τj​ for all m0≤j≤Nm_0\le j\le Nm0​≤j≤N. Then

P((INW)c)≤2PcK(N+1)PρP+2P4d(ρ/τm0)dτm0P(Hneg(k,16d+1,B)(N+1)3k+(N+1nC+1)d+22P(cK(nC+1)P+(2C)P)).\mathbb P\big((I^W_N)^c\big)\le\frac{2^{P}c_K(N+1)^{P}}{\rho^{P}}+\frac{2^{P}4^{d}(\rho/\tau_{m_0})^{d}}{\tau_{m_0}^{P}}\Big(H_{\rm neg}(k,16d+1,B)(N+1)^{3k}+\Big(\frac{N+1}{n_C+1}\Big)^{d+2}2^{P}\big(c_K(n_C+1)^{P}+(2C)^{P}\big)\Big).P((INW​)c)≤ρP2PcK​(N+1)P​+τm0​P​2P4d(ρ/τm0​​)d​(Hneg​(k,16d+1,B)(N+1)3k+(nC​+1N+1​)d+22P(cK​(nC​+1)P+(2C)P)).

The first term is Markov's inequality for the absolute envelope of WWW; the second applies the crossing envelope from the start nCn_CnC​, where the negative moment of WWW is bounded by its absolute moment plus the shift 2C2C2C. This is the event {I=0}\{I=0\}{I=0} that the block argument of Lemma G.29 must exclude before using the per-action variables.

Formalization Note Rounds are 0-based.

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 Ω}
open G26G.Sharp
variable (H : Sharp 𝒜 ℬ θ astar)
include H
variable (he : Function.Surjective e)
include he
Formal statement
theorem G26G.Sharp.prep_prob (hR : IsGIAFTRLRun P 𝒜 ℬ e T R) {C : ℝ} (hC : 0 ≤ C)
    (hcor : IsCorruptedG P 𝒜 θ C T R) {τ : ℕ → ℝ} (hτmono : ∀ n, τ n ≤ τ (n + 1))
    {m0 N nC : ℕ} (hN : N ≤ T) (hnN : nC ≤ N) (hτ1 : 1 ≤ τ m0) {ρ : ℝ} (hρτ : τ m0 ≤ ρ)
    (hρC : 4 * C ≤ ρ) :
    P.real (IW 𝒜 ℬ R θ astar C τ m0 N)ᶜ ≤
      2 ^ (4 * kk d) * cK d * ((N : ℝ) + 1) ^ (4 * kk d) / ρ ^ (4 * kk d) +
      2 ^ (4 * kk d) * 4 ^ d * (ρ / τ m0) ^ d / τ m0 ^ (4 * kk d) *
        (Hneg (kk d) (16 * d + 1) (gB d) * ((N : ℝ) + 1) ^ (3 * kk d) +
          (((N : ℝ) + 1) / ((nC : ℝ) + 1)) ^ (d + 2) *
            (2 ^ (4 * kk d) * (cK d * ((nC : ℝ) + 1) ^ (4 * kk d) + (2 * C) ^ (4 * kk d)))) := 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, (G.623)–(G.628) (pp.182–183), with Lemma G.30 (G.678) (p.188)

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