Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma D.14 — direct corruption contribution ≤162 cRC\le16\sqrt2\,c_R\sqrt C≤162​cR​C​

Proved
IAFTRL.lemma_D_14

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

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

Consider an execution of IA-FTRL for TTT rounds in the corrupted stochastic regime with fixed loss vector θ\thetaθ (∥θ∥A≤1\|\theta\|_{\mathcal A}\le1∥θ∥A​≤1) and deterministic budget C≥0C\ge0C≥0, i.e. ∑t≤T∥θt−θ∥A≤C\sum_{t\le T}\|\theta_t-\theta\|_{\mathcal A}\le C∑t≤T​∥θt​−θ∥A​≤C almost surely. Let a∗a^*a∗ be an action, ctvec=θt−θc^{\mathrm{vec}}_t=\theta_t-\thetactvec​=θt​−θ, et,a=(a−a∗)⊤ctvece_{t,a}=(a-a^*)^\top c^{\mathrm{vec}}_tet,a​=(a−a∗)⊤ctvec​ and cR=dlog⁡(eK)c_R=\sqrt{d\log(eK)}cR​=dlog(eK)​. Then

I4:=∑t=1TE[⟨pt−qt,et⟩]≤∑t=1TE[∣∑a(pt,a−qt,a)a⊤ctvec∣]≤162 cRC.I_4:=\sum_{t=1}^T\mathbb E[\langle p_t-q_t,e_t\rangle]\le\sum_{t=1}^T\mathbb E\Big[\Big|\sum_a(p_{t,a}-q_{t,a})a^\top c^{\mathrm{vec}}_t\Big|\Big]\le16\sqrt2\,c_R\sqrt C .I4​:=t=1∑T​E[⟨pt​−qt​,et​⟩]≤t=1∑T​E[​a∑​(pt,a​−qt,a​)a⊤ctvec​​]≤162​cR​C​.

The exploration perturbation pt−qtp_t-q_tpt​−qt​ pays only O(dlog⁡KC)O(\sqrt{d\log K}\sqrt C)O(dlogK​C​) against an adaptive corruption, independently of TTT.

Formalization Note Rounds are 0-based; the Lean qtq_tqt​ is the paper's qt+1q_{t+1}qt+1​.

Differences from the source:

  • generalization: a∗a^*a∗ the unique optimal action → any action aj∗a_{j^*}aj∗​; reason: the bound uses only ∑a(pt,a−qt,a)=0\sum_a(p_{t,a}-q_{t,a})=0∑a​(pt,a​−qt,a​)=0; specializes to the source
  • 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
  • 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
  • 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: 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 lemma uses only feasibility of ptp_tpt​
  • 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)
Preamble
import Mathlib
import Definitions.Def_IAFTRL_IsActionSet
import Definitions.Def_IAFTRL_IsIAFTRLRun
import Definitions.Def_IAFTRL_IsCorrupted
import Definitions.Def_IAFTRL_cR
import Definitions.Def_IAFTRL_beta
import Definitions.Def_IAFTRL_qSoft
Formal statement
namespace IAFTRL

open Matrix MeasureTheory

/-- **Lemma D.14 (Direct corruption contribution).** Zhao–Tan, *Best-of-Both-Worlds FTRL for Linear Bandits*, arXiv:2611.01299, Lemma D.14, p.86: "For
`e_{t,a} = (a − a*)^⊤c^{vec}_t`,
`I_4 := Σ_{t=1}^T E[⟨p_t − q_t, e_t⟩] ≤ Σ_{t=1}^T E[|Σ_a (p_{t,a} − q_{t,a})a^⊤c^{vec}_t|] ≤ 16√2 c_R √C`."

For every execution of IA-FTRL for `T` rounds in the corrupted stochastic regime with fixed loss
vector `θ` (`‖θ‖_𝒜 ≤ 1`) and deterministic budget `C ≥ 0` (`Σ_{t<T} ‖θ_t − θ‖_𝒜 ≤ C` a.s.), every action
index `jstar`, with `c^{vec}_t = θ_t − θ` and `c_R = √(d log(eK))`:
`Σ_t E[⟨p_t − q_t, e_t⟩] ≤ Σ_t E[|Σ_a (p_{t,a} − q_{t,a})a^⊤c^{vec}_t|] ≤ 16√2 c_R √C`.

**Formalization Note.** Rounds are 0-based; the Lean `q_t` is the paper's `q_{t+1}`. The
inequalities hold for any reference index `jstar` (the paper's `a*`); uniqueness of `a*` is not used. -/
theorem lemma_D_14 {d K : ℕ} (hd : 1 ≤ d) (arms : Fin K → Fin d → ℝ) (hA : IsActionSet arms)
    {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P] (T : ℕ)
    (R : Run d K Ω) (hR : IsIAFTRLRun P arms T R) (θ : Fin d → ℝ) (jstar : Fin K) (C : ℝ)
    (hC : 0 ≤ C) (hcor : IsCorrupted P arms θ C T R) :
    let q : ℕ → Ω → Fin K → ℝ := fun t ω => qSoft (beta d K (t + 1)) arms (R.cumEst arms t ω)
    (∑ t ∈ Finset.range T,
        ∫ ω, ∑ a, (R.p t ω a - q t ω a) * ((arms a - arms jstar) ⬝ᵥ (R.θs t ω - θ)) ∂P) ≤
      ∑ t ∈ Finset.range T,
        ∫ ω, |∑ a, (R.p t ω a - q t ω a) * (arms a ⬝ᵥ (R.θs t ω - θ))| ∂P ∧
    (∑ t ∈ Finset.range T,
        ∫ ω, |∑ a, (R.p t ω a - q t ω a) * (arms a ⬝ᵥ (R.θs t ω - θ))| ∂P) ≤
      16 * Real.sqrt 2 * cR d K * Real.sqrt C := by sorry

end IAFTRL
Source
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits, arXiv:2611.01299, Appendix D.5, Lemma D.14, p.86
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