Online learning and regret bounds: why continuous ingestion follows

Scoring a sequence of guesses

Suppose you must act in rounds. Each round, before you know the outcome, you commit to a decision. Afterwards a loss is revealed — how wrong you were, how much it cost. You cannot change the decision retroactively, and you do not get to see the future before choosing. This is the setting online learning studies, and it is deliberately stripped of the assumptions that decision theory usually leans on. No distribution generates the data. No stationarity is assumed. No model of the underlying process is required to get started.

What replaces those assumptions is a comparison. You do not ask whether your decisions were good in some absolute sense — good against what? You ask how you did against a benchmark: the best decision, chosen after the fact, from some fixed class of candidate decisions. The gap between what you actually accrued in losses and what that best-in-hindsight candidate would have accrued is called regret. An algorithm is useful to the extent its regret grows slowly. Online gradient descent, for instance, can guarantee that regret grows no faster than the square root of the number of rounds, which means average regret per round shrinks to zero as the game goes on. You never catch the best fixed choice exactly, but you get arbitrarily close to matching it on average, without ever having known in advance what it was.

The elegance here is structural. The guarantee holds against any sequence of outcomes whatsoever — adversarial, random, cyclical, anything. There is exactly one place where an assumption sneaks in, and it is worth naming before it becomes load-bearing later: the comparator class. You have to decide what you are being compared against. Everything else in the framework is assumption-free; that one choice is not.

Where the idea came from

The mathematics traces to James Hannan, working in the mid-1950s on the compound decision problem — how to play a repeated game well against an opponent about whom you know nothing. Hannan showed that a player could achieve, asymptotically, the same average payoff as the best fixed action in hindsight, no matter how the opponent behaved. This property is now called Hannan consistency, and it sits alongside David Blackwell's approachability theorem from the same period as one of the founding results of what would become online learning theory.

The idea lay somewhat dormant as a decision-theoretic curiosity until Nick Littlestone and Manfred Warmuth's weighted majority algorithm, in 1994, gave it a computational form suited to prediction with expert advice. Martin Zinkevich's online gradient descent, in 2003, generalised it to convex optimisation and gave the field its modern shape. The problem all of this solved, across five decades, was the same one: how to give a performance guarantee to a sequential decision-maker without pretending to know the process generating the world. Replace the model of the world with a comparator, and prove a bound relative to it.

The comparator problem

There are, in the end, only two honest choices of comparator, and a third option that isn't really a comparator at all.

You can compare yourself against the best single fixed action, chosen once, with hindsight over the whole sequence. This is static regret — the setting Hannan solved, the setting Cover's universal portfolio (1991) solved for wealth allocation, attaining regret that grows only logarithmically in the number of trading periods against the best constant-rebalanced portfolio. It is a genuine result. It is also a result about a fixed portfolio. A fund manager living through a sector rotation, a change in the rate regime, or a delisting is not being scored against anything relevant by that guarantee; the best fixed weighting for the whole period is not the object anyone cares about matching.

Or you can compare yourself against a sequence of best actions, one chosen anew each round with hindsight — dynamic regret. This is the harder, more honest question: not "did you match the best thing to have done throughout," but "did you keep up with the best thing to do now, as now kept changing." Herbster and Warmuth's fixed-share algorithm, in 1998, gives a bound of this kind: regret against a comparator that switches between k experts costs roughly k times the log of the number of experts, on top of the usual term. That switching cost is not a defect in the algorithm. It is the price, made explicit and payable, of tracking a moving target instead of a fixed one.

And here is the fact that does the work in this argument: dynamic regret bounds are provably unachievable without continued observation. Every bound of this type in the literature is stated in terms of a quantity — path length, number of switches, variation budget — that can only be estimated by watching the sequence unfold. Besbes, Gur and Zeevi's 2015 result on non-stationary bandits makes the trade explicit: with a variation budget of size V_T over T rounds, the best achievable dynamic regret scales as T^(2/3)·V_T^(1/3), strictly worse than the √T of the stationary case, and the algorithm that achieves it has to restart on a schedule tuned to an estimate of V_T. No amount of data collected before round one tells you what V_T is. You find out by living through the rounds.

The turn to intake

This is where the three generations in the lineage separate cleanly, because they occupy exactly the three positions the comparator taxonomy allows.

A Large Language Model is a single weight vector, chosen once, against a corpus that was frozen at some cutoff. It is, whether its builders phrase it this way or not, a static-regret object: it can be scored against the best fixed action over that corpus, and it can be scored against nothing else with any rigour. From the moment of the cutoff, it begins accruing dynamic regret against a world that keeps moving, and there is no mechanism by which it could measure how much, because measuring requires exactly the ongoing observation the model was not built to receive.

A Large World Model narrows the comparator to the present: it is scored, well, against the currently sensed scene, and while the scene lasts that is the correct comparator to use. But a scene ends, another begins, and nothing in the architecture accounts for the interval — the path length between one bounded episode and the next goes entirely unmeasured. The model performs well inside each window and has no error signal about the gap between windows.

A Large Universe Model is what the taxonomy leaves as the remaining slot: the intake regime in which the moving comparator — and therefore the variation budget that dynamic regret bounds are expressed in — becomes something you can actually estimate, because the streams that would let you estimate it are still running. Beliefs are held with provenance and revision dates specifically because the object being tracked is not the state of the world but the rate at which the state of the world is changing.

Three objections, one that narrows the claim

Dynamic regret bounds are mostly vacuous in practice. If the variation budget grows linearly with time, the bound is worse than trivial. The argument for continuous intake rests on a quantity that real environments routinely blow through.

This is the sharpest objection and it should not be waved off. A bound of order √(T·V_T) tells you nothing when V_T scales with T itself. But the failure is symmetric. If the environment is moving that fast, the static comparator fares worse, not better — a frozen model is not a safer fallback, it is a guaranteed loser against the same variation. What continuous intake buys is not a guarantee of good performance; it is the ability to detect that your problem has become untrackable. Vacuity you can see coming is a different situation from vacuity you cannot measure at all.

Continuous updating is a documented route to instability — adaptive controllers that never stop adapting can chase noise or be steered by a poisoned stream. Periodic retraining under review, with some loss of freshness, is the safer trade.

Correct, and the instability is real; bursting in adaptive control and demonstrated poisoning attacks on continuously updated recommenders are not hypothetical. But the remedy in the literature is not to stop observing. It is to constrain how observation is allowed to move the estimate: trust regions, forgetting factors, fixed-share priors that cap the switching rate. Every one of those mechanisms needs the stream to operate on. Restraint is a control law applied to intake, not a reason to close it.

Regret is relative to a comparator class you chose. A richer stream fed into an inadequate hypothesis class just produces confident wrongness. The binding constraint is representation, not observation.

Granted without qualification: low regret inside a poor class is a poor result, and this caveat has been attached to Hannan consistency since it was first proved. But class adequacy is itself an empirical claim, and only sustained observation falsifies it. Misspecification shows up as structure in the residuals over time — autocorrelation, regime-dependent bias — and that structure is invisible to a system that samples once. Observation does not repair a bad model. It is the only mechanism by which a bad model's badness becomes visible.

The misreading to disown

The weak, popular version of this argument says regret theory proves that continuous updating simply outperforms static models, so the sensible policy is always to keep learning. That is not what has been shown, and it should not be attributed to this theory. Regret bounds are relative claims, not absolute ones. An algorithm with vanishing regret against a bad comparator class can still perform badly in every round; matching the best available option is worthless if every available option is poor. And unconstrained adaptation degrades measurably under noise — the instability objection above is not a strawman.

What the theory actually forces is narrower and, for that reason, harder to argue around: the moment you stop pretending the optimum is fixed, your performance guarantee acquires terms that no archive can supply, because they are properties of a path that has not finished being walked.

What this does and does not establish

The argument establishes that there are exactly two coherent scoring rules for sequential decisions under an uncontrolled distribution, that the more honest of the two requires quantities only observable in motion, and that this is a fact about the mathematics of regret, not a preference for freshness. It places a hard floor under the claim that a frozen system can be scored on anything beyond the sample it was frozen against.

It does not establish that continuous ingestion produces good decisions. It does not establish that any particular architecture handles a moving comparator well, or that adaptation is safe by default, or that representation problems dissolve once observation is continuous. It says, more modestly, that once stationarity is denied — and no operational environment sustains it indefinitely — the comparator that matters is one whose defining quantities go unmeasured without a live stream. That is a claim about what can be known, not a claim about what has been built.