Theorem 19, supp. p. 3 — optimistic FTRL regret ≤ R/η + Σ‖uᵗ−Mᵗ‖_*‖wᵗ−gᵗ‖ − (1/2η)Σ(‖wᵗ−gᵗ‖² + ‖wᵗ−gᵗ⁻¹‖²)
ProvedRegLearnGames.TotalRegret.theorem_19Let be the probability simplex, a regularizer that is 1-strongly convex with respect to on , a step size, and a bound on the range of on : for all . Let be an arbitrary utility sequence and an arbitrary predictor sequence in , let be any run of optimistic FTRL on them, and let be any leader sequence, . Then for every horizon and every comparator ,
where and .
This is the basic regret bound of optimistic FTRL. Its negative terms, which measure how far each iterate is from the leader, are what Proposition 7 converts into the negative movement term of the RVU property.
Formalization Note The paper states the result for a single player and a general norm with ; here the norm is (the case Theorem 4 and Corollary 8 use), and is any upper bound on the range of over , which includes the exact range. The utilities and predictors are arbitrary real vectors, as on the page.
import Mathlib import Definitions.Def_RegLearnGames_TotalRegret_Setting
namespace RegLearnGames.TotalRegret
theorem theorem_19 {d : ℕ} (𝓡 : (Fin d → ℝ) → ℝ) (η R : ℝ) (hη : 0 < η)
(h𝓡 : IsOneStronglyConvexL1 𝓡)
(hR : ∀ f ∈ stdSimplex ℝ (Fin d), ∀ g ∈ stdSimplex ℝ (Fin d), 𝓡 f - 𝓡 g ≤ R)
(M u w g : ℕ → Fin d → ℝ) (hw : IsOFTRL 𝓡 η M u w) (hg : IsLeader 𝓡 η u g)
(T : ℕ) (wstar : Fin d → ℝ) (hwstar : wstar ∈ stdSimplex ℝ (Fin d)) :
∑ t ∈ Finset.Icc 1 T, (wstar - w t) ⬝ᵥ u t ≤
R / η + ∑ t ∈ Finset.Icc 1 T, ‖u t - M t‖ * l1 (w t - g t)
- 1 / (2 * η) * ∑ t ∈ Finset.Icc 1 T, (l1 (w t - g t) ^ 2 + l1 (w t - g (t - 1)) ^ 2) := by sorry
end RegLearnGames.TotalRegret
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.