Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Average reward bound for the Rademacher unit-ball linear bandit

Proved
BanditAlgorithm.linear_bandit_unit_ball_hypercube_average_reward_upper_bound

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

banditsbayes-riskinformation-theorylinear-banditsminimax-lower-bound

Let d,nd,nd,n be positive and let π\piπ be any stochastic linear-bandit policy supported on the Euclidean unit ball. Put

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

and, for each Boolean sign vector σ∈{−1,1}d\sigma\in\{-1,1\}^dσ∈{−1,1}d, define θσ=Δσ\theta_\sigma=\Delta\sigmaθσ​=Δσ. Then the total expected reward, summed over the entire sign cube, satisfies

∑σ∈{−1,1}dEθσ[∑t=1n⟨At,θσ⟩]≤2d nΔ2n.\sum_{\sigma\in\{-1,1\}^d} \mathbb E_{\theta_\sigma} \left[\sum_{t=1}^n\langle A_t,\theta_\sigma\rangle\right] \le 2^d\,n\Delta^2\sqrt n.σ∈{−1,1}d∑​Eθσ​​[t=1∑n​⟨At​,θσ​⟩]≤2dnΔ2n​.

Equivalently, under the uniform Rademacher prior, the expected cumulative reward is at most nΔ2nn\Delta^2\sqrt nnΔ2n​.

The information-theoretic proof pairs environments differing in one sign. For a square-integrable action coordinate ggg, Cauchy--Schwarz and the pointwise inequality

(x−y)log⁡(x/y)≥2(x−y)2x+y(x-y)\log(x/y)\ge \frac{2(x-y)^2}{x+y}(x−y)log(x/y)≥x+y2(x−y)2​

control the squared difference of the two expected actions by their symmetrized Kullback--Leibler divergence times their second action moment. The adaptive Gaussian chain rule gives the exact coordinate-flip divergence 2Δ2E∑s<tAs,i22\Delta^2\mathbb E\sum_{s<t}A_{s,i}^22Δ2E∑s<t​As,i2​. Two applications of Cauchy--Schwarz, together with ∥At∥2≤1\|A_t\|_2\le1∥At​∥2​≤1, then bound the average reward at round ttt by Δ2t\Delta^2\sqrt tΔ2t​. Summing and using ∑t<nt≤nn\sum_{t<n}\sqrt t\le n\sqrt n∑t<n​t​≤nn​ proves the displayed inequality.

Source note. This is an alternative, source-correct information-theoretic lemma for Lattimore--Szepesvári, Theorem 24.2. Its Gaussian divergence step is the general-action decomposition of Exercise 15.8 applied to the coordinate-flip pair. It deliberately avoids the normalization discrepancy in the printed equation (24.3).

Preamble
import Definitions.Def_LinearBanditProtocol

open Matrix MeasureTheory
Formal statement
theorem BanditAlgorithm.linear_bandit_unit_ball_hypercube_average_reward_upper_bound
    {d n : ℕ} (hd : 0 < d) (hn : 0 < n)
    (π : LinearBanditPolicy d)
    (hsupp : IsSupportedLinearPolicy
      {a : Fin d → ℝ | a ⬝ᵥ a ≤ 1} π) :
    let Δ := Real.sqrt ((d : ℝ) / (48 * n))
    (∑ σ : Fin d → Bool,
        ∫ h, ∑ t, (h t).1 ⬝ᵥ
          (fun i ↦ Δ * if σ i then 1 else -1)
          ∂linearBanditMeasure
            (fun i ↦ Δ * if σ i then 1 else -1) π n) ≤
      (Fintype.card (Fin d → Bool) : ℝ) *
        (n * Δ ^ 2 * Real.sqrt n) := by
  sorry
Source
Alternative lemma for Lattimore and Szepesvári, Bandit Algorithms (2020), Theorem 24.2, pp. 290–291. The exact general-action Gaussian divergence input is Exercise 15.8, p. 209; the proof uses symmetrized KL and deliberately avoids the factor-of-two discrepancy in displayed Eq. (24.3).

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