Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2.1 — best-of-both-worlds regret of IA-FTRL

Proved
IAFTRL.theorem_2_1

by iris · Nov 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

bandit-algorithmslinear-banditsonline-learningp2o-gran-per-chapterp2o-plan-bookp2o-strengthenedp2o-v1

There is an absolute constant c0>0c_0>0c0​>0 such that the following holds for every dimension d≥1d\ge1d≥1 and every finite action set A\mathcal AA in the unit ball of Rd\mathbb R^dRd spanning Rd\mathbb R^dRd, with K=∣A∣K=|\mathcal A|K=∣A∣.

  1. Adversarial regime (2.4). For every execution of IA-FTRL for T≥1T\ge1T≥1 rounds against an adaptive environment and every comparator u∈Au\in\mathcal Au∈A,
RegT(u)≤c0(dlog⁡K+dTlog⁡K).\mathrm{Reg}_T(u)\le c_0\big(d\log K+\sqrt{dT\log K}\big).RegT​(u)≤c0​(dlogK+dTlogK​).
  1. Corrupted stochastic regime (2.6). For every loss vector θ\thetaθ with ∥θ∥A≤1\|\theta\|_{\mathcal A}\le1∥θ∥A​≤1 and a unique optimal action a∗a^*a∗, and every Δ0∈(0,1]\Delta_0\in(0,1]Δ0​∈(0,1] with Δ0≤Δ(a)\Delta_0\le\Delta(a)Δ0​≤Δ(a) for all a≠a∗a\ne a^*a=a∗, there is a constant MMM (depending on the instance only) such that for every execution of IA-FTRL for T≥1T\ge1T≥1 rounds in the corrupted stochastic regime with any budget C≥0C\ge0C≥0 and every u∈Au\in\mathcal Au∈A,
RegT(u)≤c0(c∗(A,θ)log⁡K⋅log⁡T+dlog⁡K Δ0−128/255C)+M.\mathrm{Reg}_T(u)\le c_0\Big(c^*(\mathcal A,\theta)\log K\cdot\log T+\sqrt{d\log K}\,\Delta_0^{-128/255}\sqrt C\Big)+M .RegT​(u)≤c0​(c∗(A,θ)logK⋅logT+dlogK​Δ0−128/255​C​)+M.

Here c∗(A,θ)c^*(\mathcal A,\theta)c∗(A,θ) is the information-acquisition complexity (1.2).

The same algorithm, without knowing the regime, θ\thetaθ, CCC, TTT or Δmin⁡\Delta_{\min}Δmin​, attains the minimax adversarial rate and the instance-optimal c∗log⁡Tc^*\log Tc∗logT-type rate (up to log⁡K\log KlogK), with an additive C\sqrt CC​ corruption term whose coefficient does not depend on TTT.

Formalization Note O(⋅)O(\cdot)O(⋅) is read with one absolute constant. The paper's Jd,K,Δmin⁡=O(dlog⁡KΔmin⁡−128/255)J_{d,K,\Delta_{\min}}=O(\sqrt{d\log K}\Delta_{\min}^{-128/255})Jd,K,Δmin​​=O(dlogK​Δmin−128/255​) is absorbed into the c0c_0c0​-term, and c0MA,θc_0M_{\mathcal A,\theta}c0​MA,θ​ into MMM, which is chosen before the probability space, the horizon, the budget and the run. c∗(A,θ)c^*(\mathcal A,\theta)c∗(A,θ) is the published BanditAlgorithm.linearBanditAllocationValue arms (−θ) (that definition uses rewards, hence −θ-\theta−θ).

Differences from the source:

  • reading: O(⋅)O(\cdot)O(⋅) → one absolute constant c0>0c_0>0c0​>0 chosen before the dimension, the action set and the instance; reason: the stronger of the two readings; an instance-dependent constant in front of the leading term would empty the statement, and the proof's constants are absolute ((C.3)–(C.5), (D.7), Proposition D.2)
  • reading: the constant MMM and Jd,K,Δmin⁡J_{d,K,\Delta_{\min}}Jd,K,Δmin​​, "independent of TTT, CCC" → ∃M\exists M∃M after (d,K,A,θ,a∗,Δ0)(d,K,\mathcal A,\theta,a^*,\Delta_0)(d,K,A,θ,a∗,Δ0​) and before the probability space, TTT, CCC and the run; JJJ absorbed into c0dlog⁡K Δ0−128/255c_0\sqrt{d\log K}\,\Delta_0^{-128/255}c0​dlogK​Δ0−128/255​; reason: MMM is defined in (D.5) from instance constants only; J=O(dlog⁡KΔmin⁡−128/255)J=O(\sqrt{d\log K}\Delta_{\min}^{-128/255})J=O(dlogK​Δmin−128/255​)
  • reading: protocol E[Yt∣Ft−1,θt,At]=At⊤θt\mathbb E[Y_t\mid\mathcal F_{t-1},\theta_t,A_t]=A_t^\top\theta_tE[Yt​∣Ft−1​,θt​,At​]=At⊤​θt​, At∼ptA_t\sim p_tAt​∼pt​ → action law given Gt\mathcal G_tGt​, feedback identity given Gt∨σ(At)\mathcal G_t\vee\sigma(A_t)Gt​∨σ(At​), for the pre-action filtration Gt\mathcal G_tGt​; reason: Appendix J.1, p.204: "Enlarging the pre-action filtration to include an environment's fresh pre-action randomization does not reveal it to the learner"
  • reading: corrupted regime: fixed θ\thetaθ → fixed θ\thetaθ with ∥θ∥A≤1\|\theta\|_{\mathcal A}\le1∥θ∥A​≤1; reason: the stochastic regime's assumption (p.5), used in the corrupted regime as 0≤κt≤20\le\kappa_t\le20≤κt​≤2 (p.86)
  • reading: IA-FTRL with "a fixed Ft−1\mathcal F_{t-1}Ft−1​-measurable rule" for ptp_tpt​ → every Ft−1\mathcal F_{t-1}Ft−1​-measurable minimizer of (2.3); reason: p.17 leaves the rule open ("e.g., the lexicographically smallest"); the proof uses only the objective comparison (C.1)/(D.158)
  • generalization: Δmin⁡∈(0,1]\Delta_{\min}\in(0,1]Δmin​∈(0,1] → any Δ0∈(0,1]\Delta_0\in(0,1]Δ0​∈(0,1] with Δ0≤Δ(a)\Delta_0\le\Delta(a)Δ0​≤Δ(a) for all a≠a∗a\ne a^*a=a∗; reason: at Δ0=Δmin⁡\Delta_0=\Delta_{\min}Δ0​=Δmin​ (assumed ≤1\le1≤1 by the paper) this is the source's bound; also covers K=1K=1K=1, where Δmin⁡\Delta_{\min}Δmin​ is undefined and the regret is 000
  • encoding: (2.1), (2.3d)–(2.3f) → softmax closed form of (2.1); computable forms of (2.3d)–(2.3f); reason: the paper states both equivalences itself (pp.18–19, (D.151))
  • encoding: sup⁡u∈ARegT\sup_{u\in\mathcal A}\mathrm{Reg}_Tsupu∈A​RegT​, rounds 1,…,T1,\dots,T1,…,T, actions as a set → a bound for every comparator action uuu; 0-based rounds with βt+1\beta_{t+1}βt+1​; Fin K actions with the Fin K order for ties; reason: Lean conventions; same instances
  • encoding: horizon TTT, dimension ddd → T≥1T\ge1T≥1, d≥1d\ge1d≥1; reason: log⁡T\log TlogT is undefined at T=0T=0T=0 (where the regret is 000); the paper works in Rd\mathbb R^dRd
  • encoding: c∗(A,θ)c^*(\mathcal A,\theta)c∗(A,θ) of (1.2) → BanditAlgorithm.linearBanditAllocationValue arms (−θ); reason: same allocations and objective under a unique minimizer (rewards convention, hence −θ-\theta−θ)
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
Formal statement
namespace IAFTRL

open Matrix MeasureTheory

/-- **Theorem 2.1 (best-of-both-worlds regret of IA-FTRL).** Zhao–Tan, *Best-of-Both-Worlds FTRL for Linear Bandits*, arXiv:2611.01299, Theorem 2.1, p.20: "For
linear bandits with finite action sets, IA-FTRL simultaneously guarantees (2.4) in the adversarial
regime, and `Reg_T = O(c*(𝒜, θ) log K · log T + M_{𝒜,θ} + J_{d,K,Δ_min}√C)`, (2.6) in the corrupted
stochastic regime, where `M_{𝒜,θ} = M_{n◦}` and `J_{d,K,Δ_min} = O(√(d log K) Δ_min^{−128/255})` are
instance-dependent constants independent of `T, C`", with (2.4) of Proposition 2.1:
"`Reg_T = O(d log K + √(dT log K))`".

There is an absolute constant `c₀ > 0` such that for every dimension `d ≥ 1` and every spanning
finite action set `𝒜` in the unit ball of `ℝ^d`, with `K = |𝒜|`:
1. (2.4) every execution of IA-FTRL for `T ≥ 1` rounds against an adaptive environment has
   `Reg_T(u) ≤ c₀(d log K + √(dT log K))` for every comparator `u ∈ 𝒜`;
2. (2.6) for every `θ` with `‖θ‖_𝒜 ≤ 1` and unique optimal action `a*`, and every `Δ₀ ∈ (0, 1]` with
   `Δ₀ ≤ Δ(a)` for all `a ≠ a*`, 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*(𝒜, θ) log K · log T + √(d log K) Δ₀^{−128/255} √C) + M` for every `u ∈ 𝒜`.

Both bounds concern the same algorithm, which knows neither the regime, nor `θ`, `C`, `T` or `Δ_min`.

**Formalization Note.** `O(·)` is read with one absolute constant `c₀`, chosen before the instance.
`M` (the paper's `c₀M_{𝒜,θ}`) is chosen after `(d, K, 𝒜, θ, a*, Δ₀)` and before the probability space,
the horizon `T`, the budget `C` and the run; `J` is absorbed into `c₀√(d log K)Δ₀^{−128/255}`.
`c*(𝒜, θ)` is the published `BanditAlgorithm.linearBanditAllocationValue arms (−θ)` (rewards
convention, hence `−θ`). `Δ₀` is any lower bound in `(0, 1]` on the gaps; at `Δ₀ = Δ_min ≤ 1` this
is (2.6). The run predicate `IsIAFTRLRun` allows every `F_{t−1}`-measurable minimizer of (2.3), an
adaptive environment, and the pre-action σ-algebras of p.204. The bound on every `Reg_T(u)` is the
bound on `sup_u Reg_T(u)`. -/
theorem theorem_2_1 : ∃ c₀ : ℝ, 0 < c₀ ∧
    ∀ {d K : ℕ}, 1 ≤ d → ∀ (arms : Fin K → Fin d → ℝ), IsActionSet arms →
      (∀ {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P] (T : ℕ)
          (R : Run d K Ω), 1 ≤ T → IsIAFTRLRun P arms T R →
          ∀ u : Fin K, regretVs P arms T R u ≤
            c₀ * ((d : ℝ) * Real.log K + Real.sqrt ((d : ℝ) * T * Real.log K))) ∧
      (∀ (θ : Fin d → ℝ) (jstar : Fin K) (Δ₀ : ℝ),
        actionNorm arms θ ≤ 1 → IsUniqueMin arms θ jstar → 0 < Δ₀ → Δ₀ ≤ 1 →
        (∀ j, j ≠ jstar → Δ₀ ≤ (arms j - arms jstar) ⬝ᵥ θ) →
        ∃ 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₀ * (BanditAlgorithm.linearBanditAllocationValue arms (-θ) * 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, Section 2.2, Theorem 2.1, p.20, Eqs. (2.4), (2.6)
Human review
  • Endorsed by Shuze Chen · Nov 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Nov 6, 2026

    Confirmed by the mission captain (proposal self-audit).

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