Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The window parameters of Definition G.8 satisfy all window hypotheses for t ≥ t₀

Proved
G26G.Sharp.win_ok

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

bandit-algorithmslinear-banditsonline-learning

Setting. The standing hypotheses Sharp of the sharp corrupted instance hold (see runN_FI), and eee is surjective. Let C≥0C\ge0C≥0, nC=⌈C⌉+1n_C=\lceil C\rceil+1nC​=⌈C⌉+1, HC=(nC+1)log⁡(e(nC+1))H_C=(n_C+1)\log(e(n_C+1))HC​=(nC​+1)log(e(nC​+1)), and for a round ttt set

m=⌈M0HC⌉+⌈HC(t+1)⌉,z=(t+1)(m+1t+1)7/8,τs=(s+1)7/8+4z,m=\lceil M_0H_C\rceil+\lceil\sqrt{H_C(t+1)}\rceil,\qquad z=(t+1)\Big(\frac{m+1}{t+1}\Big)^{7/8},\qquad\tau_s=(s+1)^{7/8}+4z,m=⌈M0​HC​⌉+⌈HC​(t+1)​⌉,z=(t+1)(t+1m+1​)7/8,τs​=(s+1)7/8+4z,

where M0M_0M0​ (H.M0 he) is an instance constant.

Claim. If t≥t0=⌈UwHC⌉t\ge t_0=\lceil U_wH_C\rceilt≥t0​=⌈Uw​HC​⌉ (H.t0f he C), then all of the following hold: 1≤m≤t1\le m\le t1≤m≤t, 2(m+1)≤t+12(m+1)\le t+12(m+1)≤t+1; cTw≤(m+1)1/8c_{Tw}\le(m+1)^{1/8}cTw​≤(m+1)1/8; ς−1C≤m+1\varsigma^{-1}C\le m+1ς−1C≤m+1; 2Sref+2≤m2S_{\rm ref}+2\le m2Sref​+2≤m; 221(nC+1)log⁡(e(nC+1))≤m+12^{21}(n_C+1)\log(e(n_C+1))\le m+1221(nC​+1)log(e(nC​+1))≤m+1; 0<z0<z0<z and m+1≤z≤(t+1)((m+1)/(t+1))7/8m+1\le z\le(t+1)((m+1)/(t+1))^{7/8}m+1≤z≤(t+1)((m+1)/(t+1))7/8; κ1((m+1)/(t+1))1/8≤1\kappa_1((m+1)/(t+1))^{1/8}\le1κ1​((m+1)/(t+1))1/8≤1; ((m+1)/z)8≤(m+1)/(t+1)((m+1)/z)^8\le(m+1)/(t+1)((m+1)/z)8≤(m+1)/(t+1); (t+1)/(m+1)≤m+1(t+1)/(m+1)\le m+1(t+1)/(m+1)≤m+1; τt≤t+1\tau_t\le t+1τt​≤t+1; and the tail bounds

(τtt+1)16≤216(1(t+1)2+416(m+1t+1)4),(m+1t+1)4≤16((M0+3)4+1)(HCt+1)2,\Big(\frac{\tau_t}{t+1}\Big)^{16}\le2^{16}\Big(\frac1{(t+1)^2}+4^{16}\Big(\frac{m+1}{t+1}\Big)^4\Big),\qquad\Big(\frac{m+1}{t+1}\Big)^4\le16\big((M_0+3)^4+1\big)\Big(\frac{H_C}{t+1}\Big)^2,(t+1τt​​)16≤216((t+1)21​+416(t+1m+1​)4),(t+1m+1​)4≤16((M0​+3)4+1)(t+1HC​​)2, (nC+1)4+1(m+1)4≤(HCt+1)2+1(t+1)2,1(m+1)4≤1(t+1)2.\frac{(n_C+1)^4+1}{(m+1)^4}\le\Big(\frac{H_C}{t+1}\Big)^2+\frac1{(t+1)^2},\qquad\frac1{(m+1)^4}\le\frac1{(t+1)^2}.(m+1)4(nC​+1)4+1​≤(t+1HC​​)2+(t+1)21​,(m+1)41​≤(t+1)21​.

These are the comparisons "m≥Nm\ge Nm≥N, m≤t/2m\le t/2m≤t/2, m≥ΛCm\ge\Lambda Cm≥ΛC, τs≥4ΛC\tau_s\ge4\Lambda Cτs​≥4ΛC, τt≤t\tau_t\le tτt​≤t" of Definition G.8, made explicit, together with the conversions of the window error terms into (t+1)−2+(HC/(t+1))2(t+1)^{-2}+(H_C/(t+1))^2(t+1)−2+(HC​/(t+1))2.

Formalization Note Rounds are 0-based; the statement uses let for HCH_CHC​, mmm, zzz.

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) (he : Function.Surjective e)
include H he
Formal statement
theorem G26G.Sharp.win_ok {C : ℝ} (hC : 0 ≤ C) {t : ℕ} (ht0 : H.t0f he C ≤ t) :
    let Hc := Hcf C
    let m := mw (H.M0 he) Hc t
    let z := zw m t
    1 ≤ m ∧ m ≤ t ∧ 2 * ((m : ℝ) + 1) ≤ (t : ℝ) + 1 ∧
    cTw d H.sig⁻¹ H.kb ≤ root8 ((m : ℝ) + 1) ∧ H.sig⁻¹ * C ≤ (m : ℝ) + 1 ∧
    2 * H.Sref he + 2 ≤ m ∧
    2 ^ 21 * (((nCf C : ℝ) + 1) * Real.log (Real.exp 1 * ((nCf C : ℝ) + 1))) ≤ (m : ℝ) + 1 ∧
    0 < z ∧ (m : ℝ) + 1 ≤ z ∧
    z ≤ ((t : ℝ) + 1) * root8 (((m : ℝ) + 1) / ((t : ℝ) + 1)) ^ 7 ∧
    H.κ1 * root8 (((m : ℝ) + 1) / ((t : ℝ) + 1)) ≤ 1 ∧
    (((m : ℝ) + 1) / z) ^ 8 ≤ ((m : ℝ) + 1) / ((t : ℝ) + 1) ∧
    ((t : ℝ) + 1) / ((m : ℝ) + 1) ≤ (m : ℝ) + 1 ∧
    tauB z t ≤ (t : ℝ) + 1 ∧
    (tauB z t / ((t : ℝ) + 1)) ^ 16 ≤
      2 ^ 16 * (1 / ((t : ℝ) + 1) ^ 2 + 4 ^ 16 * (((m : ℝ) + 1) / ((t : ℝ) + 1)) ^ 4) ∧
    (((m : ℝ) + 1) / ((t : ℝ) + 1)) ^ 4 ≤
      16 * (((H.M0 he : ℝ) + 3) ^ 4 + 1) * (Hc / ((t : ℝ) + 1)) ^ 2 ∧
    (((nCf C : ℝ) + 1) ^ 4 + 1) / ((m : ℝ) + 1) ^ 4 ≤
      (Hc / ((t : ℝ) + 1)) ^ 2 + 1 / ((t : ℝ) + 1) ^ 2 ∧
    1 / ((m : ℝ) + 1) ^ 4 ≤ 1 / ((t : ℝ) + 1) ^ 2 := 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, Definition G.8, (G.522) and the comparisons stated after it (p.173)

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