Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 2.1 (2.5), exploration term — ∑tE[⟨pt−qt,Δ⟩]\sum_t\mathbb E[\langle p_t-q_t,\Delta\rangle]∑t​E[⟨pt​−qt​,Δ⟩]

Proved
IAFTRL.proposition_2_1_exploration

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

bandit-algorithmslinear-banditsonline-learning

This is the exploration term I3I_3I3​ of the four-term decomposition behind the corrupted stochastic bound (2.5) of Proposition 2.1, and the term that carries the information-acquisition cost.

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. Let θ\thetaθ satisfy ∥θ∥A≤1\|\theta\|_{\mathcal A}\le1∥θ∥A​≤1 and have a unique optimal action a∗a^*a∗, write Δ(a)=(a−a∗)⊤θ\Delta(a)=(a-a^*)^\top\thetaΔ(a)=(a−a∗)⊤θ, and let Δ0∈(0,1]\Delta_0\in(0,1]Δ0​∈(0,1] satisfy Δ0≤Δ(a)\Delta_0\le\Delta(a)Δ0​≤Δ(a) for all a≠a∗a\ne a^*a=a∗. Let nnn be a feasible sampling allocation of (1.2), with cost cn(A,θ)=∑anaΔ(a)c^n(\mathcal A,\theta)=\sum_an_a\Delta(a)cn(A,θ)=∑a​na​Δ(a). Consider an execution of IA-FTRL for T≥1T\ge1T≥1 rounds in the corrupted stochastic regime with budget C≥0C\ge0C≥0, with sampling laws ptp_tpt​ and exponential weights qt∝exp⁡(−L^t−1/βt)q_t\propto\exp(-\hat L_{t-1}/\beta_t)qt​∝exp(−L^t−1​/βt​), where βt=16d+dt/(1+log⁡K)\beta_t=16d+\sqrt{dt/(1+\log K)}βt​=16d+dt/(1+logK)​.

There is an absolute constant c0>0c_0>0c0​>0 such that, for every such instance and allocation nnn, there is a constant MMM, independent of TTT, CCC and the run, with

I3:=∑t=1TE[⟨pt−qt,Δ⟩] ≤ c0(cn(A,θ)log⁡K⋅log⁡T+dlog⁡K Δ0−128/255C)+M.I_3:=\sum_{t=1}^T\mathbb E\big[\langle p_t-q_t,\Delta\rangle\big]\ \le\ c_0\Big(c^n(\mathcal A,\theta)\log K\cdot\log T+\sqrt{d\log K}\,\Delta_0^{-128/255}\sqrt C\Big)+M .I3​:=t=1∑T​E[⟨pt​−qt​,Δ⟩] ≤ c0​(cn(A,θ)logK⋅logT+dlogK​Δ0−128/255​C​)+M.

Here ⟨pt−qt,Δ⟩=∑a(pt,a−qt,a)Δ(a)\langle p_t-q_t,\Delta\rangle=\sum_a(p_{t,a}-q_{t,a})\Delta(a)⟨pt​−qt​,Δ⟩=∑a​(pt,a​−qt,a​)Δ(a) is the regret paid for exploring beyond the FTRL update. In the source, I3≤222Bcnlog⁡(eT)+M3,n+8cRETI_3\le2^{22}Bc^n\log(eT)+M_{3,n}+8c_RE_TI3​≤222Bcnlog(eT)+M3,n​+8cR​ET​ with B=2⌈256+log⁡(2K)⌉≤2048log⁡(eK)B=2\lceil256+\log(2K)\rceil\le2048\log(eK)B=2⌈256+log(2K)⌉≤2048log(eK). This rests on the objective comparison with a feasible distribution built from the allocation nnn after a horizon-independent burn-in.

Formalization Note The left-hand side is the corresponding term of the regret decomposition (D.167) (IAFTRL.lemma_D_18, third inequality, centered at θ\thetaθ and a∗a^*a∗), with 0-based rounds. The paper bounds the term by an instance constant plus a multiple of cRETc_R E_TcR​ET​, where ET=∑tt−1/2P(Gtc)E_T=\sum_tt^{-1/2}P(G_t^c)ET​=∑t​t−1/2P(Gtc​) is the good-event failure sum. Lemma C.24 and (C.4) of v1 turn cRETc_R E_TcR​ET​ into an instance constant plus O(cRΔmin⁡−128/255)CO(c_R\Delta_{\min}^{-128/255})\sqrt CO(cR​Δmin−128/255​)C​; MMM collects all budget-independent constants. The right-hand side has the shape of (2.5) for all three term bounds.

Preamble
import Mathlib
import Definitions.Def_IAFTRL_IsActionSet
import Definitions.Def_IAFTRL_IsIAFTRLRun
import Definitions.Def_LinearBanditProtocol
import Definitions.Def_IAFTRL_actionNorm
import Definitions.Def_IAFTRL_IsUniqueMin
import Definitions.Def_IAFTRL_IsCorrupted
import Definitions.Def_IAFTRL_regretVs
import Definitions.Def_IAFTRL_IsFeasibleAlloc
import Definitions.Def_IAFTRL_allocCost
import Definitions.Def_IAFTRL_beta
import Definitions.Def_IAFTRL_qSoft
import Definitions.Def_IAFTRL_proxyC
Formal statement
namespace IAFTRL

open Matrix MeasureTheory

/-- **Exploration contribution in the corrupted stochastic regime.** Zhao–Tan, *Best-of-Both-Worlds
FTRL for Linear Bandits*, arXiv:2611.01299v1, Lemma C.6 (with Lemma C.24, (C.4) and (B.4)): "Fix a
finite feasible sampling allocation `n`. … `I_3 := Σ_{t=1}^T E[⟨p_t − q_t, Δ⟩] ≤ 2^22 B c^n log(eT) +
M_{3,n} + 8c_R E_T`", with `B = 2⌈256 + log(2K)⌉ ≤ 2048 log(eK)` (B.4). The term
`2^22 B c^n log(eT) = 2^22 B c^n (1 + log T)` gives `O(c^n log K · log T)` for `K ≥ 2` and puts the
`T`-free part `2^22 B c^n` into `M`.

**Formalization Note.** Rounds are 0-based: Lean round `t` is the paper's round `t + 1`, with
`q_t = qSoft β_{t+1} arms (Σ_{s<t} θ̂_s)`; the left side is the corresponding term of Lemma D.18
(`IAFTRL.lemma_D_18`, third inequality, at center `θ` and reference action `a*`). The failure-event
sum `c_R E_T` is bounded through Lemma C.24 and (C.4) of v1 (`√n₀ ≤ √N_burn + √C`,
`√T_◦ ≤ √(Q+1) Δ_min^{-5/2} + 32 Δ_min^{-1/2} √n₀`); every budget-independent constant goes into `M`,
chosen after `(d, K, 𝒜, θ, a*, Δ₀, n)` and before the probability space, `T`, `C` and the run.
`c_R = √(d log(eK)) ≤ √3 √(d log K)` for `K ≥ 2`, and `Δ_min^{-1/2}, Δ_min^{-γ₀} ≤ Δ₀^{-128/255}` for
`Δ₀ ≤ min(Δ_min, 1)`, `γ₀ = 128/255` ((C.5e)). All three term bounds use the right-hand side shape of
(2.5); only the exploration term needs the cost term. -/
theorem proposition_2_1_exploration : ∃ c₀ : ℝ, 0 < c₀ ∧
    ∀ {d K : ℕ}, 1 ≤ d → ∀ (arms : Fin K → Fin d → ℝ), IsActionSet arms →
      ∀ (θ : Fin d → ℝ) (jstar : Fin K) (Δ₀ : ℝ),
        actionNorm arms θ ≤ 1 → IsUniqueMin arms θ jstar → 0 < Δ₀ → Δ₀ ≤ 1 →
        (∀ j, j ≠ jstar → Δ₀ ≤ (arms j - arms jstar) ⬝ᵥ θ) →
        ∀ n : Fin K → ℝ, IsFeasibleAlloc arms θ jstar n →
        ∃ M : ℝ, ∀ {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
          (T : ℕ) (C : ℝ) (R : Run d K Ω), 1 ≤ T → 0 ≤ C →
          IsIAFTRLRun P arms T R → IsCorrupted P arms θ C T R →
          ∑ t ∈ Finset.range T, ∫ ω, ∑ a, (R.p t ω a -
              qSoft (beta d K (t + 1)) arms (R.cumEst arms t ω) a) *
            ((arms a - arms jstar) ⬝ᵥ θ) ∂P ≤
            c₀ * (allocCost arms θ jstar n * Real.log K * Real.log T +
              Real.sqrt ((d : ℝ) * Real.log K) * Δ₀ ^ (-(128 : ℝ) / 255) * Real.sqrt C) + M := by sorry

end IAFTRL
Source
Zhao–Tan, Best-of-Both-Worlds FTRL for Linear Bandits, arXiv:2611.01299v1, Appendix C.4, Lemma C.6 (p.57), with Lemma C.24 (p.81), (C.4) (p.50) and (B.4) (p.44)

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