BanditAlgorithm.linear_bandit_linucb_regret_bound
Proved(LinUCB/OFUL regret, GOAL — Theorem 19.2, stated pathwise) Under Assumption 19.1:
- (a) ;
- (b) ;
- (c) for all —
if the sequences form a LinUCB trace (Eqs. 19.2/19.3/19.7/19.12) and for all (the event of Assumption 19.1(d), taken as a hypothesis; its probabilistic wrapper is Mission IX's Theorem 20.5), then
— both inequalities, as in the book.
import Mathlib.Data.Real.Sqrt import Mathlib.Analysis.SpecialFunctions.Log.Basic import Definitions.Def_StochasticLinearBandit open Matrix
theorem BanditAlgorithm.linear_bandit_linucb_regret_bound {d n : ℕ} (hd : 0 < d) (hn : 0 < n)
{lam L : ℝ} (hlam : 0 < lam)
(𝓐 𝓒 : ℕ → Set (Fin d → ℝ)) (β : ℕ → ℝ)
(a θtilde astar : ℕ → Fin d → ℝ) (x : ℕ → ℝ) (θstar : Fin d → ℝ)
-- Assumption 19.1 (a): `1 ≤ β_1 ≤ β_2 ≤ ⋯ ≤ β_n`
(hβ_one : 1 ≤ β 1)
(hβ_mono : ∀ s t : ℕ, 1 ≤ s → s ≤ t → t ≤ n → β s ≤ β t)
-- Assumption 19.1 (b): `max_{t∈[n]} sup_{a,b∈𝓐_t} ⟨θ*, a − b⟩ ≤ 1`
(hb : ∀ t ∈ Finset.range n, ∀ b ∈ 𝓐 (t + 1), ∀ b' ∈ 𝓐 (t + 1),
θstar ⬝ᵥ (b - b') ≤ 1)
-- Assumption 19.1 (c): `‖a‖₂ ≤ L` for all `a ∈ ⋃_{t=1}^n 𝓐_t`
(hL : ∀ t ∈ Finset.range n, ∀ b ∈ 𝓐 (t + 1), Real.sqrt (b ⬝ᵥ b) ≤ L)
-- the run of LinUCB (Eqs. (19.2), (19.3), (19.7), (19.12))
(htrace : IsLinUCBTrace lam n 𝓐 𝓒 β a θtilde astar x θstar)
-- the `1 − δ` event of Assumption 19.1 (d): `θ* ∈ 𝓒_t` for all `t ∈ [n]`
(hmem : ∀ t ∈ Finset.range n, θstar ∈ 𝓒 (t + 1)) :
linearPseudoRegret θstar a astar n ≤
Real.sqrt (8 * n * β n *
Real.log ((regularizedDesignMatrixSeq d lam a n).det /
(regularizedDesignMatrixSeq d lam a 0).det)) ∧
Real.sqrt (8 * n * β n *
Real.log ((regularizedDesignMatrixSeq d lam a n).det /
(regularizedDesignMatrixSeq d lam a 0).det)) ≤
Real.sqrt (8 * d * n * β n *
Real.log ((d * lam + n * L ^ 2) / (d * lam))) := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Setup and notation. This is a fully deterministic statement about a recorded run of a LinUCB-style interaction; no probability appears. Fix , , round-indexed action sets and confidence sets , radii , sequences of played actions , optimistic parameters , comparator actions (all in ), rewards , and a parameter . Write
and . Note , so (the statement literally uses the determinant of the time- matrix).
Assertion (a conjunction of two inequalities):
Hypotheses.
- , , .
- Radii: , and monotonicity on the window : whenever ( and values beyond are unconstrained; the bound uses ).
- Bounded mean spread: for every round and every ordered pair , (one-sided as written; quantifying over both orders makes it symmetric).
- Bounded actions: for every , .
- LinUCB trace: for every : (i) ; (ii) ; (iii) ; (iv) for all and all ; (v) ; (vi) for all .
- Correct confidence sets: for every .
Edge cases.
- No probabilistic model ties the rewards to or to any noise; is an arbitrary real sequence entering only through inside the trace's ellipsoid condition.
- Since , all are positive definite, so the inverses and determinants are non-degenerate.
- The real square root maps negative arguments to ; nothing in the hypotheses forbids -dependent radicands from being handled by that convention, and the second inequality compares the two square-rooted quantities as stated.
- Because the trace condition puts (nonempty) and , the norm bound forces .
- Membership of in the confidence sets is a hypothesis, not a probabilistic event.
Confirmed by the mission captain (proposal self-audit).