Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition G.2 — all-history adversarial guarantee of GIA-FTRL

Proved
IAFTRL.proposition_G_2

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, definition IAFTRL_GIAFTRL) 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 K≥1k=\dim\mathrm{aff}\,\mathcal K\ge1k=dimaffK≥1 for K=Conv(B)\mathcal K=\mathrm{Conv}(\mathcal B)K=Conv(B), and with a surjective enumeration eee of Qd\mathbb Q^dQd.
  • The run lasts T≥1T\ge1T≥1 rounds against an adaptive environment: θt\theta_tθt​ is predictable, ∥θt∥A≤1\|\theta_t\|_{\mathcal A}\le1∥θt​∥A​≤1, ∣Yt∣≤1|Y_t|\le1∣Yt​∣≤1, and E[Yt∣⋅]=At⊤θt\mathbb E[Y_t\mid\cdot]=A_t^\top\theta_tE[Yt​∣⋅]=At⊤​θt​.

Claim. For every comparator u∈Ku\in\mathcal Ku∈K,

RegT(u)=E[∑t<T(At−u)⊤θt]≤320(d+1)T log⁡(eT).\mathrm{Reg}_T(u)=\mathbb E\Big[\sum_{t<T}(A_t-u)^\top\theta_t\Big]\le 320(d+1)\sqrt T\,\log(eT).RegT​(u)=E[t<T∑​(At​−u)⊤θt​]≤320(d+1)T​log(eT).

No sharpness is assumed.

Proof outline (Appendix G.6.3).

  1. Use the potential Fβ(S)=−βlog⁡∫e−S/βdμ=inf⁡q{⟨q,S⟩+βDKL(q,μ)}F_\beta(S)=-\beta\log\int e^{-S/\beta}d\mu=\inf_q\{\langle q,S\rangle+\beta D_{\mathrm{KL}}(q,\mu)\}Fβ​(S)=−βlog∫e−S/βdμ=infq​{⟨q,S⟩+βDKL​(q,μ)} (Lemma J.2). It telescopes as in (G.218)–(G.225), with a deterministic comparison law qu,Tq_{u,T}qu,T​ satisfying DKL(qu,T,μ)≤log⁡2+16klog⁡TD_{\mathrm{KL}}(q_{u,T},\mu)\le\log2+16k\log TDKL​(qu,T​,μ)≤log2+16klogT and ∣(∫x dqu,T−u)⊤ϑ∣≤2/T|(\int x\,dq_{u,T}-u)^\top\vartheta|\le2/T∣(∫xdqu,T​−u)⊤ϑ∣≤2/T (Lemma G.11).
  2. Bound the per-round term by Et−1[Dt]≤Ct(pt)≤2d/βt\mathbb E_{t-1}[D_t]\le C_t(p_t)\le2d/\beta_tEt−1​[Dt​]≤Ct​(pt​)≤2d/βt​, using the proxy constraint (3.7) and Lemma J.4.
  3. Bound the exploration term by ⟨pt−qt,x⊤θt⟩≤8d/βt\langle p_t-q_t,x^\top\theta_t\rangle\le8d/\beta_t⟨pt​−qt​,x⊤θt​⟩≤8d/βt​, using marginal domination.
  4. Use unbiasedness of the reconstruction.
  5. Sum the schedule with βt=16d+t\beta_t=16d+\sqrt tβt​=16d+t​.
Preamble
import Mathlib
import Definitions.Def_IAFTRL_LinEnv
import Definitions.Def_IAFTRL_GIAFTRL
Formal statement
namespace IAFTRL

open MeasureTheory

/-- **Proposition G.2 (All-history adversarial guarantee).** Zhao–Tan, *Best-of-Both-Worlds FTRL
for Linear Bandits* (STOC submission version), Proposition G.2, p.145: "GIA-FTRL obeys
`Reg_T ≤ U_SH(T) ≤ 320(d+1)√T log(eT)` for every predictable bounded-mean environment."

For every execution of GIA-FTRL on a compact generator `ℬ` of the compact action set
`𝒜 ⊆ 𝔹^d` (`span 𝒜 = ℝ^d`, `k = dim aff 𝒦 ≥ 1`, `e` an enumeration of `ℚ^d`) for `T ≥ 1` rounds
against an adaptive environment, and every comparator `u ∈ 𝒦 = Conv ℬ`,
`Reg_T(u) ≤ 320(d+1)√T log(eT)`. No sharpness is assumed. -/
theorem proposition_G_2 {d : ℕ} (hd : 1 ≤ d) (𝒜 ℬ : Set (Fin d → ℝ)) (e : ℕ → Fin d → ℚ)
    (h𝒜 : IsCompact 𝒜) (hℬ : IsCompact ℬ) (hgen : IsGenerator 𝒜 ℬ)
    (hball : ∀ a ∈ 𝒜, a ⬝ᵥ a ≤ 1) (hspan : Submodule.span ℝ 𝒜 = ⊤) (hk : 1 ≤ kdim ℬ)
    (he : Function.Surjective e) {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω)
    [IsProbabilityMeasure P] (T : ℕ) (R : GRun d Ω) (hT : 1 ≤ T) (hR : IsGIAFTRLRun P 𝒜 ℬ e T R)
    (u : Fin d → ℝ) (hu : u ∈ Kset ℬ) :
    gRegretVs P T R u ≤ 320 * ((d : ℝ) + 1) * Real.sqrt T * Real.log (Real.exp 1 * 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), Appendix G.6.3, Proposition G.2, pp. 145–147

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