Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

GIA-FTRL corrupted analysis: exponential weights, relative entropy, mixability gap, and the four regret sums I₁–I₄

Definition
IAFTRL_GTerms

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

bandit-algorithmslinear-banditsonline-learning

This file names the four expectation sums in the corrupted analysis of GIA-FTRL, Appendix G.1.1, (G.3)–(G.5). A run's round ttt (counted from 000) is the paper's round t+1t+1t+1, played with βt+1=16d+t+1\beta_{t+1}=16d+\sqrt{t+1}βt+1​=16d+t+1​.

Definitions.

  • Exponential weights. qt+1=gq(t+1,St)q_{t+1}=\mathrm{gq}(t+1,S_t)qt+1​=gq(t+1,St​) is the exponential-weights law, with St=∑s<tθ^sS_t=\sum_{s<t}\hat\theta_sSt​=∑s<t​θ^s​.
  • Relative entropy. DKL(q,μ)=∫log⁡dqdμ dqD_{\mathrm{KL}}(q,\mu)=\int\log\frac{dq}{d\mu}\,dqDKL​(q,μ)=∫logdμdq​dq.
  • Prior cost. For an atom aaa of the reference measure μ\muμ, ha=log⁡(1/μ({a}))h_a=\log(1/\mu(\{a\}))ha​=log(1/μ({a})).
  • Mixability gap. Dt=⟨qt,f^t⟩+βtlog⁡⟨qt,e−f^t/βt⟩D_t=\langle q_t,\hat f_t\rangle+\beta_t\log\langle q_t,e^{-\hat f_t/\beta_t}\rangleDt​=⟨qt​,f^​t​⟩+βt​log⟨qt​,e−f^​t​/βt​⟩, where f^t(x)=x⊤θ^t\hat f_t(x)=x^\top\hat\theta_tf^​t​(x)=x⊤θ^t​.

The four sums. Write Δ(x)=(x−a∗)⊤θ\Delta(x)=(x-a^*)^\top\thetaΔ(x)=(x−a∗)⊤θ and ctvec=θt−θc^{\mathrm{vec}}_t=\theta_t-\thetactvec​=θt​−θ.

I1=β1h∗+∑t=2T(βt−βt−1) E[h∗−DKL(qt,μ)],I2=∑t=1TE[Dt],I_1=\beta_1h^*+\sum_{t=2}^T(\beta_t-\beta_{t-1})\,\mathbb E[h^*-D_{\mathrm{KL}}(q_t,\mu)],\qquad I_2=\sum_{t=1}^T\mathbb E[D_t],I1​=β1​h∗+t=2∑T​(βt​−βt−1​)E[h∗−DKL​(qt​,μ)],I2​=t=1∑T​E[Dt​], I3=∑t=1TE[⟨pt−qt,Δ⟩],I4=∑t=1TE[⟨pt−qt,x⊤ctvec⟩].I_3=\sum_{t=1}^T\mathbb E[\langle p_t-q_t,\Delta\rangle],\qquad I_4=\sum_{t=1}^T\mathbb E[\langle p_t-q_t,x^\top c^{\mathrm{vec}}_t\rangle].I3​=t=1∑T​E[⟨pt​−qt​,Δ⟩],I4​=t=1∑T​E[⟨pt​−qt​,x⊤ctvec​⟩].
Definition code
import Mathlib
import Definitions.Def_IAFTRL_LinEnv
import Definitions.Def_IAFTRL_GIAFTRL

/-!
# The four regret terms of GIA-FTRL in the corrupted analysis

Zhao–Tan, *Best-of-Both-Worlds FTRL for Linear Bandits* (STOC submission version), Appendix G.1.1,
(G.3)–(G.5) and Lemmas G.1, G.4, G.5, G.9. Rounds of a run are `0`-based: the run's round `t`
is the paper's round `t + 1`, played with `β_{t+1}` and the exponential-weights law
`q_{t+1} = gq ℬ e (t + 1) (Σ_{s<t} θ̂_s)`.

* `GRun.qw`: the exponential-weights law `q_{t+1}`;
* `klDivR q μ = ∫ log (dq/dμ) dq`, the relative entropy `D_KL(q, μ)`;
* `hStar ℬ e a = log (1 / μ({a}))`, the prior cost of the atom `a`;
* `GRun.mixGap`: `D_t = ⟨q_t, f̂_t⟩ + β_t log ⟨q_t, e^{-f̂_t/β_t}⟩` with `f̂_t(x) = xᵀθ̂_t`;
* `penI1`, `stabI2`, `exploI3`, `corrI4`: the penalty, stability, exploration (under the fixed
  loss vector `θ`) and direct-corruption sums `I₁, I₂, I₃, I₄` of (G.3)–(G.5).
-/

open MeasureTheory

namespace IAFTRL

variable {d : ℕ}

/-- the exponential-weights law of run round `t` (paper round `t + 1`) -/
noncomputable def GRun.qw {Ω : Type*} (R : GRun d Ω) (ℬ : Set (Fin d → ℝ))
    (e : ℕ → Fin d → ℚ) (t : ℕ) (ω : Ω) : Measure (Fin d → ℝ) :=
  gq ℬ e (t + 1) (R.cumEst t ω)

/-- the relative entropy `D_KL(q, μ) = ∫ log (dq/dμ) dq` -/
noncomputable def klDivR (q μ : Measure (Fin d → ℝ)) : ℝ :=
  ∫ x, Real.log (q.rnDeriv μ x).toReal ∂q

/-- the prior cost `h_a = log (1 / μ({a}))` of an atom `a` of the reference measure -/
noncomputable def hStar (ℬ : Set (Fin d → ℝ)) (e : ℕ → Fin d → ℚ) (a : Fin d → ℝ) : ℝ :=
  Real.log (1 / (refMu ℬ e {a}).toReal)

/-- the mixability gap `D_t = ⟨q_t, f̂_t⟩ + β_t log ⟨q_t, e^{-f̂_t/β_t}⟩` -/
noncomputable def GRun.mixGap {Ω : Type*} (R : GRun d Ω) (ℬ : Set (Fin d → ℝ))
    (e : ℕ → Fin d → ℚ) (t : ℕ) (ω : Ω) : ℝ :=
  ∫ x, x ⬝ᵥ R.thetaHat t ω ∂(R.qw ℬ e t ω) +
    gbeta d (t + 1) * Real.log
      (∫ x, Real.exp (-(x ⬝ᵥ R.thetaHat t ω) / gbeta d (t + 1)) ∂(R.qw ℬ e t ω))

/-- the penalty sum `I₁ = β₁ h* + Σ_{t=2}^T (β_t − β_{t−1}) E[h* − D_KL(q_t, μ)]` -/
noncomputable def penI1 {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) (ℬ : Set (Fin d → ℝ))
    (e : ℕ → Fin d → ℚ) (T : ℕ) (R : GRun d Ω) (astar : Fin d → ℝ) : ℝ :=
  gbeta d 1 * hStar ℬ e astar + ∑ t ∈ Finset.Ico 1 T, (gbeta d (t + 1) - gbeta d t) *
    ∫ ω, (hStar ℬ e astar - klDivR (R.qw ℬ e t ω) (refMu ℬ e)) ∂P

/-- the stability sum `I₂ = Σ_t E[D_t]` -/
noncomputable def stabI2 {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) (ℬ : Set (Fin d → ℝ))
    (e : ℕ → Fin d → ℚ) (T : ℕ) (R : GRun d Ω) : ℝ :=
  ∑ t ∈ Finset.range T, ∫ ω, R.mixGap ℬ e t ω ∂P

/-- the exploration sum `I₃ = Σ_t E[⟨p_t − q_t, Δ⟩]`, `Δ(x) = (x − a*)ᵀθ` -/
noncomputable def exploI3 {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω)
    (ℬ : Set (Fin d → ℝ)) (e : ℕ → Fin d → ℚ) (T : ℕ) (R : GRun d Ω) (θ astar : Fin d → ℝ) :
    ℝ :=
  ∑ t ∈ Finset.range T, ∫ ω, (∫ x, (x - astar) ⬝ᵥ θ ∂(R.p t ω) -
    ∫ x, (x - astar) ⬝ᵥ θ ∂(R.qw ℬ e t ω)) ∂P

/-- the direct-corruption sum `I₄ = Σ_t E[⟨p_t − q_t, xᵀc_t⟩]`, `c_t = θ_t − θ` -/
noncomputable def corrI4 {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω)
    (ℬ : Set (Fin d → ℝ)) (e : ℕ → Fin d → ℚ) (T : ℕ) (R : GRun d Ω) (θ : Fin d → ℝ) : ℝ :=
  ∑ t ∈ Finset.range T, ∫ ω, (∫ x, x ⬝ᵥ (R.θs t ω - θ) ∂(R.p t ω) -
    ∫ x, x ⬝ᵥ (R.θs t ω - θ) ∂(R.qw ℬ e t ω)) ∂P

end IAFTRL
Source
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits: The Interplay of Information Acquisition, Corruption, and Geometry (STOC submission version; arXiv:2611.01299), Appendix G.1.1, (G.3)–(G.5); Lemmas G.1, G.4, G.5, G.9

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