Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

BanditAlgorithm.linear_bandit_linucb_regret_bound

Proved

by Shuze Chen · Jul 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

banditslinearlinucbregret

(LinUCB/OFUL regret, GOAL — Theorem 19.2, stated pathwise) Under Assumption 19.1:

  • (a) 1≤β1≤⋯≤βn1 \le \beta_1 \le \cdots \le \beta_n1≤β1​≤⋯≤βn​;
  • (b) max⁡t∈[n]sup⁡a,b∈At⟨θ∗,a−b⟩≤1\max_{t\in[n]} \sup_{a,b\in\mathcal{A}_t}\langle\theta_*, a-b\rangle \le 1maxt∈[n]​supa,b∈At​​⟨θ∗​,a−b⟩≤1;
  • (c) ∥a∥2≤L\|a\|_2 \le L∥a∥2​≤L for all a∈⋃t=1nAta\in\bigcup_{t=1}^n\mathcal{A}_ta∈⋃t=1n​At​ —

if the sequences form a LinUCB trace (Eqs. 19.2/19.3/19.7/19.12) and θ∗∈Ct\theta_* \in \mathcal{C}_tθ∗​∈Ct​ for all t∈[n]t\in[n]t∈[n] (the 1−δ1-\delta1−δ event of Assumption 19.1(d), taken as a hypothesis; its probabilistic wrapper is Mission IX's Theorem 20.5), then

R^n≤8nβnlog⁡det⁡Vn(λ)det⁡V0(λ)≤8dnβnlog⁡dλ+nL2dλ\hat R_n \le \sqrt{8n\beta_n\log\frac{\det V_n(\lambda)}{\det V_0(\lambda)}} \le \sqrt{8dn\beta_n\log\frac{d\lambda+nL^2}{d\lambda}}R^n​≤8nβn​logdetV0​(λ)detVn​(λ)​​≤8dnβn​logdλdλ+nL2​​

— both inequalities, as in the book.

Preamble
import Mathlib.Data.Real.Sqrt
import Mathlib.Analysis.SpecialFunctions.Log.Basic
import Definitions.Def_StochasticLinearBandit


open Matrix
Formal statement
theorem BanditAlgorithm.linear_bandit_linucb_regret_bound {d n : ℕ} (hd : 0 < d) (hn : 0 < n)
    {lam L : ℝ} (hlam : 0 < lam)
    (𝓐 𝓒 : ℕ → Set (Fin d → ℝ)) (β : ℕ → ℝ)
    (a θtilde astar : ℕ → Fin d → ℝ) (x : ℕ → ℝ) (θstar : Fin d → ℝ)
    -- Assumption 19.1 (a): `1 ≤ β_1 ≤ β_2 ≤ ⋯ ≤ β_n`
    (hβ_one : 1 ≤ β 1)
    (hβ_mono : ∀ s t : ℕ, 1 ≤ s → s ≤ t → t ≤ n → β s ≤ β t)
    -- Assumption 19.1 (b): `max_{t∈[n]} sup_{a,b∈𝓐_t} ⟨θ*, a − b⟩ ≤ 1`
    (hb : ∀ t ∈ Finset.range n, ∀ b ∈ 𝓐 (t + 1), ∀ b' ∈ 𝓐 (t + 1),
      θstar ⬝ᵥ (b - b') ≤ 1)
    -- Assumption 19.1 (c): `‖a‖₂ ≤ L` for all `a ∈ ⋃_{t=1}^n 𝓐_t`
    (hL : ∀ t ∈ Finset.range n, ∀ b ∈ 𝓐 (t + 1), Real.sqrt (b ⬝ᵥ b) ≤ L)
    -- the run of LinUCB (Eqs. (19.2), (19.3), (19.7), (19.12))
    (htrace : IsLinUCBTrace lam n 𝓐 𝓒 β a θtilde astar x θstar)
    -- the `1 − δ` event of Assumption 19.1 (d): `θ* ∈ 𝓒_t` for all `t ∈ [n]`
    (hmem : ∀ t ∈ Finset.range n, θstar ∈ 𝓒 (t + 1)) :
    linearPseudoRegret θstar a astar n ≤
      Real.sqrt (8 * n * β n *
        Real.log ((regularizedDesignMatrixSeq d lam a n).det /
          (regularizedDesignMatrixSeq d lam a 0).det)) ∧
    Real.sqrt (8 * n * β n *
        Real.log ((regularizedDesignMatrixSeq d lam a n).det /
          (regularizedDesignMatrixSeq d lam a 0).det)) ≤
      Real.sqrt (8 * d * n * β n *
        Real.log ((d * lam + n * L ^ 2) / (d * lam))) := by
  sorry
Source
L&S Theorem 19.2 with Assumption 19.1, p.243

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