Stochastic Online Protocols and Expected Regret

Why Two Regret Comparisons Arise

In an online problem, a learner chooses a decision before seeing the next observation. After the data arrive, one can compare the learner with the fixed decision that would have performed best on the realized sequence. In a stochastic problem, there is also a natural population benchmark: the fixed decision with the smallest expected loss under the data-generating distribution. These comparisons answer different questions. The first depends on the particular sample; the second depends on the distribution.

Under iid sampling, expected regret against the hindsight decision controls cumulative expected excess loss against the population-optimal decision. The key point is that minimizing empirical loss makes the hindsight benchmark optimistic on average. The comparison is an expectation inequality, not a claim that the two regrets are ordered on every realized sample.

An Iid Stochastic Online Protocol

Definition: Let $\mathcal A$ be a nonempty finite set of decisions, let $Z_1,\ldots,Z_n$ be iid observations with distribution $P$, and let $\ell(a,z)$ be a measurable loss. At round $t$, the learner chooses $A_t\in\mathcal A$ using only past observations and randomization independent of $Z_1,\ldots,Z_n$; it then incurs loss $\ell(A_t,Z_t)$. The population risk of a fixed decision $a$ is $L(a)=E[\ell(a,Z)]$, where $Z\sim P$. Assume $E[\max_{a\in\mathcal A}|\ell(a,Z)|]<\infty$.

The timing matters: $A_t$ is chosen before $Z_t$ is observed. The learner may use past observations, so its decisions can depend on the history, but the current observation is independent of that history. The learner's randomization may also be shared across rounds, provided it is independent of the observations.

Write the realized cumulative loss of a fixed decision as $S_n(a)=\sum_{t=1}^n\ell(a,Z_t)$. The hindsight comparator is the decision minimizing this sum on the observed sample. Since $\mathcal A$ is finite, the minimum exists and is measurable. Define the two quantities to compare:

R_n^{\mathrm{hin}}=\sum_{t=1}^n\ell(A_t,Z_t)-\min_{a\in\mathcal A}S_n(a), \qquad R_n^{\mathrm{pop}}=\sum_{t=1}^n\ell(A_t,Z_t)-nL_*, \qquad L_*=\min_{a\in\mathcal A}L(a).

The first is external regret against the best fixed decision in hindsight. The second is cumulative loss minus the risk of using the best fixed population decision on every round. It is a random quantity because the learner's incurred losses are random, even though $L_*$ is not. It need not be nonnegative on every sample.

Worked Example: One Round With Two Decisions

Let $Z$ be Bernoulli with $P(Z=1)=1/4$, and let $\mathcal A=\{0,1\}$. Define $\ell(0,z)=z$ and $\ell(1,z)=1-z$. The learner always chooses decision 0.

The two risks are $L(0)=1/4$ and $L(1)=3/4$, so $L_*=1/4$. The learner's population excess loss is zero in expectation: its expected incurred loss is $1/4$, exactly the optimal risk.

If $Z=0$, both the learner and the hindsight decision incur loss 0, so $R_1^{\mathrm{hin}}=0$. If $Z=1$, the learner incurs 1 and hindsight chooses decision 1, which incurs 0, so $R_1^{\mathrm{hin}}=1$. Therefore $E[R_1^{\mathrm{hin}}]=(1/4)(1)+(3/4)(0)=1/4$, greater than the learner's expected population excess loss of 0.

The empirical minimum is 0 for either possible observation. Thus $E[\min_a S_1(a)]-L_*=0-1/4=-1/4$, which accounts exactly for the difference between the two expected comparisons.

Two Identities Behind the Comparison

First, conditional on the past and the learner's randomization, the current observation still has distribution $P$. Let $\mathcal F_{t-1}$ contain $Z_1,\ldots,Z_{t-1}$ and all learner randomization. Then $A_t$ is $\mathcal F_{t-1}$-measurable and $Z_t$ is independent of $\mathcal F_{t-1}$. Consequently,

E[\ell(A_t,Z_t)\mid\mathcal F_{t-1}] = \sum_{a\in\mathcal A}\mathbf 1\{A_t=a\}E[\ell(a,Z_t)\mid\mathcal F_{t-1}] = L(A_t).

All conditional expectations exist by the integrability assumption. Taking expectations and summing gives $E[\sum_t\ell(A_t,Z_t)]=\sum_t E[L(A_t)]$. In particular, the expected population regret is the sum of expected population excess risks:

E[R_n^{\mathrm{pop}}] = \sum_{t=1}^n E[L(A_t)-L_*]\geq 0.

Second, subtracting the definitions gives an exact sample-by-sample identity. This algebra does not require independence:

R_n^{\mathrm{pop}} = R_n^{\mathrm{hin}}+\min_{a\in\mathcal A}S_n(a)-nL_*.

The final two terms are the hindsight comparator's realized loss minus the population-optimal cumulative risk. Their expectation is nonpositive, because the hindsight comparator can only do at least as well on the sample as any fixed population-optimal decision.

Theorem: Under the iid stochastic online protocol above, $$ E[R_n^{\mathrm{pop}}]\leq E[R_n^{\mathrm{hin}}]. $$ More precisely, $$ E[R_n^{\mathrm{hin}}]-E[R_n^{\mathrm{pop}}] = nL_*-E\!\left[\min_{a\in\mathcal A}S_n(a)\right]\geq 0. $$

Proof. Since $\mathcal A$ is finite, choose a population-risk minimizer $a_*\in\mathcal A$ with $L(a_*)=L_*$. For every sample, the minimum over decisions is no larger than the loss of $a_*$:

\min_{a\in\mathcal A}S_n(a)\leq S_n(a_*).

Taking expectations and using iid sampling and integrability,

E\!\left[\min_{a\in\mathcal A}S_n(a)\right] \leq E[S_n(a_*)] =\sum_{t=1}^n E[\ell(a_*,Z_t)] =nL_*.

Now take expectations in the exact identity above and rearrange. The displayed inequality yields the claimed ordering and the stated difference formula. $\square$

The learner's predictability and the iid condition are what identify its expected cumulative loss with cumulative population risks. The comparison of the two benchmarks then follows from the fixed population minimizer being one of the candidates in the hindsight minimum.

Worked Example: Two Rounds and the Hindsight Gap

Use the Bernoulli model and losses from the previous example, now with $n=2$, and let the learner choose 0 on both rounds. Let $K=Z_1+Z_2$, the number of observations equal to 1. The learner's cumulative loss is $K$. Decision 0 has loss $K$, while decision 1 has loss $2-K$. Hence the hindsight loss is $\min(K,2-K)$.

The distribution of $K$ is $P(K=0)=9/16$, $P(K=1)=6/16$, and $P(K=2)=1/16$. Thus

E[\min(K,2-K)] = (9/16)0+(6/16)1+(1/16)0 = 3/8.

The population-optimal risk is $L_*=1/4$, so $nL_*=1/2$. The expected hindsight regret is

E[R_2^{\mathrm{hin}}] = E[K-\min(K,2-K)] = E[K]-3/8 = 1/2-3/8 = 1/8.

The learner's expected cumulative loss is $E[K]=1/2$, so its expected population regret is $1/2-1/2=0$. The difference is $1/8=1/2-3/8$, exactly $nL_*-E[\min_a S_2(a)]$.

Worked Example: A Randomized Learner With Positive Excess Risk

Keep the same two-round problem, but now let the learner independently choose decision 1 on each round with probability $q=2/5$, and decision 0 otherwise. Because the decisions are independent of the current observations, the expected loss per round is

$$ (1-q)L(0)+qL(1) = (3/5)(1/4)+(2/5)(3/4) = 3/20+6/20 = 9/20. $$

The best population risk is $1/4=5/20$, so the expected population excess loss per round is $4/20=1/5$. Across two rounds, $E[R_2^{\mathrm{pop}}]=2/5$. The learner's expected cumulative loss is $2(9/20)=9/10$.

The hindsight loss depends only on the observed data, not on the learner's randomization. From the preceding calculation its expectation is $3/8$. Therefore

E[R_2^{\mathrm{hin}}] = 9/10-3/8 = 36/40-15/40 = 21/40.

Indeed, $21/40\geq 2/5=16/40$, with difference $5/40=1/8$. The benchmark gap is unchanged by the learner's randomization because it depends only on the data distribution and the set of fixed decisions.

What the Inequality Does—and Does Not—Say

The theorem is useful because a guarantee on expected regret against the best fixed decision in hindsight immediately gives a guarantee on the learner's expected cumulative excess risk. If, for example, an analysis shows $E[R_n^{\mathrm{hin}}]\leq B_n$, then the theorem gives

\sum_{t=1}^n E[L(A_t)-L_*] = E[R_n^{\mathrm{pop}}] \leq B_n.

This statement concerns the decisions made during the online protocol. It does not say that each round has excess risk at most $B_n/n$, nor does it identify a single decision with that risk. Those are different claims and require further argument.

The inequality is generally strict because the hindsight decision is selected after seeing the sample. Its empirical minimum is no larger than the empirical loss of the population-optimal fixed decision, and taking a minimum over multiple candidates can lower the value further. The difference $nL_*-E[\min_a S_n(a)]$ measures this expected optimism of the hindsight benchmark.

Common Pitfall

A tempting but incorrect argument is: “Each fixed decision's empirical cumulative loss is unbiased for $nL(a)$, so the minimum empirical loss is unbiased for $nL_*$.” Unbiasedness does not pass through minimization. The minimum is chosen after observing the data, so it is systematically no larger in expectation than the loss of a fixed population minimizer:

E[\min_a S_n(a)] \leq E[S_n(a_*)] =nL_*.

A second mistake is to read the theorem as a pathwise ordering. The proof compares expectations; it does not show that $R_n^{\mathrm{pop}}\leq R_n^{\mathrm{hin}}$ for every sample. The correction is to retain the exact identity and then take expectations under the stated iid and integrability assumptions.

Key takeaway: In an iid online protocol with decisions chosen before each observation, expected cumulative population excess risk is no larger than expected regret against the best fixed decision in hindsight. The difference is exactly the expected gap between population-optimal cumulative risk and the hindsight empirical minimum.

Check Your Understanding

Use the definitions and comparison above to answer the following.

Why must the learner choose $A_t$ before observing $Z_t$ for the conditional-risk identity to apply?
State the exact identity relating $R_n^{\mathrm{pop}}$ and $R_n^{\mathrm{hin}}$.
Why is $E[\min_a S_n(a)]\leq nL_*$ even though each fixed decision has an unbiased empirical cumulative loss?
For a learner with $E[R_n^{\mathrm{hin}}]\leq B_n$, what bound follows for the sum of its expected population excess risks?
Does the theorem assert that population regret is no greater than hindsight regret on every sample? Explain.