Regret in Online Learning
A hypothesis class with only two constant predictors is still vulnerable to an adversary that reacts to the learner's current prediction.
A Tiny Class with a Large Problem
Online learning can remain difficult even when the learner chooses between only two hypotheses. Consider two constant predictors: one always predicts 0, and the other always predicts 1. A deterministic learner may alternate between these predictions or follow any other fixed strategy, but an adversary that reacts to the learner's current prediction can choose the opposite outcome on every round. The learner then makes a mistake every time.
The size of the hypothesis class alone does not guarantee easy online classification. What matters is also how the adversary chooses outcomes and what information it can observe.
Round-by-Round Adversarial Response
Suppose the learner predicts 0 on a round. The adversary chooses outcome 1. If the learner predicts 1 instead, the adversary chooses outcome 0. The adversary is not trying to make one fixed hypothesis wrong on every round. It is reacting to the learner's current prediction, which is enough to make the learner lose on every round.
What do you think happens?
A deterministic learner predicts 0 on the next round. If the adversary can observe that current prediction before choosing the outcome, what outcome creates a mistake?
Reveal answer
Answer: 1
Choosing 1 makes the outcome different from the learner's prediction. The same reasoning applies in reverse when the learner predicts 1.
Comparing Against the Best Constant
Regret is not measured against a perfect predictor invented after the fact. The comparison is with the best hypothesis in the given class after the sequence has been revealed. Here the class contains the constant predictor that always predicts 0 and the constant predictor that always predicts 1.
Why the Regret Lower Bound Is T/2
Across T rounds, an adaptive adversary makes the learner wrong on every round. What can be said about the best of the two constant predictors?
Learner loss: Because the adversary chooses the opposite outcome to the learner's current prediction, the learner makes a mistake on every round. Its cumulative loss is therefore T.
Constant predictors: Every outcome sequence contains T outcomes divided between 0 and 1. One of the two constant predictors makes no more than T/2 mistakes, because at least one label occurs no more often than the other.
Comparison: The learner's loss is T, while the best constant predictor's loss is at most T/2. The difference is at least T/2.
The regret can be at least T/2, which is not sublinear in T.
What Randomization Changes
Randomization changes the situation only under a specific information condition. The adversary must be unable to observe the learner's current random choice before selecting the label. If the adversary can see the realized current prediction first, it can still choose the opposite outcome and force a mistake on that round.
| Adversary information | Effect of randomization |
|---|---|
| The adversary observes the learner's current realized prediction before choosing the label. | The adversary can choose the opposite outcome on that round. |
| The adversary cannot observe the learner's current random choice before choosing the label. | The current choice is hidden when the label is selected, so randomization changes the game. |
Expected Loss Before the Outcome
A randomized learner has a probability of making each possible prediction. Expected loss combines the loss associated with each possible prediction, weighted by the probability of that prediction. It describes an average over the learner's possible random choices; it is not necessarily the loss of the one prediction that is eventually realized.
A Fifty-Fifty Randomized Prediction
The learner predicts 0 with probability 1/2 and 1 with probability 1/2. Suppose the losses for these two possible predictions are 1 and 0, respectively. What is the expected loss?
Weight the first loss: The prediction 0 has probability 1/2 and loss 1, so its contribution to expected loss is 1/2 multiplied by 1.
Weight the second loss: The prediction 1 has probability 1/2 and loss 0, so its contribution is 1/2 multiplied by 0.
Add the contributions: The expected loss is 1/2 multiplied by 1 plus 1/2 multiplied by 0.
The expected loss is 1/2.
Realized Prediction and Average Loss
On one actual round, the learner makes one realized prediction. That prediction has one realized loss once the label is known. Expected loss is different: it averages the losses of the possible predictions according to their probabilities. For example, an expected loss of 1/2 does not mean that the learner literally predicted half of 0 and half of 1 on that round. It means that the probability-weighted average loss is 1/2.
Keep two questions separate: What prediction was actually selected? What loss would be expected across the learner's possible random choices?
Mistakes About Randomized Regret
Assuming two hypotheses automatically imply sublinear regret.
An adversary that reacts to the learner's current prediction can make a deterministic learner wrong on every round.
Fix:
Analyze both the hypothesis class and the adversary's information and timing.Assuming randomization always prevents the adversary from forcing mistakes.
The adversary can choose the opposite outcome after seeing the current prediction.
Fix:
Check whether the current random choice is hidden when the adversary selects the label.Treating expected loss as the learner's literal prediction or literal single-round loss.
The learner still makes one realized prediction on the actual round. Expected loss is a probability-weighted average over possible predictions.
Fix:
Report the realized prediction separately from the expected loss.Comparing the learner with a perfect predictor instead of the best hypothesis in the class.
Regret in this setting is measured against the best hypothesis in the specified class after the sequence is revealed.
Fix:
Compare with the better of the always-0 and always-1 hypotheses.
Check Your Understanding
A learner predicts 0 with probability 0.7 and 1 with probability 0.3. If the loss of predicting 0 is 1 and the loss of predicting 1 is 0, calculate the expected loss. Then explain whether the expected loss tells you which prediction was actually realized.
Hints
- Multiply each possible loss by the probability of its corresponding prediction.
- Add the two weighted contributions.
- Expected loss is an average, while the realized prediction is one actual choice.
Imagine that a deterministic learner is choosing between the two constant hypotheses. Explain how an adversary that observes the learner's current prediction can force a mistake on every round. Then state why the best constant hypothesis can still make at most T/2 mistakes.
Hints
- Choose the outcome opposite to the learner's current prediction.
- Among the two labels, at least one appears no more often than the other in the revealed sequence.
Main Takeaways
- Even a hypothesis class with only two constant predictors can suffer linear regret when an adversary reacts to the learner's current prediction.
- The learner can be forced to lose on every round, while the better constant predictor makes at most T/2 mistakes.
- This produces a regret lower bound of T/2, which is not sublinear in T.
- Randomization changes the game only when the adversary cannot observe the learner's current random choice before selecting the label.
- Expected loss is a probability-weighted average of possible losses, whereas realized prediction and realized loss refer to one actual round.
Key Takeaways
- A small hypothesis class does not by itself ensure low regret.
- An adaptive adversary can choose the opposite of a deterministic learner's current prediction and cause a mistake every round.
- The best of the two constant predictors makes at most T/2 mistakes, so the regret lower bound can be T/2.
- Randomization is useful only when the adversary cannot see the current random choice before selecting the label.
- Expected loss averages possible losses; it is distinct from the learner's single realized prediction and loss.