AI Glossary / Causal inference and experimentation / Advanced
Randomized weighted majority algorithm
Definition
The randomized weighted majority algorithm combines a set of predictors by choosing predictions randomly according to their current weights, then reducing the weights of predictors that make mistakes. It is an online learning method: it updates as outcomes arrive, rather than waiting for a complete training dataset.
What it means
Imagine several forecasting rules offering different answers. Instead of permanently trusting one rule, you keep a changing record of their relative performance. Better-performing rules receive more influence, while a weaker rule can still be selected if it retains some weight. Random selection distinguishes this approach from always taking the outcome with the largest total vote. The weights describe the algorithm's selection policy; they do not automatically represent reliable probabilities of real-world events.
How it works
Begin with positive expert weights. For each round, collect their predictions and sample an expert in proportion to its weight, or equivalently sample an outcome using the combined weights supporting it. After observing the correct answer, multiply every incorrect expert's weight by a chosen penalty factor between zero and one. Correct experts retain their weights. Repeat with the new distribution. The basic setting assumes feedback sufficient to score every expert, not only the selected one. Its performance comparison concerns expected cumulative mistakes against a fixed expert chosen in hindsight, under the relevant feedback and adversary assumptions.
Three practical examples
- A delivery team compares three rules predicting whether tomorrow's parcel volume will exceed capacity. A trial combines their predictions and updates weights when the actual volume becomes known.
- An analyst tests several binary demand signals. A replay of historical dates shows how the algorithm distributes influence, provided each day's inputs contain only information available then.
- A classroom exercise combines students' forecasting strategies. Students record the random draw separately from the outcome, making it clear why two runs can differ even with identical expert predictions.
Think of it this way
Think of a rotating advisory panel with a weighted lottery for whose answer to follow. A member who is repeatedly wrong receives fewer lottery tickets. The panel still needs a dependable way to learn what actually happened. If feedback is missing or biased, the ticket counts can become misleading regardless of how carefully the lottery is conducted.
Worked example
Suppose three experts have weights 4, 2 and 1, and predict outcomes 1, 0 and 1 respectively. The algorithm predicts 1 with probability 5/7 and 0 with probability 2/7. The observed answer is 0. Using a penalty factor of one-half changes the weights to 2, 2 and 0.5. Both experts that predicted 1 are penalized, even if the algorithm happened to choose 0 and was correct. If the experts offer the same predictions next round, the probability of choosing 1 is now 2.5/4.5, or 5/9. This original calculation illustrates the update; it does not establish a forecasting success rate.
Illustrative case study
A fictional parcel depot has a seasonal rule, a promotions rule and a recent-trend rule for predicting capacity pressure. It runs the algorithm in a historical replay before considering operational use. The team records each rule's daily answer, the combined decision and the eventual label, then compares cumulative mistakes with the best single rule over the same period. Several random seeds reveal variation between runs. The replay also exposes late labels and an inconsistent definition of capacity pressure. Staff fix those measurement problems before drawing conclusions. This is an illustrative evaluation design, not evidence that the method improves a real depot's performance.
Common misconceptions and mistakes
The most common confusion is treating randomized weighted majority as deterministic majority voting. Another is updating only the sampled expert; the basic full-information procedure evaluates all experts. A third is assuming that every random run must beat every individual predictor. Expected performance guarantees are not promises about each run. Operationally, teams can also leak future information into experts, compare against a changing hindsight oracle, or ignore the different costs of false alarms and missed events. Those choices change what the evaluation means.
Business use
The method provides a simple way to study sequential combinations of existing decision rules. Its appeal is a transparent update process and an explicit comparison with individual alternatives. Before using it, define what counts as a mistake, when outcomes become available and whether random decisions are acceptable in the application. Track the operational cost of errors alongside their count. A theoretically useful baseline can still be unsuitable where decisions require stable explanations, delayed feedback dominates, or the chosen action changes which outcomes are observable.
People also ask
Are the experts necessarily people?
No. They can be algorithms, models or fixed rules.
Does the largest weight always win?
No. Selection is randomized according to relative weights.
Is this a bandit algorithm?
The basic version assumes all experts can be scored after feedback; bandit settings require different treatment of unobserved losses.
Check your understanding
Why were two experts penalized in the example?
Answer: Both predicted the wrong outcome.
Why can repeated runs differ?
Answer: Their sampled choices differ.
What should an evaluator record besides the combined mistakes?
Answer: Individual expert predictions and mistakes, outcome timing, the random seed and the comparison period.
Related terms
- Online learning
- Regret
- Ensemble learning
- prediction with expert advice
- multiplicative weights
- bandit feedback
Learn next
Implement a small replay with three fixed rules and an explicit outcome log. Compare deterministic and randomized selection across several seeds. Then study regret bounds and the distinction between full-information and bandit feedback before interpreting theoretical guarantees as deployment evidence.
More in Causal inference and experimentation
- Proper accuracy scoring rule - A proper accuracy scoring rule evaluates probability forecasts so that reporting the true outcome probabilities achieves the best expected score.
- Proxy metric - A proxy metric is a measurable quantity used as an indirect indicator of an outcome or quality that is harder to measure directly.
- Random experiment - A random experiment is a process with an uncertain outcome drawn from a defined set of possible outcomes, called its sample space.
- Ranking loss - Ranking loss, in the multilabel evaluation sense used here, measures the fraction of relevant-versus-irrelevant label pairs that a model orders incorrectly...
- Recall - Recall is the fraction of actual positive cases that a system correctly identifies as positive.
- Recall at k (recall@k) - Recall at k, written recall@k or R@k, is the fraction of a defined set of relevant items that appears among the first k ranked results.
Sources
Carnegie Mellon University, course notes on online learning with experts and bandits, including randomized weighted majority: https://www.cs.cmu.edu/~15850/notes/lec15.pdf Littlestone and Warmuth, original weighted majority conference paper: https://mwarmuth.bitbucket.io/pubs/C14.pdf The numerical example, business scenarios and evaluation suggestions are original illustrations.
Previous: Randomized Response Next: Randomness