Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma D.15 — conditional identities of the executed loss-difference estimates

Proved
IAFTRL.lemma_D_15

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

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

Consider an execution of IA-FTRL for TTT rounds, a round t<Tt<Tt<T and actions a,ca,ca,c, and let

gt,a=(a−rt)⊤vt,AtYt.g_{t,a}=(a-r_t)^\top v_{t,A_t}Y_t .gt,a​=(a−rt​)⊤vt,At​​Yt​.

Then gt,ag_{t,a}gt,a​ and gt,a2g_{t,a}^2gt,a2​ are integrable and, with Et−1\mathbb E_{t-1}Et−1​ the conditional expectation given the pre-action σ-algebra Gt\mathcal G_tGt​,

Et−1[gt,a]=(a−rt)⊤θt,Et−1[gt,a−gt,c]=(a−c)⊤θt,\mathbb E_{t-1}[g_{t,a}]=(a-r_t)^\top\theta_t,\qquad \mathbb E_{t-1}[g_{t,a}-g_{t,c}]=(a-c)^\top\theta_t,Et−1​[gt,a​]=(a−rt​)⊤θt​,Et−1​[gt,a​−gt,c​]=(a−c)⊤θt​, Et−1[gt,a2]≤βt+Zt,a2Bt,∣gt,a∣≤βt+Zt,aB,\mathbb E_{t-1}[g_{t,a}^2]\le\beta_t+\frac{Z_{t,a}^2}{Bt},\qquad |g_{t,a}|\le\beta_t+\frac{Z_{t,a}}{B},Et−1​[gt,a2​]≤βt​+BtZt,a2​​,∣gt,a​∣≤βt​+BZt,a​​,

the first three almost surely and the last on every outcome.

The executed estimates are conditionally unbiased for the loss differences and obey the program's moment and magnitude budgets; these identities enter the regret decomposition and the moment analysis.

Formalization Note Rounds are 0-based: the Lean round ttt uses βt+1\beta_{t+1}βt+1​, Zt+1Z_{t+1}Zt+1​ and B(t+1)B(t+1)B(t+1). Since the right-hand sides are Ft−1\mathcal F_{t-1}Ft−1​-measurable, the identities given Ft−1\mathcal F_{t-1}Ft−1​ follow by the tower property.

Differences from the source:

  • reading: Et−1\mathbb E_{t-1}Et−1​ → conditional expectation given the pre-action σ-algebra Gt⊇Ft−1∨σ(θt)\mathcal G_t\supseteq\mathcal F_{t-1}\vee\sigma(\theta_t)Gt​⊇Ft−1​∨σ(θt​); reason: Appendix J.1 (p.204) enlarges the pre-action filtration; the right-hand sides are Ft−1\mathcal F_{t-1}Ft−1​-measurable, so this also gives the identities given Ft−1\mathcal F_{t-1}Ft−1​
  • encoding: conditional expectations → integrability of gt,ag_{t,a}gt,a​ and gt,a2g_{t,a}^2gt,a2​ added to the conclusion; reason: guards Lean's junk conditional expectation; true by Lemma D.1
  • 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​
Preamble
import Mathlib
import Definitions.Def_IAFTRL_IsActionSet
import Definitions.Def_IAFTRL_IsIAFTRLRun
import Definitions.Def_IAFTRL_Run_gEst
import Definitions.Def_IAFTRL_Bc
Formal statement
namespace IAFTRL

open Matrix MeasureTheory

/-- **Lemma D.15 (Executed reconstruction and conditional estimator identities).** Zhao–Tan, *Best-of-Both-Worlds FTRL for Linear Bandits*, arXiv:2611.01299,
Lemma D.15, p.88: "For IA-FTRL, define `g_{t,a} = (a − r_t)^⊤v_{t,A_t}Y_t`. Then
`E_{t−1}[g_{t,a}] = (a − r_t)^⊤θ_t`, `E_{t−1}[(g_{t,a} − g_{t,c})] = (a − c)^⊤θ_t`,
`E_{t−1}[g²_{t,a}] ≤ β_t + Z²_{t,a}/(Bt)`, `|g_{t,a}| ≤ β_t + Z_{t,a}/B`."

For every execution of IA-FTRL for `T` rounds (spanning finite action set in the unit ball of
`ℝ^d`, `d ≥ 1`), every round `t < T` (paper round `t + 1`) and all actions `a, c`, with
`g_{t,a} = (a − r_t)^⊤ v_{t,A_t} Y_t`:
1. `g_{t,a}` and `g²_{t,a}` are integrable;
2. `E[g_{t,a} | G_t] = (a − r_t)^⊤θ_t` a.s.;
3. `E[g_{t,a} − g_{t,c} | G_t] = (a − c)^⊤θ_t` a.s.;
4. `E[g²_{t,a} | G_t] ≤ β_{t+1} + Z²_{t+1,a}/(B(t+1))` a.s.;
5. `|g_{t,a}| ≤ β_{t+1} + Z_{t+1,a}/B` everywhere.

**Formalization Note.** `E_{t−1}` is conditioning on the pre-action σ-algebra `G_t` (p.204), which
contains `F_{t−1}` and `θ_t`. Since the right-hand sides are `F_{t−1}`-measurable, the identities
conditional on `F_{t−1}` follow by the tower property. Integrability is stated so that the
conditional expectations are not Mathlib's junk value. 0-based round `t` uses `β_{t+1}`,
`Z_{t+1}` and `B(t+1)`. -/
theorem lemma_D_15 {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) (t : ℕ) (ht : t < T) (a c : Fin K) :
    Integrable (R.gEst arms t a) P ∧ Integrable (fun ω => R.gEst arms t a ω ^ 2) P ∧
    P[R.gEst arms t a | R.G t] =ᵐ[P]
      (fun ω => (arms a - refArm arms (R.cumEst arms t ω)) ⬝ᵥ R.θs t ω) ∧
    P[fun ω => R.gEst arms t a ω - R.gEst arms t c ω | R.G t] =ᵐ[P]
      (fun ω => (arms a - arms c) ⬝ᵥ R.θs t ω) ∧
    P[fun ω => R.gEst arms t a ω ^ 2 | R.G t] ≤ᵐ[P]
      (fun ω => beta d K (t + 1) + Zd arms (R.cumEst arms t ω) a ^ 2 / (Bc K * (t + 1))) ∧
    ∀ ω, |R.gEst arms t a ω| ≤ beta d K (t + 1) + Zd arms (R.cumEst arms t ω) a / Bc K := by sorry

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