No-Regret Learning

No-regret learning is a class of online learning algorithms in which an agent's cumulative performance approaches the performance of the best fixed strategy in hindsight. The regret of an algorithm is the difference between the payoff it achieved and the payoff it would have achieved by consistently playing the optimal strategy, knowing the entire sequence of outcomes in advance. An algorithm is no-regret if this difference grows sublinearly — that is, the average regret per round approaches zero as the number of rounds increases.

No-regret learning originated in the analysis of repeated games and has become foundational in online learning, multi-agent reinforcement learning, and algorithmic game theory. The canonical algorithms — regret matching, multiplicative weights, and follow-the-regularized-leader — are computationally lightweight and require no model of the environment. This makes them the natural learning rules for boundedly rational agents in complex or non-stationary environments.

The connection to bounded rationality is direct: no-regret learning is what agents do when they cannot solve the game but can observe their own outcomes. It is also the formalization of adaptive expectations in strategic settings: agents update gradually, respond to feedback, and do not assume knowledge of the underlying model. The convergence of no-regret dynamics to Nash equilibrium in certain game classes — and to correlated equilibrium more broadly — provides the first rigorous bridge between bounded rationality and equilibrium behavior.

The rational expectations framework assumes that agents know the best strategy in advance and play it from the first period. No-regret learning assumes the opposite: that agents discover the best strategy through trial and error, paying a cost for exploration that diminishes over time. The first assumption produces elegant theorems; the second produces theories that might actually describe human behavior.