Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition D.2 — all-history adversarial guarantee

Proved
IAFTRL.proposition_D_2

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

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

Let A\mathcal AA be a finite action set in the unit ball of Rd\mathbb R^dRd (d≥1d\ge1d≥1) spanning Rd\mathbb R^dRd, with K=∣A∣K=|\mathcal A|K=∣A∣. For every execution of IA-FTRL for T≥1T\ge1T≥1 rounds against an adaptive environment and every comparator action u∈Au\in\mathcal Au∈A,

RegT(u)≤min⁡{2T, 16dlog⁡(eK)+21dTlog⁡(eK)}.\mathrm{Reg}_T(u)\le\min\Big\{2T,\ 16d\log(eK)+21\sqrt{dT\log(eK)}\Big\}.RegT​(u)≤min{2T, 16dlog(eK)+21dTlog(eK)​}.

Hence sup⁡u∈ARegT(u)\sup_{u\in\mathcal A}\mathrm{Reg}_T(u)supu∈A​RegT​(u) obeys the same bound. This is the adversarial half of Proposition 2.1, with explicit constants.

Formalization Note A bound for every comparator action is the bound on the supremum, which is taken outside the expectation (Appendix J.1).

Differences from the source:

  • encoding: sup⁡u∈ARegT(u)\sup_{u\in\mathcal A}\mathrm{Reg}_T(u)supu∈A​RegT​(u) → a bound on RegT(u)\mathrm{Reg}_T(u)RegT​(u) for every u∈Au\in\mathcal Au∈A; reason: finite A\mathcal AA; same statement
  • 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 bound uses only feasibility
  • 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"
  • encoding: dimension ddd of Rd\mathbb R^dRd → d≥1d\ge1d≥1; reason: the paper works in Rd\mathbb R^dRd with a spanning action set in the unit ball; only the degenerate d=0d=0d=0 is excluded
  • encoding: paper rounds t=1,…,Tt=1,\dots,Tt=1,…,T → 0-based Lean rounds t<Tt<Tt<T, Lean round ttt using βt+1\beta_{t+1}βt+1​, qt+1q_{t+1}qt+1​, Zt+1Z_{t+1}Zt+1​; reason: Lean indexing convention; same instances
Preamble
import Mathlib
import Definitions.Def_IAFTRL_IsActionSet
import Definitions.Def_IAFTRL_IsIAFTRLRun
import Definitions.Def_IAFTRL_regretVs
Formal statement
namespace IAFTRL

open Matrix MeasureTheory

/-- **Proposition D.2 (The all-history adversarial guarantee).** Zhao–Tan, *Best-of-Both-Worlds FTRL for Linear Bandits*, arXiv:2611.01299, Proposition D.2, p.67:
"IA-FTRL satisfies, for every `T ≥ 1`,
`sup_{u∈𝒜} Reg_T(u) ≤ min{2T, 16d log(eK) + 21√(dT log(eK))}`."

For every execution of IA-FTRL for `T ≥ 1` rounds against an adaptive environment (spanning finite
action set in the unit ball of `ℝ^d`, `d ≥ 1`) and every comparator action `u`:
`Reg_T(u) ≤ min{2T, 16d log(eK) + 21√(dT log(eK))}`.

**Formalization Note.** A bound on every `Reg_T(u)` is the bound on `sup_u Reg_T(u)` (finite
`𝒜`, supremum outside the expectation, p.204). -/
theorem proposition_D_2 {d K : ℕ} (hd : 1 ≤ d) (arms : Fin K → Fin d → ℝ)
    (hA : IsActionSet arms) {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω)
    [IsProbabilityMeasure P] (T : ℕ) (hT : 1 ≤ T) (R : Run d K Ω) (hR : IsIAFTRLRun P arms T R)
    (u : Fin K) :
    regretVs P arms T R u ≤
      min (2 * (T : ℝ)) (16 * (d : ℝ) * Real.log (Real.exp 1 * K) +
        21 * Real.sqrt ((d : ℝ) * T * Real.log (Real.exp 1 * K))) := by sorry

end IAFTRL
Source
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits, arXiv:2611.01299, Appendix D.1.3, Proposition D.2, p.67
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