Proposition 7, p. 5 — OFTRL with Mᵗ = uᵗ⁻¹ has the RVU property with α = R/η, β = η, γ = 1/(4η)
ProvedRegLearnGames.TotalRegret.proposition_7Let be the probability simplex, a regularizer that is 1-strongly convex with respect to on , , and a bound on the range of on . Let be an arbitrary utility sequence in , and let be any run of optimistic FTRL with the one-step recency bias . Then for every horizon and every comparator ,
This is inequality (1) of Definition 3 — regret bounded by variation in utilities (RVU) — with constants , and . Together with Theorem 4 it gives Corollary 8.
Formalization Note "Satisfies the RVU property" is rendered as inequality (1) for every utility sequence, every horizon and every comparator. Definition 3 also asks and of the constants; these hold when and and are not part of the conclusion. The norm is with dual (the paper allows any norm). is any upper bound on the range of over , which includes the paper's .
import Mathlib import Definitions.Def_RegLearnGames_TotalRegret_Setting
namespace RegLearnGames.TotalRegret
theorem proposition_7 {d : ℕ} (𝓡 : (Fin d → ℝ) → ℝ) (η R : ℝ) (hη : 0 < η)
(h𝓡 : IsOneStronglyConvexL1 𝓡)
(hR : ∀ f ∈ stdSimplex ℝ (Fin d), ∀ g ∈ stdSimplex ℝ (Fin d), 𝓡 f - 𝓡 g ≤ R)
(u w : ℕ → Fin d → ℝ) (hw : IsOFTRL 𝓡 η (fun T => u (T - 1)) u w)
(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 - u (t - 1)‖ ^ 2
- 1 / (4 * η) * ∑ t ∈ Finset.Icc 1 T, l1 (w t - w (t - 1)) ^ 2 := by sorry
end RegLearnGames.TotalRegret
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.