Average reward bound for the Rademacher unit-ball linear bandit
ProvedBanditAlgorithm.linear_bandit_unit_ball_hypercube_average_reward_upper_boundLet be positive and let be any stochastic linear-bandit policy supported on the Euclidean unit ball. Put
and, for each Boolean sign vector , define . Then the total expected reward, summed over the entire sign cube, satisfies
Equivalently, under the uniform Rademacher prior, the expected cumulative reward is at most .
The information-theoretic proof pairs environments differing in one sign. For a square-integrable action coordinate , Cauchy--Schwarz and the pointwise inequality
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 . Two applications of Cauchy--Schwarz, together with , then bound the average reward at round by . Summing and using 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).
import Definitions.Def_LinearBanditProtocol open Matrix MeasureTheory
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