Regret, equilibrium, and learning in games: A guided tour
Panayotis Mertikopoulos
cs.GT, cs.LG, math.OC
2026-08-10
Unifies single-agent bandit regret with multi-agent equilibrium convergence under one regularized-learning template; strict Nash equilibria emerge as the only stable attractors.
Game theory has an old question called "as-if rationality": when selfish, short-sighted agents who may not even know they are in a game play repeatedly, do they drift to a Nash equilibrium? In the 1950s this was a theoretical curiosity. In machine learning it is an engineering problem. Ad auctions, recommender systems, multi-agent reinforcement learning, and GAN training are all learners playing games, and none of the standard rationality postulates (everyone knows the rules, can compute equilibria, executes them perfectly) holds.
This is a guided tour by Mertikopoulos (Grenoble/CNRS/Inria) that stitches the question's two threads together. One thread is single-agent "playing against nature": a learner faces an arbitrary, possibly adversarial sequence of payoff vectors and tries to drive down regret, the gap between cumulative payoff and the best fixed action in hindsight. This is the adversarial multi-armed bandit. The other thread is multi-agent and closed-loop: several players interact, payoffs are shaped by everyone's actions, and the question is whether play converges and to what. Both threads hang off one template, regularized learning.
Two negative results frame what is possible. Computing a Nash equilibrium is PPAD-complete (Daskalakis et al.), so general poly-time computation is off the table. And Hart and Mas-Colell proved no uncoupled dynamics converge to Nash in all games. The live question is therefore not "does it converge" but "in which game classes, under which policies".
The core template is follow-the-regularized-leader (FTRL): each round, best-respond to the cumulative payoff history minus a regularization penalty h that encourages exploration and prevents over-commitment. The penalty is what makes the whole thing work. Without it, follow-the-leader (FTL) is too predictable and gets exploited; a two-armed bandit counterexample in the paper has FTL always one round behind the optimal arm, with regret growing as Θ(T). A strongly convex regularizer smooths the strategy sequence and kills the catastrophic back-and-forth.
The iterative form is compact: accumulate each round's payoff into a "score" vector y, then map the score to a mixed strategy through a choice map Q(ηy). Swapping the regularizer h yields a family of classic algorithms:
Oracle (full-information) and bandit (payoff-only) feedback are unified through a black-box model (BBM): the learner receives not the true payoff vector v but an estimate v̂ = v + Z, whose variance and bias are set by the feedback type. Under full information Z is zero; under bandit feedback its variance is O(1/δ), with δ the exploration parameter. One analysis covers both.
Single-agent regret (Theorem 2): FTRL with a K-strongly convex regularizer and constant step size η satisfies E[Reg(T)] ≤ H/η + ηM²T/(2K); tuning η to (1/M)√(2KH/T) gives the standard O(√T). The engine is a potential function called the Fenchel coupling. In continuous time FTRL regret is a constant O(1), and discrete time adds a controllable discretization error that strong convexity is precisely what controls.
Bandit side:
| Algorithm | Feedback | Regret |
| EXP3 | bandit | O(√(AT log A)), the first no-regret bandit algorithm |
| Tsallis-INF | bandit | O(√(AT)), optimal, shaving the log A off EXP3 |
On the multi-agent side, two-player zero-sum games carry the main positive result (Theorem 4): the equilibrium gap of the ergodic average x̄T (a step-size-weighted time average) converges at Õ(T^{-min{1-p, β, p-2μ}}). Plugging in concrete algorithms gives Õ(T^{-1/2}) for full-information (EW/SEW) and Õ(T^{-1/3}) for bandit (EXP3/Tsallis-INF), with the latter tighten-able to T^{-1/2} via a local-norm argument.
The centerpiece is the "folk theorem of regularized learning" (Theorem 5), which ports the classical folk theorem of replicator dynamics from evolutionary game theory to discrete, stochastic learning:
The upshot is that mixed (non-pure) Nash equilibria are not attractors. Regularized learning avoids them in the long run; only strict (pure) Nash equilibria persist. This is "survival of the strictest." Even under bandit feedback and even with a constant step size, strict Nash equilibria remain asymptotically stable, a property unusually strong for stochastic approximation.
For anyone deploying multi-agent learning systems (MARL, GANs, ad auctions, recommenders), this is a convergence expectation. If your game has a strict (pure) Nash equilibrium, no-regret learners will find it and stick; do not assume they converge to mixed equilibria. That is both a guarantee (strict equilibria are reachable even with bandit feedback and constant step size) and a warning (in general-sum games, convergence is not assured).
The unification is the engineering payoff: oracle and bandit versions are two special cases of one analysis, with explicit rates for both. As a survey rather than a new method, its value is synthesis. One Fenchel-coupling thread runs from bandit regret bounds all the way to equilibrium convergence, turning results scattered across game theory, optimization, and probability into a single story.
The author repeatedly flags that the note only scratches the surface: extensive-form and stochastic games, extra-gradient and optimistic variants are deferred to a longer treatise.
More substantively, the zero-sum convergence is for the ergodic average x̄T, not the actual iterate xt, which can drift along the boundary of the simplex. Last-iterate convergence needs an extrapolation step (extra-gradient), not treated in depth. The folk theorem's converse is also incomplete in the stochastic case (Remark 9).
The structural limit is sharper: two-player zero-sum is the only general positive multi-agent result. General-sum games get only the folk-theorem-style statement that strict Nash equilibria alone are stable, with no general convergence guarantee. The PPAD-completeness of Nash and the Hart and Mas-Colell impossibility loom over everything, and the survey neither can nor tries to overturn them. Finally, the whole thing is convex analysis and stochastic approximation, dense and purely theoretical; the "applications to ML" appear as motivation, with no experiments.