The algorithm is almost too small to deserve its reputation.

Keep a weight for each adviser. Ask them all what to do. Lose a little. Multiply the weights of the advisers that lost more. Repeat.

That is the multiplicative weights update method. It is a voting rule, a portfolio rule, an online-learning rule, a game-playing rule, and one of the quiet engines inside boosting. Arora, Hazan, and Kale describe it as a meta-algorithm: maintain a distribution over a set, update the distribution multiplicatively, then analyze the whole process with an exponential potential.1

The surprising thing is not that the algorithm works in friendly worlds. The surprising thing is that it gives a useful receipt in hostile ones.

You can feed it losses chosen after the learner has already placed its weight. You can make one adviser look brilliant for a while, then punish anyone who trusted it. You can make the best strategy visible only in hindsight. The learner may look gullible round by round, but its cumulative loss is pinned close to the loss of the best fixed adviser after the fact.

That is a very particular kind of intelligence:

not "I know the future"
but "I will not pay much more than the best constant story I could have told"

A Ledger With Teeth

Suppose there are N experts. On round t, the learner has nonnegative weights w_t,i. It turns them into probabilities:

p_t,i = w_t,i / sum_j w_t,j

Then the world reveals a loss vector:

loss_t,i in [0, 1]

The learner pays the mixture loss:

sum_i p_t,i loss_t,i

and updates:

w_{t+1,i} = w_{t,i} exp(-eta loss_t,i)

Bad losses do not subtract capital. They shrink it by a factor. That one choice is the entire personality of the method.

If an expert loses 0, its weight is unchanged. If it loses 1, its weight is multiplied by exp(-eta). If it repeatedly loses, the punishment compounds. The learner is not averaging scores in a notebook. It is moving probability mass away from explanations that keep costing it.

For losses in [0, 1], this version of exponential weights satisfies a compact certificate:

L_algorithm <= min_i L_i + log(N) / eta + eta T / 8

where T is the number of rounds, L_algorithm is the learner’s cumulative mixture loss, and min_i L_i is the cumulative loss of the best single expert chosen in hindsight.

The two extra terms are the price of not knowing:

log(N) / eta   pays for searching among experts
eta T / 8      pays for being aggressive with noisy evidence

Make eta tiny and the learner is polite, slow, and pays a large search tax. Make eta huge and it moves fast, but can overreact to early noise. The theorem is not a magic learning-rate oracle. It is a tradeoff written on the receipt.

Hedge Lab

The lab below implements the full-information Hedge update with log-weights for numerical stability. Each expert receives a synthetic loss every round. The learner pays the probability-weighted loss, updates all expert weights, and plots both the actual regret and the theorem’s certificate line.

The default scenario is deliberately mean. Expert E1 is excellent early, then becomes bad. Expert E2 is boring and steady. With the default seed, E1 ends around 95.53 cumulative loss, E2 wins in hindsight at 55.79, and Hedge pays 61.78. That is 5.99 regret against the best fixed expert, beneath a certificate gap of 13.43; by the end, 99.995% of the weight sits on E2.

In other words: it gets fooled, notices, and still keeps the bill bounded.

I also audited the lab as code, not just as a picture. Across 972 combinations of scenario, learning rate, expert count, horizon, noise, and seed, every run kept finite losses, nonnegative weights, probabilities summing to one, and regret below the displayed certificate gap. The default sweep is doing what the theorem says it should: small eta is sluggish, huge eta is jumpy, and the middle of the plot is where the rent gets negotiated.

Algorithm loss Best fixed expert Regret certificate Expert loss Eta sweep

Deterministic toy model. Losses are bounded in [0, 1], the learner sees all expert losses after each round, and the certificate is for the best fixed expert in hindsight.

Try the four scenarios as different adversaries.

One expert is quietly best is the friendly case. The learner should drift toward the lowest-loss expert, and the regret line becomes a small tax on not knowing the answer from the start.

Early winner turns bad is the default. This is the most useful cautionary case because the final top weight is nearly all on E2, even though E1 looked attractive early. Multiplicative weights is not loyal. It remembers in capital, and capital can flee.

The best expert changes usually looks better than it deserves. The fixed expert comparator is weak in a changing world: if E1 is best early, E4 is best later, and E7 is best at the end, the theorem does not promise to track that switching sequence. For that you need a richer comparator class, such as tracking the best expert with a limited number of switches. Same update spirit, different receipt.

Penalize the crowd makes the environment attack the expert with the largest current probability. This is the game-theoretic cartoon. A deterministic leader is exploitable; a distribution is harder to pin down. The algorithm’s safety comes from randomization and accounting, not from discovering a permanently correct expert.

Why Multiplication Is the Right Kind of Forgetting

Additive penalties are tempting:

score_i = score_i - loss_i

Then pick the best score. This is often fine when the score differences are small and the world is gentle. But additive bookkeeping does not naturally produce a probability distribution, and it does not treat repeated evidence as compound evidence.

Multiplication does.

Write the log-weight after T rounds:

log w_{T,i} = log w_{0,i} - eta L_i

So final weight is proportional to:

exp(-eta L_i)

That is a soft minimum over cumulative losses. The learner does not commit to the current champion; it keeps a Gibbs-like distribution over explanations, where eta controls how sharply loss is converted into probability.

This is why the method keeps reappearing. In online prediction, the experts are forecasters. In portfolio selection, they are assets or strategies. In game playing, they are actions. In boosting, a related exponential reweighting emphasizes training examples that the current ensemble still mishandles. Freund and Schapire’s Hedge paper frames the core problem as dynamically apportioning resources among options under worst-case online losses, and then connects that logic to boosting.2

The object changes. The ledger stays.

The Bound Is Not a Vibe

The proof is short enough to keep in your head.

Let:

W_t = sum_i w_t,i

This total weight is the potential. Initially, if all weights are 1, then W_0 = N.

On a round, the update gives:

W_{t+1} = sum_i w_t,i exp(-eta loss_t,i)

Normalize by W_t:

W_{t+1} / W_t = sum_i p_t,i exp(-eta loss_t,i)

For bounded losses, Hoeffding’s lemma controls this exponential average by the mixture loss plus a curvature term:

log(W_{t+1} / W_t) <= -eta learner_loss_t + eta^2 / 8

Sum over rounds:

log W_T <= log N - eta L_algorithm + eta^2 T / 8

Now lower-bound the same final potential by any single expert’s remaining weight:

W_T >= w_{T,i} = exp(-eta L_i)

For the best fixed expert:

-eta min_i L_i <= log W_T

Put the upper and lower bounds on log W_T together, rearrange, and the certificate appears:

L_algorithm <= min_i L_i + log(N) / eta + eta T / 8

There is no distributional assumption hiding here. The losses can be generated by a stochastic process, a market, a benchmark suite, a player, or a cranky script that looks at your current weights before deciding whom to punish. The price is that the guarantee is relative to the comparator you named.

That last sentence matters.

Regret Is Always Regret To Something

“No regret” is an incomplete phrase.

No regret to the best fixed expert is different from no regret to the best sequence of experts. It is different from no regret to a policy that observes state. It is different from low loss in absolute terms. An algorithm can have small regret and still be terrible if every expert is terrible.

This is the most common abuse of online-learning language in product work. A team says the selector has low regret, but the comparator class is too weak to mean what the business question needs.

Examples:

ad ranking        best fixed ranker is weaker than a context-aware policy
model routing     best fixed model is weaker than routing by query type
market making     best fixed spread is weaker than state-dependent inventory control
game AI           best fixed action is weaker than a strategy over board states

The lab’s shifting scenario is a small version of this mistake. The theorem is true, and the guarantee is still useful, but it answers a narrower question:

How much worse was the learner than the best single expert after the fact?

If the desired comparator changes over time, the algorithm has to pay for that extra freedom somewhere: switch costs, sleeping experts, specialist experts, contextual policies, or another structure that describes the richer benchmark.

Regret is not humility unless you say who you are comparing yourself to.

Why This Still Feels Modern

The first Weighted Majority work was about prediction from a pool of algorithms: combine many imperfect advisers, make few mistakes if one of them is good, and do this online.3 Hedge generalized the loss model and helped make the connection to boosting explicit.2 The Arora-Hazan-Kale survey then showed how the same update template runs through algorithms, game theory, machine learning, optimization, and approximate solving.1

That lineage is old enough to be classic and current enough to remain useful.

A lot of modern systems are expert problems in disguise:

Which retriever should answer this query?
Which model should handle this request?
Which cache admission policy should get traffic?
Which market signal should size risk today?
Which heuristic should guide search in this part of the game tree?

The full system may need features, delayed feedback, off-policy evaluation, guardrails, and cost constraints. Fine. But the first useful baseline is often still the little ledger:

assign probability
observe bounded loss
multiply down what hurt
check regret against a named comparator

It is not glamorous. It is better than that. It is auditable.

What the Lab Leaves You With

The lesson is not “use eta equals 0.35.” That number is just a knob in a toy.

The lesson is that multiplicative weights separates three questions that are often blended together:

What did the learner pay?
What did the best comparator pay?
How much extra did ignorance and adaptivity cost?

That third number is the algorithm’s rent.

When the rent is small, the aggregate learner has done its job. When the rent is large, the lab gives you suspects: too many experts, too short a horizon, too much noise, too aggressive a learning rate, or a comparator class that does not match the world.

And when all experts lose badly, the method gives you no romance. It says: your ensemble was well managed, and your ensemble was still bad.

That is a useful kind of honesty.

  1. Sanjeev Arora, Elad Hazan, and Satyen Kale, “The Multiplicative Weights Update Method: A Meta-Algorithm and Applications”, Theory of Computing 8(6), 2012. ↩ ↩2

  2. Yoav Freund and Robert E. Schapire, “A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting”, Journal of Computer and System Sciences 55, 1997. ↩ ↩2

  3. Nick Littlestone and Manfred K. Warmuth, “The Weighted Majority Algorithm”, Information and Computation 108(2), 1994. ↩