Regret With Sleeping and Specialist Experts

Why Sleeping Experts Need a Different Comparator

In ordinary expert aggregation, every expert supplies a prediction on every round. In many applications, however, an expert is only available in certain contexts: a specialist may cover particular diagnoses, a forecasting model may apply only to a particular season, or a recommendation system may have advice only for some users. Comparing the forecaster with such an expert on rounds when it had no advice would not answer the relevant question.

The appropriate benchmark is therefore conditional on availability. The forecaster must still make a prediction each round, using the experts that are available then, while the comparator’s loss includes only rounds on which that particular expert was active.

We consider a protocol in which the forecaster can aggregate the active experts so its loss equals their weighted average loss. This holds, for example, for expected loss under randomized expert selection, or for appropriate convex prediction losses when the forecaster predicts with the weighted mixture. The losses are observed after the round. Let \(\pi_i>0\) be a prior weight for each expert, with \(\sum_i\pi_i=1\); the collection may be finite or countable.

The Specialist Update

Fix a learning rate \(\eta>0\). Let \(w_{i,1}=\pi_i\), and write \(W_t=\sum_i w_{i,t}\) for the total weight before round \(t\). Among the active experts, normalize the weights to obtain the prediction probabilities. The forecaster’s loss is the corresponding weighted mean. After observing losses, update active experts relative to that forecaster loss; leave sleeping experts’ weights alone.

Centering each active expert’s loss at \(L_t\) is the key. An expert doing better than the forecaster gains weight; one doing worse loses weight. Since the same factor is applied to every active weight when changing from a loss-based update to this centered form, the active experts’ normalized prediction probabilities have the usual exponential-weight structure. But the centered form makes it possible to control the total weight even as the active set changes.

A Prior-Weighted Regret Guarantee

The guarantee holds simultaneously for every expert. Its complexity term is determined by that expert’s prior weight: an expert assigned smaller prior weight pays a larger comparison penalty. The time term uses the total number of rounds, not just the number of rounds on which the comparator is active.

We first give the exponential-moment fact used in the proof. If \(Z\) is any random variable supported on \([0,1]\), then \(E[\exp(s(Z-E[Z]))]\le\exp(s^2/8)\) for every real \(s\). To verify it, set \(g(s)=\log E[\exp(s(Z-E[Z]))]\). Boundedness permits differentiation under the expectation, and \(g(0)=g'(0)=0\). The second derivative is the variance of \(Z\) under the exponentially tilted distribution. Any distribution supported on \([0,1]\) has variance at most \(1/4\): its variance is at most its mean squared distance from \(1/2\), which is at most \(1/4\). Thus \(g''(s)\le1/4\). Integrating this bound from zero to \(s\), twice (or from \(s\) to zero when \(s<0\)), gives \(g(s)\le s^2/8\), proving the fact.

Proof of the theorem. Fix a round \(t\). Let \(q_t=(\sum_{i\in A_t}w_{i,t})/W_t\), the fraction of total weight that is active. Under probabilities \(p_{i,t}\) on \(A_t\), consider the random variable that takes value \(\ell_{i,t}\) with probability \(p_{i,t}\). Its mean is \(L_t\). The exponential-moment fact, with \(s=-\eta\), gives \(\sum_{i\in A_t}p_{i,t}\exp(-\eta(\ell_{i,t}-L_t))\le\exp(\eta^2/8)\).

Inactive weights do not change. Dividing the updated total weight by its old value therefore yields

The last inequality follows because \(0\le q_t\le1\), so \(1-q_t+q_t e^a\le e^a\) for \(a\ge0\). Iterating over rounds and using \(W_1=1\) gives \(W_{T+1}\le\exp(\eta^2T/8)\).

For a fixed expert \(i\), its update multiplies its weight only on rounds when it is active. Consequently,

Taking logarithms, rearranging, and dividing by \(\eta>0\) proves the stated bound. \(\square\)

For a fixed horizon and known prior, the right-hand side is minimized by \(\eta=\sqrt{8\log(1/\pi_i)/T}\) when \(\pi_i<1\). Substitution gives the bound \(\sqrt{T\log(1/\pi_i)/2}\). In practice a single learning rate is used for all experts, so the theorem applies to that same \(\eta\) for every \(i\); choosing a separate rate based on the unknown comparator is not required for the theorem.

Common Mistake and Practical Interpretation

A common mistake is to assign an asleep expert loss zero and include that round in its comparator sum. That would make sleeping count as perfect performance, rather than treating the expert as unavailable. The correction is to sum both comparator loss and forecaster loss only over \(t\) for which \(i\in A_t\), as in the definition of \(R_i(T)\). Similarly, an unavailable prediction should not receive weight in the forecaster’s round-\(t\) mixture.

The result matters when expert availability reflects genuine scope rather than poor performance. It lets a forecaster use whichever specialists are relevant and still compare with each specialist on the rounds it could have advised. The prior-weighted form also accommodates countably many candidates without requiring a uniform distribution over them.