BanditAlgorithm.linear_bandit_unit_ball_minimax_lower_bound
Proved(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 .)
import Definitions.Def_LinearBanditProtocol open Matrix MeasureTheory
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
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Consider the -dimensional linear stochastic bandit protocol: a policy assigns to each round a probability kernel from length- histories of action–reward pairs to actions in ; under parameter the history law is built recursively, each round drawing an action from the policy kernel applied to the past and recording reward with independent . The action set is the closed Euclidean unit ball , and the expected regret is
The theorem asserts:
Hypotheses:
- and (natural numbers; together these force , though no positivity of is stated separately).
- is an arbitrary -dimensional linear bandit policy.
- is supported on the unit ball: for every round and every history , assigns probability to the complement of .
Edge cases and conventions:
- The squared norm of the hard parameter is pinned exactly to (an equality, not a bound).
- The expectation term of the regret is a Bochner integral, silently if not integrable; the supremum is the real supremum over the ball.
- The noise is exactly unit-variance Gaussian.
Confirmed by the mission captain (proposal self-audit).