External Regret Against a Fixed Comparator

Why Compare With a Fixed Decision?

In sequential prediction, a learner makes a decision on each round and then incurs a loss. A useful performance question is not simply how large the learner’s loss was, but how it compares with a decision that could have been used on every round. External regret measures this difference against the best such fixed decision, selected after the sequence of losses is known.

The word “fixed” matters: the comparator must be the same action on every round, although the best action can be chosen in hindsight. Regret is therefore a comparison with a benchmark, not a claim that the learner’s loss must be positive or that the learner performs worse on every individual round.

Definition and Three Scales of Regret

Let $\mathcal{A}$ be a nonempty finite set of actions, such as a set of experts. There are $T$ rounds. On round $t$, the learner selects an action $A_t\in\mathcal{A}$, and the loss of action $a$ is $\ell_t(a)$. Losses and actions may be random. Assume throughout that the losses are integrable, so the expectations below are well-defined.

Definition: For a realized sequence of actions and loss vectors, the learner’s cumulative loss is $\sum_{t=1}^T \ell_t(A_t)$. The cumulative loss of a fixed comparator $a\in\mathcal{A}$ is $\sum_{t=1}^T\ell_t(a)$. The pathwise external regret is $$ R_T=\sum_{t=1}^T\ell_t(A_t)-\min_{a\in\mathcal{A}}\sum_{t=1}^T\ell_t(a). $$ The minimum is taken after the whole loss sequence is realized. The expected external regret is $E[R_T]$, and the average (per-round) regret is $R_T/T$. Its expectation is $E[R_T]/T$.

For a particular fixed comparator $a$, define the round-$t$ regret relative to $a$ by $r_t(a)=\ell_t(A_t)-\ell_t(a)$. Summing gives regret relative to that comparator, $\sum_{t=1}^T r_t(a)$; external regret is the smallest such cumulative difference across the comparator set. “Per-round regret” can also refer to $r_t(a)$, the instantaneous difference on a particular round. It is important to distinguish that quantity from average cumulative regret, $R_T/T$.

Pathwise regret can be negative: the learner’s sequence of actions may do better than every single fixed action. It is nonnegative only under additional conditions, such as when the learner itself must use one fixed action throughout the sequence and that action belongs to $\mathcal{A}$. Randomly changing actions from round to round does not have that property.

Worked Example: Computing Pathwise and Average Regret

There are three actions, Red, Blue, and Green, and four rounds. Their losses are:

Round	Red	Blue	Green	Learner’s action
1	1	0	1	Green
2	0	2	1	Blue
3	2	0	1	Red
4	1	1	0	Green

The learner’s cumulative loss is $1+2+2+0=5$. Red’s fixed cumulative loss is $1+0+2+1=4$, Blue’s is $0+2+0+1=3$, and Green’s is $1+1+1+0=3$. The best fixed comparator therefore has loss $3$, so $R_4=5-3=2$. The average cumulative regret is $R_4/4=0.5$ per round.

If Blue is selected as the comparator, the round-by-round differences are $1-0=1$, $2-2=0$, $2-0=2$, and $0-1=-1$. They sum to $2$, as they must, because Blue is one of the best fixed comparators. The negative difference on round 4 does not cancel the meaning of the cumulative comparison; it simply says the learner did better than Blue on that round.

Randomized Learners and Expected Regret

A randomized learner may choose an action $A_t$ according to a distribution $p_t$ on $\mathcal{A}$. If the loss vector is known before the learner samples $A_t$, the conditional expected loss for that round is the probability-weighted loss $\sum_{a\in\mathcal{A}}p_t(a)\ell_t(a)$. This is a per-round statement conditioned on the information available before the draw. When later distributions can depend on earlier sampled actions, conditioning on the entire sequence of distributions and losses is generally different and can be invalid.

Result: Let $\mathcal{G}_t$ denote the information available immediately before the learner samples $A_t$. Suppose $p_t$ and the loss vector $(\ell_t(a):a\in\mathcal{A})$ are $\mathcal{G}_t$-measurable, and the conditional distribution of $A_t$ given $\mathcal{G}_t$ is $p_t$. Then $$ E[\ell_t(A_t)\mid\mathcal{G}_t]=\sum_{a\in\mathcal{A}}p_t(a)\ell_t(a). $$ Consequently, $$ E\left[\sum_{t=1}^T\ell_t(A_t)\right] = E\left[\sum_{t=1}^T\sum_{a\in\mathcal{A}}p_t(a)\ell_t(a)\right]. $$

Proof. Since $\mathcal{A}$ is finite, write the realized loss as a sum over the possible actions:

\ell_t(A_t)=\sum_{a\in\mathcal{A}}\mathbf{1}\{A_t=a\}\ell_t(a).

The losses are $\mathcal{G}_t$-measurable, so taking conditional expectation and using $P(A_t=a\mid\mathcal{G}_t)=p_t(a)$ gives

E[\ell_t(A_t)\mid\mathcal{G}_t] =\sum_{a\in\mathcal{A}}\ell_t(a)P(A_t=a\mid\mathcal{G}_t) =\sum_{a\in\mathcal{A}}p_t(a)\ell_t(a).

Taking expectations of both sides and applying the law of total expectation yields the unconditional identity for round $t$. Summing those identities over $t=1,\ldots,T$, using linearity of expectation for the finite sum, proves the cumulative identity. No conditioning on the entire sequence of future distributions or losses is needed. $\square$

Worked Example: Expected Regret for a Randomized Learner

There are two actions, A and B, with the following fixed loss vectors on three rounds: $(0,2)$, $(2,0)$, and $(0,1)$, where the first entry is A’s loss. The learner samples independently on each round, choosing A with probabilities $0.75$, $0.25$, and $0.75$, respectively.

The expected losses on the rounds are $0.75(0)+0.25(2)=0.5$, $0.25(2)+0.75(0)=0.5$, and $0.75(0)+0.25(1)=0.25$. Thus the expected learner loss is $0.5+0.5+0.25=1.25$. A’s fixed total is $0+2+0=2$, while B’s is $2+0+1=3$, so the best fixed comparator has loss $2$. The expected external regret is consequently $1.25-2=-0.75$.

Here the loss sequence is deterministic, so the hindsight comparator’s loss is the constant $2$. The negative expected regret is possible because randomizing across rounds lets the learner combine favorable actions from the two fixed alternatives. For instance, the realized action sequence A, B, A has loss $0$, and its regret is $0-2=-2$. This example also shows why external regret need not be nonnegative.

Hindsight Is Not the Same as Best in Expectation

When the losses are random, the best fixed action in hindsight is itself selected using the realized loss sequence. Its loss is $\min_a\sum_t\ell_t(a)$, and expected external regret subtracts this random minimum before taking expectation. That is not generally equivalent to first taking each action’s expected loss and then choosing the smallest. In symbols, the quantities $E[\min_a Z_a]$ and $\min_a E[Z_a]$ need not agree.

Worked Example: A Random Hindsight Comparator

There is one round and two actions, A and B. With probability $1/2$, their losses are $(0,1)$; with probability $1/2$, their losses are $(1,0)$. The learner always chooses A. Its expected loss is $0.5(0)+0.5(1)=0.5$. In either outcome, the best fixed action in hindsight has loss $0$, so expected external regret is $0.5-0=0.5$.

In contrast, the expected loss of A is $0.5$, and the expected loss of B is also $0.5$, so the minimum expected loss of a fixed action is $0.5$. Subtracting that quantity from the learner’s expected loss would give zero, not the expected external regret. The difference arises because the hindsight comparator can select A in the first outcome and B in the second, whereas a comparator chosen before the losses are observed cannot adapt that way.

Adaptive Protocols: Condition Before the Draw

The per-round identity remains valid when the environment or learner adapts to past observations, provided the current loss vector and current distribution are known before the current action is sampled. The next example shows why replacing this pre-sample conditioning with conditioning on the full sequence can fail.

Worked Example: Why Full-Sequence Conditioning Can Fail

There are two actions, A and B. On round 1, the learner chooses each with probability $1/2$, and the losses are $0$ for A and $1$ for B. On round 2, both losses are zero. The round-2 distribution is chosen adaptively: it puts probability one on A if the learner chose A on round 1, and probability one on B otherwise.

Before the first draw, the conditional expected loss is $0.5(0)+0.5(1)=0.5$. On round 2, the loss is zero whatever action is selected. Thus the expected cumulative learner loss is $0.5$, which also equals the expected cumulative mixture loss.

However, the full sequence of distributions reveals the round-1 action: the round-2 distribution is concentrated on A exactly when the first action was A. Conditional on that full sequence, the learner’s cumulative loss is therefore known to be either $0$ or $1$. The sum of the mixture losses remains $0.5$, so conditioning on the full sequence does not give the claimed equality. The correct argument conditions separately on the information available immediately before each draw, then takes unconditional expectations and sums.

Common Mistake and Practical Interpretation

Confusing the best hindsight action with the best expected action. Expected external regret uses the expected value of the minimum cumulative loss after the sequence is realized. It does not generally subtract the minimum of the expected cumulative losses.
Conditioning on information that reveals the action. In an adaptive protocol, later distributions can encode earlier actions. Use the pre-sample information for the conditional expectation identity, then take unconditional expectations.
Assuming regret is always nonnegative. A learner that switches actions can outperform every fixed comparator on a realized sequence. Nonnegativity does not follow from the definition.
Calling an instantaneous difference cumulative regret. A round’s $r_t(a)$ can be negative. Cumulative regret sums the differences over all rounds and compares with a fixed action.

Key takeaway: External regret compares the learner’s total realized loss with the loss of the best single action chosen in hindsight. Keep the pathwise minimum inside the expectation, distinguish it from a comparator chosen in advance, and apply conditional expectation only with respect to pre-sample information.

Check Your Understanding

Try these questions before moving on.

For a fixed realized sequence, what is the difference between regret against a specified comparator $a$ and external regret?
Can pathwise external regret be negative? Give a condition under which it can happen.
What information must be available before the round-$t$ draw for the conditional mixture-loss identity to apply?
Why can the distribution sequence reveal earlier actions in an adaptive protocol?
In a random-loss problem, explain the difference between $E[\min_a\sum_t\ell_t(a)]$ and $\min_a E[\sum_t\ell_t(a)]$.