Online Learning and Regret Bounds

Most machine-learning training happens once, on a fixed batch of historical data, and then the model is frozen and deployed. Online learning instead updates the model after every single new observation, forever — a market-making quote model that revises itself after every fill, or a spread-prediction model that adjusts after every tick. There's no "training set" and "test set" in the usual sense; there's just a stream, and the question becomes how to measure whether the ongoing stream of decisions was any good.

What "regret" actually measures

After $T$ rounds, define regret as $R_T = \sum_{t=1}^{T} \ell_t(\theta_t) - \min_{\theta} \sum_{t=1}^{T} \ell_t(\theta)$, where $\ell_t$ is the loss suffered in round $t$, $\theta_t$ is the parameter the algorithm actually used at round $t$, and $\theta$ ranges over every fixed parameter choice you could have committed to from the start. In words: add up how much loss the algorithm actually incurred, subtract how much loss the single best strategy in hindsight would have incurred over that entire stretch, and the difference is regret. A standard result for online gradient descent on convex losses is $R_T = O(\sqrt{T})$ — regret grows, but slower than $T$ itself, so average regret per round, $R_T / T$, shrinks toward zero as more rounds accumulate.

Worked example

A spread-quoting model updates its bid-ask width after every trade using online gradient descent, and over $T = 10{,}000$ trades its regret bound guarantees $R_T \le c\sqrt{T} = c \times 100$ for some constant $c$ tied to the loss's smoothness. Suppose $c = 2$, so $R_T \le 200$ — the model's cumulative loss across all 10,000 trades is at most 200 loss-units worse than the single best fixed spread width chosen with full hindsight of every trade that would occur. That may sound unimpressive in absolute terms, but per-trade it's an average disadvantage of at most $200/10{,}000 = 0.02$ loss-units — and if the stream ran to 1,000,000 trades instead, the bound only grows to $\sqrt{100}\times$ larger ($2{,}000$), while the number of trades grew $100\times$, so the average disadvantage per trade falls to $0.002$: the online learner is closing in on hindsight-optimal performance as it sees more data, without ever needing to re-solve from scratch.

What this means in practice

Online learning fits any setting where the environment keeps changing and a batch-trained model would go stale — adaptive market-making, real-time fraud scoring, order-routing that adjusts to shifting venue liquidity. Regret bounds are a guarantee about the worst case over the sequence actually observed, not a promise about future accuracy in some absolute sense, and they typically assume the loss functions are convex; regret bounds for the non-convex losses that show up with neural networks are much weaker or unavailable.