Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma C.34 (v1) — the full-history scalar difference interface of IA-FTRL

Proved
IAFTRL.lemma_C_34_interface

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

bandit-algorithmslinear-banditsonline-learning

This lemma translates the constraints of the IA-FTRL program into conditional properties of the observed increments of the estimated cumulative loss differences. These are the only properties of the learner used by the scalar moment analysis of the source (Appendix C.6).

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. Consider an execution of IA-FTRL for TTT rounds against an adaptive environment. Round ttt has pre-action σ\sigmaσ-algebra Gt\mathcal G_tGt​, loss vector θt\theta_tθt​, sampling law ptp_tpt​, played action AtA_tAt​, feedback Yt∈[−1,1]Y_t\in[-1,1]Yt​∈[−1,1] and loss estimate θ^t=Yt M(pt)−1At\hat\theta_t=Y_t\,M(p_t)^{-1}A_tθ^t​=Yt​M(pt​)−1At​, where M(p)=∑bpb bb⊤M(p)=\sum_bp_b\,bb^\topM(p)=∑b​pb​bb⊤. Fix any action a∗a^*a∗, and write

Dt,a=(a−a∗)⊤θ^t,Zt,a=(a−rt)⊤∑s<tθ^s,D_{t,a}=(a-a^*)^\top\hat\theta_t ,\qquad Z_{t,a}=\Big(a-r_t\Big)^\top\sum_{s<t}\hat\theta_s ,Dt,a​=(a−a∗)⊤θ^t​,Zt,a​=(a−rt​)⊤s<t∑​θ^s​,

where rtr_trt​ is the action minimizing the cumulative estimate (the program's reference). Let βt=16d+dt/(1+log⁡K)\beta_t=16d+\sqrt{dt/(1+\log K)}βt​=16d+dt/(1+logK)​ and B=225⌈256+log⁡(2K)⌉B=2^{25}\lceil256+\log(2K)\rceilB=225⌈256+log(2K)⌉.

Claim. For every round ttt (paper indexing) and every action aaa:

  1. Dt,aD_{t,a}Dt,a​ is measurable with respect to Gt+1\mathcal G_{t+1}Gt+1​;
  2. E[Dt,a∣Gt]=(a−a∗)⊤θtE[D_{t,a}\mid\mathcal G_t]=(a-a^*)^\top\theta_tE[Dt,a​∣Gt​]=(a−a∗)⊤θt​ almost surely;
  3. ∣Dt,a∣≤2βt+(Zt,a+Zt,a∗)/B|D_{t,a}|\le2\beta_t+(Z_{t,a}+Z_{t,a^*})/B∣Dt,a​∣≤2βt​+(Zt,a​+Zt,a∗​)/B on every history;
  4. E[Dt,a2∣Gt]≤4βt+2(Zt,a2+Zt,a∗2)/(Bt)E[D_{t,a}^2\mid\mathcal G_t]\le4\beta_t+2(Z_{t,a}^2+Z_{t,a^*}^2)/(Bt)E[Dt,a2​∣Gt​]≤4βt​+2(Zt,a2​+Zt,a∗2​)/(Bt) almost surely.

Item 2 is the difference unbiasedness of the executed reconstruction: ∑bpt,bvt,bb⊤=Id\sum_bp_{t,b}v_{t,b}b^\top=I_d∑b​pt,b​vt,b​b⊤=Id​, so E[gt,a−gt,b∣Gt]=(a−b)⊤θtE[g_{t,a}-g_{t,b}\mid\mathcal G_t]=(a-b)^\top\theta_tE[gt,a​−gt,b​∣Gt​]=(a−b)⊤θt​ for gt,a=(a−rt)⊤vt,AtYtg_{t,a}=(a-r_t)^\top v_{t,A_t}Y_tgt,a​=(a−rt​)⊤vt,At​​Yt​. Items 3 and 4 combine Dt,a=gt,a−gt,a∗D_{t,a}=g_{t,a}-g_{t,a^*}Dt,a​=gt,a​−gt,a∗​ with the update-magnitude and second-moment constraints (2.3d) and (2.3e) of the selected law. Together they are the interface (C.226)–(C.228) on which the source's good-event and moment analysis rests.

Formalization Note Rounds are 0-based (Lean round ttt is the paper's round t+1t+1t+1, so βt+1\beta_{t+1}βt+1​ and B(t+1)B(t+1)B(t+1) appear). Zt,aZ_{t,a}Zt,a​ is Zd arms (R.cumEst arms t ω) a. Conditional expectations are taken with respect to the pre-action σ\sigmaσ-algebra R.G t of IsIAFTRLRun. Measurability is also stated with respect to the ambient σ\sigmaσ-algebra.

Preamble
import Mathlib
import Definitions.Def_IAFTRL_IsActionSet
import Definitions.Def_IAFTRL_IsIAFTRLRun
import Definitions.Def_LinearBanditProtocol
import Definitions.Def_IAFTRL_Zd
import Definitions.Def_IAFTRL_beta
import Definitions.Def_IAFTRL_Bc
import Definitions.Def_IAFTRL_Run_cumEst
import Definitions.Def_IAFTRL_Run_thetaHat
Formal statement
namespace IAFTRL

open Matrix MeasureTheory

/-- **The full-history scalar difference interface of IA-FTRL.** Zhao–Tan, *Best-of-Both-Worlds FTRL
for Linear Bandits*, arXiv:2611.01299v1, Lemma C.34 ((C.226)–(C.228), (C.229)), from Lemma C.20
("`E_{t−1}[g_{t,a} − g_{t,b}] = (a − b)^⊤θ_t`, `E_{t−1}[g²_{t,a}] ≤ V_{t,a}`, `|g_{t,a}| ≤ U_{t,a}`") and
Lemma C.18: for any fixed action `a*`, the increments `D_{t,a} = g_{t,a} − g_{t,a*} = (a − a*)^⊤ θ̂_t` of
the estimated cumulative loss differences satisfy, for every round of an IA-FTRL run,
1. `D_{t,a}` is measurable after the round (w.r.t. the next pre-action σ-algebra and the ambient one);
2. `E[D_{t,a} | G_t] = (a − a*)^⊤ θ_t` (difference unbiasedness, (C.229a));
3. `|D_{t,a}| ≤ 2β_t + (Z_{t,a} + Z_{t,a*})/B` (update magnitude, (C.229b)–(C.229c));
4. `E[D²_{t,a} | G_t] ≤ 4β_t + 2(Z²_{t,a} + Z²_{t,a*})/(Bt)` (second moment, (C.229d)–(C.229f)),
where `Z_{t,a} = Zd arms (Σ_{s<t} θ̂_s) a` is the program's reference gap and `G_t` the pre-action
σ-algebra.

**Formalization Note.** Rounds are 0-based: Lean round `t` is the paper's round `t + 1`, so `β_{t+1}`
and `B(t + 1)` appear. `M_t = Z_{t,a*}` in the source's notation. The identities hold for every
fixed `a*` (no optimality is used). Item 2 uses `P(A_t = b | G_t) = p_{t,b}`,
`E[Y_t | G_t ∨ σ(A_t)] = A_t^⊤θ_t` and `Σ_b p_{t,b} v_{t,b} b^⊤ = I_d` (the design matrix of a feasible
`p_t` is invertible on a spanning action set); items 3–4 use `|Y_t| ≤ 1` and the constraints
(2.3d)–(2.3e) of the selected law. -/
theorem lemma_C_34_interface {d K : ℕ} (hd : 1 ≤ d) (arms : Fin K → Fin d → ℝ)
    (hA : IsActionSet arms) (jstar : Fin K) {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω)
    [IsProbabilityMeasure P] (T : ℕ) (R : Run d K Ω) (hR : IsIAFTRLRun P arms T R) :
    ∀ t < T, ∀ a : Fin K,
      (Measurable[R.G (t + 1)] (fun ω => (arms a - arms jstar) ⬝ᵥ R.thetaHat arms t ω) ∧
        Measurable (fun ω => (arms a - arms jstar) ⬝ᵥ R.thetaHat arms t ω)) ∧
      P[fun ω => (arms a - arms jstar) ⬝ᵥ R.thetaHat arms t ω | R.G t] =ᵐ[P]
        (fun ω => (arms a - arms jstar) ⬝ᵥ R.θs t ω) ∧
      (∀ ω, |(arms a - arms jstar) ⬝ᵥ R.thetaHat arms t ω| ≤ 2 * beta d K (t + 1) +
        (Zd arms (R.cumEst arms t ω) a + Zd arms (R.cumEst arms t ω) jstar) / Bc K) ∧
      P[fun ω => ((arms a - arms jstar) ⬝ᵥ R.thetaHat arms t ω) ^ 2 | R.G t] ≤ᵐ[P]
        (fun ω => 4 * beta d K (t + 1) + 2 * (Zd arms (R.cumEst arms t ω) a ^ 2 +
          Zd arms (R.cumEst arms t ω) jstar ^ 2) / (Bc K * ((t : ℝ) + 1))) := by sorry

end IAFTRL
Source
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits, arXiv:2611.01299v1, Lemma C.34 ((C.226)–(C.229), p.87), Lemma C.20 and Lemma C.18 (p.71–73)

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