Compare with the best fixed expert
In online prediction, a learner must act before seeing the current loss. An expert can make mistakes, so eliminating it permanently after one bad round may be too harsh. Exponential weights gradually reduces the influence of high-loss experts and compares the learner's total loss with the best single expert chosen in hindsight.
Fix experts and rounds. On round , expert has loss . For the guarantee below, regard the entire loss sequence as fixed independently of the learner's random draws. In the full-information setting, after acting the learner observes every expert's loss, not just the loss of the sampled expert. Losses need not be independent or generated by a statistical distribution.
Definition 5.3.1
(Exponential weights)
Initialize and choose a learning rate . At the start of each round form
Definition 5.3.2
(Expected regret against the best fixed expert)
The learner samples one expert from before seeing round 's losses, then updates all weights after the losses are revealed. For fixed losses, is a deterministic function of past losses, so its expected round loss is . The expected regret against the best fixed expert is
Regret can be negative; the inequality below is an upper bound.
Common mistake
(Comparing with the best expert of each round)
The benchmark , which picks a different expert every round, is never larger than and can be far smaller. With two rounds of losses and it equals , while each fixed expert loses . The theorem below concerns the second benchmark, which uses one expert throughout.
The potential calculation
Theorem 5.3.3
(Regret of exponential weights)
Let the losses be fixed in advance and let . Then for every fixed expert ,
In particular, if is known and , the expected regret against the best fixed expert is at most , so for fixed the average regret tends to zero as grows.
Proof
(Potential argument with a chord bound)
For , convexity of puts it below the chord joining its endpoint values:
Consequently, using for ,
The logarithm is defined because and . On the other hand, any fixed expert has final weight , so is at least that weight. Combining this lower bound with the summed upper bound and gives
For , , hence for . Since , substitution and rearrangement first give . Using yields, for every fixed expert ,
Proof X-ray
Where each assumption enters
Three ingredients are used, each once. Convexity of together with the range gives the chord bound, which turns the mixture into a function of the expected loss alone; for losses outside the chord inequality is false. Full information is used when every weight is updated, so that depends on all the losses. The key move is the potential : its increments telescope to , which is bounded above through the learner's loss and below by a single expert's weight, discarding every other term of the sum. Because was arbitrary, the bound holds for all fixed experts at once, and the best one is chosen only afterwards. The final step trades for , and this is where the term comes from.
This chord argument supplies a valid bound, not a claim that its constant is optimal. This is an additive expected-loss comparison; it does not say the absolute loss is small when all experts perform poorly, nor is it a high-probability guarantee for one sampled run.
Counterexample mode
Losses larger than one
It is tempting to apply the bound with the same constants to any bounded losses. Take , , and the loss vector . The bound gives . But , so , while the best expert has loss : the regret is . The chord inequality fails at , since . The repair is to rescale: if losses lie in , apply the theorem to , which multiplies the regret bound by .
Worked examples
Worked example 5.3.4
(Two rounds with three experts)
Let . The first loss vector is , the second . Initially all weights are one, so the first expected loss is . After round one the weights are , giving the next distribution . The second expected loss is ; total expected loss is . The three fixed experts have losses , so the best has loss zero and the expected regret is . After the second update the weights are .
Worked example 5.3.5
(Tuning the learning rate)
Take and . Then , and both and . The two terms of the bound coincide, which is why this choice minimizes . The guarantee is : over rounds the expected total loss exceeds that of the best expert by at most about , an average of about per round.
Worked example 5.3.6
(Identical experts)
Let and suppose in every round. Both weights are multiplied by , so for all , , and the regret against either expert is . The bound is far from tight here, since it is a worst case over all loss sequences.
Common mistake
(Expected loss is not the loss of one run)
A single realized run can differ from , because the learner samples an expert. The calculation averages over those samples, while the expert-loss sequence remains fixed. For instance, if the learner draws the second expert in both rounds, which has probability , its realized loss is , not .
Boundaries of the guarantee
The full-information assumption matters: if only the sampled expert's loss is revealed, the prescribed update cannot be performed as written. Bandit feedback needs a different estimator and analysis. Likewise the chosen uses the horizon ; unknown-horizon procedures need their own schedule or restarting analysis. A distribution-free sequence bound is not, by itself, a claim about future prediction risk under a changing environment.
Exercises
Quick check
(With , and losses on one round, give the initial distribution, expected loss and updated weights.)
Start from .
Solution · Answer
The initial distribution is and the expected loss is . The weights become .
Quick check
(Explain why the potential proof compares against each fixed expert, even though the best expert is identified only after all rounds.)
The expert in the argument is arbitrary.
Solution · Answer
The lower bound on holds for every expert , so the regret bound holds for all fixed experts simultaneously. The algorithm never needs to know which one is best; the minimum over is taken only in the analysis.
Quick check
(Why does the stated update require full feedback? Which weights are unavailable after observing only the sampled expert's loss?)
Look at the factor .
Solution · Answer
The update multiplies by for every . After observing only the sampled expert's loss, the factors for all the other experts are unknown, so their weights cannot be updated.
Exercise 5.3.7
(Prove that for and .)
FoundationProof
Solution(3)
- 1
Write as a convex combination of the endpoints
with weights and in .
- 2
Apply convexity
Since is convex, .
Because: The function has second derivative .
- 3
Simplify the right side
∎, which is the claimed bound.