Proof of Theorem 11, p. 5 — ‖uᵢ − uᵢ′‖²_* ≤ (n−1)Σ_{j≠i}‖wⱼ − wⱼ′‖² ≤ (n−1)²κ²
ProvedRegLearnGames.IndivRegret.theorem_11_variation_boundno-regret-dynamicsnormal-form-gamesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1regret
Consider an -player game in which every player has strategies and utilities . Let and be two mixed profiles, and let bound every player's movement: for all . Write and for player 's utility vectors against and against . Then for every player ,
Applied to consecutive profiles of a repeated game, this bounds the variation of player 's utilities by the movement of the other players; summed over it turns the RVU property into the regret bound of Theorem 11.
Formalization Note The movement bound is assumed for every player , including , as in the stability property of Theorem 11, which holds for all players.
Preamble
import Mathlib import Definitions.Def_RegLearnGames_TotalRegret_Setting
Formal statement
namespace RegLearnGames.IndivRegret
theorem theorem_11_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))
(κ : ℝ) (hκ : ∀ j, RegLearnGames.TotalRegret.l1 (w j - w' j) ≤ κ) :
∀ i, ‖RegLearnGames.TotalRegret.utilVec u w i - RegLearnGames.TotalRegret.utilVec u w' i‖ ^ 2 ≤
((n : ℝ) - 1) * ∑ j ∈ Finset.univ.erase i, RegLearnGames.TotalRegret.l1 (w j - w' j) ^ 2 ∧
((n : ℝ) - 1) * ∑ j ∈ Finset.univ.erase i, RegLearnGames.TotalRegret.l1 (w j - w' j) ^ 2 ≤
((n : ℝ) - 1) ^ 2 * κ ^ 2 := by sorry
end RegLearnGames.IndivRegret
Source
Syrgkanis, Agarwal, Luo, Schapire, Fast Convergence of Regularized Learning in Games, arXiv:1507.00407v5, p. 5, §3.2, the display after Theorem 11 ("Similar reasoning as in Theorem 4 yields")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.