Theorem 28.11 core: untuned FTRL unit-ball regret bound
ProvedBanditAlgorithm.adversarial_linear_bandit_ftrl_unit_ball_regret_untunedThis is the untuned regret bound at the end of the proof of Theorem 28.11.
Fix dimension , horizon , oblivious loss vectors with , learning rate , and shrunken radius
Let the FTRL iterates use the potential
on the closed ball of radius . At each round, let be uniform on and let be uniform on the signed coordinate directions. Assume the pairs are mutually independent across rounds and that and are independent within every round. The action explores in direction when , and otherwise plays the radial normalization of ; the loss estimate is the one-point importance-weighted estimator from Eq. (28.12).
Then, for every comparator in the Euclidean unit ball,
This parameterized form isolates the stochastic FTRL analysis from the final choice of learning rate and is reusable for alternative tuning rules.
Formalization Note The random exploration seed and signed-direction seed are represented separately. Their within-round independence is stated explicitly in addition to independence of the pairs across rounds.
import Definitions.Def_OnlineLinearOptimization import Mathlib.Probability.Independence.Basic import Mathlib.MeasureTheory.Measure.Lebesgue.Basic import Mathlib.MeasureTheory.Integral.Bochner.Basic open RealInnerProductSpace MeasureTheory ProbabilityTheory
theorem BanditAlgorithm.adversarial_linear_bandit_ftrl_unit_ball_regret_untuned
(d n : ℕ) (hd : 0 < d) (hn : 2 ≤ n)
(y : ℕ → EuclideanSpace ℝ (Fin d)) (hy : ∀ t, ‖y t‖ ≤ 1)
(η r : ℝ) (hη0 : 0 < η)
(hr : r = 1 - 2 * η * d) (hr0 : 0 < r)
{Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
(V : ℕ → Ω → ℝ) (W : ℕ → Ω → Fin d × Bool)
(hVmeas : ∀ t, Measurable (V t)) (hWmeas : ∀ t, Measurable (W t))
(hindep : iIndepFun (fun t ω => (V t ω, W t ω)) P)
(hVW : ∀ t, IndepFun (V t) (W t) P)
(hV : ∀ t, Measure.map (V t) P = (volume : Measure ℝ).restrict (Set.Icc 0 1))
(hW : ∀ t (u : Fin d × Bool), P {ω | W t ω = u} = ((2 * d : ℕ) : ENNReal)⁻¹)
(Abar A Yhat : ℕ → Ω → EuclideanSpace ℝ (Fin d))
(hftrl : ∀ ω, IsFTRLIterates η
(fun b : EuclideanSpace ℝ (Fin d) => -Real.log (1 - ‖b‖) - ‖b‖)
(Metric.ball 0 1) (Metric.closedBall 0 r)
(fun t => Yhat t ω) (fun t => Abar t ω))
(hA : ∀ t ω, A t ω =
if V t ω < 1 - ‖Abar t ω‖ then
(if (W t ω).2 then (1 : ℝ) else -1) • EuclideanSpace.single (W t ω).1 1
else ‖Abar t ω‖⁻¹ • Abar t ω)
(hY : ∀ t ω, Yhat t ω =
(if V t ω < 1 - ‖Abar t ω‖ then
d * ⟪A t ω, y t⟫ / (1 - ‖Abar t ω‖) else 0) • A t ω) :
∀ a₀ ∈ Metric.closedBall (0 : EuclideanSpace ℝ (Fin d)) 1,
∫ ω, oloRegret (fun t => A t ω) y n a₀ ∂P ≤
(1 - r) * n + Real.log (1 / (1 - r)) / η + η * n * d := by
sorry