Hedge Regret for Bounded Expert Losses

Why Exponential Weights?

Suppose a learner observes the losses of \(K\) experts over \(T\) rounds and wants to perform nearly as well as the best single expert in hindsight. The learner must choose weights before seeing the current round’s losses; afterward, the full loss vector is revealed. Hedge turns this protocol into a simple update: experts that have accumulated larger losses receive exponentially less weight.

The update is useful because it adapts to the observed losses without knowing in advance which expert will do best. A potential function—the sum of exponentials of cumulative losses—will let us compare the learner’s cumulative loss with every expert’s cumulative loss at once.

Protocol and Hedge Update

There are \(K\) experts, where \(K\) is finite and at least 2. On round \(t\), the learner chooses a probability vector \(p_t=(p_{t,1},\ldots,p_{t,K})\) using the losses from rounds \(1,\ldots,t-1\). The environment then reveals losses \(\ell_{t,i}\in[0,1]\) for all experts \(i\). The learner’s round-\(t\) mixture loss is \(\sum_{i=1}^K p_{t,i}\ell_{t,i}\). Define expert \(i\)’s cumulative loss through round \(T\) by \(L_{T,i}=\sum_{t=1}^T\ell_{t,i}\), and define the learner’s cumulative mixture loss by \(\widehat L_T=\sum_{t=1}^T\sum_{i=1}^K p_{t,i}\ell_{t,i}\).

Hedge starts with equal, unnormalized weights \(w_{1,i}=1\). Given a learning rate \(\eta>0\), after observing the losses on round \(t\), it updates the weights according to

Equivalently, since \(w_{t,i}=\exp(-\eta L_{t-1,i})\), the round-\(t\) probability is proportional to the exponential of minus \(\eta\) times the expert’s past cumulative loss. The learner uses past losses to choose \(p_t\), then updates only after the current loss vector is revealed. This is the full-information setting: every expert’s current loss is observed, including the losses of experts the learner did not choose.

The Potential Argument

For the proof, let \(L_{0,i}=0\) and define the potential after round \(t\) as the sum of exponentiated negative cumulative losses:

The crucial step is to bound how much the potential can decrease on one round. We first prove the bounded-variable exponential-moment inequality used in that step.

Proof. Write \(\mu=E[X]\). Convexity of \(x\mapsto\exp(\lambda x)\) implies, for every \(x\in[0,1]\), that \(\exp(\lambda x)\leq (1-x)+x\exp(\lambda)\). Taking expectations and centering gives

For \(0<\mu<1\), let \(g(\lambda)=\log(1-\mu+\mu\exp(\lambda))-\mu\lambda\). Direct differentiation gives \(g(0)=g'(0)=0\) and \(g''(\lambda)=q(\lambda)(1-q(\lambda))\), where \(q(\lambda)=\mu\exp(\lambda)/(1-\mu+\mu\exp(\lambda))\). Since \(0\leq q(\lambda)\leq1\), \(g''(\lambda)\leq1/4\). The integral form of Taylor’s theorem, valid for either sign of \(\lambda\), therefore yields \(g(\lambda)\leq\lambda^2/8\). If \(\mu=0\) or \(\mu=1\), then \(X=\mu\) with probability 1 and the desired inequality holds directly. Taking logarithms proves the lemma. \(\square\)

Proof. The ratio of successive potentials is

Consider a random variable that takes value \(\ell_{t,i}\) with probability \(p_{t,i}\). Its mean is the learner’s mixture loss on round \(t\). Apply the lemma with \(\lambda=-\eta\), and then take logarithms of the potential ratio. This gives

Summing over \(t=1,\ldots,T\) telescopes the left side. Since \(W_0=K\), we obtain

For any expert \(i\), the potential includes its term \(\exp(-\eta L_{T,i})\). In particular, it includes a term for an expert with minimum cumulative loss, so \(W_T\geq\exp(-\eta\min_i L_{T,i})\). Thus \(\log W_T\geq-\eta\min_i L_{T,i}\). Combining this lower bound with the upper bound just derived and rearranging gives

Dividing by \(\eta>0\) proves the theorem. \(\square\)

Choosing the Learning Rate When the Horizon Is Known

The theorem gives a bound for every positive learning rate. If \(T\) is known before learning begins, choose \(\eta\) to minimize \(\log(K)/\eta+\eta T/8\). For \(K\geq2\) and \(T\geq1\), differentiating with respect to \(\eta\) gives \(-\log(K)/\eta^2+T/8=0\), so the minimizing rate and the resulting guarantee are

At this choice, the two terms in the original bound are equal: each is \(\sqrt{T\log K/8}\). The guarantee grows with the square root of the horizon and the logarithm of the number of experts, rather than linearly with \(T\). The learning rate controls the tradeoff: a small \(\eta\) makes the penalty \(\log(K)/\eta\) large, while a large \(\eta\) makes the term \(\eta T/8\) large.

What the Guarantee Does—and Does Not—Say

The theorem is deterministic once the loss vectors are specified: it applies to every bounded sequence, even if the environment chooses each loss vector after observing the learner’s current probabilities. It compares cumulative mixture loss with the single best expert over the whole sequence. It does not claim that Hedge will identify the best expert before the sequence ends, nor does it compare against a different expert chosen separately on every round.

If the learner implements \(p_t\) by randomly sampling one expert, then \(\sum_i p_{t,i}\ell_{t,i}\) is the conditional expected loss on that round. The bound proved here is for the sum of these mixture losses, equivalently the cumulative conditional expected loss. It is not a pathwise bound on the cumulative losses of the sampled experts: sampling adds randomness, and a guarantee for realized sampled loss would require additional analysis.

A common mistake is to update the probabilities using the current loss vector and then describe the resulting decision as though it had been made before that vector was revealed. That reverses the protocol: \(p_t\) must depend only on losses through round \(t-1\). Another mistake is to treat the theorem as a bound on regret to a changing comparator. The potential argument lower-bounds the final potential using one expert’s total loss, so the comparator is fixed across rounds.