Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma C.3 (second claim) — c∗(A,θ)≤2d/Δmin⁡c^*(\mathcal A,\theta)\le 2d/\Delta_{\min}c∗(A,θ)≤2d/Δmin​

Proved
IAFTRL.lemma_C_3_cstar_bound

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

bandit-algorithmslinear-banditsonline-learning

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 (d≥1d\ge1d≥1) that spans Rd\mathbb R^dRd. Let θ∈Rd\theta\in\mathbb R^dθ∈Rd have a unique minimizing action a∗a^*a∗, write Δ(a)=(a−a∗)⊤θ\Delta(a)=(a-a^*)^\top\thetaΔ(a)=(a−a∗)⊤θ for the loss gap, and let 0<Δ0≤Δ(a)0<\Delta_0\le\Delta(a)0<Δ0​≤Δ(a) for every a≠a∗a\ne a^*a=a∗. Then the information-acquisition complexity (1.2),

c∗(A,θ)=inf⁡n∈R≥0A{∑anaΔ(a)  :  Hn=∑anaaa⊤≻0, ∥a∥Hn−12≤Δ(a)22 ∀a≠a∗},c^*(\mathcal A,\theta)=\inf_{n\in\mathbb R_{\ge0}^{\mathcal A}}\Big\{\sum_a n_a\Delta(a)\;:\;H_n=\sum_a n_a aa^\top\succ0,\ \|a\|^2_{H_n^{-1}}\le\tfrac{\Delta(a)^2}{2}\ \forall a\ne a^*\Big\},c∗(A,θ)=n∈R≥0A​inf​{a∑​na​Δ(a):Hn​=a∑​na​aa⊤≻0, ∥a∥Hn−1​2​≤2Δ(a)2​ ∀a=a∗},

satisfies

c∗(A,θ)≤2dΔ0.c^*(\mathcal A,\theta)\le\frac{2d}{\Delta_0}.c∗(A,θ)≤Δ0​2d​.

At Δ0=Δmin⁡\Delta_0=\Delta_{\min}Δ0​=Δmin​ this is the bound c∗≤2dΔmin⁡−1c^*\le 2d\Delta_{\min}^{-1}c∗≤2dΔmin−1​: the instance-dependent leading constant of IA-FTRL is never worse than the classical d/Δmin⁡d/\Delta_{\min}d/Δmin​ rate.

Formalization Note This is the second conjunct of IAFTRL.lemma_C_3, with the same hypotheses; c∗(A,θ)c^*(\mathcal A,\theta)c∗(A,θ) is BanditAlgorithm.linearBanditAllocationValue arms (−θ) (rewards convention, so its gap at −θ-\theta−θ is the loss gap Δ\DeltaΔ).

Preamble
import Mathlib
import Definitions.Def_LinearBanditProtocol
import Definitions.Def_IAFTRL_IsActionSet
import Definitions.Def_IAFTRL_IsUniqueMin
Formal statement
namespace IAFTRL

open Matrix

/-- **Lemma C.3, second claim (`c* ≤ 2d/Δ_min`).** Zhao–Tan, *Best-of-Both-Worlds FTRL for Linear
Bandits*, arXiv:2611.01299, Lemma C.3, p.60: "Also `c* ≤ 2dΔ_min^{−1}`."

Same setting as `IAFTRL.lemma_C_3`: `𝒜 = {a_1, …, a_K}` a finite action set in the unit ball of `ℝ^d`
spanning `ℝ^d`, `θ` with a unique minimizing action `a* = a_{jstar}`, and `0 < Δ₀ ≤ Δ(a)` for all
`a ≠ a*`. Then `c*(𝒜, θ) ≤ 2d/Δ₀`.

**Formalization Note.** The second conjunct of `IAFTRL.lemma_C_3`, with the same hypotheses and
conventions (`c*` is `BanditAlgorithm.linearBanditAllocationValue arms (−θ)`). -/
theorem lemma_C_3_cstar_bound {d K : ℕ} (hd : 1 ≤ d) (arms : Fin K → Fin d → ℝ) (hA : IsActionSet arms)
    (θ : Fin d → ℝ) (jstar : Fin K) (hu : IsUniqueMin arms θ jstar) (Δ₀ : ℝ) (hΔ₀ : 0 < Δ₀)
    (hΔ : ∀ j, j ≠ jstar → Δ₀ ≤ (arms j - arms jstar) ⬝ᵥ θ) :
    BanditAlgorithm.linearBanditAllocationValue arms (-θ) ≤ 2 * (d : ℝ) / Δ₀ := by sorry

end IAFTRL
Source
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits, arXiv:2611.01299, Lemma C.3, p.60 (second sentence: "Also c* ≤ 2dΔ_min^{-1}")

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