Prediction with Expert Advice
The learner distributes probability across experts rather than having to select one expert deterministically.
A Choice Across Experts
Prediction with expert advice does not require the learner to select one expert deterministically. Instead, the learner distributes probability across the available experts. This distribution describes how strongly the learner relies on each expert during the current round.
The current distribution determines the learner's averaged cost for the round. The learner therefore pays a distribution-weighted cost rather than simply paying the cost of one fixed expert. The distribution records the learner's current reliance on the experts, while the costs record how well those experts performed in that round.
One Round in Order
The Weighted-Majority algorithm is easiest to understand as a repeated decision process. There are d experts and a planned horizon of T rounds. At the start of a round, the algorithm has an unnormalized weight for every expert. It then normalizes those weights, uses the resulting distribution for the learner's choice, observes the costs assigned to all experts, pays the distribution-weighted cost, and updates every expert's weight.
Normalization converts the current unnormalized weights into probabilities. If the current unnormalized weights are written as w̃_i^(t), the normalization constant is Z_t = sum_i w̃_i^(t). Each expert's probability is its current weight divided by Z_t.
A Cost Changes Future Influence
After the learner observes the costs, the algorithm updates every expert's unnormalized weight. For expert i, the update multiplies its weight by exp(-eta v_t,i), where v_t,i is that expert's cost in the current round. Costs lie in the interval from 0 to 1. A larger cost therefore produces a smaller multiplicative factor than a smaller cost.
Comparing two expert updates
Suppose two experts enter a round with unnormalized weights wA and wB. Expert A receives cost vA and Expert B receives cost vB, with vA larger than vB.
Apply the update: Expert A's weight is multiplied by exp(-eta vA), while Expert B's weight is multiplied by exp(-eta vB).
Compare the factors: Because vA is larger than vB, exp(-eta vA) is smaller than exp(-eta vB) under the stated cost-based update.
Interpret the result: Expert A loses more relative weight, while Expert B retains more of its weight and therefore has greater potential influence after the next normalization.
The expert with the larger current cost receives the smaller multiplicative factor and loses more relative influence in the future distribution.
The parameter eta controls the update expression and is set from the number of experts d and the planned number of rounds T. The update first produces new unnormalized weights. Normalization then turns those updated weights into the distribution used for the next choice.
Tracing a Full Round
What do you think happens?
Three experts have entering weights 2, 1, and 1. Before any costs are observed, which expert has the greatest probability in the learner's current distribution?
Reveal answer
Answer: Expert A, whose weight is 2
The weights are normalized by their total, 4. Expert A receives probability 2 divided by 4, while each other expert receives probability 1 divided by 4.
Following one round from start to finish
Use entering weights 2, 1, and 1 for Experts A, B, and C. Let their observed costs be 0, 1, and 0.5. Keep eta symbolic so the update rule remains visible.
Enter the round: The unnormalized weights are 2 for Expert A, 1 for Expert B, and 1 for Expert C.
Normalize: The total is 4, so the current probabilities are 2 divided by 4, 1 divided by 4, and 1 divided by 4.
Predict and calculate loss: The learner uses this distribution. Its averaged cost is the probability-weighted combination of the three observed costs: (2 divided by 4) times 0, plus (1 divided by 4) times 1, plus (1 divided by 4) times 0.5.
Observe all costs: The cost vector is now known: Expert A has cost 0, Expert B has cost 1, and Expert C has cost 0.5.
Update every weight: The new unnormalized weights are 2 times exp(0), 1 times exp(-eta), and 1 times exp(-0.5 eta).
Prepare the next round: The updated weights must be normalized by their new total before they become the next round's probability distribution.
Expert A retains its full entering weight because its cost is 0. Expert B is reduced more strongly because its cost is 1, and Expert C receives an intermediate reduction because its cost is 0.5.
This trace separates two different roles of the weights. The entering weights determine the current distribution and therefore the current averaged cost. The observed costs do not change that already-made round's distribution; they change the unnormalized weights that will influence the next round.
Debugging the Procedure
An implementation can appear close to the intended algorithm while still producing a different result if it changes the order of operations. The most useful debugging method is to compare four checkpoints in sequence: the weights entering the round, the normalization constant, the cost-weighted loss, and the post-cost update.
Using the cost update before forming the current distribution
The intended procedure uses the entering weights to form the current distribution, then observes costs and updates weights for the next round.
Fix:
Record the entering weights, calculate their total, normalize them, and make the current prediction before applying the cost update.Treating the learner's loss as one expert's cost
The learner's loss is an average determined by the whole current distribution.
Fix:
Calculate the cost-weighted combination of all experts' costs.Checking only the final distribution
A mismatch may have started earlier in the entering weights, normalization constant, loss calculation, or update.
Fix:
Compare the four checkpoints in order to locate the first divergence.Ignoring the planned horizon when choosing eta
The source specifies that eta is set from the number of experts and the planned number of rounds.
Fix:
Treat the choice of eta as part of the algorithm's horizon-dependent setup, or use the doubling trick when the horizon is unavailable.
For each round, write down the entering weights, their total, the resulting distribution, the distribution-weighted loss, and the updated unnormalized weights. This makes it possible to identify the first checkpoint at which an implementation differs from the intended procedure.
Unknown Horizons
The standard setup assumes that the number of rounds T is known because eta is chosen using the number of experts d and the planned horizon T. If the learner cannot rely on a known total number of rounds, that dependence becomes a practical problem.
The doubling trick removes the need for one final round count in advance by organizing the run into progressively extended time periods. Rather than choosing one eta from a horizon that is unknown, the learner works through a sequence of phases whose planned lengths grow. The important idea is the repeated restart or reorganization into longer periods, not a single horizon chosen before the entire run begins.
Check Your Understanding
An implementation reports an unexpected next-round distribution. Describe the four checkpoints you would compare, in order, against the intended Weighted-Majority procedure.
Hints
- Start with the values available before the current prediction.
- Then check the total used to turn weights into probabilities.
- Next inspect the learner's averaged cost.
- Finish by checking how each observed expert cost changed its unnormalized weight.
Explain why an expert with a larger cost has less relative influence after the update, assuming the costs lie between 0 and 1.
Hints
- Look at the multiplicative factor used in the update.
- Compare exp(-eta times a larger cost) with exp(-eta times a smaller cost).
Key Takeaways
- The learner represents its current choice as a probability distribution over experts rather than selecting one expert deterministically.
- The current distribution determines the learner's averaged cost for the round.
- A round proceeds in order: normalize entering weights, predict, observe all expert costs, and update every weight.
- The exponential multiplicative update gives a smaller factor to an expert with a larger cost, reducing that expert's future relative influence.
- The doubling trick organizes the run into progressively extended periods when the total number of rounds is not known in advance.
Key Takeaways
- Prediction with expert advice spreads reliance across experts through a probability distribution.
- Normalization determines the current round's distribution, while the cost update determines the weights used later.
- The correct debugging order is entering weights, normalization, cost-weighted loss, and post-cost update.
- The doubling trick handles an unknown total number of rounds by using progressively extended time periods.