Corollary 8, p. 5 — optimistic FTRL with η = 1/(2(n−1)) for every player: Σᵢ rᵢ(T) ≤ nR/η = 2n(n−1)R

Consider an $n$-player game, $n \ge 2$, with $d$ strategies per player and utilities $u_i(s) \in [0,1]$. Each player $i$ has a regularizer $\mathcal R_i$ that is 1-strongly convex with respect to $\|\cdot\|_1$ on the simplex $\Delta$, and $R$ bounds the range of every regularizer on $\Delta$: $\mathcal R_i(f) - \mathcal R_i(g) \le R$ for all $i$ and $f, g \in \Delta$ (so $R$ may be taken to be $\max_i(\sup_\Delta \mathcal R_i - \inf_\Delta \mathcal R_i)$). Suppose every player runs optimistic FTRL with step size

and one-step recency bias $M_i^t = u_i^{t-1}$, where $u_i^t$ is player $i$'s utility vector against the others' mixed strategies at time $t$ (with $u_i^0$ computed from the initial profile $w^0$). Then for every horizon $T$ and every profile of comparators $(w_i^*)_i$ with each $w_i^* \in \Delta$,

that is, $\sum_{i} r_i(T) \le nR/\eta = 2n(n-1)R$, a bound independent of $T$.

This is the paper's constant bound on the total regret of uncoupled no-regret dynamics in general games; with Proposition 2 it gives convergence of the average welfare at rate $O(1/T)$.

Formalization Note The statement holds for every joint trajectory produced by the dynamics (OFTRL is an argmax predicate). $2 \le n$ is added because $\eta$ is undefined at $n = 1$. Per-player regularizers are allowed (footnote 2), a generalization of a common $\mathcal R$. Continuity of each $\mathcal R_i$ on $\Delta$ is part of strong convexity here (see the Setting). The "$= O(1)$" of the page is not stated; the identity $nR/\eta = 2n(n-1)R$ is the second conjunct.