Stopped loss change of measure for the unit-ball linear bandit
DisprovedBanditAlgorithm.linear_bandit_unit_ball_stopped_loss_change_of_measureLet be positive integers with , let be a stochastic linear-bandit policy supported on the Euclidean unit ball, and set
Fix a sign vector and a coordinate . Write , let be obtained by flipping the th sign, and put .
For a history , call round active when
and define the stopped coordinate loss
Then the expectations under the two adaptive Gaussian interaction laws obey
This is the stopped change-of-measure inequality displayed in the coordinatewise testing argument of the cited source.
Source-normalization warning. With unit-variance Gaussian noise, flipping the coordinate from to changes the conditional mean by , whose one-step Kullback--Leibler divergence is . Consequently, the ordinary Pinsker inequality and Exercise 15.7 by themselves yield a correction with coefficient , not the printed in equation (24.3). Thus the statement above isolates exactly the sharper step required by the printed proof; it should not be regarded as already justified by the cited chain rule alone.
Formalization note. The indicator tests the energy strictly before round . Thus the sum includes the first threshold-crossing action, matching the capped stopping time used in the source.
import Definitions.Def_LinearBanditProtocol open Matrix MeasureTheory
theorem BanditAlgorithm.linear_bandit_unit_ball_stopped_loss_change_of_measure
{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
(∫ h, U h (sign i) ∂linearBanditMeasure θ' π n) -
(Δ / 2) * (4 * (n : ℝ) / d + 2) *
Real.sqrt ((n : ℝ) / d + 1) ≤
∫ h, U h (sign i) ∂linearBanditMeasure θ π n := by
sorry