Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2.2 — finite-action corruption lower bound Ω(min⁡{T,C/Δmin⁡})\Omega(\min\{\sqrt T,\sqrt{C/\Delta_{\min}}\})Ω(min{T​,C/Δmin​​}) with c∗=Θ(1)c^*=\Theta(1)c∗=Θ(1)

Proved
IAFTRL.theorem_2_2

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

bandit-algorithmslinear-banditsonline-learning

Let e1,e2e_1,e_2e1​,e2​ be the standard basis of R2\mathbb R^2R2 and A={−e1,e1,e2}\mathcal A=\{-e_1,e_1,e_2\}A={−e1​,e1​,e2​}. For 0<Δmin⁡≤1/20<\Delta_{\min}\le1/20<Δmin​≤1/2 and σ=±1\sigma=\pm1σ=±1, let θσ=(σΔmin⁡/2, 1/2)\theta_\sigma=(\sigma\Delta_{\min}/2,\,1/2)θσ​=(σΔmin​/2,1/2). Losses are minimized, so the unique optimal action of θσ\theta_\sigmaθσ​ is −σe1-\sigma e_1−σe1​.

  1. The instances. For each σ=±1\sigma=\pm1σ=±1, the instance (A,θσ)(\mathcal A,\theta_\sigma)(A,θσ​) has a unique optimal action and minimum gap exactly Δmin⁡\Delta_{\min}Δmin​. Its information-acquisition complexity (1.2) is
c∗(A,θσ)=41+Δmin⁡=Θ(1).c^*(\mathcal A,\theta_\sigma)=\frac{4}{1+\Delta_{\min}}=\Theta(1).c∗(A,θσ​)=1+Δmin​4​=Θ(1).
  1. The lower bound. Fix a corruption budget C≥Δmin⁡−1C\ge\Delta_{\min}^{-1}C≥Δmin−1​ and an integer T≥⌈Δmin⁡−2⌉T\ge\lceil\Delta_{\min}^{-2}\rceilT≥⌈Δmin−2​⌉. Then there are two corrupted stochastic environments, indexed by σ=±1\sigma=\pm1σ=±1, with the following properties. Each has fixed loss vector θσ\theta_\sigmaθσ​, bounded feedback in [−1,1][-1,1][−1,1] with mean a⊤θta^\top\theta_ta⊤θt​, and total corruption ∑t≤T∥θt−θσ∥A≤C\sum_{t\le T}\|\theta_t-\theta_\sigma\|_{\mathcal A}\le C∑t≤T​∥θt​−θσ​∥A​≤C. Moreover, every policy π\piπ that plays actions in A\mathcal AA satisfies
max⁡σ=±1RegT,σ(π) ≥ 116min⁡{T, C/Δmin⁡}.\max_{\sigma=\pm1}\mathrm{Reg}_{T,\sigma}(\pi)\ \ge\ \frac1{16}\min\Big\{\sqrt T,\ \sqrt{C/\Delta_{\min}}\Big\}.σ=±1max​RegT,σ​(π) ≥ 161​min{T​, C/Δmin​​}.

Here RegT,σ=sup⁡u∈AE[∑t≤T(At−u)⊤θt]\mathrm{Reg}_{T,\sigma}=\sup_{u\in\mathcal A}\mathbb E\big[\sum_{t\le T}(A_t-u)^\top\theta_t\big]RegT,σ​=supu∈A​E[∑t≤T​(At​−u)⊤θt​] is computed in the environment indexed by σ\sigmaσ, using the actual (corrupted) loss vectors θt\theta_tθt​.

The two instances keep c∗c^*c∗ bounded while Δmin⁡\Delta_{\min}Δmin​ can be arbitrarily small. The theorem therefore shows that the coefficient of C\sqrt CC​ in the corruption term of a regret bound cannot, in general, be bounded in terms of c∗c^*c∗ alone; it must grow like Δmin⁡−1/2\Delta_{\min}^{-1/2}Δmin−1/2​. This complements the Jd,K,Δmin⁡CJ_{d,K,\Delta_{\min}}\sqrt CJd,K,Δmin​​C​ term of Theorem 2.1.

Formalization Note. The actions are listed as arms = (−e₁, e₁, e₂), and A\mathcal AA is Set.range arms. The complexity c∗c^*c∗ is linearBanditAllocationValue arms (−θ), the loss-convention reading of (1.2) also used in Theorem 2.1. A policy is any LinearBanditPolicy 2 (Markov kernels from histories to actions) with IsSupportedLinearPolicy (Set.range arms) π. The environments are oblivious LinEnvs (definition IAFTRL_LinEnv), with deterministic corruption and feedback laws that depend only on the round and the action. Exhibiting environments in this subclass is at least as strong as the source's existence claim. The condition T≥⌈Δmin⁡−2⌉T\ge\lceil\Delta_{\min}^{-2}\rceilT≥⌈Δmin−2​⌉ is written ⌈(Δ ^ 2)⁻¹⌉₊ ≤ T.

Preamble
import Mathlib
import Definitions.Def_LinearBanditProtocol
import Definitions.Def_IAFTRL_IsUniqueMin
import Definitions.Def_IAFTRL_LinEnv
Formal statement
namespace IAFTRL

open MeasureTheory ProbabilityTheory Matrix BanditAlgorithm

/-- **Theorem 2.2 (finite-action corruption lower bound).** Zhao–Tan, *Best-of-Both-Worlds FTRL
for Linear Bandits* (STOC submission version), Theorem 2.2, p.20: "Let `𝒜 = {−e₁, e₁, e₂}` and
`θ_σ = (σΔ_min/2, 1/2)`, with `σ = ±1` and `0 < Δ_min ≤ 1/2`. Both instances have minimum gap
`Δ_min` and `c*(𝒜, θ_σ) = 4/(1+Δ_min) = Θ(1)` for all `0 < Δ_min ≤ 1/2`. For every corruption
budget `C ≥ Δ_min⁻¹` and every integer `T ≥ ⌈Δ_min⁻²⌉`, there are two corrupted stochastic
environments indexed by `σ = ±1`, each with loss vector `θ_σ`, such that every policy satisfies
`max_{σ=±1} Reg_{T,σ} ≥ (1/16) min{√T, √(C/Δ_min)}` in the corrupted stochastic regime with budget
at most `C`."

The actions are listed as `arms = (−e₁, e₁, e₂)`; `c*` is `linearBanditAllocationValue arms (−θ)`
(the loss convention of (1.2), as in Theorem 2.1). A policy is any `LinearBanditPolicy 2` that
plays only actions of `𝒜`. The two environments are oblivious (`LinEnv`): deterministic
corruption and feedback whose law depends only on the round and the action. -/
theorem theorem_2_2 (Δ : ℝ) (hΔ : 0 < Δ) (hΔ' : Δ ≤ 1 / 2) :
    let arms : Fin 3 → Fin 2 → ℝ := ![![-1, 0], ![1, 0], ![0, 1]]
    let θ : ℝ → Fin 2 → ℝ := fun σ => ![σ * Δ / 2, 1 / 2]
    (∀ σ : ℝ, (σ = 1 ∨ σ = -1) →
      (∃ jstar : Fin 3, IsUniqueMin arms (θ σ) jstar ∧
        (∀ j, j ≠ jstar → Δ ≤ (arms j - arms jstar) ⬝ᵥ θ σ) ∧
        ∃ j, j ≠ jstar ∧ (arms j - arms jstar) ⬝ᵥ θ σ = Δ) ∧
      linearBanditAllocationValue arms (-θ σ) = 4 / (1 + Δ)) ∧
    ∀ C : ℝ, Δ⁻¹ ≤ C → ∀ T : ℕ, ⌈(Δ ^ 2)⁻¹⌉₊ ≤ T →
      ∃ E : ℝ → LinEnv 2,
        (∀ σ : ℝ, (σ = 1 ∨ σ = -1) → (E σ).IsCorruptedStoch (Set.range arms) (θ σ) C T) ∧
        ∀ π : LinearBanditPolicy 2, IsSupportedLinearPolicy (Set.range arms) π →
          (1 / 16) * min (Real.sqrt T) (Real.sqrt (C / Δ)) ≤
            max ((E 1).regret (Set.range arms) π T) ((E (-1)).regret (Set.range arms) π 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 2.3, Theorem 2.2, p. 20; setting of Section 1.1 (pp. 5–6), c* defined in (1.2); proof in Appendix E (pp. 112–115)

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