Proof of Theorem 4, display after “so that”, p. 4 — Σᵢ‖uᵢ(w)−uᵢ(w′)‖²_* ≤ (n−1)ΣᵢΣ_{j≠i}‖wⱼ−w′ⱼ‖² = (n−1)²Σᵢ‖wᵢ−w′ᵢ‖²
ProvedRegLearnGames.TotalRegret.theorem_4_variation_boundno-regret-dynamicsnormal-form-gamesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1rvu-property
Consider an -player game with strategies per player and utilities , and let be two mixed profiles (every ). With player 's utility vector against ,
This is the variation bound of Theorem 4: the total squared movement of the utility vectors is at most times the total squared movement of the players' strategies. It is what lets the negative terms of the RVU property absorb the positive ones when .
Formalization Note Stated for two arbitrary mixed profiles; the paper applies it to and . is computed in .
Preamble
import Mathlib import Definitions.Def_RegLearnGames_TotalRegret_Setting
Formal statement
namespace RegLearnGames.TotalRegret
theorem theorem_4_variation_bound {n d : ℕ} (u : Fin n → (Fin n → Fin d) → ℝ)
(hu : ∀ i s, u i s ∈ Set.Icc (0 : ℝ) 1)
(w w' : Fin n → Fin d → ℝ) (hw : ∀ j, w j ∈ stdSimplex ℝ (Fin d))
(hw' : ∀ j, w' j ∈ stdSimplex ℝ (Fin d)) :
∑ i, ‖utilVec u w i - utilVec u w' i‖ ^ 2 ≤
((n : ℝ) - 1) * ∑ i, ∑ j ∈ Finset.univ.erase i, l1 (w j - w' j) ^ 2 ∧
((n : ℝ) - 1) * ∑ i, ∑ j ∈ Finset.univ.erase i, l1 (w j - w' j) ^ 2 =
((n : ℝ) - 1) ^ 2 * ∑ i, l1 (w i - w' i) ^ 2 := by sorry
end RegLearnGames.TotalRegret
Source
Syrgkanis, Agarwal, Luo, Schapire, Fast Convergence of Regularized Learning in Games, arXiv:1507.00407v5, p. 4, proof of Theorem 4, display after “so that”
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.