Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 3.1 — GIA-FTRL regret for every fixed centered sampling allocation

Proved
IAFTRL.proposition_3_1

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

bandit-algorithmslinear-banditsonline-learning

Setting. Let A⊆Bd\mathcal A\subseteq\mathbb B^dA⊆Bd (d≥1d\ge1d≥1) be a compact action set with span(A)=Rd\mathrm{span}(\mathcal A)=\mathbb R^dspan(A)=Rd. GIA-FTRL (Algorithm 2) runs on a compact generator B\mathcal BB, meaning B⊆A⊆Conv(B)\mathcal B\subseteq\mathcal A\subseteq\mathrm{Conv}(\mathcal B)B⊆A⊆Conv(B), with k=dim⁡aff⁡(Conv B)≥1k=\dim\operatorname{aff}(\mathrm{Conv}\,\mathcal B)\ge1k=dimaff(ConvB)≥1 and a fixed enumeration of Qd\mathbb Q^dQd. The regret against a comparator uuu is RegT(u)=E[∑t≤T(At−u)⊤θt]\mathrm{Reg}_T(u)=\mathbb E\big[\sum_{t\le T}(A_t-u)^\top\theta_t\big]RegT​(u)=E[∑t≤T​(At​−u)⊤θt​], and RegT=sup⁡u∈ARegT(u)\mathrm{Reg}_T=\sup_{u\in\mathcal A}\mathrm{Reg}_T(u)RegT​=supu∈A​RegT​(u). In the corrupted stochastic regime, θt=θ+ct\theta_t=\theta+c_tθt​=θ+ct​ with ∥θ∥A≤1\|\theta\|_{\mathcal A}\le1∥θ∥A​≤1 and ∑t≤T∥ct∥A≤C\sum_{t\le T}\|c_t\|_{\mathcal A}\le C∑t≤T​∥ct​∥A​≤C almost surely, and θ\thetaθ has a unique optimal action a∗∈Aa^*\in\mathcal Aa∗∈A. All objects are those of the definition IAFTRL_GIAFTRL.

There is an absolute constant c0>0c_0>0c0​>0 with the following two properties.

  1. Adversarial regime. Every run of GIA-FTRL satisfies RegT(u)≤c0 dTlog⁡T\mathrm{Reg}_T(u)\le c_0\,d\sqrt T\log TRegT​(u)≤c0​dT​logT for all T≥2T\ge2T≥2 and all u∈Au\in\mathcal Au∈A. This is (3.8).
  2. Corrupted stochastic regime. If the instance is sharp (1.3), then there is a finite constant JθcorJ^{\mathrm{cor}}_\thetaJθcor​ with the following property. For every finite feasible centered sampling allocation nnn on the generator B\mathcal BB (Definition 1.2 with B\mathcal BB in place of A\mathcal AA), there is a finite constant MnM_nMn​ such that, for all T≥1T\ge1T≥1, C≥0C\ge0C≥0 and u∈Au\in\mathcal Au∈A,
RegT(u)≤c0 cctrn(B,θ) dlog⁡T+Mn+JθcorClog⁡+(C).(3.9)\mathrm{Reg}_T(u)\le c_0\,c^n_{\mathrm{ctr}}(\mathcal B,\theta)\,d\log T+M_n+J^{\mathrm{cor}}_\theta\sqrt C\log_+(C). \tag{3.9}RegT​(u)≤c0​cctrn​(B,θ)dlogT+Mn​+Jθcor​C​log+​(C).(3.9)

The constant JθcorJ^{\mathrm{cor}}_\thetaJθcor​ does not depend on TTT, CCC or nnn. The constant MnM_nMn​ depends on the instance and on nnn, but not on TTT or CCC.

Theorem 3.1 follows from this proposition by choosing a fixed allocation with cctrn≤2cctr∗c^{n}_{\mathrm{ctr}}\le2c^*_{\mathrm{ctr}}cctrn​≤2cctr∗​ (Appendix F.1.1) and using cctr∗(B,θ)=cctr∗(A,θ)c^*_{\mathrm{ctr}}(\mathcal B,\theta)=c^*_{\mathrm{ctr}}(\mathcal A,\theta)cctr∗​(B,θ)=cctr∗​(A,θ) (Lemma J.10).

Formalization Note. As in Theorem 3.1: (3.8) is stated for T≥2T\ge2T≥2, O(⋅)O(\cdot)O(⋅) is an absolute constant c0c_0c0​, and the regret bound is written for every comparator. In the formal statement, JJJ is chosen before nnn.

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

open MeasureTheory

/-- **Proposition 3.1.** Zhao–Tan, *Best-of-Both-Worlds FTRL for Linear Bandits* (STOC submission
version), Proposition 3.1, p.25: "For linear bandits with compact action sets, GIA-FTRL guarantees
`Reg_T = O(d√T log T)` (3.8) in the adversarial regime. Simultaneously, if the linear bandit
instance satisfies the sharpness condition in (1.3), then for every feasible centered sampling
allocation `n` in (1.4) and an arbitrary generator `ℬ` of `𝒜`, GIA-FTRL guarantees
`Reg_T = O(c^n_ctr(ℬ, θ) d log T + M_n + J^cor_θ √C log₊(C))` (3.9) in the corrupted stochastic
regime, where `J^cor_θ` is a finite instance-dependent constant independent of `T, C, n`, and `M_n`
is a finite constant depending on the instance and the sampling allocation `n`, but independent of
`T` and `C`."

The setting is that of `theorem_3_1`; the allocation `n` is a finite feasible centered sampling
allocation on the generator `ℬ` (`IsCtrAlloc ℬ θ a* n`), and `J` is chosen before `n`. -/
theorem proposition_3_1 : ∃ c₀ : ℝ, 0 < c₀ ∧
    ∀ {d : ℕ}, 1 ≤ d → ∀ (𝒜 ℬ : Set (Fin d → ℝ)) (e : ℕ → Fin d → ℚ),
      IsCompact 𝒜 → IsCompact ℬ → IsGenerator 𝒜 ℬ → (∀ a ∈ 𝒜, a ⬝ᵥ a ≤ 1) →
      Submodule.span ℝ 𝒜 = ⊤ → 1 ≤ kdim ℬ → Function.Surjective e →
      (∀ {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P] (T : ℕ)
          (R : GRun d Ω), 2 ≤ T → IsGIAFTRLRun P 𝒜 ℬ e T R →
          ∀ u ∈ 𝒜, gRegretVs P T R u ≤ c₀ * ((d : ℝ) * Real.sqrt T * Real.log T)) ∧
      (∀ (θ astar : Fin d → ℝ), setNorm 𝒜 θ ≤ 1 → astar ∈ 𝒜 →
        (∀ a ∈ 𝒜, a ≠ astar → astar ⬝ᵥ θ < a ⬝ᵥ θ) → IsSharp 𝒜 θ astar →
        ∃ J : ℝ, ∀ n : Measure (Fin d → ℝ), IsCtrAlloc ℬ θ astar n →
          ∃ M : ℝ, ∀ {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
            (T : ℕ) (C : ℝ) (R : GRun d Ω), 1 ≤ T → 0 ≤ C →
            IsGIAFTRLRun P 𝒜 ℬ e T R → IsCorruptedG P 𝒜 θ C T R →
            ∀ u ∈ 𝒜, gRegretVs P T R u ≤
              c₀ * (ctrCost θ astar n * d * Real.log T) + M +
                J * Real.sqrt C * Real.log (max (Real.exp 1) C)) := 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.2, Proposition 3.1, p. 25 (proof in Appendix G, pp. 123–190)

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