Proposition 7, p. 5 — OFTRL with Mᵗ = uᵗ⁻¹ satisfies RVU with α = R/η, β = η, γ = 1/(4η)
ProvedRegLearnGames.IndivRegret.proposition_7Let be a regularizer on that is 1-strongly convex with respect to on the simplex , let , and let bound the range of on : for all . Let be any utility sequence in and let be a run of optimistic FTRL with regularizer , step size and one-step recency bias . Then for every horizon and every comparator ,
This is the RVU property (Regret bounded by Variation in Utilities, Definition 3 of the paper) with constants , , . The negative movement term is what lets the regret of interacting players stay small.
Formalization Note "Satisfies the RVU property" is formalized as inequality (1) holding on every utility sequence, which is what the quantification over gives; the side conditions , of Definition 3 are conditions on the constants and are not part of the conclusion. The paper's is replaced by any upper bound on that range, which includes the exact range. The norm is with dual . This statement coincides with the one of the companion mission I of this series.
import Mathlib import Definitions.Def_RegLearnGames_TotalRegret_Setting
namespace RegLearnGames.IndivRegret
theorem proposition_7 {d : ℕ} (𝓡 : (Fin d → ℝ) → ℝ) (η : ℝ) (hη : 0 < η)
(h𝓡 : RegLearnGames.TotalRegret.IsOneStronglyConvexL1 𝓡) (R : ℝ)
(hR : ∀ f ∈ stdSimplex ℝ (Fin d), ∀ g ∈ stdSimplex ℝ (Fin d), 𝓡 f - 𝓡 g ≤ R)
(u w : ℕ → Fin d → ℝ) (hw : RegLearnGames.TotalRegret.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, RegLearnGames.TotalRegret.l1 (w t - w (t - 1)) ^ 2 := by sorry
end RegLearnGames.IndivRegret
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.