No-Regret Learning

The multiplicative weights update algorithm with learning rate $\eta = \sqrt{2 \ln K / T}$ achieves regret:

$R_T \leq \sqrt{2T \ln K}$

Equivalently, the average regret $R_T / T \leq \sqrt{2 \ln K / T} = O(1/\sqrt{T})$.

The bound has two notable features. First, the dependence on the number of actions is $\sqrt{\ln K}$, not $\sqrt{K}$. You can compete with exponentially many actions at only logarithmic cost. Second, the regret grows as $O(\sqrt{T})$, meaning the average regret $R_T/T$ vanishes as $O(1/\sqrt{T})$. No matter how the adversary behaves, the algorithm converges to the performance of the best fixed action.

The $O(\sqrt{T \ln K})$ regret bound is tight: no algorithm can achieve $o(\sqrt{T \ln K})$ regret against an adaptive adversary. This makes multiplicative weights optimal up to constants. The same algorithm, under different names (Hedge, exponentiated gradient, entropic mirror descent), appears throughout machine learning, optimization, and game theory.

The bound requires knowing $T$ in advance to set $\eta$. The doubling trick (restart with doubled horizon) removes this requirement at a constant factor cost. Also, the bound competes with the best fixed action. Competing with the best sequence of actions (shifting regret) requires stronger algorithms and incurs higher regret.

FTRL with a regularizer $R$ that is 1-strongly convex with respect to a norm $\|\cdot\|$ achieves:

$R_T \leq \frac{R_{\max}}{\eta} + \eta \sum_{t=1}^{T} \|\ell_t\|_*^2$

where $R_{\max} = \max_{p \in \Delta_K} R(p) - \min_{p \in \Delta_K} R(p)$. With optimal $\eta$, this gives $R_T = O(\sqrt{T})$.

FTRL balances exploitation (minimize cumulative loss so far) against exploration (the regularizer prevents the distribution from collapsing onto a single action too early). The learning rate $\eta$ controls this tradeoff. Large $\eta$ trusts past losses more (faster convergence, more variance); small $\eta$ regularizes more (slower convergence, more stability).

FTRL unifies many online learning algorithms. Choosing the regularizer and norm gives different algorithms: negative entropy yields multiplicative weights, squared $\ell_2$ norm yields online gradient descent. This framework extends naturally to online convex optimization where the action space is continuous.

If both players in a two-player zero-sum game use no-regret learning algorithms, then their average strategies $\bar{p} = \frac{1}{T}\sum_{t=1}^T p_t$ and $\bar{q} = \frac{1}{T}\sum_{t=1}^T q_t$ converge to a Nash equilibrium. Specifically, the pair $(\bar{p}, \bar{q})$ is an $\epsilon$-Nash equilibrium with $\epsilon = (R_T^{(1)} + R_T^{(2)})/T$, where $R_T^{(1)}$ and $R_T^{(2)}$ are the regret of each player.

In a zero-sum game, player 1's loss is player 2's gain. If both players have low regret, neither can improve much by deviating to any fixed strategy. This is precisely the definition of a Nash equilibrium (up to the regret slack). The minimax theorem guarantees that Nash equilibria exist in zero-sum games, and no-regret learning provides a constructive, decentralized method to find them.

This theorem is the theoretical foundation for self-play in AI. When you train a poker AI or a Go-playing agent by having it play against itself, you are implicitly running no-regret dynamics. The convergence guarantee says that the resulting average strategy is approximately optimal against any opponent. Counterfactual regret minimization (CFR), the algorithm behind superhuman poker AI, is a specific instantiation of this principle.

Convergence is for average strategies, not last-iterate strategies. The actual play $p_t$ may cycle or oscillate even as the average converges. Also, the result is specific to zero-sum games. In general-sum games, no-regret dynamics may not converge to Nash equilibria (they converge to the weaker notion of coarse correlated equilibria).