Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 2.1 (2.5) — corrupted stochastic regret for every fixed feasible allocation

Proved
IAFTRL.proposition_2_1_stochastic

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

bandit-algorithmslinear-banditsonline-learning

This is the corrupted stochastic half, (2.5), of Proposition 2.1.

There is an absolute constant c0>0c_0>0c0​>0 with the following property. Let d≥1d\ge1d≥1 and let A={a1,…,aK}\mathcal A=\{a_1,\dots,a_K\}A={a1​,…,aK​} be a finite action set in the Euclidean unit ball of Rd\mathbb R^dRd that spans Rd\mathbb R^dRd. Let θ\thetaθ satisfy ∥θ∥A=max⁡a∈A∣a⊤θ∣≤1\|\theta\|_{\mathcal A}=\max_{a\in\mathcal A}|a^\top\theta|\le1∥θ∥A​=maxa∈A​∣a⊤θ∣≤1 and have a unique optimal (loss-minimizing) action a∗a^*a∗, and let Δ0∈(0,1]\Delta_0\in(0,1]Δ0​∈(0,1] satisfy Δ0≤Δ(a)=(a−a∗)⊤θ\Delta_0\le\Delta(a)=(a-a^*)^\top\thetaΔ0​≤Δ(a)=(a−a∗)⊤θ for all a≠a∗a\ne a^*a=a∗. Let nnn be any feasible sampling allocation of (1.2), with information-acquisition cost cn(A,θ)=∑anaΔ(a)c^n(\mathcal A,\theta)=\sum_a n_a\Delta(a)cn(A,θ)=∑a​na​Δ(a). Then there is a constant MMM, depending only on these data, such that every execution of IA-FTRL for T≥1T\ge1T≥1 rounds in the corrupted stochastic regime with corruption budget C≥0C\ge0C≥0 satisfies, for every comparator u∈Au\in\mathcal Au∈A,

RegT(u)≤c0(cn(A,θ)log⁡K⋅log⁡T+dlog⁡K Δ0−128/255C)+M.\mathrm{Reg}_T(u)\le c_0\Big(c^n(\mathcal A,\theta)\log K\cdot\log T+\sqrt{d\log K}\,\Delta_0^{-128/255}\sqrt C\Big)+M .RegT​(u)≤c0​(cn(A,θ)logK⋅logT+dlogK​Δ0−128/255​C​)+M.

Together with the adversarial bound of Proposition D.2, this gives Proposition 2.1. Applied at the allocation of Lemma C.3, it yields the c∗(A,θ)log⁡K⋅log⁡Tc^*(\mathcal A,\theta)\log K\cdot\log Tc∗(A,θ)logK⋅logT rate of Theorem 2.1.

Formalization Note This is the second conjunct of IAFTRL.proposition_2_1, with its own absolute constant and the same quantifier order: c0c_0c0​ is chosen before the instance, and MMM (the paper's c0Mnc_0M_nc0​Mn​) after (d,K,A,θ,a∗,Δ0,n)(d,K,\mathcal A,\theta,a^*,\Delta_0,n)(d,K,A,θ,a∗,Δ0​,n) but before the probability space, TTT, CCC and the run. The paper's Jd,K,Δmin⁡J_{d,K,\Delta_{\min}}Jd,K,Δmin​​ is absorbed into c0dlog⁡K Δ0−128/255c_0\sqrt{d\log K}\,\Delta_0^{-128/255}c0​dlogK​Δ0−128/255​.

Preamble
import Mathlib
import Definitions.Def_IAFTRL_IsActionSet
import Definitions.Def_IAFTRL_IsIAFTRLRun
import Definitions.Def_LinearBanditProtocol
import Definitions.Def_IAFTRL_actionNorm
import Definitions.Def_IAFTRL_IsUniqueMin
import Definitions.Def_IAFTRL_IsCorrupted
import Definitions.Def_IAFTRL_regretVs
import Definitions.Def_IAFTRL_IsFeasibleAlloc
import Definitions.Def_IAFTRL_allocCost
Formal statement
namespace IAFTRL

open Matrix MeasureTheory

/-- **Proposition 2.1, corrupted stochastic part (2.5).** Zhao–Tan, *Best-of-Both-Worlds FTRL for
Linear Bandits*, arXiv:2611.01299, Proposition 2.1, p.20: "Simultaneously, for every feasible
sampling allocation `n` in (1.2), IA-FTRL guarantees
`Reg_T = O(c^n(𝒜, θ) log K · log T + M_n + J_{d,K,Δ_min}√C)`, (2.5) in the corrupted stochastic
regime, where `J_{d,K,Δ_min} = O(√(d log K) Δ_min^{−128/255})`, and `M_n` is a finite constant
depending on the instance `(𝒜, θ)` and the sampling allocation `n`, but independent of `T` and `C`."

There is an absolute constant `c₀ > 0` such that for every dimension `d ≥ 1`, every spanning finite
action set `𝒜` in the unit ball of `ℝ^d` with `K = |𝒜|`, every `θ` with `‖θ‖_𝒜 ≤ 1` and unique
optimal action `a*`, every `Δ₀ ∈ (0, 1]` with `Δ₀ ≤ Δ(a)` for all `a ≠ a*`, and every feasible
sampling allocation `n` of (1.2), there is a constant `M` such that every execution of IA-FTRL for
`T ≥ 1` rounds in the corrupted stochastic regime with any budget `C ≥ 0` has
`Reg_T(u) ≤ c₀(c^n(𝒜, θ) log K · log T + √(d log K) Δ₀^{−128/255} √C) + M` for every `u ∈ 𝒜`.

**Formalization Note.** This is the second conjunct of `IAFTRL.proposition_2_1`, with its own
absolute constant and the same quantifier order: `c₀` before the instance, `M` (the paper's `c₀M_n`)
after `(d, K, 𝒜, θ, a*, Δ₀, n)` and before the probability space, `T`, `C` and the run. -/
theorem proposition_2_1_stochastic : ∃ c₀ : ℝ, 0 < c₀ ∧
    ∀ {d K : ℕ}, 1 ≤ d → ∀ (arms : Fin K → Fin d → ℝ), IsActionSet arms →
      ∀ (θ : Fin d → ℝ) (jstar : Fin K) (Δ₀ : ℝ),
        actionNorm arms θ ≤ 1 → IsUniqueMin arms θ jstar → 0 < Δ₀ → Δ₀ ≤ 1 →
        (∀ j, j ≠ jstar → Δ₀ ≤ (arms j - arms jstar) ⬝ᵥ θ) →
        ∀ n : Fin K → ℝ, IsFeasibleAlloc arms θ jstar n →
        ∃ M : ℝ, ∀ {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
          (T : ℕ) (C : ℝ) (R : Run d K Ω), 1 ≤ T → 0 ≤ C →
          IsIAFTRLRun P arms T R → IsCorrupted P arms θ C T R →
          ∀ u : Fin K, regretVs P arms T R u ≤
            c₀ * (allocCost arms θ jstar n * Real.log K * Real.log T +
              Real.sqrt ((d : ℝ) * Real.log K) * Δ₀ ^ (-(128 : ℝ) / 255) * Real.sqrt C) + M := by sorry

end IAFTRL
Source
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits, arXiv:2611.01299, Proposition 2.1, p.20, bound (2.5); M_n defined in (D.5)

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