Adversarial Regret Versus Stochastic Excess Risk

Two Benchmarks, Two Questions

An online regret guarantee and a stochastic excess-risk guarantee can both describe how well a learning rule performs, but they compare it with different benchmarks. Regret asks how the rule performed on a particular sequence relative to the single decision that would have performed best after that sequence was known. Excess risk asks how a decision performs on average under a probability distribution relative to the best decision for that distribution. Confusing the benchmarks can make a valid guarantee sound stronger than it is.

Let $\mathcal A$ be a nonempty decision class, $z$ an outcome, and $\ell(a,z)$ the loss of decision $a\in\mathcal A$. On a realized sequence $z_1,\ldots,z_n$, an online learner chooses $A_t$ before observing $z_t$. Its cumulative comparator regret is

R_n=\sum_{t=1}^n \ell(A_t,z_t) -\inf_{a\in\mathcal A}\sum_{t=1}^n\ell(a,z_t).

The comparator is fixed across rounds, but it is selected with hindsight: it minimizes loss on the realized sequence. In contrast, under an outcome distribution $P$, define the population risk $r_P(a)=E_{Z\sim P}[\ell(a,Z)]$. If a minimizer exists, the excess risk of a decision $a$ is $r_P(a)-\inf_{b\in\mathcal A}r_P(b)$.

Definition: Adversarial comparator regret compares cumulative online loss with the smallest cumulative loss of a fixed decision chosen after seeing the sequence. Stochastic excess risk compares population risk with the smallest population risk in the decision class. The first is sequence-based; the second is distribution-based.

If the learner or its output is random, excess risk is itself random until an expectation is taken over the training data and learner randomness. We will state explicitly when that expectation is used. For simplicity, assume losses are measurable and integrable wherever their expectations appear.

Worked Examples of the Difference

Worked Example: Small Regret, Poor Final Iterate

Take $\mathcal A=\{0,1\}$, outcomes $z\in\{0,1\}$, and zero-one loss $\ell(a,z)=\mathbf 1\{a\ne z\}$. Let every outcome be zero, so $P(Z=0)=1$. Consider a learner that chooses $A_t=0$ for $t<n$ and $A_n=1$.

The learner makes one error, so its cumulative loss is $1$. The best fixed decision in hindsight is $a=0$, with cumulative loss $0$. Thus $R_n=1$, and $R_n/n=1/n$ tends to zero as $n$ grows.

The final decision, however, has risk $r_P(A_n)=\ell(1,0)=1$, while the population minimizer $a_P^*=0$ has risk zero. The final iterate has excess risk $1$, for every $n$. Low average regret therefore need not mean that the last decision has low excess risk. The regret is small because only one round used the poor decision.

Worked Example: Zero Stochastic Excess Risk, Linear Adversarial Regret

Use the same action set and loss. Suppose $P(Z=0)=1$, and a learner always chooses action $0$. Its population risk is $r_P(0)=0$, which is minimal, so its excess risk is zero.

Now evaluate the learner on the adversarial sequence $z_t=1$ for every $t$. It incurs loss $1$ each round, for cumulative loss $n$. The hindsight decision $a=1$ incurs loss zero on every round, so $R_n=n$.

There is no contradiction: the stochastic guarantee refers to outcomes drawn from $P$, whereas the adversarial sequence is not drawn from this degenerate distribution. A guarantee under one specified law does not control performance on every possible sequence.

Worked Example: A Good Realized Comparison Need Not Identify the Population Optimum

Again let $\mathcal A=\{0,1\}$ and use zero-one loss, but now let $P(Z=1)=0.1$ and $P(Z=0)=0.9$. The population risks are $r_P(0)=0.1$ and $r_P(1)=0.9$, so the population minimizer is $0$, and action $1$ has excess risk $0.8$.

On the particular sequence $z_1=\cdots=z_n=1$, a learner that chooses action $1$ every round incurs cumulative loss zero. The hindsight comparator also incurs zero, so the regret on this sequence is zero.

That realized comparison does not make action $1$ a good decision under $P$. This sequence has probability $0.1^n$, which is positive for every finite $n$, and on it the hindsight winner is unlike the population minimizer. A favorable regret value on one realized sequence is not a population-risk statement.

When Expected Regret Does Control Average Excess Risk

There is an important connection when outcomes are iid and actions are chosen online. The key is that the action for round $t$ is selected before the fresh outcome $Z_t$ is observed. Conditional on the information used to choose that action, $Z_t$ still has distribution $P$. The resulting guarantee concerns the average risk of the online actions in expectation, not necessarily the final action.

Theorem: Suppose $Z_1,\ldots,Z_n$ are iid from $P$. For each $t$, let $A_t$ be measurable with respect to the learner's information before observing $Z_t$, and assume this information and any learner randomization are independent of the fresh $Z_t$. Suppose the losses are integrable and a population minimizer $a_P^*\in\mathcal A$ exists. Then $$ \frac{1}{n}\sum_{t=1}^n E\!\left[r_P(A_t)-r_P(a_P^*)\right] \leq \frac{E[R_n]}{n}. $$ In particular, if $E[R_n]\leq B_n$, the left-hand side is at most $B_n/n$.

Proof. Since $a_P^*$ is an available fixed comparator, on every realized sequence,

\inf_{a\in\mathcal A}\sum_{t=1}^n\ell(a,Z_t) \leq \sum_{t=1}^n\ell(a_P^*,Z_t).

Subtracting the left-hand side from the learner's cumulative loss therefore gives a value at least as large as subtracting the right-hand side. Hence, pointwise,

R_n \geq \sum_{t=1}^n \bigl(\ell(A_t,Z_t)-\ell(a_P^*,Z_t)\bigr).

Take expectations. By the stated independence and the fact that $A_t$ is chosen before $Z_t$, conditioning on the information available when $A_t$ is chosen gives

E[\ell(A_t,Z_t)\mid A_t]=r_P(A_t), \qquad E[\ell(a_P^*,Z_t)]=r_P(a_P^*).

Taking expectations in the pointwise inequality and summing these identities yields

E[R_n]\geq \sum_{t=1}^n E\!\left[r_P(A_t)-r_P(a_P^*)\right].

Dividing by $n$ proves the claim. $\square$

For example, if an index $J$ is drawn uniformly from $\{1,\ldots,n\}$, independently of the data and learner, the output $A_J$ satisfies

E[r_P(A_J)-r_P(a_P^*)] =\frac{1}{n}\sum_{t=1}^n E[r_P(A_t)-r_P(a_P^*)] \leq \frac{E[R_n]}{n}.

This is an expected-risk statement about a randomly selected online action. The first worked example shows why the same conclusion cannot simply be assigned to $A_n$: a bound on the sum can leave an individual term large.

What the Conversion Does Not Say

The theorem depends on both the sampling protocol and the form of the conclusion. If actions use future outcomes, the conditional risk identity need not hold. If outcomes are dependent or their distribution changes over time, a single fixed $P$ may not describe the conditional law of each new outcome. And if regret is controlled only on one sequence, rather than in expectation under the sampling law or uniformly over sequences, that realized comparison alone need not bound population risk.

Even under the theorem's assumptions, the conclusion is an average over the online actions. It does not say that every action has small excess risk, that the final iterate does, or that an arbitrary data-dependent output generalizes. Nor does a small stochastic excess risk guarantee low regret on sequences outside the assumed distribution. These are different targets, not competing descriptions of the same quantity.

Key takeaway: Expected regret can imply small average expected excess risk when actions are predictable and outcomes are iid from a fixed law. It does not, by itself, guarantee a good final iterate or worst-case performance under a different sequence.

Common Mistakes

Calling the hindsight comparator a population minimizer. The hindsight decision minimizes the observed cumulative loss; the population minimizer minimizes expected loss under $P$. They need not coincide on a finite sample.
Turning an average guarantee into a final-iterate guarantee. A small sum of excess risks can include one large term, as the first example demonstrates.
Using stochastic performance as a worst-case guarantee. Risk is evaluated under a specified distribution. It does not cover all sequences unless an additional adversarial guarantee is established.
Applying the conversion when actions see the current outcome. The proof uses the fact that $A_t$ is chosen before the independent $Z_t$; without that condition, the conditional expectation step can fail.

Check Your Understanding

For each question, identify the benchmark and the conditions that matter.

In one sentence, distinguish the comparator in cumulative regret from the comparator in population excess risk.
Why does the expected-regret theorem require that $A_t$ be chosen before $Z_t$ is observed?
If $E[R_n]\leq 12$, what upper bound does the theorem give for the average expected excess risk of the online actions?
Can this average-risk bound by itself establish that $A_n$ has small excess risk? Explain.
Why does zero excess risk under a degenerate distribution not imply small regret on every adversarial sequence?