Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.2(i) — information-acquisition lower bound on a sharp curve: cctr∗=8/τc^*_{\rm ctr}=8/\taucctr∗​=8/τ and lim inf⁡RegT/log⁡T≥7/(16τ)\liminf \mathrm{Reg}_T/\log T\ge 7/(16\tau)liminfRegT​/logT≥7/(16τ)

Proved
IAFTRL.theorem_3_2_i

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

bandit-algorithmslinear-banditsonline-learning

Setting. Let

Acurve={a(s)=(−12+s4, s+s24):0≤s≤1},θτ=(τ,0),0<τ≤1.\mathcal A_{\rm curve}=\Big\{a(s)=\Big(-\frac12+\frac s4,\ \frac{s+s^2}{4}\Big):0\le s\le1\Big\},\qquad \theta_\tau=(\tau,0),\quad 0<\tau\le1 .Acurve​={a(s)=(−21​+4s​, 4s+s2​):0≤s≤1},θτ​=(τ,0),0<τ≤1.

The unique optimal action of θτ\theta_\tauθτ​ is a(0)=(−12,0)a(0)=(-\tfrac12,0)a(0)=(−21​,0), with gap Δ(a(s))=τs/4\Delta(a(s))=\tau s/4Δ(a(s))=τs/4. The feedback is a sign observation of the linear mean: playing aaa yields Y∈{±1}Y\in\{\pm1\}Y∈{±1} with E[Y]=a⊤θ\mathbb E[Y]=a^\top\thetaE[Y]=a⊤θ (Proposition H.1). A policy is consistent if it plays only actions of Acurve\mathcal A_{\rm curve}Acurve​ and satisfies RegT,θ=o(Tα)\mathrm{Reg}_{T,\theta}=o(T^\alpha)RegT,θ​=o(Tα) for every α>0\alpha>0α>0 and every sharp stochastic instance θ\thetaθ on this curve, i.e. every θ\thetaθ with ∥θ∥A≤1\|\theta\|_{\mathcal A}\le1∥θ∥A​≤1, a unique optimal action, and geometric sharpness.

Claim. The centered information-acquisition complexity (1.4) of (Acurve,θτ)(\mathcal A_{\rm curve},\theta_\tau)(Acurve​,θτ​) is

cctr∗(Acurve,θτ)=8τ,c^*_{\rm ctr}(\mathcal A_{\rm curve},\theta_\tau)=\frac8\tau ,cctr∗​(Acurve​,θτ​)=τ8​,

and every consistent policy satisfies

lim inf⁡T→∞RegT,θτlog⁡T ≥ 716τ=7128 cctr∗(Acurve,θτ).\liminf_{T\to\infty}\frac{\mathrm{Reg}_{T,\theta_\tau}}{\log T}\ \ge\ \frac{7}{16\tau}=\frac{7}{128}\,c^*_{\rm ctr}(\mathcal A_{\rm curve},\theta_\tau).T→∞liminf​logTRegT,θτ​​​ ≥ 16τ7​=1287​cctr∗​(Acurve​,θτ​).

On this sharp curve the minimum positive gap is zero. The claim shows that the logarithmic term cctr∗log⁡Tc^*_{\rm ctr}\log Tcctr∗​logT in the upper bound of Theorem 3.1 cannot be improved beyond a constant factor.

Formalization Note cctr∗c^*_{\rm ctr}cctr∗​ is cstarCtr curve θ ![-1/2, 0]. The environment is signEnv θ, and consistency is IsConsistentOn curve (sharpInstances curve) π with IsSupportedLinearPolicy curve π. The lower limit is stated in its elementary form: for every ε>0\varepsilon>0ε>0, eventually (7/(16τ)−ε)log⁡T≤RegT,θτ(7/(16\tau)-\varepsilon)\log T\le\mathrm{Reg}_{T,\theta_\tau}(7/(16τ)−ε)logT≤RegT,θτ​​.

Preamble
import Mathlib
import Definitions.Def_LinearBanditProtocol
import Definitions.Def_IAFTRL_LinEnv
import Definitions.Def_IAFTRL_GIAFTRL
import Definitions.Def_IAFTRL_SignModel
Formal statement
namespace IAFTRL

open MeasureTheory ProbabilityTheory Matrix BanditAlgorithm Filter Topology

/-- **Theorem 3.2, first part (information-acquisition lower bound).** Zhao–Tan,
*Best-of-Both-Worlds FTRL for Linear Bandits* (STOC submission version), Theorem 3.2, p.25:
"On `A_curve = {(−1/2 + s/4, (s + s²)/4) : 0 ≤ s ≤ 1}`, `θ_τ = (τ, 0)` and `0 < τ ≤ 1`, we have
`c*_ctr = 8/τ`. Every consistent policy satisfies
`liminf_{T→∞} Reg_{T,θ_τ} / log T ≥ 7/(16τ) = (7/128) c*_ctr`."
The feedback model is that of Proposition H.1 (p.193): sign observations of the linear mean, and
consistency is on the sharp stochastic instances on this curve.

The optimal action of `θ_τ` is `a(0) = (−1/2, 0)`, which is the `a*` of `c*_ctr` in (1.4). The
lower limit is stated in its elementary form: for every `ε > 0`, eventually
`(7/(16τ) − ε) log T ≤ Reg_{T,θ_τ}`. -/
theorem theorem_3_2_i (τ : ℝ) (hτ : 0 < τ) (hτ1 : τ ≤ 1) :
    let curve : Set (Fin 2 → ℝ) := {a | ∃ s ∈ Set.Icc (0 : ℝ) 1, a = ![-1 / 2 + s / 4, (s + s ^ 2) / 4]}
    let θ : Fin 2 → ℝ := ![τ, 0]
    cstarCtr curve θ ![-1 / 2, 0] = 8 / τ ∧
    ∀ π : LinearBanditPolicy 2, IsSupportedLinearPolicy curve π →
      IsConsistentOn curve (sharpInstances curve) π →
      ∀ ε : ℝ, 0 < ε → ∀ᶠ T : ℕ in atTop,
        (7 / (16 * τ) - ε) * Real.log T ≤ (signEnv θ).regret curve π T := by sorry

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), Section 3.3, Theorem 3.2 (first bullet), p.25; proof in Appendix H.1, Proposition H.1 (H.3), pp.191–194

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