Corollary 12, p. 5 — OFTRL with η = (n−1)^{−1/2}T^{−1/4} for every player: each regret ≤ (R+4)√(n−1)·T^{1/4}

Consider an $n$-player game with $n\ge2$ in which every player has $d$ strategies 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 every range: $\mathcal R_i(f)-\mathcal R_i(g)\le R$ for all $i$ and all $f,g\in\Delta$. Fix a horizon $T\ge1$ and the step size

Suppose the game is played repeatedly and every player runs optimistic FTRL with regularizer $\mathcal R_i$, step size $\eta$ and one-step recency bias $M_i^t=u_i^{t-1}$, where $u_i^t$ is player $i$'s utility vector against the profile $w^t$ played at time $t$. Then for every player $i$ and every fixed strategy $w_i^*\in\Delta$,

Each player's regret thus grows like $T^{1/4}$, so its average regret decays like $T^{-3/4}$, against the $T^{-1/2}$ rate that holds against an adversary. It is the paper's result on the convergence of individual utilities.

Formalization Note The conditions $n\ge2$ and $T\ge1$ are added because the step size is undefined otherwise. The paper's $R=\max_i(\sup_\Delta\mathcal R_i-\inf_\Delta\mathcal R_i)$ is replaced by any common upper bound on the ranges, which includes the exact value. The regret $r_i(T)=\sup_{w^*}\sum_t\langle w^*-w_i^t,u_i^t\rangle$ is bounded through every comparator $w^*\in\Delta$. The statement covers every run of the dynamics, and the vector $u_i^0$ entering $M_i^1$ is the utility vector against $w^0$. The horizon $T$ is fixed before play, because $\eta$ depends on it.