BanditAlgorithm.linear_bandit_unit_ball_minimax_lower_bound
Provedbanditslinearlower-boundsminimax
(Unit-ball lower bound, GOAL, L&S Theorem 24.2) Assume and let , with unit-variance Gaussian noise. Then, for any policy supported in , there exists a parameter with such that
(The book's explicit condition is , not .)
Preamble
import Definitions.Def_LinearBanditProtocol open Matrix MeasureTheory
Formal statement
theorem BanditAlgorithm.linear_bandit_unit_ball_minimax_lower_bound {d n : ℕ}
(hd : 0 < d) (hdn : d ≤ 2 * n) (π : LinearBanditPolicy d)
(hsupp : IsSupportedLinearPolicy {a : Fin d → ℝ | a ⬝ᵥ a ≤ 1} π) :
∃ θ : Fin d → ℝ, θ ⬝ᵥ θ = (d : ℝ) ^ 2 / (48 * n) ∧
d * Real.sqrt n / (16 * Real.sqrt 3) ≤
linearBanditExpectedRegret {a : Fin d → ℝ | a ⬝ᵥ a ≤ 1} θ π n := by
sorry
Source
L&S Theorem 24.2, p.290