Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Coordinate-flip stopped-loss lower bound for unit-ball linear bandits

Proved
BanditAlgorithm.linear_bandit_unit_ball_coordinate_flip_stopped_loss_lower_bound

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

banditschange-of-measurelinear-banditsminimax-lower-boundstopping-times

Let d,nd,nd,n be positive integers with d≤2nd\le 2nd≤2n, let π\piπ be a stochastic linear-bandit policy supported on the Euclidean unit ball, and put

Δ=d48n.\Delta=\sqrt{\frac{d}{48n}}.Δ=48nd​​.

Fix a sign vector σ∈{−1,1}d\sigma\in\{-1,1\}^dσ∈{−1,1}d and a coordinate iii. Let σ(i)\sigma^{(i)}σ(i) be obtained by flipping only the iiith sign, and set θ=Δσ\theta=\Delta\sigmaθ=Δσ and θ′=Δσ(i)\theta'=\Delta\sigma^{(i)}θ′=Δσ(i).

For a history h=(A1,X1,…,An,Xn)h=(A_1,X_1,\ldots,A_n,X_n)h=(A1​,X1​,…,An​,Xn​), retain round ttt while the coordinate energy accumulated strictly before that round is below n/dn/dn/d:

∑s<tAs,i2<nd.\sum_{s<t}A_{s,i}^2<\frac nd.s<t∑​As,i2​<dn​.

For x∈{−1,1}x\in\{-1,1\}x∈{−1,1} define the corresponding stopped squared loss

Ui(x;h)=∑t=1n1 ⁣{∑s<tAs,i2<nd}(1d−At,ix)2.U_i(x;h)= \sum_{t=1}^n \mathbf 1\!\left\{\sum_{s<t}A_{s,i}^2<\frac nd\right\} \left(\frac1{\sqrt d}-A_{t,i}x\right)^2.Ui​(x;h)=t=1∑n​1{s<t∑​As,i2​<dn​}(d​1​−At,i​x)2.

Writing Eθ\mathbb E_\thetaEθ​ and Eθ′\mathbb E_{\theta'}Eθ′​ for expectation under the two Gaussian linear-bandit interaction laws, the coordinate-flip pair satisfies

Eθ[Ui(σi)]+Eθ′[Ui(σi(i))]≥nd.\mathbb E_\theta[U_i(\sigma_i)] + \mathbb E_{\theta'}[U_i(\sigma_i^{(i)})] \ge \frac nd.Eθ​[Ui​(σi​)]+Eθ′​[Ui​(σi(i)​)]≥dn​.

This is the coordinatewise testing estimate used by the randomisation argument for the unit-ball minimax lower bound. It isolates the reusable stopped change-of-measure core from the subsequent finite hypercube averaging.

Formalization Note A round is active according to energy strictly before it, which is equivalent to summing through the capped first threshold-crossing round in the source. Boolean values encode the two signs.

Preamble
import Definitions.Def_LinearBanditProtocol

open Matrix MeasureTheory
Formal statement
theorem BanditAlgorithm.linear_bandit_unit_ball_coordinate_flip_stopped_loss_lower_bound
    {d n : ℕ} (hd : 0 < d) (hdn : d ≤ 2 * n)
    (π : LinearBanditPolicy d)
    (hsupp : IsSupportedLinearPolicy
      {a : Fin d → ℝ | a ⬝ᵥ a ≤ 1} π)
    (σ : Fin d → Bool) (i : Fin d) :
    let Δ := Real.sqrt ((d : ℝ) / (48 * n))
    let sign : Fin d → ℝ := fun j ↦ if σ j then 1 else -1
    let θ : Fin d → ℝ := fun j ↦ Δ * sign j
    let σ' : Fin d → Bool := Function.update σ i (!(σ i))
    let sign' : Fin d → ℝ := fun j ↦ if σ' j then 1 else -1
    let θ' : Fin d → ℝ := fun j ↦ Δ * sign' j
    let active : LinearBanditHistory d n → Fin n → Prop := fun h t ↦
      (∑ s ∈ Finset.univ.filter (fun s : Fin n ↦ s < t),
          ((h s).1 i) ^ 2) < (n : ℝ) / d
    let U : LinearBanditHistory d n → ℝ → ℝ := fun h x ↦
      ∑ t, if active h t then
        (1 / Real.sqrt d - (h t).1 i * x) ^ 2 else 0
    (n : ℝ) / d ≤
      (∫ h, U h (sign i) ∂linearBanditMeasure θ π n) +
      ∫ h, U h (sign' i) ∂linearBanditMeasure θ' π n := by
  sorry
Source
Lattimore and Szepesvári, Bandit Algorithms (Cambridge University Press, 2020), proof of Theorem 24.2, pp. 290–291, Eqs. (24.3)–(24.5) and the immediately following paired-loss display; https://tor-lattimore.com/downloads/book/book.pdf

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