What is the price of being wrong before you have enough evidence to know better?
A compressor begins a stream believing A and B are equally likely. Then A appears again and again. The model adapts, but the early codewords were longer than they would have been if the compressor had known the true bias from the beginning.
Those extra bits are a receipt for ignorance.
Information theory and online learning give us several precise ways to compare an adaptive strategy with a stronger benchmark. One of the most useful ideas is regret: how much worse did our sequential decisions perform than a reference strategy we wish we had known to use?
Quick Read
- A compressor often chooses probabilities or models before seeing the complete sequence.
- A hindsight benchmark can choose a better model after seeing all the data.
- Regret measures the excess loss or code length of the online strategy relative to that benchmark.
- Small regret means the cost of not knowing in advance grows slowly relative to the sequence.
- Universal coding can be understood partly as controlling the penalty for model uncertainty.
- Model switching creates regret when the source changes and adaptation lags.
- Regret turns “we learned eventually” into a quantitative question: how much did learning cost?
The One-Sentence Answer
Regret measures the extra description cost an adaptive or online compressor pays compared with a chosen benchmark that, with hindsight or extra knowledge, could have encoded the same sequence more efficiently.
The Oracle Who Knows the Coin
Suppose a coin lands heads 90% of the time.
An oracle knows this before the first flip. It immediately assigns high probability to heads and codes accordingly.
Our universal compressor does not know the bias. It starts uncertain and learns from observations.
After 10,000 flips, both may behave similarly. But the universal compressor paid extra bits early on.
Regret asks us to total that difference.
Why Hindsight Is Such a Strong Opponent
The benchmark may be allowed to inspect the entire sequence and then choose the best parameter or model from a specified class.
The online compressor had no such privilege. It made each prediction before the next symbol arrived.
Comparing them may seem unfair.
That is exactly why the comparison is useful. If an online strategy remains close even to this powerful hindsight benchmark, we have strong evidence that it adapts efficiently.
Log Loss Becomes Code Length
Prediction and compression are linked through logarithms.
If a model assigns probability p to what actually occurs, the associated idealised coding cost is roughly -log₂ p bits. Assign high probability to reality and the cost is small. Assign tiny probability and the cost is large.
Sum these costs across a sequence and predictive performance becomes cumulative description length.
Regret is therefore not merely emotional language borrowed by mathematics. It is literally a difference in accumulated loss—and under coding interpretations, a difference in bits.
Learning Faster Saves Bits
Two adaptive compressors eventually discover that A is common.
Compressor 1 adapts after ten observations. Compressor 2 takes ten thousand.
Both can claim they learned.
Only one learned cheaply.
Regret distinguishes eventual correctness from efficient adaptation.
But Adapting Too Fast Can Also Hurt
Suppose a fair coin happens to produce HHHHH at the beginning. A hyper-reactive model decides heads is almost certain. Then tails arrive and the model pays heavily.
Stable models resist small-sample noise. Responsive models follow genuine changes quickly.
Good online compression balances both.
Regime Change Creates Switching Regret
Imagine a text stream in English suddenly switches to computer code.
The model trained on English keeps expecting spaces, common words and familiar letter sequences. For a while, every wrong expectation costs bits.
Eventually the compressor adapts.
The interval between change and adaptation is expensive.
A stronger benchmark might be allowed to switch models at the correct moment. Comparing against it tells us how well our method handles non-stationarity.
Model Mixtures Hedge Regret
Instead of betting everything on one model, a compressor can combine several.
One model expects English prose. Another expects source code. Another expects numbers. Their weights change according to predictive success.
Mixtures pay some overhead for uncertainty but reduce the danger of catastrophic commitment to one wrong theory.
This is diversification expressed in bits.
The Benchmark Must Be Declared
“Low regret” means nothing without saying: regret relative to what?
- The best fixed probability distribution?
- The best model in a finite class?
- The best parameter chosen after seeing the sequence?
- The best sequence of models allowed a limited number of switches?
- An oracle with source knowledge?
A stronger benchmark makes the problem harder.
Good analysis names the opponent.
Regret and Redundancy Are Close Relatives
Universal source coding often speaks of redundancy: excess expected code length compared with a source-aware ideal. Sequential prediction often speaks of regret: excess cumulative loss compared with a benchmark.
The concepts are not interchangeable in every formal setting, but they share a deep theme: quantify the cost of not having perfect model knowledge.
Ignorance is no longer a vague disadvantage. It has a measurable price.
Finite Data Makes Regret Visible
Asymptotically, an extra 100 bits over a billion-symbol sequence may be negligible.
On a 50-byte message, 100 bits is enormous.
This is why finite-length performance matters. A universal method can be theoretically excellent in the long run yet poor for tiny messages because its learning overhead has not been amortised.
Cold Start Is Regret at the Beginning
A fresh compressor knows little about a source. Its early probabilities are broad. Its dictionaries are empty. Its context counts are sparse.
That is cold start.
A shared dictionary or pretrained model can reduce cold-start regret by bringing prior knowledge—but then we must count the cost of distributing that knowledge.
Every shortcut moves the bill somewhere.
Human Learning Has Regret Too
A student uses the wrong algebra method for ten questions before recognising the pattern. Another notices after one.
Both eventually learn the correct strategy.
The first paid a larger learning cost.
Education often measures final correctness but ignores the trajectory. Regret gives us a useful metaphor for accumulated unnecessary work before calibration.
Feedback Can Reduce Human Regret
Fast feedback tells a learner that the current model is wrong before twenty more errors accumulate.
A marked step, a teacher question or a test case changes the learner’s probability over strategies.
The purpose of feedback is not merely to label the past. It changes future decisions.
Primary School: Guess, Update, Count the Misses
Hide coloured counters in a bag with an unknown colour bias. Let pupils predict each draw and update their beliefs.
Compare a learner who updates gradually with one who never changes strategy. Count how many predictions each wastes.
Secondary School: Model Competition
Give students a sequence generated by one of several simple rules. Each rule predicts the next item. As observations arrive, students assign weights to the candidate rules.
They experience model mixtures and cumulative prediction loss.
JC and Beyond: Minimax Regret
At higher levels, universal coding can seek schemes that minimise worst-case regret over sequences relative to a model class. Normalized maximum likelihood is one celebrated MDL construction connected with minimax regret.
The mathematics asks an unusually fair question: if nature gives us the sequence most embarrassing for our coding strategy, how large can our disadvantage be relative to the best hindsight model?
A Regret Checklist
- What benchmark are we comparing against?
- How many extra bits did early uncertainty cost?
- How quickly does the model learn?
- How stable is it against small-sample noise?
- How quickly does it detect regime change?
- Would a mixture reduce commitment risk?
- Is the message long enough to amortise learning overhead?
- Would shared prior knowledge reduce regret enough to justify its setup cost?
The Deeper Point
Compression is not only about the final model.
It is about the path taken before the model became good.
A system that eventually understands the source may still have spent thousands of unnecessary bits getting there.
Regret is the price of learning the right compression after the message has already begun.
Explore the How Compression Works.