Why Specify a Comparator?
A risk value says how well a prediction rule performs under a specified distribution. A regret value compares that performance with something else. The comparison is meaningful only after that reference point—the comparator—has been specified. Comparing with one chosen rule answers a different question from comparing with the best risk available in an entire class.
Here, regret means a difference between population risks. It is not automatically nonnegative: a rule can outperform its comparator. This sign is useful information, not a defect in the definition. To keep the comparison precise, we will distinguish regret against one fixed comparator from excess risk above the infimum risk in a class.
Definition: Regret Against a Fixed Comparator
Let \(Z=(X,Y)\) have distribution \(P\), let \(h\) be a measurable prediction rule, and let \(\ell(h(X),Y)\) be its loss. Assume the population risks of the rules being compared are finite, where
A comparator \(g\) is another specified prediction rule evaluated on the same distribution with the same loss. It need not be chosen from the same class as \(h\).
The comparator must be held fixed when interpreting this quantity. A statement such as “the regret is \(0.1\)” is incomplete unless it is clear which distribution, loss, and comparator produced that difference. The two risks must also be well-defined and finite: subtracting two infinite risks does not define a regret.
Worked Example: Regret for Two Binary Predictors
Suppose \(Y\in\{0,1\}\), \(P(Y=1)=0.7\), and \(P(Y=0)=0.3\). There is no informative feature, and the loss is zero-one loss: predicting \(a\) incurs loss \(1\) if \(a\ne Y\), and \(0\) otherwise. Let \(h_1\) always predict \(1\), and let \(h_0\) always predict \(0\).
For \(h_1\), the loss is \(1\) exactly when \(Y=0\), so \(R_P(h_1)=P(Y=0)=0.3\). For \(h_0\), the loss is \(1\) exactly when \(Y=1\), so \(R_P(h_0)=P(Y=1)=0.7\).
Relative to \(h_0\), the regret of \(h_1\) is \(\Delta_P(h_1;h_0)=0.3-0.7=-0.4\). The negative sign says that \(h_1\) has lower risk than its comparator, by \(0.4\). Reversing the comparison gives \(\Delta_P(h_0;h_1)=0.7-0.3=0.4\).
How Fixed-Comparator Regret Differs from Class Excess Risk
A class-relative comparison uses a collection \(\mathcal H\) of prediction rules rather than one fixed rule. Its oracle risk is the infimum risk available in that class:
The class excess risk of a rule \(f\) is \(R_P(f)-R_P^*(\mathcal H)\). If \(f\in\mathcal H\), this quantity is nonnegative, whether or not a rule in the class actually attains the infimum. Fixed-comparator regret, by contrast, subtracts the risk of one particular rule and can have either sign.
Worked Example: Comparator Regret and Class Excess Risk
Let \(Y\) take values \(0,1,2\) with probabilities \(0.5,0.3,0.2\), respectively. Use zero-one loss and let \(\mathcal H=\{h_0,h_1,h_2\}\), where \(h_j\) always predicts \(j\). Take \(f=h_2\) and choose \(g=h_1\) as the comparator.
The risk of a constant rule is the probability that \(Y\) differs from its prediction. Thus \(R_P(h_0)=0.3+0.2=0.5\), \(R_P(h_1)=0.5+0.2=0.7\), and \(R_P(h_2)=0.5+0.3=0.8\). The class infimum is \(R_P^*(\mathcal H)=0.5\), attained by \(h_0\).
The regret of \(f\) relative to \(g\) is \(0.8-0.7=0.1\). The class excess risk of \(f\) is \(0.8-0.5=0.3\). These differ because the comparator \(h_1\) is itself \(0.7-0.5=0.2\) above the class’s best risk.
The values satisfy the exact decomposition \(0.3=0.1+0.2\): the class excess risk of \(f\) equals its regret relative to \(g\) plus the excess risk of \(g\) within the class. This calculation shows why naming the comparator matters.
A Decomposition for Comparators Inside a Class
The preceding example illustrates an identity that is useful whenever the comparator belongs to the class. The identity does not require a class minimizer to exist.
Proof. Since \(g\in\mathcal H\), the definition of infimum gives \(R_P^*(\mathcal H)\le R_P(g)\), so \(R_P(g)-R_P^*(\mathcal H)\ge 0\). For the identity, add and subtract \(R_P(g)\):
All terms are finite under the assumptions, so the rearrangement is valid. This proves the identity and the claimed sign. \(\square\)
If \(g\) attains the class infimum, the second term is zero, and the class excess risk of \(f\) equals its regret relative to \(g\). If \(g\) is only a convenient benchmark, its own distance from the class infimum must be accounted for.
Calculating Regret as an Expected Loss Difference
When both risks are finite, regret can also be computed by taking the expectation of the difference in losses. This form is especially convenient for finite distributions, where the expectation is a weighted sum.
Proof. The losses are nonnegative and have finite expectations. Therefore they are integrable, and their difference is integrable because \(\lvert \ell(h(X),Y)-\ell(g(X),Y)\rvert \le \ell(h(X),Y)+\ell(g(X),Y)\). Linearity of expectation then gives
This proves the result. \(\square\)
Worked Example: Summing Loss Differences on a Finite Distribution
Let \(Y\in\{0,1,2\}\) have probabilities \(0.2,0.5,0.3\). A rule chooses an action \(a\in\{A,B\}\). The loss table is:
| Outcome \(Y\) | Loss for \(A\) | Loss for \(B\) |
|---|---|---|
| 0 | 0 | 2 |
| 1 | 1 | 0 |
| 2 | 3 | 1 |
Let \(h\) choose \(A\) and let \(g\) choose \(B\). First calculate each risk by weighting the losses by the probabilities of the corresponding outcomes:
Thus \(\Delta_P(h;g)=1.4-0.7=0.7\). The loss differences for outcomes \(0,1,2\) are, respectively, \(-2,1,2\). Directly summing those differences gives \((0.2)(-2)+(0.5)(1)+(0.3)(2)=-0.4+0.5+0.6=0.7\), matching the risk difference.
When the Learning Rule Is Random
A learning rule may produce different predictors on different runs because its training data or its auxiliary randomness changes. In that case, the output \(\hat h\) is random, and so is \(R_P(\hat h)-R_P(g)\) for a fixed comparator \(g\). When the expectation exists, the average comparator-relative regret is
Here the expectation is over the randomness in the learning rule and its data; \(P\) remains the target distribution used to evaluate each output rule. This is not the same as evaluating a single realized output, and it is not obtained by changing the comparator from run to run without saying so.
Worked Example: Average Regret of a Randomized Rule
Suppose \(Y\in\{0,1\}\) with \(P(Y=1)=0.6\), and use zero-one loss. A learning rule outputs \(h_1\), which always predicts \(1\), with probability \(0.75\), and outputs \(h_0\), which always predicts \(0\), with probability \(0.25\). Use \(g=h_1\) as the fixed comparator.
The risks are \(R_P(h_1)=P(Y=0)=0.4\) and \(R_P(h_0)=P(Y=1)=0.6\). The regret is \(0\) when the rule outputs \(h_1\), and \(0.6-0.4=0.2\) when it outputs \(h_0\). Consequently, its average regret is \((0.75)(0)+(0.25)(0.2)=0.05\).
Equivalently, its expected risk is \((0.75)(0.4)+(0.25)(0.6)=0.3+0.15=0.45\). Subtracting the comparator risk gives \(0.45-0.4=0.05\), the same result.
Common Mistake: Assuming Regret Is Always Nonnegative
A common error is to define regret as a risk difference against a named comparator and then claim it must be nonnegative. That conclusion does not follow from subtraction alone. In the first example, \(R_P(h_1)-R_P(h_0)=-0.4\), because the supposedly compared rule \(h_1\) actually performs better.
The correction is to identify the reference point and the assumptions that make a sign claim valid. Regret against an arbitrary fixed comparator can be negative, zero, or positive. Excess risk over a class is nonnegative when the evaluated rule belongs to that class, because its risk cannot be below the class infimum. Regret against a comparator known to attain that infimum is also nonnegative for a rule in the class. Without those conditions, do not assert nonnegativity.
A second pitfall is silently switching the comparison target. A fixed comparator is one rule; a class comparator represents the infimum risk across a set of rules. If the fixed comparator is not class-optimal, the decomposition above shows the additional gap that must be included.
Check Your Understanding
Use the definitions and results above to answer these questions.
- If \(R_P(h)=0.25\) and \(R_P(g)=0.40\), what is the regret of \(h\) relative to \(g\), and what does its sign mean?
- Why can fixed-comparator regret be negative while excess risk over a class is nonnegative for a rule in that class?
- If \(g\in\mathcal H\), write the decomposition of the class excess risk of \(f\) into comparator-relative regret and the comparator’s gap above the class infimum.
- A randomized rule outputs predictors with risks \(0.3\) and \(0.5\) with probabilities \(0.6\) and \(0.4\). Its fixed comparator has risk \(0.35\). Calculate its average regret.
- What must be true of a comparator in \(\mathcal H\) for regret relative to it to equal class excess risk for every evaluated rule \(f\)?