Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.2(ii) — corruption lower bound 132min⁡{T,C/φ}\frac1{32}\min\{\sqrt T,\sqrt{C/\varphi}\}321​min{T​,C/φ​} on a sharp arch with small modulus

Proved
IAFTRL.theorem_3_2_ii

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

bandit-algorithmslinear-banditsonline-learning

Setting. Let

Aarch={a(x)=(x, 1−x22):−1≤x≤1},θσ=(σφ2,12),σ∈{−1,1},0<φ≤18.\mathcal A_{\rm arch}=\Big\{a(x)=\Big(x,\ \frac{1-x^2}{2}\Big):-1\le x\le1\Big\},\qquad \theta_\sigma=\Big(\frac{\sigma\varphi}{2},\frac12\Big),\quad\sigma\in\{-1,1\},\quad 0<\varphi\le\frac18 .Aarch​={a(x)=(x, 21−x2​):−1≤x≤1},θσ​=(2σφ​,21​),σ∈{−1,1},0<φ≤81​.

The unique optimal action of θσ\theta_\sigmaθσ​ is a∗=−σe1=(−σ,0)a^*=-\sigma e_1=(-\sigma,0)a∗=−σe1​=(−σ,0). Let ςσ\varsigma_\sigmaςσ​ be the sharpness modulus (1.3) with generator Aarch\mathcal A_{\rm arch}Aarch​, and cctr∗c^*_{\rm ctr}cctr∗​ the centered information-acquisition complexity (1.4).

Claim. For each σ=±1\sigma=\pm1σ=±1, a∗=−σe1∈Aarcha^*=-\sigma e_1\in\mathcal A_{\rm arch}a∗=−σe1​∈Aarch​ is the unique optimal action, and

φ6≤ςσ≤φ2,12825≤cctr∗(Aarch,θσ)≤10.\frac\varphi6\le\varsigma_\sigma\le\frac\varphi2,\qquad \frac{128}{25}\le c^*_{\rm ctr}(\mathcal A_{\rm arch},\theta_\sigma)\le10 .6φ​≤ςσ​≤2φ​,25128​≤cctr∗​(Aarch​,θσ​)≤10.

Moreover, take any corruption budget C≥φ−1C\ge\varphi^{-1}C≥φ−1 and any integer T≥⌈φ−2⌉T\ge\lceil\varphi^{-2}\rceilT≥⌈φ−2⌉. There exist two corrupted stochastic environments E+1,E−1E_{+1},E_{-1}E+1​,E−1​ over the horizon TTT, where EσE_\sigmaEσ​ has fixed loss vector θσ\theta_\sigmaθσ​, a deterministic corruption sequence of total budget at most CCC, and feedback in [−1,1][-1,1][−1,1] with the linear mean. For these environments, every policy that plays only actions of Aarch\mathcal A_{\rm arch}Aarch​ satisfies

max⁡σ=±1RegT,σ ≥ 132min⁡{T, C/φ}.\max_{\sigma=\pm1}\mathrm{Reg}_{T,\sigma}\ \ge\ \frac1{32}\min\Big\{\sqrt T,\ \sqrt{C/\varphi}\Big\}.σ=±1max​RegT,σ​ ≥ 321​min{T​, C/φ​}.

The instances stay sharp and cctr∗c^*_{\rm ctr}cctr∗​ stays bounded, but the corruption penalty grows like C/ςσ\sqrt{C/\varsigma_\sigma}C/ςσ​​ as the modulus ςσ≍φ→0\varsigma_\sigma\asymp\varphi\to0ςσ​≍φ→0. So the dependence of the C\sqrt CC​ term on the geometry in Theorem 3.1 is necessary.

Formalization Note The environments are oblivious (LinEnv), and the regret is sup⁡u∈AE[∑t≤T(At−u)⊤θt]\sup_{u\in\mathcal A}\mathbb E[\sum_{t\le T}(A_t-u)^\top\theta_t]supu∈A​E[∑t≤T​(At​−u)⊤θt​] against the actual loss vectors (LinEnv.regret). The sharpness modulus is sharpModulus arch (θ σ) ![-σ, 0].

Preamble
import Mathlib
import Definitions.Def_LinearBanditProtocol
import Definitions.Def_IAFTRL_LinEnv
import Definitions.Def_IAFTRL_GIAFTRL
import Definitions.Def_IAFTRL_SignModel
Formal statement
namespace IAFTRL

open MeasureTheory ProbabilityTheory Matrix BanditAlgorithm

/-- **Theorem 3.2, second part (corruption on a sharp instance with arbitrarily small gaps).**
Zhao–Tan, *Best-of-Both-Worlds FTRL for Linear Bandits* (STOC submission version), Theorem 3.2,
pp.25–26: "Let `A_arch = {(x, (1 − x²)/2) : −1 ≤ x ≤ 1}`, `θ_σ = (σϕ/2, 1/2)`, and `σ = ±1`, where
`0 < ϕ ≤ 1/8`. For each `σ = ±1`, the sharpness modulus `ς_σ` in (1.3) and the centered
information-acquisition complexity satisfy `ϕ/6 ≤ ς_σ ≤ ϕ/2` and
`128/25 ≤ c*_ctr(A_arch, θ_σ) ≤ 10`. For every corruption budget `C ≥ ϕ⁻¹` and every integer
`T ≥ ⌈ϕ⁻²⌉`, there exist two corrupted stochastic environments indexed by `σ = ±1`, each with fixed
loss vector `θ_σ` and a deterministic corruption sequence of total budget at most `C`, such that
every policy satisfies `max_{σ=±1} Reg_{T,σ} ≥ (1/32) min{√T, √(C/ϕ)}`."

The unique optimal action of `θ_σ` is `a* = −σe₁ = (−σ, 0)` (Lemma H.1, p.196); the sharpness
modulus and `c*_ctr` are taken at this `a*`, with generator `ℬ = A_arch`. The environments are
oblivious (`LinEnv`), and a policy is any `LinearBanditPolicy 2` that plays only actions of
`A_arch`. -/
theorem theorem_3_2_ii (φ : ℝ) (hφ : 0 < φ) (hφ' : φ ≤ 1 / 8) :
    let arch : Set (Fin 2 → ℝ) := {a | ∃ x ∈ Set.Icc (-1 : ℝ) 1, a = ![x, (1 - x ^ 2) / 2]}
    let θ : ℝ → Fin 2 → ℝ := fun σ => ![σ * φ / 2, 1 / 2]
    (∀ σ : ℝ, (σ = 1 ∨ σ = -1) →
      ![-σ, 0] ∈ arch ∧ (∀ a ∈ arch, a ≠ ![-σ, 0] → ![-σ, 0] ⬝ᵥ θ σ < a ⬝ᵥ θ σ) ∧
      φ / 6 ≤ sharpModulus arch (θ σ) ![-σ, 0] ∧ sharpModulus arch (θ σ) ![-σ, 0] ≤ φ / 2 ∧
      128 / 25 ≤ cstarCtr arch (θ σ) ![-σ, 0] ∧ cstarCtr arch (θ σ) ![-σ, 0] ≤ 10) ∧
    ∀ C : ℝ, φ⁻¹ ≤ C → ∀ T : ℕ, ⌈(φ ^ 2)⁻¹⌉₊ ≤ T →
      ∃ E : ℝ → LinEnv 2,
        (∀ σ : ℝ, (σ = 1 ∨ σ = -1) → (E σ).IsCorruptedStoch arch (θ σ) C T) ∧
        ∀ π : LinearBanditPolicy 2, IsSupportedLinearPolicy arch π →
          (1 / 32) * min (Real.sqrt T) (Real.sqrt (C / φ)) ≤
            max ((E 1).regret arch π T) ((E (-1)).regret arch π T) := by sorry

end IAFTRL
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), Section 3.3, Theorem 3.2 (second bullet), pp.25–26; proof in Appendix H.2 and Lemma H.1 (H.5)–(H.7), pp.194–198

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