Theorem 11, p. 5 — RVU (α > 0, β > 0, γ ≥ 0) and stability κ give each player regret ≤ α + βκ²(n−1)²T
ProvedRegLearnGames.IndivRegret.theorem_11Consider an -player game in which every player has strategies and utilities , played repeatedly: are mixed profiles, and is player 's utility vector against . Let , , and fix a horizon . Suppose that every player's play satisfies the RVU inequality: for every player and every ,
and that the play is stable: for every player and every . Then for every player and every ,
In words, if the players use algorithms with the RVU property that also move slowly, then each player's regret grows like ; for optimistic FTRL, and , so the growth is of order , which is what the choice of step size in Corollary 12 exploits.
Formalization Note The paper assumes the RVU property on any utility sequence; here it is assumed only on the realized play, which is weaker as a hypothesis and makes the theorem stronger. The paper's parameters "" are kept and Definition 3's is not required, since the proof does not use it. Stability is required for the movements that enter the sum. The vector is the utility vector against .
import Mathlib import Definitions.Def_RegLearnGames_TotalRegret_Setting
namespace RegLearnGames.IndivRegret
theorem theorem_11 {n d : ℕ} (u : Fin n → (Fin n → Fin d) → ℝ)
(hu : ∀ i s, u i s ∈ Set.Icc (0 : ℝ) 1)
(w : ℕ → Fin n → Fin d → ℝ) (hw : ∀ t i, w t i ∈ stdSimplex ℝ (Fin d))
(α β γ : ℝ) (hα : 0 < α) (hβ : 0 < β) (hγ : 0 ≤ γ) (T : ℕ)
(hRVU : ∀ i, ∀ v ∈ stdSimplex ℝ (Fin d),
∑ t ∈ Finset.Icc 1 T, (v - w t i) ⬝ᵥ RegLearnGames.TotalRegret.utilVec u (w t) i ≤
α + β * ∑ t ∈ Finset.Icc 1 T, ‖RegLearnGames.TotalRegret.utilVec u (w t) i - RegLearnGames.TotalRegret.utilVec u (w (t - 1)) i‖ ^ 2
- γ * ∑ t ∈ Finset.Icc 1 T, RegLearnGames.TotalRegret.l1 (w t i - w (t - 1) i) ^ 2)
(κ : ℝ) (hκ : ∀ i, ∀ t < T, RegLearnGames.TotalRegret.l1 (w t i - w (t + 1) i) ≤ κ) :
∀ i, ∀ wstar ∈ stdSimplex ℝ (Fin d),
∑ t ∈ Finset.Icc 1 T, (wstar - w t i) ⬝ᵥ RegLearnGames.TotalRegret.utilVec u (w t) i ≤
α + β * κ ^ 2 * ((n : ℝ) - 1) ^ 2 * T := by sorry
end RegLearnGames.IndivRegret
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.