Prior-Weighted Regret for Countable Experts

Why Prior-Weighted Regret?

A regret guarantee compares a learner’s cumulative loss with the loss of a fixed expert. When there are finitely many experts, one common strategy begins with equal weights. For a countably infinite class, equal positive weights cannot sum to one. A prior distribution solves this problem: it assigns each expert a positive initial weight, and the regret bound charges an expert according to how much prior mass it receives.

The resulting comparison is individual and simultaneous: the same learner can be bounded against every expert in the countable class. An expert with large prior mass has a smaller complexity penalty; an expert with very small prior mass is still covered, but the bound reflects the additional cost of assigning it little initial weight.

Definition: Let $\mathcal{I}$ be a finite or countable set of experts. A prior on $\mathcal{I}$ is a collection $(\pi_i)_{i\in\mathcal{I}}$ such that $\pi_i>0$ for every expert under consideration and $\sum_{i\in\mathcal{I}}\pi_i=1$. On round $t$, expert $i$ has loss $\ell_{t,i}\in[0,1]$. Its cumulative loss through round $T$ is $L_{T,i}=\sum_{t=1}^T\ell_{t,i}$.

The losses may be chosen adversarially and may depend on earlier rounds. The guarantee below is pathwise: for any realized sequence of loss vectors in $[0,1]^{\mathcal{I}}$, it bounds the learner’s cumulative loss. At the start of a round, the learner forms weights using losses observed before that round. It then incurs the weighted average loss, or a loss no greater than that average when its prediction is a convex combination and the loss is convex.

Exponential Weights With a Countable Prior

Fix a learning rate $\eta>0$. After observing the losses through round $t-1$, assign expert $i$ the weight proportional to its prior mass times its cumulative exponential discount. The normalizing constant is finite and positive: each exponential factor lies in $(0,1]$, and at least one prior mass is positive.

Definition: Set $L_{0,i}=0$, and define $$ Z_t=\sum_{i\in\mathcal{I}}\pi_i\exp(-\eta L_{t,i}),\qquad w_{t,i}=\frac{\pi_i\exp(-\eta L_{t-1,i})}{Z_{t-1}}. $$ Then $Z_0=1$, $Z_t>0$, and $\sum_i w_{t,i}=1$. The learner’s weighted loss on round $t$ is $m_t=\sum_i w_{t,i}\ell_{t,i}$.

In a prediction problem, the weighted loss $m_t$ can be the learner’s actual loss, for example when it randomizes among experts and loss is evaluated in expectation. If the learner instead predicts the weighted average of expert predictions under a convex loss, Jensen’s inequality gives learner loss at most $m_t$. We first bound the sum of the weighted losses; either interpretation then gives the corresponding bound on learner loss.

Worked Example: Updating Two Prior Weights

Consider two experts with prior masses $\pi_1=2/3$ and $\pi_2=1/3$, and set $\eta=2$. Suppose the first-round losses are $\ell_{1,1}=0$ and $\ell_{1,2}=c$, where $c=\frac12\ln(2\sqrt{2})$. Since $c=\frac34\ln 2$, it is approximately $0.5199$, within the required loss range.

After round one, the unnormalized weights are $$ \pi_1\exp(-2\ell_{1,1})=\frac23,\qquad \pi_2\exp(-2\ell_{1,2})=\frac13\exp\bigl(-\ln(2\sqrt{2})\bigr)=\frac{1}{6\sqrt{2}}. $$

Their sum is $2/3+1/(6\sqrt{2})$. Therefore the second-round weight on expert 2 is $$ w_{2,2}=\frac{1/(6\sqrt{2})}{2/3+1/(6\sqrt{2})} =\frac{1}{1+4\sqrt{2}}\approx 0.1502. $$ The other weight is $w_{2,1}=1-w_{2,2}\approx 0.8498$. If the second-round losses are $0$ and $1$, respectively, the weighted loss is $m_2=w_{2,2}\approx 0.1502$. The calculation illustrates how a prior mass and observed losses jointly determine the next-round mixture.

A Bounded-Loss Exponential Inequality

The regret proof relies on a one-round inequality: the log of the weighted exponential average is controlled by the weighted mean loss plus a quadratic term. We give the underlying argument so the constant and boundedness condition are explicit.

Lemma: If $X$ is any random variable supported on $[0,1]$, then for every real $s$, $$ \log E\!\left[\exp\{s(X-E[X])\}\right]\le \frac{s^2}{8}. $$

Proof. Define $\psi(s)=\log E[\exp\{s(X-E[X])\}]$. Because $X$ is bounded, the expectation is finite and can be differentiated twice under the expectation: on every bounded interval of $s$, the integrands and their first two derivatives are bounded. Differentiating shows that $\psi''(s)$ is the variance of $X$ under the probability distribution tilted by the factor $\exp(sX)$. That tilted variable is still supported on $[0,1]$. Any random variable $Y$ in this interval satisfies $\operatorname{Var}(Y)\le 1/4$, since $\operatorname{Var}(Y)=\min_a E[(Y-a)^2]\le E[(Y-1/2)^2]\le 1/4$. Thus $\psi''(s)\le 1/4$ for all $s$. Also $\psi(0)=\psi'(0)=0$. Integrating the second-derivative bound from zero to $s$, for either sign of $s$, gives $\psi(s)\le s^2/8$. $\square$

For any probability weights $(w_i)$ on a finite or countable set and losses $\ell_i\in[0,1]$, apply the lemma to a random variable taking value $\ell_i$ with probability $w_i$, and set $s=-\eta$. It follows that $$ \log\left(\sum_i w_i\exp(-\eta\ell_i)\right) \le -\eta\sum_i w_i\ell_i+\frac{\eta^2}{8}. $$ The countable case is covered because the random variable is bounded; no finite-support assumption is needed.

Prior-Weighted Regret Guarantee

The theorem converts the one-round inequality into a comparison with every individual expert. The prior mass appears because the cumulative exponential weight always retains the contribution from that expert.

Theorem: For any countable expert set, prior $(\pi_i)$, learning rate $\eta>0$, and sequence of losses $\ell_{t,i}\in[0,1]$, the exponential-weights learner satisfies, for every expert $i$ and every $T\ge 1$, $$ \sum_{t=1}^T m_t-L_{T,i} \le \frac{\ln(1/\pi_i)}{\eta}+\frac{\eta T}{8}. $$ If the learner’s loss on each round is at most $m_t$, the same upper bound holds for its cumulative regret against expert $i$.

Proof. The normalizers obey a round-by-round identity: $$ \frac{Z_t}{Z_{t-1}}=\sum_j w_{t,j}\exp(-\eta\ell_{t,j}). $$ Apply the exponential inequality just proved, with weights $w_{t,j}$. Taking logs gives $$ \ln Z_t-\ln Z_{t-1}\le -\eta m_t+\frac{\eta^2}{8}. $$ Sum over $t=1,\ldots,T$. The normalizer terms telescope, and $Z_0=1$, so $$ \ln Z_T\le -\eta\sum_{t=1}^T m_t+\frac{\eta^2T}{8}. $$ On the other hand, the term for expert $i$ is one of the nonnegative terms in $Z_T$. Consequently, $$ Z_T\ge \pi_i\exp(-\eta L_{T,i}), \qquad \ln Z_T\ge \ln\pi_i-\eta L_{T,i}. $$ Combining the upper and lower bounds on $\ln Z_T$, and rearranging using $\eta>0$, yields $$ \sum_{t=1}^T m_t-L_{T,i} \le \frac{\ln(1/\pi_i)}{\eta}+\frac{\eta T}{8}. $$ This argument holds for each $i$, so the conclusion is simultaneous over the countable class. If the actual learner loss is at most $m_t$ on every round, summing those inequalities gives the stated version for the learner’s loss. $\square$

The bound has two parts. The term $\ln(1/\pi_i)/\eta$ is the penalty for the expert’s prior mass; the term $\eta T/8$ grows with the number of rounds. For a fixed horizon and comparator, balancing these terms is possible by selecting $\eta=\sqrt{8\ln(1/\pi_i)/T}$, when $\pi_i<1$. The resulting bound is $\sqrt{T\ln(1/\pi_i)/2}$. A single choice of $\eta$ does not make this choice separately for every expert, and the choice displayed here uses $T$.

Worked Example: A Numerical Regret Bound

Suppose a particular expert has prior mass $\pi_i=1/16$, the horizon is $T=100$, and the learning rate is $\eta=\sqrt{8\ln(16)/100}$. Since $\ln(16)\approx 2.7726$, this gives $\eta\approx 0.4710$.

The complexity contribution is $\ln(16)/\eta\approx 2.7726/0.4710\approx 5.887$. The horizon contribution is $\eta T/8\approx 0.4710(100)/8\approx 5.887$. Thus the theorem bounds regret against this expert by approximately $11.77$. Equivalently, the optimized expression is $\sqrt{100\ln(16)/2}\approx 11.77$. The bound is an upper bound, not a claim that the realized regret equals this number.

Worked Example: Geometric Prior Over Infinitely Many Experts

Index experts by positive integers $j=1,2,\ldots$, and assign $\pi_j=2^{-j}$. This is a valid prior because $$ \sum_{j=1}^{\infty}2^{-j}=\frac{1/2}{1-1/2}=1. $$ For expert $j=5$, the prior mass is $1/32$, so its complexity term is $\ln(1/\pi_5)/\eta=\ln(32)/\eta=5\ln(2)/\eta$. At $T=50$ and $\eta=0.4$, the theorem gives $$ \sum_{t=1}^{50}m_t-L_{50,5} \le \frac{5\ln(2)}{0.4}+\frac{0.4(50)}{8} \approx 8.664+2.5=11.164. $$ The same construction provides a guarantee for every indexed expert, with a penalty that increases logarithmically in the index.

Interpreting the Bound and Avoiding a Common Error

A prior is a way to express relative preference before the losses are observed, not a requirement that an expert be likely to perform well. The regret guarantee remains valid even if the prior assigns little mass to the best-performing expert; the price is the larger $\ln(1/\pi_i)$ term. For example, multiplying an expert’s prior mass by a factor of 100, while still maintaining a normalized prior, reduces its logarithmic penalty by $\ln(100)/\eta$.

Common mistake: “There are countably many experts, so give every expert the same positive initial weight.” This cannot define a probability prior: if every expert receives weight $c>0$, then the sum over infinitely many experts is infinite, not one. Assigning weight zero to all but finitely many experts is also not a solution if a guarantee is required for the excluded experts, because $\ln(1/\pi_i)$ is not finite when $\pi_i=0$. The correction is to choose a summable positive sequence, such as $\pi_j=2^{-j}$, or another normalized prior appropriate to the class.

The bound is useful when a learner must compete with a structured collection of alternatives, including countably many models or prediction rules. It turns an infinite comparison into a collection of explicit guarantees: each comparator pays according to its assigned mass. The guarantee requires losses in a bounded interval; changing the loss range changes the scale of the quadratic term. It also makes no claim that the prior-weighted learner always beats the best expert on a particular sequence: regret may be positive, and the theorem controls how large it can be.

Check Your Understanding

Use the definitions and proof above to answer these questions.

Why does the normalizer $Z_t$ remain positive and finite when the expert set is countable and losses lie in $[0,1]$?
For a prior mass $\pi_i=1/8$, write the expert’s complexity penalty as a function of $\eta$.
In the theorem’s proof, which inequality supplies the lower bound on $Z_T$, and why is it valid for every expert?
Why can’t all experts in a countably infinite set receive the same positive prior mass?
If the loss range changes from $[0,1]$ to $[0,B]$, what rescaling would let you apply the bounded-loss result stated here?