Learning with Expert Advice

In online learning, you do not know the cost of your decision until after you make it. The multiplicative weights algorithm learns by reweighting experts based on their past performance. This note covers the algorithm, its regret bound, and intuition for the learning rate.

The idea

Imagine you have a set of experts (algorithms, models, or strategies) and you do not know which is best. Each round, you pick one expert, learn its cost, and adjust your weights. The multiplicative weights algorithm multiplies the weight of an expert by a factor β (close to 1) if it performs poorly, and leaves it unchanged if it performs well. Over time, good experts accumulate higher weight, and you learn.

The key insight is that this simple reweighting strategy is provably near-optimal. You incur regret proportional to the number of experts and the number of rounds, but the constant factors are small. This makes it useful for diverse problems: portfolio management, online classification, combinatorial optimization.

The maths

Initialize all expert weights to 1. Each round:

Sample an expert proportional to its weight: Pr(expert i) = weight[i] / sum(weights)
Incur cost cost for the chosen expert.
For all experts, multiply weight by β^cost if they also incurred that cost, or leave unchanged. A common rule is weight[i] ← weight[i] × (1 - η × cost[i]) for small learning rate η.

The regret (cumulative difference from always following the best expert) is O((log n) / η + η T) where n is the number of experts and T is the number of rounds. Optimal η balances these two terms.

Try it

The widget runs a simplified multiplicative weights simulation. Move the learning rate slider to see how fast experts are reweighted. The "New experts" button reshuffles qualities to show how the algorithm adapts.

Learning rate (η): 0.10

Round: 10

Expert A

–

Expert B

–

Expert C

–

Expert D

–

Cumulative regret

Multiplicative weights after 10 rounds with η = 0.10.

Multiplicative weights algorithm with 5 synthetic experts and dynamic cost. Adjust learning rate to see convergence speed.

High learning rate (η near 1): fast response to poor experts, but noisy.
Low learning rate (η near 0.01): smooth, but slow to shift away from unlucky experts.
The algorithm never fully commits to one expert; it hedges.

Where I used it

Easy to get wrong

Sources

Introduction to Online Convex Optimization (Hazan)arXiv 1206.4670Comprehensive treatment of multiplicative weights and online learning algorithms with detailed regret analysis.

First noted in (2023), expanded in 2026.