Regret Minimization
Regret measures how much worse a sequence of decisions did than the best fixed choice in hindsight; minimizing it is the goal of online learning.
Defining regret
Regret compares an adaptive learner's cumulative loss against a benchmark chosen with perfect hindsight. External regret uses the best single fixed action as the benchmark: regret = sum of losses incurred minus the loss the best fixed action would have incurred over the same sequence. If regret grows slower than the number of rounds T, then the per-round regret vanishes and the learner is, on average, as good as the best fixed action.
Varieties of regret
External regret compares to the best fixed action. Internal (or swap) regret compares to the best strategy that consistently swaps one action for another, a stronger benchmark. Dynamic regret compares to a changing sequence of best actions and is appropriate for nonstationary environments. Each notion demands a different algorithm and yields a different achievable rate.
- External regret: versus the best single fixed action
- Swap/internal regret: versus the best action-relabeling
- Dynamic regret: versus a time-varying comparator
- Adaptive/tracking regret: versus the best action on each segment
No-regret algorithms
An algorithm is no-regret if its average external regret tends to zero. Multiplicative weights (the Hedge algorithm) is the classic example, achieving O(sqrt(T log n)) regret over n actions by exponentially reweighting actions according to their accumulated loss. Online gradient descent is the continuous-space counterpart. These algorithms need no model of the environment and tolerate adversarial inputs.
The game-theory connection
Regret minimization has a deep link to game theory. If every player in a repeated game runs a no-regret algorithm, the empirical distribution of play converges to a coarse correlated equilibrium; with no-swap-regret, to a correlated equilibrium. This makes regret minimization both a practical online-learning tool and a decentralized route to equilibrium, and it is the engine behind superhuman play in large imperfect-information games such as poker via counterfactual regret minimization.