Multiplicative Weights, in depth: weighted majority, Hedge and its regret proof, measured runs, and solving games and LPs

Experts, losses and regret

There are n experts. In each round t = 1 to T, you choose a probability distribution p_t over experts, the environment reveals a loss vector l_t with every entry in [0, 1], and you pay the expected loss p_t . l_t. The environment may be adversarial: it can pick losses after seeing your algorithm, though not your random draw.

Since nothing is assumed about the losses, no algorithm can promise a small absolute loss. The benchmark is regret: your total loss minus the total loss of the best single expert in hindsight. An algorithm is no-regret if regret grows slower than T, so that the average per-round gap goes to zero. Multiplicative weights achieves regret of order sqrt(T ln n). The dependence on n is only logarithmic, which is why it works with thousands of experts.

Experts are whatever you are choosing among: forecasting models, routing paths, ad creatives, constraints of a linear program or the pure strategies of a game.

Weighted majority: the deterministic version

Start with binary prediction and a deterministic rule. Each expert predicts 0 or 1. Predict with the weighted majority vote, and after the truth arrives multiply the weight of every wrong expert by beta = 1/2. The analysis uses the total weight W as a potential.

• Initially W = n.
• Whenever the algorithm is wrong, at least half the weight was on wrong experts, so W shrinks by a factor of at least 3/4.
• The best expert, with m mistakes, still has weight (1/2)^m, and W is at least that.

So (1/2)^m is at most n (3/4)^M, where M is the algorithm's mistakes. Taking logs, M is at most (m ln 2 + ln n) / ln(4/3), which is about 2.41 (m + log2 n). A deterministic algorithm cannot do better than a factor of 2 on m, because the adversary sees its prediction and can make it wrong every round.

Measured: 16 experts, 1,000 rounds, 15 experts right 60 percent of the time and one right 90 percent. The best expert made 88 mistakes. Weighted majority also made 88, against a worst-case bound of 221.7. On benign data the bound is loose; it is a guarantee against an adversary, not a forecast.

Hedge: randomise and keep log-weights

Hedge, from Freund and Schapire, randomises to beat the factor of 2. Keep weights w_i = exp(-eta L_i), where L_i is expert i's cumulative loss, and play p_i = w_i / W. In code, keep the logarithms and normalise with the maximum subtracted, exactly like a numerically stable softmax:

import math

class Hedge:
    def __init__(self, n, eta):
        self.logw = [0.0] * n
        self.eta = eta

    def distribution(self):
        m = max(self.logw)
        w = [math.exp(x - m) for x in self.logw]   # largest term is exactly 1.0
        s = sum(w)
        return [x / s for x in w]

    def update(self, losses):                      # every loss must be in [0, 1]
        for i, l in enumerate(losses):
            self.logw[i] -= self.eta * l

def run(losses, eta):
    h, total = Hedge(len(losses[0]), eta), 0.0
    for l in losses:
        p = h.distribution()
        total += sum(pi * li for pi, li in zip(p, l))
        h.update(l)
    return total

Trace it by hand once. Three experts start with log-weights (0, 0, 0), so p is uniform. With eta = 0.5, round 1 brings losses (0, 1, 1): the log-weights become (0, -0.5, -0.5) and p becomes (0.452, 0.274, 0.274). Round 2 brings (1, 0, 1): the log-weights become (-0.5, -0.5, -1.0) and p becomes (0.384, 0.384, 0.233). The third expert, wrong twice, now carries the least weight, while the first two are tied because each has been wrong once. Only cumulative loss matters, not when it happened, which is both the strength of Hedge and the reason it adapts slowly after a regime change.

The naive version multiplies raw weights. After 800 rounds of loss 1 at eta = 1, a raw weight is exp(-800), which underflows to exactly 0.0 in double precision, and once every weight is zero the distribution is 0/0.

The regret bound, derived

The proof again tracks the potential W_t, the sum of weights. In round t the ratio W_(t+1) / W_t equals the expectation, under p_t, of exp(-eta l). Hoeffding's lemma bounds the expectation of exp(-eta X) for X in [0, 1] by exp(-eta E[X] + eta^2 / 8). With E[X] = p_t . l_t, this gives:

ln W_(T+1) - ln W_1  <=  -eta * (your total loss)  +  eta^2 * T / 8
ln W_(T+1)           >=  -eta * L_best             (one term of the sum)
ln W_1                =   ln n

=>  your loss - L_best  <=  ln(n) / eta  +  eta * T / 8

The two terms pull in opposite directions. A small eta learns slowly and pays ln(n) / eta; a large eta overreacts and pays eta T / 8. Setting eta = sqrt(8 ln n / T) balances them and gives regret at most sqrt(T ln n / 2). For n = 10 and T = 2,000 that is eta = 0.096 and a bound of 48.0.

Worked example: measured regret

Ten experts with Bernoulli losses over 2,000 rounds: eight lose with probability 0.5, one with 0.45 and the best (expert 3) with 0.4.

The best expert lost 807 times, Hedge with the tuned rate lost 835.2 in expectation, and the uniform mix lost 980.6. At the end, the distribution put weight 1.0 (to three decimals) on expert 3.

Notice that larger rates did better. The tuned rate protects against an adversary, and stochastic data with a clear winner is not adversarial. In a second run where the best expert switched halfway, eta = 0.5 had regret 5.9 against 25.2 for the tuned rate. Do not read this as a reason to pick large rates blindly: against data designed to whipsaw the leader, follow-the-leader behaviour has regret linear in T. Tune on replayed history and keep the theoretical rate as the safe default.

Beyond prediction: games, LPs and boosting

The same loop solves problems that have nothing to do with prediction, because many problems reduce to a game between a weighting player and a best-responding oracle.

Zero-sum games. Let the row player run Hedge over rows of a loss matrix A, rescaled to [0, 1], and let the column player best-respond each round. The averaged strategies form an approximate equilibrium, and the gap between the upper and lower value estimates is at most the average regret. On a weighted rock-paper-scissors matrix with payoffs 1, 2 and 3 and value 0, whose exact equilibrium is (1/2, 1/3, 1/6), 4,883 rounds gave the row strategy (0.502, 0.330, 0.168) and bracketed the value in [-0.0094, 0.0061]. The theoretical gap bound was 0.064. Exact methods are in Game Theory Algorithms, in depth; MW wins when the matrix is too large to write down but best responses are cheap.

for t in range(T):
    x = hedge.distribution()                   # row mixed strategy
    j = argmax_j sum_i x[i] * A[i][j]           # column best response
    x_avg += x / T;  y_count[j] += 1
    hedge.update([(A[i][j] + R) / (2 * R) for i in rows])   # R = max |A|

Linear programs. To find x in an easy set P with Ax at least b, treat the m constraints as experts. Each round, ask an oracle for x in P satisfying the single weighted constraint p . (Ax - b) at least 0; if none exists, p itself is a certificate of infeasibility. Give each constraint the gain (A_i x - b_i) / rho, where rho is the width, the largest possible violation, and shrink the weights of satisfied constraints so violated ones gain attention. After O(rho^2 ln m / eps^2) rounds, the average x violates no constraint by more than eps. This is the Arora, Hazan and Kale framework, and it underlies fast approximate multicommodity flow solvers. See LP duality for why the weights are dual variables.

Boosting. AdaBoost keeps multiplicative weights on training examples, raising those the current weak learner gets wrong, so examples play the role of constraints.

Operational guidance

• Scale losses into [0, 1]. The bound assumes it. With losses in [0, B], divide by B, and expect regret to scale by B.
• Unknown horizon. Use the doubling trick, restarting with T = 1, 2, 4 and so on and the tuned rate for each block, which costs at most a constant factor of about 3.4; or use the decaying rate eta_t = sqrt(8 ln n / t).
• Drift. Plain Hedge compares you with the best fixed expert. If the best expert changes, mix a small fraction of uniform weight back in each round (the fixed-share method of Herbster and Warmuth) so that no weight becomes unrecoverable.
• Partial feedback. If you only see the loss of the option you chose, as in ad or route selection, you need an importance-weighted variant such as EXP3, with regret of order sqrt(T n ln n). See multi-armed bandits.
• Log what you need to audit. Store the log-weights and the loss vector per round. Replaying the log reproduces every decision exactly.

Failure modes

• Raw weights underflow. Everything becomes 0.0 and the next normalisation divides by zero. Keep log-weights.
• Unbounded or negative losses. One huge loss wipes out an expert permanently. Clip or rescale, and record clipping counts.
• Deterministic play against an adaptive opponent. Taking the argmax of the weights instead of sampling turns Hedge into follow-the-leader, which an adversary can exploit every round.
• Delayed feedback. Losses that arrive late must be applied to the round they belong to; with delay d, regret grows roughly with sqrt(d).
• Correlated experts. Fifty copies of one model drown a single diverse one at the start. Deduplicate or set non-uniform priors.

Trade-offs

What to do next

1. Implement the Hedge class above with log-weights and a test that feeds 10,000 rounds of loss 1 without producing NaN.
2. Replay a week of your own decision log, such as model choice per request, and plot regret against the best fixed choice for three learning rates.
3. Add fixed-share mixing and compare on a period that contains a known regime change.
4. If you only observe the chosen option's outcome, switch to EXP3 and read the bandit article.
5. Solve one small matrix game with both MW and an exact LP and check that the MW bracket contains the exact value.
6. Read Online Algorithms, in depth for competitive analysis, the other way to judge decisions made without the future.