Theorem 28.11: FTRL unit-ball bandit regret (corrected root)
ProvedBanditAlgorithm.adversarial_linear_bandit_ftrl_unit_ball_regret_indep_seeds(Adversarial linear bandit on the unit ball, GOAL, Theorem 28.11; corrected root — supersedes BanditAlgorithm.adversarial_linear_bandit_ftrl_unit_ball_regret, whose hypotheses omitted the within-round independence of the two seeds.) Fix oblivious losses , , and action set the Euclidean unit ball. On a probability space carrying per-round seeds and such that the pairs are mutually independent across rounds and, within each round, is independent of — so the seeds are jointly independent, exactly as Algorithm 17 samples the exploration bit and the direction separately — Algorithm 16/17 runs FTRL with the Legendre potential
on the shrunken ball of radius with : with exploration indicator it plays
and feeds FTRL the one-point importance-weighted estimator (Eq. (28.12))
Then the expected regret satisfies
for every comparator in the unit ball.
The within-round independence hypothesis is used exactly once in the source proof: it makes conditionally unbiased given the past (the sentence after Eq. (28.12)), which is what allows the FTRL master bound (Theorem 28.10) to be applied to the estimated losses.
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_indep_seeds
(d n : ℕ) (hd : 0 < d) (hn : 2 ≤ n)
(y : ℕ → EuclideanSpace ℝ (Fin d)) (hy : ∀ t, ‖y t‖ ≤ 1)
(η r : ℝ)
(hη : η = Real.sqrt (Real.log n / (3 * d * n)))
(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 ≤
2 * Real.sqrt (3 * n * d * Real.log n) := by
sorry