Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemmas C.24–C.26 (v1) — predictable good events with separation and a C\sqrt CC​ weighted failure sum

Proved
IAFTRL.lemma_C_24_good_event

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

bandit-algorithmslinear-banditsonline-learning

This is the probabilistic core shared by the penalty, stability and exploration terms in the corrupted stochastic analysis of IA-FTRL. It combines the predictable good events of Definition C.25, their separation property (Lemma C.26), and their weighted failure sum (Lemma C.24 with (C.4)).

Setting. 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≤1\|\theta\|_{\mathcal A}\le1∥θ∥A​≤1 with a unique optimal action a∗a^*a∗, and let Δ0∈(0,1]\Delta_0\in(0,1]Δ0​∈(0,1] satisfy Δ0≤(a−a∗)⊤θ\Delta_0\le(a-a^*)^\top\thetaΔ0​≤(a−a∗)⊤θ for all a≠a∗a\ne a^*a=a∗. Consider an execution of IA-FTRL for T≥1T\ge1T≥1 rounds in the corrupted stochastic regime with budget C≥0C\ge0C≥0, with loss estimates θ^s\hat\theta_sθ^s​. Write

Xt,a=(a−a∗)⊤∑s<tθ^sX_{t,a}=(a-a^*)^\top\sum_{s<t}\hat\theta_sXt,a​=(a−a∗)⊤s<t∑​θ^s​

for the estimated cumulative loss difference before round t+1t+1t+1, and cR=dlog⁡(eK)c_R=\sqrt{d\log(eK)}cR​=dlog(eK)​.

Claim. There is an absolute constant c0>0c_0>0c0​>0 such that, for every such instance, there is a constant MMM (independent of TTT, CCC and the run) with the following property. Every run admits measurable events G0,G1,…G_0,G_1,\dotsG0​,G1​,… such that

  1. on GtG_tGt​, for every t<Tt<Tt<T, every suboptimal action is separated from a∗a^*a∗:
Xt,a≥4 (t+1)3/4(a≠a∗);X_{t,a}\ge4\,(t+1)^{3/4}\qquad(a\ne a^*);Xt,a​≥4(t+1)3/4(a=a∗);
  1. the weighted failure sum is controlled:
cR∑t<TP(Gtc)t+1≤c0dlog⁡K Δ0−128/255C+M.c_R\sum_{t<T}\frac{P(G_t^{c})}{\sqrt{t+1}}\le c_0\sqrt{d\log K}\,\Delta_0^{-128/255}\sqrt C+M .cR​t<T∑​t+1​P(Gtc​)​≤c0​dlogK​Δ0−128/255​C​+M.

On the good events the FTRL weights concentrate on a∗a^*a∗, so the entropy and proxy-function costs decay exponentially (Lemma C.22). Off them, every round costs O(cR/t)O(c_R/\sqrt t)O(cR​/t​). Hence this statement is what turns the penalty and stability terms into instance constants plus an O(C)O(\sqrt C)O(C​) corruption term.

Formalization Note Rounds are 0-based (Lean round ttt is the paper's round t+1t+1t+1). The source's separation exponent α=3/4+13/(10P)\alpha=3/4+13/(10P)α=3/4+13/(10P) is replaced by the smaller exponent 3/43/43/4, which suffices for Lemma C.22. The source's bound 2T∘+3A+130n0+2K56P+3ctailΔmin⁡−γ0n02\sqrt{T_\circ}+3A+130\sqrt{n_0}+2K56^P+3c_{\mathrm{tail}}\Delta_{\min}^{-\gamma_0}\sqrt{n_0}2T∘​​+3A+130n0​​+2K56P+3ctail​Δmin−γ0​​n0​​ becomes the displayed one via n0=max⁡{Nburn,⌈C⌉}n_0=\max\{N_{\mathrm{burn}},\lceil C\rceil\}n0​=max{Nburn​,⌈C⌉}, n0≤Nburn+C\sqrt{n_0}\le\sqrt{N_{\mathrm{burn}}}+\sqrt Cn0​​≤Nburn​​+C​, (C.4), γ0=128/255\gamma_0=128/255γ0​=128/255, Δmin⁡−1/2≤Δ0−128/255\Delta_{\min}^{-1/2}\le\Delta_0^{-128/255}Δmin−1/2​≤Δ0−128/255​ and cR≤3dlog⁡Kc_R\le\sqrt3\sqrt{d\log K}cR​≤3​dlogK​ for K≥2K\ge2K≥2. For K=1K=1K=1 there is no suboptimal action and Gt=ΩG_t=\OmegaGt​=Ω works.

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_beta
import Definitions.Def_IAFTRL_qSoft
import Definitions.Def_IAFTRL_proxyC
import Definitions.Def_IAFTRL_cR
import Definitions.Def_IAFTRL_Run_cumEst
Formal statement
namespace IAFTRL

open Matrix MeasureTheory

/-- **Predictable good events and their weighted failure sum.** Zhao–Tan, *Best-of-Both-Worlds FTRL
for Linear Bandits*, arXiv:2611.01299v1, Definition C.25, Lemma C.26 and Lemma C.24, with (C.4):
the predictable scalar good event `G_t` satisfies, "On `G_t`, `r_t = a*`, `M_t = 0`, and
`Z_{t,a} = X_{t,a} ≥ 4τ_t ≥ 4t^α (a ≠ a*)`" (Lemma C.26, `α = 3/4 + 13/(10P) ≥ 3/4`), and
"`Σ_{t≥1} t^{-1/2} P(G_t^c) ≤ 2√T_◦ + 3A + 130√n₀ + 2K56P + 3c_tail Δ_min^{-γ₀} √n₀`" (Lemma C.24),
where `n₀ = max{N_burn, ⌈C⌉}` and `√T_◦ ≤ √(Q+1) Δ_min^{-5/2} + 32 Δ_min^{-1/2} √n₀` (C.4).

For every instance of the corrupted stochastic regime there are measurable events `G_t` (Lean
round `t`, paper round `t + 1`) on which every suboptimal action's estimated cumulative loss
difference `X_{t,a} = (a − a*)^⊤ Σ_{s<t} θ̂_s` is at least `4(t + 1)^{3/4}`, and whose weighted failure
sum satisfies `c_R Σ_{t<T} P(G_t^c)/√(t+1) ≤ c₀ √(d log K) Δ₀^{-128/255} √C + M`.

**Formalization Note.** `c₀` is absolute; `M` is chosen after `(d, K, 𝒜, θ, a*, Δ₀)` and before the
probability space, `T`, `C` and the run; the events are chosen after the run. The separation is
stated with the exponent `3/4 ≤ α`. With `c_R = √(d log(eK)) ≤ √3 √(d log K)` for `K ≥ 2`,
`√n₀ ≤ √N_burn + √C` and `Δ_min^{-1/2}, Δ_min^{-γ₀} ≤ Δ₀^{-128/255}` (`γ₀ = 128/255`, `Δ₀ ≤ min(Δ_min, 1)`),
Lemma C.24 gives the displayed bound; for `K = 1` there is no suboptimal action and `G_t = Ω`. -/
theorem lemma_C_24_good_event : ∃ 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) ⬝ᵥ θ) →
        ∃ 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 →
          ∃ G : ℕ → Set Ω, (∀ t, MeasurableSet (G t)) ∧
            (∀ t < T, ∀ ω ∈ G t, ∀ a, a ≠ jstar →
              4 * (t + 1 : ℝ) ^ ((3 : ℝ) / 4) ≤ (arms a - arms jstar) ⬝ᵥ R.cumEst arms t ω) ∧
            cR d K * ∑ t ∈ Finset.range T, (P (G t)ᶜ).toReal / Real.sqrt (t + 1) ≤
              c₀ * (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.01299v1, Definition C.25 and Lemma C.26 (p.81), Lemma C.24 (p.77), (C.4) (p.50), (C.5e)–(C.7) (p.50)

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