Smoothness step, supp. p. 10 — expected deviation cost is at most λOPT′ + µC(w)
ProvedRegLearnGames.FirstOrder.smoothness_stepalgorithmic-game-theoryexpected-costp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1smooth-games
Let witness -smoothness: for every pure profile , the sum of costs incurred by players who each unilaterally switch to is at most . For every mixed profile ,
This transfers the pure-profile smoothness inequality to the independent mixed play generated during learning.
Formalization Note The Lean statement takes the explicit witness condition from equation (20), rather than an arbitrary unrelated profile. No sign assumptions on or are needed for this expectation step.
Preamble
import Mathlib import Definitions.Def_RegLearnGames_FirstOrder_Setting
Formal statement
namespace RegLearnGames.FirstOrder
open Finset
/-- Expected unilateral deviation costs are bounded by smoothness. -/
theorem smoothness_step {n d : ℕ} [NeZero d]
(c : Fin n → (Fin n → Fin d) → ℝ)
(w : Fin n → Fin d → ℝ) (hw : AGT.IsMixedProfile w)
(lam mu : ℝ) (sstar : Fin n → Fin d)
(hsmooth : ∀ s : Fin n → Fin d,
(∑ i, c i (Function.update s i (sstar i))) ≤
lam * optCost c + mu * socialCostPure c s) :
(∑ i, costVec c w i (sstar i)) ≤
lam * optCost c + mu * socialCost c w := 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), display after equation (22), beginning ‘By the smoothness assumption’
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.