Adversarial Regret Lower Bounds

Why a Lower Bound Needs Care

An adversarial regret lower bound asks what a learner cannot avoid, even when it sees each loss vector after acting and can use the full history to choose its next prediction. The key comparison is with the best single expert in hindsight. A randomized construction makes this comparison precise: the learner must choose before seeing a fresh random loss, while the comparator gets to select the better expert after the entire sequence is known.

There is an important distinction between average regret over randomly generated sequences and regret on each particular sequence. A learner’s loss can vary greatly from one sequence to another. The argument below averages the learner’s loss and the comparator’s loss separately; it does not assign their average values to every sequence.

Definition: On round $t$, a learner chooses a distribution $p_t=(p_{t,1},p_{t,2})$ over two experts, where $p_{t,1},p_{t,2}\geq 0$ and $p_{t,1}+p_{t,2}=1$. After the loss vector $\ell_t=(\ell_{t,1},\ell_{t,2})$ is revealed, the learner’s prediction loss is $p_t\cdot\ell_t$. For a fixed horizon $T$, its regret against the best fixed expert is $$ R_T=\sum_{t=1}^T p_t\cdot\ell_t-\min_{i\in\{1,2\}}\sum_{t=1}^T\ell_{t,i}. $$

We study losses in $[0,1]$, and the learner chooses $p_t$ using only information available before round $t$’s loss is revealed. The learner may be randomized; statements about its regret then refer to expectation over its internal randomness as well as any randomized losses. For a randomized prediction that selects one expert according to $p_t$, $p_t\cdot\ell_t$ is the conditional expected loss of that prediction.

A Randomized Adversary

Let $\varepsilon_1,\ldots,\varepsilon_T$ be independent random signs, each taking $+1$ and $-1$ with probability $1/2$. On round $t$, set $$ \ell_t=\left(\frac{1+\varepsilon_t}{2},\frac{1-\varepsilon_t}{2}\right). $$ Thus, when $\varepsilon_t=+1$, the losses are $(1,0)$, and when $\varepsilon_t=-1$, they are $(0,1)$. This is an oblivious randomized construction: the whole sequence can be drawn independently of the learner, before play begins.

The learner cannot use the current sign when choosing $p_t$. Conditional on the information available before that sign is drawn, either expert is equally likely to have loss one. Consequently, the learner’s conditional expected loss on the round is $1/2$, whatever distribution it chooses. This statement is conditional on the past and averages over the fresh sign; it does not say the learner loses $1/2$ on every individual sequence.

Worked Example: Two Rounds and Four Sign Sequences

Take $T=2$, and suppose the learner always chooses expert 1. Write $+$ for a round with losses $(1,0)$, and $-$ for a round with losses $(0,1)$. Each of the four sign sequences has probability $1/4$.

For $++$, the learner’s total loss is $2$, while the best expert’s total loss is $0$; regret is $2$. For $+-$, the learner loses $1$, and each expert has total loss $1$; regret is $0$. For $-+$, the learner again loses $1$, and each expert has total loss $1$; regret is $0$. For $--$, the learner loses $0$, and the best expert’s loss is $0$; regret is $0$.

The average learner loss across the four sequences is $(2+1+1+0)/4=1$. The average best-expert loss is $(0+1+1+0)/4=1/2$. Therefore the average regret is $1-1/2=1/2$. These are averages across sequences: the learner’s total loss is not $1$ on each sequence, and its regret is not $1/2$ on each sequence.

Deriving the Lower Bound

Let $S_T=\sum_{t=1}^T\varepsilon_t$. The two experts’ cumulative losses are $(T+S_T)/2$ and $(T-S_T)/2$. Hence the best fixed expert’s loss is $(T-|S_T|)/2$. Meanwhile, the learner’s expected cumulative loss, averaging over the random signs and its own randomization if any, is $T/2$: each round contributes conditional expected loss $1/2$.

Subtracting these expected losses gives the exact identity $$ E[R_T]=\frac{1}{2}E[|S_T|]. $$ The expectation is over the randomized signs and, when relevant, the learner’s internal randomness. The identity follows by linearity of expectation and the formula for the best expert’s loss; it does not assert that regret is the same on every sequence.

Theorem: For every learner obeying the round-by-round protocol above, and every positive integer $T$, there is a fixed loss sequence in $\{(1,0),(0,1)\}^T$ for which the learner’s expected regret is at least $\sqrt{T/12}$. Here the expectation in the conclusion is only over the learner’s internal randomization.

Proof. First calculate the moments of $S_T$. Independence, symmetry, and $\varepsilon_t^2=1$ give $E[S_T^2]=T$: when the square is expanded, each squared term has expectation one and every cross term has expectation zero. For the fourth moment, an expanded term has nonzero expectation only when each sign index occurs an even number of times. There are $T$ terms with one index repeated four times, and $6\binom{T}{2}$ terms with two distinct indices each repeated twice. Thus

E[S_T^4]=T+6\binom{T}{2}=3T^2-2T\leq 3T^2.

Hölder’s inequality, applied with exponents $3/2$ and $3$, yields

E[|S_T|^2] =E\!\left[|S_T|^{2/3}|S_T|^{4/3}\right] \leq (E[|S_T|])^{2/3}(E[|S_T|^4])^{1/3}.

Raising both sides to the power $3/2$ and rearranging gives

E[|S_T|]\geq \frac{(E[S_T^2])^{3/2}}{(E[S_T^4])^{1/2}} \geq \frac{T^{3/2}}{\sqrt{3T^2}} =\sqrt{\frac{T}{3}}.

The exact expected-regret identity therefore implies $E[R_T]\geq \sqrt{T/12}$ under the randomized sign construction. There are finitely many possible sign sequences. If every fixed sequence had learner-expected regret less than $\sqrt{T/12}$, their average would also be less than that value, contradicting the bound. At least one fixed sequence must therefore have learner-expected regret at least $\sqrt{T/12}$. This proves the theorem. $\square$

Worked Example: Four Rounds Under the Randomized Construction

For $T=4$, the absolute sum $|S_4|$ is $4$ with probability $2/16$, $2$ with probability $8/16$, and $0$ with probability $6/16$. Therefore

E[|S_4|]=4\left(\frac{2}{16}\right)+2\left(\frac{8}{16}\right)=\frac{3}{2}.

The learner’s average total loss over these sequences is $T/2=2$. The average best-expert loss is $(T-E|S_4|)/2=(4-3/2)/2=5/4$. Their difference is $2-5/4=3/4$. Thus every learner has average regret $3/4$ under this distribution, and at least one of the 16 fixed sequences has learner-expected regret at least $3/4$. The theorem’s general bound at $T=4$ is $\sqrt{4/12}=1/\sqrt{3}$, which is smaller than $3/4$, as it should be.

What the Bound Does—and Does Not—Say

The theorem gives a worst-case lower bound of square-root order: at each horizon $T$, some fixed sequence forces expected regret at least a constant times $\sqrt{T}$. In particular, no learner can guarantee a regret bound that is $o(\sqrt{T})$ uniformly over all horizons and all loss sequences in this setting. The randomized construction is useful because it establishes this limitation even for an adversary that does not adapt its losses to the learner’s actions.

It would be incorrect, however, to conclude that no learner can guarantee sublinear regret in $T$. Sublinear means $R_T/T\to 0$, and a square-root bound is sublinear: $\sqrt{T}/T=1/\sqrt{T}\to 0$. The lower bound rules out guarantees substantially smaller than square-root order; it does not rule out sublinear regret. In fact, for two experts with losses in $[0,1]$, regret guarantees of square-root order are attainable. The lower bound and such an upper bound are compatible.

This distinction matters when interpreting statements about “no uniform guarantee.” A guarantee $R_T\leq C\sqrt{T}$ for every horizon and every permitted loss sequence is uniform and sublinear. What the lower bound excludes is a uniform guarantee $R_T\leq r(T)$ with $r(T)/\sqrt{T}\to 0$. It also does not say that every sequence causes large regret: many sequences, including ones on which both experts have the same cumulative loss, can have zero regret.

Worked Example: Comparing Candidate Regret Rates

Consider three proposed uniform guarantees: $R_T\leq 2$, $R_T\leq 10\sqrt{T}$, and $R_T\leq T^{1/3}$, each for every horizon and every loss sequence in the construction. The constant bound $2$ is impossible for all horizons because $2$ eventually falls below $\sqrt{T/12}$. The square-root bound $10\sqrt{T}$ is not contradicted by this lower bound: its rate is at least as large, up to constants. The $T^{1/3}$ bound is impossible for all sufficiently large $T$, since

\frac{T^{1/3}}{\sqrt{T/12}}=\sqrt{12}\,T^{-1/6}\longrightarrow 0.

Thus $T^{1/3}=o(\sqrt{T})$, while $10\sqrt{T}$ is still sublinear relative to $T$. A lower bound of square-root order excludes the first type of rate, not every rate that is sublinear in the horizon.

Common Mistakes

Turning an average into a sequence-by-sequence claim. Fresh random signs make the learner’s expected loss $1/2$ per round after averaging over the current sign, conditional on the past. They do not make the learner’s total loss $T/2$ on each realized sequence. Average the learner’s loss over sequences, then separately average the best-expert loss.
Subtracting the wrong comparator quantity. The best expert’s cumulative loss is determined by the realized sign sum: $(T-|S_T|)/2$. It is not generally the sum of the per-round minimum losses, which is zero here.
Calling square-root regret non-sublinear. The ratio $\sqrt{T}/T$ tends to zero. This lower bound sets a scale for the smallest possible worst-case regret; it does not prohibit sublinear regret.
Confusing an average lower bound with a single fixed sequence. The conversion is valid because the random construction has finite support: if every fixed sequence had smaller learner-expected regret, their average would be smaller too.

Key takeaway: Independent random signs force expected regret $E|S_T|/2$, which is at least $\sqrt{T/12}$. Therefore two-expert regret cannot be uniformly $o(\sqrt{T})$, but square-root regret remains sublinear in the horizon.

Check Your Understanding

Try to answer each question by distinguishing realized-sequence quantities from averages over the randomized construction.

For a realized sign sequence, why is the best expert’s cumulative loss $(T-|S_T|)/2$?
What independence property makes the learner’s conditional expected loss on round $t$ equal to $1/2$, even when $p_t$ depends on the past?
Why does a lower bound on average regret over the finite set of sign sequences imply that at least one fixed sequence has at least that much learner-expected regret?
Which rate does the theorem rule out: a uniform $O(\sqrt{T})$ guarantee or a uniform $o(\sqrt{T})$ guarantee? Explain.
Does the theorem imply that regret cannot be sublinear in $T$? Give the relevant limiting ratio.