Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4, p. 4 — RVU for every player with β ≤ γ/(n−1)² and ‖·‖ = ‖·‖₁ implies Σᵢ rᵢ(T) ≤ αn

Proved
RegLearnGames.TotalRegret.theorem_4

by mikedeng1 · Oct 9, 2026 · Mathlib 0df444a (Lean v4.33.1)

no-regret-dynamicsnormal-form-gamesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1regretrvu-property

Consider an nnn-player game with ddd strategies per player and utilities ui(s)∈[0,1]u_i(s) \in [0,1]ui​(s)∈[0,1], played repeatedly: w0,w1,…w^0, w^1, \dotsw0,w1,… are mixed profiles and uit=ui(wt)u_i^t = u_i(w^t)uit​=ui​(wt) is player iii's utility vector at time ttt (so ui0u_i^0ui0​ is computed from w0w^0w0). Let α>0\alpha > 0α>0 and 0<β≤γ0 < \beta \le \gamma0<β≤γ with β(n−1)2≤γ\beta(n-1)^2 \le \gammaβ(n−1)2≤γ, and fix a horizon TTT. Suppose each player's play satisfies the RVU inequality with these constants and ∥⋅∥=∥⋅∥1\|\cdot\| = \|\cdot\|_1∥⋅∥=∥⋅∥1​: for every player iii and every v∈Δv \in \Deltav∈Δ,

∑t=1T⟨v−wit,uit⟩≤α+β∑t=1T∥uit−uit−1∥∞2−γ∑t=1T∥wit−wit−1∥12.\sum_{t=1}^T\langle v - w_i^t, u_i^t\rangle \le \alpha + \beta\sum_{t=1}^T \|u_i^t - u_i^{t-1}\|_\infty^2 - \gamma \sum_{t=1}^T \|w_i^t - w_i^{t-1}\|_1^2.t=1∑T​⟨v−wit​,uit​⟩≤α+βt=1∑T​∥uit​−uit−1​∥∞2​−γt=1∑T​∥wit​−wit−1​∥12​.

Then for every profile of comparators (wi∗)i(w_i^*)_i(wi∗​)i​ with each wi∗∈Δw_i^* \in \Deltawi∗​∈Δ,

∑i∑t=1T⟨wi∗−wit,uit⟩≤αn,\sum_{i} \sum_{t=1}^T \langle w_i^* - w_i^t, u_i^t\rangle \le \alpha n,i∑​t=1∑T​⟨wi∗​−wit​,uit​⟩≤αn,

that is, ∑iri(T)≤αn\sum_i r_i(T) \le \alpha n∑i​ri​(T)≤αn.

The sum of all players' regrets is therefore bounded by a constant independent of TTT; with Proposition 2 this makes the average welfare converge to within the price of anarchy of the optimum at rate O(1/T)O(1/T)O(1/T).

Formalization Note The paper's condition β≤γ/(n−1)2\beta \le \gamma/(n-1)^2β≤γ/(n−1)2 is written β(n−1)2≤γ\beta(n-1)^2 \le \gammaβ(n−1)2≤γ, which agrees for n≥2n \ge 2n≥2 and avoids division by zero at n=1n = 1n=1. The RVU inequality is assumed only on the realized play and for the given horizon, a weaker hypothesis than the paper's "on any sequence of utilities", so the statement is a disclosed strengthening. The bound on ∑iri(T)\sum_i r_i(T)∑i​ri​(T) is stated for every comparator profile, which is equivalent to bounding the sum of suprema.

Preamble
import Mathlib
import Definitions.Def_RegLearnGames_TotalRegret_Setting
Formal statement
namespace RegLearnGames.TotalRegret

theorem theorem_4 {n d : ℕ} (u : Fin n → (Fin n → Fin d) → ℝ)
    (hu : ∀ i s, u i s ∈ Set.Icc (0 : ℝ) 1)
    (w : ℕ → Fin n → Fin d → ℝ) (hw : ∀ t i, w t i ∈ stdSimplex ℝ (Fin d))
    (α β γ : ℝ) (hα : 0 < α) (hβ : 0 < β) (hβγ : β ≤ γ)
    (hβγn : β * ((n : ℝ) - 1) ^ 2 ≤ γ) (T : ℕ)
    (hRVU : ∀ i, ∀ v ∈ stdSimplex ℝ (Fin d),
      ∑ t ∈ Finset.Icc 1 T, (v - w t i) ⬝ᵥ utilVec u (w t) i ≤
        α + β * ∑ t ∈ Finset.Icc 1 T, ‖utilVec u (w t) i - utilVec u (w (t - 1)) i‖ ^ 2
          - γ * ∑ t ∈ Finset.Icc 1 T, l1 (w t i - w (t - 1) i) ^ 2)
    (wstar : Fin n → Fin d → ℝ) (hwstar : ∀ i, wstar i ∈ stdSimplex ℝ (Fin d)) :
    ∑ i, ∑ t ∈ Finset.Icc 1 T, (wstar i - w t i) ⬝ᵥ utilVec u (w t) i ≤ α * n := by sorry

end RegLearnGames.TotalRegret
Source
Syrgkanis, Agarwal, Luo, Schapire, Fast Convergence of Regularized Learning in Games, arXiv:1507.00407v5, p. 4, Theorem 4; Definition 3, inequality (1), p. 3
Human review
  • Endorsed by Shuze Chen · Oct 9, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 9, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me