No-Regret Learning

Learning dynamics where a player's cumulative payoff is no worse than the best fixed action in hindsight, up to a vanishing average error.

Ask the Game theory assistant1 min read · Updated September 9, 2026

Definition

Cumulative regret of player $i$ after $T$ rounds is $R_i(T)=\max_{s_i^*}\sum_{t=1}^T u_i(s_i^*,s_{-i}^t)-\sum_{t=1}^T u_i(s_i^t,s_{-i}^t)$ . A no-regret algorithm guarantees $R_i(T)=o(T)$ (sublinear).

Hannan (1957): there exist strategies ensuring $\lim_{T\to\infty} R_i(T)/T = 0$ in any finite game.

Intuition

No-regret means you eventually do as well as any fixed strategy — you learn to avoid systematic exploitation.

It does not require knowledge of the game or opponents — only observed payoffs.

Worked example

Multiplicative weights / Hedge algorithm achieves regret $O(\sqrt{T\log n})$ in any finite action set.

In a repeated matching-pennies game, no-regret play converges to the minimax value.

The math

Hart-Mas-Colell (2000): if all players use no-regret algorithms, empirical play converges to the set of correlated equilibria.

"No internal regret" and "no swap regret" characterize convergence to correlated and coarse-correlated equilibria.

Where it is used

Online learning, multi-agent systems, algorithmic game theory, and AI training (regret-based policy improvement).

Core theoretical foundation for multi-agent reinforcement learning.

Go deeper

More in Game theory

Assembled from the ReLU.chat curated knowledge base. These explanations are concise on purpose; check the sources for anything important.