Equation (22), supp. p. 10 — aggregate first-order regret bound
ProvedRegLearnGames.FirstOrder.eq_22algorithmic-game-theoryfirst-order-regretp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1smooth-games
Consider players with strategies each and costs in . Let be a mixed profile at each round through . Suppose every player satisfies the first-order bound (21) with constants and . For any fixed pure profile , write . Then
This is the aggregate cost bound before the smoothness condition is used.
Formalization Note The source's Cauchy–Schwarz step requires , stated explicitly here. The printed final sum in (22) uses as both bound and index; the index is read as . The is natural logarithm.
Preamble
import Mathlib import Definitions.Def_RegLearnGames_FirstOrder_Setting
Formal statement
namespace RegLearnGames.FirstOrder
open Finset
/-- The final line of display (22), after the sum over players. -/
theorem eq_22 {n d : ℕ} [NeZero d]
(c : Fin n → (Fin n → Fin d) → ℝ)
(hc : ∀ i s, c i s ∈ Set.Icc (0 : ℝ) 1)
(w : ℕ → Fin n → Fin d → ℝ) (T : ℕ)
(hw : ∀ t ∈ Finset.Icc 1 T, AGT.IsMixedProfile (w t))
(A₁ A₂ : ℝ) (hA₁ : 0 ≤ A₁)
(hreg : HasFirstOrderRegret c w T A₁ A₂)
(sstar : Fin n → Fin d) :
(∑ t ∈ Finset.Icc 1 T, socialCost c (w t)) ≤
(∑ t ∈ Finset.Icc 1 T, ∑ i, costVec c (w t) i (sstar i)) +
A₁ * Real.sqrt ((n : ℝ) * Real.log (d : ℝ)) *
Real.sqrt (∑ t ∈ Finset.Icc 1 T,
∑ i, costVec c (w t) i (sstar i)) +
A₂ * (n : ℝ) * Real.log (d : ℝ) := by sorry
end RegLearnGames.FirstOrder
Source
Syrgkanis, Agarwal, Luo, Schapire, Fast Convergence of Regularized Learning in Games, arXiv:1507.00407v5, supp. p. 10 (PDF p. 19), equation (22)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.