Adversarial Environments in Online Learning

A Tiny Class with a Large Problem

A small hypothesis class is not automatically easy for an online learner. Consider only two constant hypotheses: one always predicts 0, and the other always predicts 1. Despite this extremely limited choice, an adversary can force a deterministic learner to make a mistake on every round by reacting to the learner's current prediction.

One Round Against a Reactive Adversary

Suppose the learner predicts 0. The adversary selects label 1. If the learner predicts 1 instead, the adversary selects label 0. In either case, the label is the opposite of the current prediction, so the learner makes a mistake on that round.

Why Two Hypotheses Still Give Linear Regret

Repeat the one-round interaction for T rounds. A reactive adversary can make a deterministic learner lose on every round, so the learner accumulates T mistakes. The best constant hypothesis is evaluated only after the full sequence is known. Among the two constant predictors, one always predicts 0 and the other always predicts 1; one of them has mistakes at most T/2 on the resulting sequence. Therefore the learner's excess loss over the best hypothesis is at least T/2.

What Randomization Changes

Randomization changes the game only when the adversary cannot observe the learner's current random choice before selecting the label. If the adversary sees the current realized prediction first, it can again select the opposite label for that round. Thus, the important issue is the order of information: the learner's current random choice must be hidden from the adversary until the label has been selected if randomization is to change this interaction.

Realized Prediction and Expected Loss

A randomized learner has two related but different descriptions. Its realized prediction is the single label selected on one run of the random process. Its expected loss is an average over the possible predictions, weighted by how likely each prediction is. The realized prediction is one actual outcome; the expected loss summarizes the average loss across the learner's randomization.

In the example, one run of the learner still produces either prediction 0 or prediction 1. The value 0.7 is not a third prediction and does not describe what must happen on every run. It is the average loss obtained by combining the possible losses with their probabilities.

Common Reasoning Errors

• Assuming that two hypotheses make the problem easy

  A reactive adversary can still force a deterministic learner to make a mistake on every round.

  Fix: Analyze how the labels are selected in response to the learner's current prediction, not only how many hypotheses exist.

• Comparing the learner with a perfect predictor

  Regret is measured against the best hypothesis in the given class after the sequence is revealed.

  Fix: Compare the learner with the better of the two constant hypotheses; that hypothesis has at most T/2 mistakes in the adversarial construction.

• Treating randomization as automatically protective

  Randomization changes the game only when the adversary cannot observe the learner's current random choice before selecting the label.

  Fix: Check whether the current realized choice is hidden at the moment the adversary selects the label.

• Calling expected loss the realized prediction

  The learner realizes one possible prediction, while 0.7 can be an average loss from several possible predictions.

  Fix: Keep the selected prediction separate from the probability-weighted average of possible losses.

Check Your Understanding

Key Takeaways

1. Even two constant hypotheses can support a linear regret lower bound when an adversary reacts to the learner's current prediction.
2. A deterministic learner can be forced to make a mistake on every round by choosing the opposite label.
3. The best hypothesis is selected from the class after the sequence is revealed, and one of the two constant hypotheses has at most T/2 mistakes.
4. Randomization changes the interaction only when the adversary cannot observe the learner's current random choice before choosing the label.
5. Expected loss is a probability-weighted average of possible losses, while the realized prediction is one actual prediction from the random process.