BanditAlgorithm.ftrl_simplex_exp_weights_regret
Provedexponential-weightsonline-learningregret
(Regret on the simplex, Proposition 28.7) Let be the probability simplex and for all . FTRL (= mirror descent = exponential weights here, Example 28.3/Eq. (28.5); the book states the proposition for mirror descent and notes the identical FTRL bound via Theorem 28.5) with the unnormalised negentropy potential
on domain and learning rate satisfies
for every simplex comparator .
Preamble
import Definitions.Def_OnlineLinearOptimization open RealInnerProductSpace
Formal statement
theorem BanditAlgorithm.ftrl_simplex_exp_weights_regret
(d n : ℕ) (y a : ℕ → EuclideanSpace ℝ (Fin d))
(hy : ∀ t, ∀ i, y t i ∈ Set.Icc (0 : ℝ) 1)
(hiter : IsFTRLIterates (Real.sqrt (2 * Real.log d / n))
(fun v : EuclideanSpace ℝ (Fin d) => ∑ i, (v i * Real.log (v i) - v i))
{v : EuclideanSpace ℝ (Fin d) | ∀ i, 0 ≤ v i}
{v : EuclideanSpace ℝ (Fin d) | (∀ i, 0 ≤ v i) ∧ ∑ i, v i = 1}
y a) :
∀ a₀ ∈ {v : EuclideanSpace ℝ (Fin d) | (∀ i, 0 ≤ v i) ∧ ∑ i, v i = 1},
oloRegret a y n a₀ ≤ Real.sqrt (2 * n * Real.log d) := by
sorry
Source
L&S Proposition 28.7, p.335