Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemmas C.13, C.14, C.24 (v1) — good events with empirical gap-ratio moments

Proved
IAFTRL.lemma_C_13_good_event

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

bandit-algorithmslinear-banditsonline-learning

This is the probabilistic core of the corrupted stochastic analysis of IA-FTRL, now with the empirical gap ratios that the exploration term needs. It extends IAFTRL.lemma_C_24_good_event (items 1–2 below) by the gap-ratio moment bounds of Definition C.12, Lemma C.13 and Lemma C.14, which live on the same good events.

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∗, gaps Δ(a)=(a−a∗)⊤θ\Delta(a)=(a-a^*)^\top\thetaΔ(a)=(a−a∗)⊤θ, and let Δ0∈(0,1]\Delta_0\in(0,1]Δ0​∈(0,1] satisfy Δ0≤Δ(a)\Delta_0\le\Delta(a)Δ0​≤Δ(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θ^s,Δ^t(a)=min⁡{2, Zt,at+1}X_{t,a}=(a-a^*)^\top\sum_{s<t}\hat\theta_s ,\qquad \hat\Delta_{t}(a)=\min\Big\{2,\ \frac{Z_{t,a}}{t+1}\Big\}Xt,a​=(a−a∗)⊤s<t∑​θ^s​,Δ^t​(a)=min{2, t+1Zt,a​​}

for the estimated cumulative loss difference and the empirical gap (2.2) 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​,… and random variables Lt,UtL_t,U_tLt​,Ut​ such that, for all t<Tt<Tt<T:

  1. on GtG_tGt​: Xt,a≥4 (t+1)3/4X_{t,a}\ge4\,(t+1)^{3/4}Xt,a​≥4(t+1)3/4 for every a≠a∗a\ne a^*a=a∗;
  2. cR∑t<TP(Gtc)t+1≤c0dlog⁡K Δ0−128/255C+M\displaystyle 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+McR​t<T∑​t+1​P(Gtc​)​≤c0​dlogK​Δ0−128/255​C​+M;
  3. on GtG_tGt​: Lt≥1L_t\ge1Lt​≥1, Ut≥0U_t\ge0Ut​≥0, (t+1)Δ(a)≤LtXt,a(t+1)\Delta(a)\le L_tX_{t,a}(t+1)Δ(a)≤Lt​Xt,a​ for a≠a∗a\ne a^*a=a∗, and for every arm
Δ(a)≤Lt Δ^t(a),Δ^t(a)≤Ut Δ(a);\Delta(a)\le L_t\,\hat\Delta_t(a),\qquad \hat\Delta_t(a)\le U_t\,\Delta(a);Δ(a)≤Lt​Δ^t​(a),Δ^t​(a)≤Ut​Δ(a);
  1. E[1GtLt8]≤c0E[\mathbf 1_{G_t}L_t^8]\le c_0E[1Gt​​Lt8​]≤c0​;
  2. E[1GtLtUt]≤ME[\mathbf 1_{G_t}L_tU_t]\le ME[1Gt​​Lt​Ut​]≤M;
  3. ∑t<TE[1GtLt3Ut]t+1≤c0 (1+log⁡T)+M\displaystyle\sum_{t<T}\frac{E[\mathbf 1_{G_t}L_t^3U_t]}{t+1}\le c_0\,(1+\log T)+Mt<T∑​t+1E[1Gt​​Lt3​Ut​]​≤c0​(1+logT)+M,

where all three random variables in 4–6 are integrable.

In the source, Lt=max⁡{1,max⁡a≠a∗tΔ(a)/Xt,a}L_t=\max\{1,\max_{a\ne a^*}t\Delta(a)/X_{t,a}\}Lt​=max{1,maxa=a∗​tΔ(a)/Xt,a​} and Ut=max⁡a≠a∗Δ^t(a)/Δ(a)U_t=\max_{a\ne a^*}\hat\Delta_t(a)/\Delta(a)Ut​=maxa=a∗​Δ^t​(a)/Δ(a) on GtG_tGt​ (Definition C.12). Lemma C.13 gives ∥1GtLt∥P≤25\|\mathbf 1_{G_t}L_t\|_P\le25∥1Gt​​Lt​∥P​≤25, E[1GtLtUt]≤400ΨtE[\mathbf 1_{G_t}L_tU_t]\le400\Psi_tE[1Gt​​Lt​Ut​]≤400Ψt​, E[1GtLt3Ut]≤250000ΨtE[\mathbf 1_{G_t}L_t^3U_t]\le250000\Psi_tE[1Gt​​Lt3​Ut​]≤250000Ψt​, and the two gap comparisons. Lemma C.14 gives Ψt≤ΨΔmin⁡\Psi_t\le\Psi_{\Delta_{\min}}Ψt​≤ΨΔmin​​ and ∑t≥T∘(Ψt−1)/t≤3A0Δmin⁡−ε0\sum_{t\ge T_\circ}(\Psi_t-1)/t\le3A_0\Delta_{\min}^{-\varepsilon_0}∑t≥T∘​​(Ψt​−1)/t≤3A0​Δmin−ε0​​. The good events are empty before T∘T_\circT∘​.

Together with the feasibility of the comparison law built from nnn (Lemma C.10, already proved), these bounds turn the exploration term into O(B cnlog⁡T)O(B\,c^n\log T)O(BcnlogT) plus instance constants plus O(C)O(\sqrt C)O(C​) (Lemmas C.6 and C.9).

Formalization Note Rounds are 0-based (Lean round ttt is the paper's round t+1t+1t+1), so Δ^t\hat\Delta_tΔ^t​ is gapHat arms (t + 1) (R.cumEst arms t ω). Item 4 follows from ∥1GtLt∥P≤25\|\mathbf 1_{G_t}L_t\|_P\le25∥1Gt​​Lt​∥P​≤25 with P≥512≥8P\ge512\ge8P≥512≥8 (Lyapunov), so c0≥258c_0\ge25^8c0​≥258. Item 5 uses 400Ψt≤400ΨΔmin⁡400\Psi_t\le400\Psi_{\Delta_{\min}}400Ψt​≤400ΨΔmin​​. Item 6 uses 250000∑t≤TΨt/t≤250000(log⁡(eT)+3A0Δmin⁡−ε0)250000\sum_{t\le T}\Psi_t/t\le250000(\log(eT)+3A_0\Delta_{\min}^{-\varepsilon_0})250000∑t≤T​Ψt​/t≤250000(log(eT)+3A0​Δmin−ε0​​). The separation exponent α=3/4+13/(10P)\alpha=3/4+13/(10P)α=3/4+13/(10P) is relaxed to 3/43/43/4. Items 1–2 are exactly the conclusion of IAFTRL.lemma_C_24_good_event. They are restated because the ratios must live on the same events. For K=1K=1K=1, take Gt=ΩG_t=\OmegaGt​=Ω, Lt=1L_t=1Lt​=1, Ut=0U_t=0Ut​=0.

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_cR
import Definitions.Def_IAFTRL_gapHat
import Definitions.Def_IAFTRL_Run_cumEst
Formal statement
namespace IAFTRL

open Matrix MeasureTheory

/-- **Predictable good events with empirical gap-ratio moments.** 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 good events, their separation and their weighted failure sum), Definition C.12 and Lemma C.13
("For `t ≥ T◦`, `‖1_{G_t}L_t‖_P ≤ 25`, `E[1_{G_t}L_tU_t] ≤ 400Ψ_t`, `E[1_{G_t}L_t³U_t] ≤ 250000Ψ_t` …
On `G_t`, `Δ(a) ≤ L_tΔ̂_t(a) ≤ L_tU_tΔ(a)` for every arm"), and Lemma C.14
(`Ψ_t ≤ Ψ_{Δmin}`, `Σ_{t≥T◦}(Ψ_t − 1)/t ≤ 3A₀Δ_min^{-ε₀}`), with `G_t = ∅` for `t < T◦`.

For every instance of the corrupted stochastic regime there are measurable events `G_t` (Lean round
`t`, paper round `t + 1`) and random variables `L_t, U_t` (the gap ratios
`L_t = max{1, max_{a≠a*} tΔ(a)/X_{t,a}}`, `U_t = max_{a≠a*} Δ̂_t(a)/Δ(a)` of Definition C.12) such that:
1. on `G_t`, `X_{t,a} = (a − a*)^⊤ Σ_{s<t} θ̂_s ≥ 4(t + 1)^{3/4}` for `a ≠ a*`;
2. `c_R Σ_{t<T} P(G_t^c)/√(t+1) ≤ c₀ √(d log K) Δ₀^{-128/255} √C + M`;
3. on `G_t`, `L_t ≥ 1`, `U_t ≥ 0`, `(t+1)Δ(a) ≤ L_t X_{t,a}` for `a ≠ a*`, and, for every arm,
   `Δ(a) ≤ L_t Δ̂(a)` and `Δ̂(a) ≤ U_t Δ(a)` (with `Δ̂ = Δ̂_{t+1}` at the cumulative estimate);
4. `E[1_{G_t} L_t^8] ≤ c₀`;
5. `E[1_{G_t} L_t U_t] ≤ M`;
6. `Σ_{t<T} E[1_{G_t} L_t³ U_t]/(t+1) ≤ c₀ (1 + log T) + 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 and ratios are chosen after the run. Item 4 is
`‖1_{G_t}L_t‖_P ≤ 25` with `P ≥ 512 ≥ 8` (Lyapunov). Item 5 is `400Ψ_t ≤ 400Ψ_{Δmin}`. Item 6 is
`250000 Σ_{t ≤ T} Ψ_t/t ≤ 250000(log(eT) + 3A₀Δ_min^{-ε₀})`. Items 1–2 are those of
`IAFTRL.lemma_C_24_good_event` (separation exponent `3/4 ≤ α`); they are restated because the gap
ratios live on the same events. For `K = 1` take `G_t = Ω`, `L_t = 1`, `U_t = 0`. -/
theorem lemma_C_13_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 Ω) (L U : ℕ → Ω → ℝ), (∀ 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 ∧
            (∀ t < T, ∀ ω ∈ G t, 1 ≤ L t ω ∧ 0 ≤ U t ω ∧
              (∀ a, a ≠ jstar → (t + 1 : ℝ) * ((arms a - arms jstar) ⬝ᵥ θ) ≤
                L t ω * ((arms a - arms jstar) ⬝ᵥ R.cumEst arms t ω)) ∧
              ∀ a, (arms a - arms jstar) ⬝ᵥ θ ≤
                  L t ω * gapHat arms (t + 1) (R.cumEst arms t ω) a ∧
                gapHat arms (t + 1) (R.cumEst arms t ω) a ≤
                  U t ω * ((arms a - arms jstar) ⬝ᵥ θ)) ∧
            (∀ t < T, Integrable ((G t).indicator fun ω => L t ω ^ 8) P ∧
              ∫ ω, (G t).indicator (fun ω => L t ω ^ 8) ω ∂P ≤ c₀) ∧
            (∀ t < T, Integrable ((G t).indicator fun ω => L t ω * U t ω) P ∧
              ∫ ω, (G t).indicator (fun ω => L t ω * U t ω) ω ∂P ≤ M) ∧
            (∀ t < T, Integrable ((G t).indicator fun ω => L t ω ^ 3 * U t ω) P) ∧
            ∑ t ∈ Finset.range T,
                (∫ ω, (G t).indicator (fun ω => L t ω ^ 3 * U t ω) ω ∂P) / (t + 1) ≤
              c₀ * (1 + Real.log T) + M := by sorry

end IAFTRL
Source
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits, arXiv:2611.01299v1, Definition C.12 and Lemma C.13 (p.65–66), Lemma C.14 (p.67), Definition C.25 and Lemma C.26 (p.81), Lemma C.24 (p.77), (C.4)

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