Randomized Predictions and Expected Regret

Two Different Ways to Randomize a Prediction

Suppose a collection of experts supplies predictions, and a learner assigns a probability to each expert. There are two distinct actions the learner might take. It can sample an expert and use that expert’s prediction, or it can combine the experts’ predictions into a mixture prediction. The first action is random; the second is a single, usually deterministic, prediction. Their losses need not be the same.

This distinction matters when translating an online regret bound into a statement about actual predictions. A bound on the probability-weighted average of expert losses is an expected-loss guarantee for sampling an expert. It is also an upper bound on the loss of a feasible mixture prediction when the loss is convex. Without convexity, that second conclusion does not follow.

Definition: On round $t$, let $\ell_{t,i}$ be expert $i$'s loss, for $i\in\{1,\ldots,N\}$. A probability vector $q_t=(q_{t,1},\ldots,q_{t,N})$ has $q_{t,i}\geq 0$ and $\sum_{i=1}^N q_{t,i}=1$. The mixture loss is $\sum_{i=1}^N q_{t,i}\ell_{t,i}$. If the learner draws $I_t$ from $q_t$ and incurs $\ell_{t,I_t}$, its loss is random; its expected regret to the best fixed expert is $$ \mathbb{E}\!\left[\sum_{t=1}^T \ell_{t,I_t}\right] -\min_{1\leq i\leq N}\sum_{t=1}^T\ell_{t,i}. $$

For the sampling interpretation, assume the current loss vector is fixed, or at least chosen before the current draw, and the draw has conditional distribution $q_t$ given the information available at that time. This timing condition prevents the losses on round $t$ from responding to the realized $I_t$. The setting here is full information: the learner can use the expert loss vector to update its probabilities. Expected loss does not mean that the learner observes a fractional portion of an expert’s loss.

Sampling an Expert: The Expected-Loss Identity

Conditionally on the current probability vector and loss vector, the sampled expert has loss $\ell_{t,i}$ with probability $q_{t,i}$. The expectation is therefore the probability-weighted average. Summing this identity over rounds gives the key link between an algorithm’s mixture losses and the expected loss of the action it actually samples.

Theorem: Suppose $q_t$ is determined before the draw $I_t$, and, conditional on the information before that draw, $I_t$ has probabilities $q_{t,1},\ldots,q_{t,N}$. Suppose also that the loss vector $(\ell_{t,1},\ldots,\ell_{t,N})$ is determined before the draw. Then $$ \mathbb{E}\!\left[\sum_{t=1}^T\ell_{t,I_t}\right] =\mathbb{E}\!\left[\sum_{t=1}^T\sum_{i=1}^N q_{t,i}\ell_{t,i}\right]. $$

Proof. Let $\mathcal{G}_t$ denote the information available just before the draw on round $t$, including the current loss vector. By the specified conditional distribution, $$ \mathbb{E}[\ell_{t,I_t}\mid\mathcal{G}_t] =\sum_{i=1}^N P(I_t=i\mid\mathcal{G}_t)\ell_{t,i} =\sum_{i=1}^N q_{t,i}\ell_{t,i}. $$ Taking expectations on both sides and summing over $t$ proves the identity. $\square$

If an algorithm guarantees that its cumulative mixture loss is at most the best expert’s cumulative loss plus $B$ for every realized loss sequence, the identity implies expected regret at most $B$. Indeed, take expectations of that inequality and use the identity for the learner’s cumulative loss. The comparator is the best fixed expert for the realized sequence; it is not a new expert drawn on each round.

Worked Example: One-Round Sampling Versus Mixture Loss

Two experts have losses $0.2$ and $0.8$, and the learner assigns probabilities $q=(0.75,0.25)$. Find the expected loss if the learner samples an expert, and compare it with the mixture loss.

With probability $0.75$, the learner incurs $0.2$; with probability $0.25$, it incurs $0.8$. Thus $$ \mathbb{E}[\ell_{t,I_t}] =0.75(0.2)+0.25(0.8) =0.15+0.20 =0.35. $$ The mixture loss is also $$ \sum_{i=1}^2 q_i\ell_{t,i} =0.75(0.2)+0.25(0.8) =0.35. $$ The numerical equality is an equality of expected loss and mixture loss. A single sampled round still incurs either $0.2$ or $0.8$, not $0.35$.

A Hedge Guarantee for Randomized Expert Selection

A familiar way to form probabilities over experts is Hedge. For losses in $[0,1]$, learning rate $\eta>0$, and cumulative expert losses before round $t$, define $$ q_{t,i}=\frac{\exp\!\left(-\eta\sum_{s=1}^{t-1}\ell_{s,i}\right)} {\sum_{j=1}^N\exp\!\left(-\eta\sum_{s=1}^{t-1}\ell_{s,j}\right)}. $$ The weights favor experts with smaller past loss. The next result first bounds the cumulative mixture loss; the expected-loss identity then gives the same bound for sampled predictions in expectation.

Theorem: For any loss sequence with $\ell_{t,i}\in[0,1]$, the Hedge probabilities above satisfy, for every $\eta>0$, $$ \sum_{t=1}^T\sum_{i=1}^Nq_{t,i}\ell_{t,i} -\min_{1\leq i\leq N}\sum_{t=1}^T\ell_{t,i} \leq \frac{\log N}{\eta}+\frac{\eta T}{8}. $$ If the learner samples $I_t$ from $q_t$ after the current loss vector is fixed, its expected regret obeys the same bound.

Proof. Define the potential $$ W_t=\sum_{i=1}^N\exp\!\left(-\eta\sum_{s=1}^{t-1}\ell_{s,i}\right). $$ Then $W_1=N$, and $$ \frac{W_{t+1}}{W_t}=\sum_{i=1}^N q_{t,i}\exp(-\eta\ell_{t,i}). $$ Hoeffding’s lemma states that if a random variable $Z$ lies in an interval of length $1$, then $\log \mathbb{E}[\exp(\lambda Z)]\leq \lambda\mathbb{E}[Z]+\lambda^2/8$. Apply it under distribution $q_t$ to $Z=\ell_{t,i}$ and $\lambda=-\eta$. This gives $$ \log\frac{W_{t+1}}{W_t} \leq -\eta\sum_{i=1}^Nq_{t,i}\ell_{t,i}+\frac{\eta^2}{8}. $$ Summing over $t$ and using $W_1=N$, $$ \log W_{T+1} \leq \log N-\eta\sum_{t=1}^T\sum_{i=1}^Nq_{t,i}\ell_{t,i} +\frac{\eta^2T}{8}. $$ For an expert $i^\star$ with minimum cumulative loss, $W_{T+1}\geq\exp(-\eta\sum_{t=1}^T\ell_{t,i^\star})$. Taking logarithms of this lower bound and combining it with the upper bound yields the claimed mixture-loss inequality after rearrangement. The expected-regret claim follows from the expected-loss identity. $\square$

Worked Example: Applying the Hedge Bound to Three Experts

Consider two rounds with three experts and loss vectors $(0,0.5,1)$ and $(0.8,0.2,0.4)$. Use Hedge with $\eta=1$. Compute its mixture losses and compare their sum with the best expert.

Initially $q_1=(1/3,1/3,1/3)$, so the first mixture loss is $$ m_1=\frac{0+0.5+1}{3}=0.5. $$ After the first loss vector, the unnormalized weights are $1,e^{-0.5},e^{-1}$. Their sum is approximately $1.9744$, so $$ q_2\approx(0.5065,0.3072,0.1863). $$ The second mixture loss is $$ m_2\approx0.5065(0.8)+0.3072(0.2)+0.1863(0.4) \approx0.5412. $$ Thus the cumulative mixture loss is approximately $0.5+0.5412=1.0412$. The experts’ cumulative losses are $0.8$, $0.7$, and $1.4$, so the best fixed expert has loss $0.7$; the mixture regret is approximately $1.0412-0.7=0.3412$. For a learner that samples from $q_t$, its expected cumulative loss is $1.0412$, and its expected regret is also approximately $0.3412$. The theorem’s upper bound is $\log 3+2/8\approx1.3486$, which is larger than the computed regret, as required.

Mixture Predictions and Convex Losses

Now suppose each expert predicts an action $a_{t,i}$ in a convex set $\mathcal{A}$, and the loss for an action $a$ is $\ell_t(a)$. The probability mixture is the single action $\bar a_t=\sum_i q_{t,i}a_{t,i}$, which belongs to $\mathcal{A}$ because the set is convex. If $\ell_t$ is convex on $\mathcal{A}$, Jensen’s inequality says that the loss of this action is no greater than the probability-weighted average loss of the expert actions.

Theorem: If $\mathcal{A}$ is convex, $a_{t,i}\in\mathcal{A}$, and $\ell_t:\mathcal{A}\to\mathbb{R}$ is convex, then $$ \ell_t\!\left(\sum_{i=1}^Nq_{t,i}a_{t,i}\right) \leq \sum_{i=1}^Nq_{t,i}\ell_t(a_{t,i}). $$ Consequently, over any fixed sequence of rounds, the cumulative loss of mixture predictions is no greater than the cumulative mixture loss. In particular, a mixture-regret bound also upper-bounds the regret of these predictions to the best expert.

Proof. Convexity means that for any $a,b\in\mathcal{A}$ and $\alpha\in[0,1]$, $\ell_t(\alpha a+(1-\alpha)b)\leq\alpha\ell_t(a)+(1-\alpha)\ell_t(b)$. Applying this two-point inequality repeatedly gives the finite-weight version for any probability vector $q_t$: $$ \ell_t\!\left(\sum_{i=1}^Nq_{t,i}a_{t,i}\right) \leq\sum_{i=1}^Nq_{t,i}\ell_t(a_{t,i}). $$ Summing over rounds gives the cumulative comparison. Subtracting the same best-expert cumulative loss from both sides shows that the mixture-prediction regret is no larger than the mixture-loss regret. $\square$

Worked Example: Squared Loss Favors the Mixture Prediction

Two experts predict $0$ and $2$, each with probability $1/2$, and the observed outcome is $y=1$. Under squared loss $\ell(a)=(a-y)^2$, compare sampling an expert with predicting the mixture.

Sampling incurs squared loss $(0-1)^2=1$ or $(2-1)^2=1$, so its expected loss is $\frac12(1)+\frac12(1)=1$. The mixture prediction is $\bar a=\frac12(0)+\frac12(2)=1$, and its loss is $(1-1)^2=0$. This satisfies the convexity inequality: $0\leq1$. The mixture is strictly better here, even though its prediction is not one of the experts’ predictions.

When the Distinction Matters

The convexity condition is substantive. For losses that are not convex in the prediction, a probability mixture need not perform as well as sampling in expectation. For example, take two label predictions $0$ and $1$, each with probability $1/2$, and use zero-one classification loss. If the true label is $0$, sampling has expected loss $1/2$. The numerical average prediction is $1/2$, but it is not a label in $\{0,1\}$; turning it into a label requires an additional rule, such as a tie-breaking convention. There is no general convex-loss argument that makes that converted prediction no worse than sampling.

A related mistake is to claim that randomized predictions have regret at most the mixture bound on every realized run. The identity proved above is an identity of expectations, not a claim that $\ell_{t,I_t}$ equals $\sum_iq_{t,i}\ell_{t,i}$ on each round. A sampled learner may incur larger loss than the mixture on one run and smaller loss on another. The deterministic guarantee applies directly to the mixture losses; the sampling guarantee is in expectation, under the stated timing condition.

Key takeaway: Sampling an expert turns a probability-weighted loss into an expected loss, provided the current draw cannot affect the current loss vector. A feasible probability-mixture action has no greater loss than that expectation when the loss is convex. These are related guarantees, but they are not the same prediction rule.

Check Your Understanding

Answer each question by identifying whether it concerns sampling, mixture loss, or a convex mixture prediction.

Why must the current loss vector be fixed before the learner draws an expert to use the expected-loss identity?
Does a bound on cumulative mixture loss imply the same bound on every realized cumulative loss of a sampled learner? Explain.
State the condition under which the mixture prediction’s loss is no greater than the probability-weighted average of expert losses.
For Hedge with $N$ experts, what is the regret upper bound when all losses lie in $[0,1]$ and the learning rate is $\eta$?
Give one reason why averaging two class labels does not automatically provide a valid convex-mixture prediction guarantee.