Adversarial Environments in Online Learning

A small hypothesis class is not automatically easy for an online learner.

Programming

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

In one round, what does the learner choose first, what does the adversary observe, and how does the adversary choose the outcome afterward?

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.

What do you think happens?

If a deterministic learner predicts 1 and the adversary observes that prediction before choosing the label, what label can make the learner err?

0
1
The adversary cannot choose a label

Reveal answer

Answer:

Choosing the opposite label makes the learner's prediction incorrect 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.

Across repeated rounds, how can the adversary make the learner lose on every round while one of the two constant predictors performs well?

Worked example

The lower bound over T rounds

A deterministic learner makes a mistake on every round, while the better of the two constant hypotheses makes at most T/2 mistakes. What lower bound follows for the learner's regret?

1
Learner loss
One mistake on each of T rounds gives T mistakes.
2
Best hypothesis loss
The better constant predictor has at most T/2 mistakes.
3
Comparison
The learner's loss exceeds the best hypothesis's loss by at least T minus T/2.

Result

The regret is at least T/2, which is not sublinear in T.

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.

Can the adversary see the learner's random seed, its probability distribution, or only the realized prediction before selecting the outcome?

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.

How can a single realized prediction differ from the average loss computed over all possible randomized predictions?

Worked example

A weighted loss calculation

A learner predicts 0 with probability 0.7 and predicts 1 with probability 0.3. Suppose the loss is 1 when the prediction is wrong and 0 when it is correct, and the selected label is 1. What is the expected loss?

1
List the possible predictions
Prediction 0 has probability 0.7 and prediction 1 has probability 0.3.
2
Assign the losses
Against label 1, prediction 0 is wrong and has loss 1; prediction 1 is correct and has loss 0.
3
Weight and combine
Multiply each loss by its probability and add the results: 0.7 times 1 plus 0.3 times 0.

Result

The expected loss is 0.7.

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

Common mistake
Assuming that two hypotheses make the problem easy
What it looks like
There are only the constant predictors that always output 0 and always output 1.
Why it fails
A reactive adversary can still force a deterministic learner to make a mistake on every round.
Do this instead
Analyze how the labels are selected in response to the learner's current prediction, not only how many hypotheses exist.
Common mistake
Comparing the learner with a perfect predictor
What it looks like
The learner makes T mistakes, so the comparison is made with a predictor that makes zero mistakes.
Why it fails
Regret is measured against the best hypothesis in the given class after the sequence is revealed.
Do this instead
Compare the learner with the better of the two constant hypotheses; that hypothesis has at most T/2 mistakes in the adversarial construction.
Common mistake
Treating randomization as automatically protective
What it looks like
The learner randomizes, so the adversary can no longer force mistakes.
Why it fails
Randomization changes the game only when the adversary cannot observe the learner's current random choice before selecting the label.
Do this instead
Check whether the current realized choice is hidden at the moment the adversary selects the label.
Common mistake
Calling expected loss the realized prediction
What it looks like
The learner predicts 0.7.
Why it fails
The learner realizes one possible prediction, while 0.7 can be an average loss from several possible predictions.
Do this instead
Keep the selected prediction separate from the probability-weighted average of possible losses.

Check Your Understanding

MEDIUM

A learner chooses between the two constant hypotheses, always 0 and always 1. An adversary observes the learner's current deterministic prediction before selecting the label. Explain how the adversary can cause a mistake on every round, and explain why the best constant hypothesis can still have at most T/2 mistakes over T rounds.

Hints

Choose the label opposite to the learner's current prediction.
Count the learner's mistakes over all T rounds.
Compare the two constant hypotheses after the complete label sequence is known.

Your attempt (not saved)

EASY

A randomized learner predicts 0 with probability 0.4 and 1 with probability 0.6. Against a selected label of 0, prediction 0 has loss 0 and prediction 1 has loss 1. Calculate the expected loss and state what a single realized prediction could be.