At time \(0\), all cumulative losses are zero, so every weight equals \(1\), and the potential equals the number of experts: \(W_0 = N\).

For any \(\eta \), loss sequence \(\ell \), time \(t\), and expert \(i\), the weight \(w_t(i) = \exp (-\eta \cdot L_t(i))\) is strictly positive.

For any \(\eta \), loss sequence \(\ell \), and time \(t\), the potential \(W_t \gt 0\). This follows because \(W_t\) is a finite sum of positive terms over the nonempty set of \(N \ge 1\) experts.

For \(\eta \gt 0\) and \(x \in [0,1]\),

This follows from convexity of the exponential: \(e^{x \cdot (-\eta )} \le x\, e^{-\eta } + (1-x)\, e^{0}\).

The cumulative loss satisfies the recurrence

for every \(t \lt T\) and expert \(i\).

At the final horizon, \(L_T(i) = \sum _{t : \mathrm{Fin}\, T} \ell _t(i)\), i.e., the cumulative loss through \(T\) equals the full sum over all rounds.

The weight factorizes across rounds:

For any \(\eta \), valid loss sequence \(\ell \), and time \(t\), \(\sum _{i=1}^{N} p_t(i) = 1\), so the Hedge distribution is a proper probability distribution.

For a valid loss sequence and \(\eta \gt 0\), the ratio of consecutive potentials satisfies

where \(\widehat{\ell }_t = \sum _i p_t(i)\, \ell _t(i)\) is the expected loss at round \(t\). This is the key potential-ratio lemma of Cesa-Bianchi and Lugosi.

For a valid loss sequence, \(\eta \gt 0\), and \(t \lt T\),

which follows from \(\ln (1-x) \le -x\) applied to the potential ratio bound.

For \(t \ge 0\),

For \(\eta \gt 0\),

This follows directly from the quadratic bound \(e^{-\eta } \le 1 - \eta + \eta ^2/2\).

The final potential is at least the weight of the best expert:

where \(L^* = \min _i L_T(i)\) is the best expert’s cumulative loss.

For any \(\eta \), loss sequence \(\ell \), time \(t\), and expert \(i\), the Hedge distribution satisfies \(p_t(i) \ge 0\).

For a valid loss sequence, the expected loss at each round satisfies \(\widehat{\ell }_t \le 1\), since individual losses are at most \(1\) and the Hedge distribution is a probability measure.

For a valid loss sequence, the expected loss at each round satisfies \(\widehat{\ell }_t \ge 0\), since individual losses are nonnegative and the Hedge distribution is nonnegative.

For \(p \in [0,1]\) and any \(h \in \mathbb {R}\),

This specializes the Bernoulli moment-generating-function bound from bernoulli_mgf_bound by substituting \(\eta = -h\).

For a valid loss sequence and \(\eta \gt 0\), applying Hoeffding’s lemma gives the tighter per-step bound