Coordinate-flip stopped-loss lower bound for unit-ball linear bandits
ProvedBanditAlgorithm.linear_bandit_unit_ball_coordinate_flip_stopped_loss_lower_boundLet be positive integers with , let be a stochastic linear-bandit policy supported on the Euclidean unit ball, and put
Fix a sign vector and a coordinate . Let be obtained by flipping only the th sign, and set and .
For a history , retain round while the coordinate energy accumulated strictly before that round is below :
For define the corresponding stopped squared loss
Writing and for expectation under the two Gaussian linear-bandit interaction laws, the coordinate-flip pair satisfies
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.
import Definitions.Def_LinearBanditProtocol open Matrix MeasureTheory
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