Proof of Theorem 4, display (2), p. 4 — ‖uᵢ(w)−uᵢ(w′)‖_* ≤ TV of the product of the others ≤ Σ_{j≠i}‖wⱼ−w′ⱼ‖₁
ProvedRegLearnGames.TotalRegret.display_2normal-form-gamesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1product-distributionstotal-variation
Consider an -player game with strategies per player and utilities . Let and be two mixed profiles (every ), and fix a player . Write for player 's utility vector against . Then
where the middle sum runs over all strategy choices of the players other than .
The middle quantity is (twice) the total variation distance between the two product distributions of the opponents' play; the second inequality is the subadditivity of total variation over product measures. In the paper it is applied with and .
Formalization Note The index set is the subtype {j : Fin n // j ≠ i}; is Mathlib's sup norm.
Preamble
import Mathlib import Definitions.Def_RegLearnGames_TotalRegret_Setting
Formal statement
namespace RegLearnGames.TotalRegret
theorem display_2 {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 : Fin n) :
‖utilVec u w i - utilVec u w' i‖ ≤
∑ s : {j : Fin n // j ≠ i} → Fin d, |∏ j, w j.1 (s j) - ∏ j, w' j.1 (s j)| ∧
∑ s : {j : Fin n // j ≠ i} → Fin d, |∏ j, w j.1 (s j) - ∏ j, w' j.1 (s j)| ≤
∑ j : {j : Fin n // j ≠ i}, l1 (w j.1 - w' j.1) := 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, first display and display (2)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.