Online Learning Game
Online learning proceeds round by round, with the environment choosing instances and revealing labels after the learner predicts.
Learning Under Pressure
Imagine making a prediction before anyone tells you whether it is correct. After you commit to the prediction, the correct label is revealed, and you use that feedback to make later predictions. This timing pattern is the central idea of online learning. Instead of completing training first and predicting later, the learner repeatedly predicts, receives feedback, and continues.
Online learning is organized as consecutive rounds. Each current example must be predicted before its true label is available.
One Round at a Time
On round t, the environment first chooses an instance x_t. The learner then predicts a binary label p_t, either 0 or 1. The environment reveals the true binary label y_t. Finally, the learner can use that revealed label when making predictions in later rounds. These are four distinct events: instance selection, prediction, label revelation, and learning from the revealed feedback.
From Test to Training
An example has two roles at different moments in the same round. Before its label is known, it is a test example: the learner must use the instance to make a prediction. After the true label is revealed, that same example becomes useful as a training example because its labeled information can support later predictions.
Following One Example Through a Round
Track the role of one instance during an online learning round.
Before prediction: The environment presents an instance, but the learner has not yet received its true label. The learner must treat it as a test example and predict a binary label.
After prediction: The environment reveals the true binary label. The prediction can now be compared with the revealed label.
For later rounds: The labeled example can support the learner's future predictions, so it now also serves a training role.
Online learning interleaves testing and training: prediction comes first, and learning from the example follows its label revelation.
Shattered Label Trees
To study all possible online histories, represent the rounds as a branching tree. Each level represents another online round. A node contains the instance chosen for that round, and its outgoing branches represent the possible labels that the environment might reveal next. A path from the root records one possible sequence of revealed labels.
A tree is shattered by a hypothesis class H when every label path through the tree can be made consistent with some hypothesis h in H. For each possible path, there must be a hypothesis whose predictions on the instances along that path agree with every label on the path.
When testing whether a tree is shattered, work from complete paths rather than individual nodes. Identify the depth, list every possible label history, and then check whether each history has a consistent hypothesis in H.
A Two-Hypothesis Test
Consider the hypothesis class H containing two hypotheses: one always predicts 0, and the other always predicts 1. We can test the greatest depth of a shattered tree by checking all label paths.
Depth One Versus Depth Two
For the class containing an always-0 hypothesis and an always-1 hypothesis, determine whether a depth-one tree and a depth-two tree can be shattered.
Depth one: A depth-one tree has two possible label paths: 0 and 1. The always-0 hypothesis is consistent with path 0, and the always-1 hypothesis is consistent with path 1. Therefore, the depth-one tree is shattered.
Depth two: A depth-two tree has four possible label histories: 00, 01, 10, and 11. The always-0 hypothesis is consistent with 00, and the always-1 hypothesis is consistent with 11. Neither hypothesis is consistent with 01 or 10.
Conclusion: Because every path must be realizable for shattering, the depth-two tree is not shattered by this class.
The class shatters depth one but not depth two. Its greatest shattered-tree depth is therefore one.
Littlestone's Dimension
Littlestone's Dimension is the greatest depth of a tree shattered by a hypothesis class.
The depth counts how many online rounds are represented along a path. A larger dimension means that the hypothesis class can support a more deeply branching collection of label histories. This makes Littlestone's Dimension a complexity measure specifically tied to online learning.
Littlestone's Dimension characterizes the best achievable mistake bound for a hypothesis class in online learning. It does not merely ask whether the class contains a good predictor. It describes the difficulty of choosing predictions online while keeping the number of mistakes under control.
Online and PAC Learning
| Feature | Online learning | PAC learning |
|---|---|---|
| Examples | Arrive one at a time through consecutive rounds | Arrive as a batch of training examples |
| Current label | Revealed after the learner predicts | Training labels are available during the training stage |
| Prediction and learning | Repeatedly combined within rounds | Separated into a training stage followed by a prediction stage |
| Role of an example | First supports a prediction, then supports later predictions after its label is revealed | Training examples are used before predictions on new examples |
Common Reasoning Errors
Treating online learning as if it had a separate training phase followed by a separate prediction phase.
Online learning interleaves prediction and learning across consecutive rounds.
Fix:
For every round, identify the instance, prediction, revealed label, and later use of feedback.Checking only whether both labels appear at one node.
Shattering requires every complete label path through the tree to be consistent with some hypothesis.
Fix:
List every path, such as 00, 01, 10, and 11, and match each path with a hypothesis.Counting hypotheses instead of checking tree depth.
Dimension is the greatest depth of a shattered tree, not the number of hypotheses.
Fix:
Find the deepest tree for which all label paths are realizable.Using the true label before making the current prediction.
The true label is revealed only after the prediction in an online round.
Fix:
Treat the example as a test example first and as training information only after label revelation.
Practice the Path Test
A hypothesis class contains three hypotheses. One always predicts 0, one always predicts 1, and one predicts 0 on the first instance and 1 on the second instance along a chosen path. Explain which depth-one or depth-two paths you would check first, and describe the procedure you would use to decide whether a particular tree is shattered. Do not assume that realizing some paths is enough.
Hints
- Start by listing all complete label paths for the proposed depth.
- For each path, ask whether at least one hypothesis agrees with every label along that path.
- A tree is shattered only if no path is left without a consistent hypothesis.
- To solve a shattering problem, work path by path. The depth tells you how many labels appear in each history, and the hypothesis class must realize every possible history at that depth.
Key Takeaways
- Online learning is a sequence of rounds in which the environment chooses an instance, the learner predicts a binary label, the true label is revealed, and the learner uses the feedback for later predictions. A tree is shattered by H when every label path through it agrees with some hypothesis in H. Littlestone's Dimension is the greatest depth of a shattered tree. It measures online learning complexity and is tied to the best achievable mistake bound. The same example is first used for testing and, after its label is revealed, can support future training. PAC learning differs by using a batch training stage before prediction on new examples.
Key Takeaways
- Online learning interleaves prediction and learning across consecutive rounds.
- Each round contains four events: instance selection, prediction, label revelation, and use of feedback.
- A tree is shattered when every complete label path is consistent with some hypothesis in the class.
- Littlestone's Dimension is the greatest depth of a shattered tree and is tied to achievable online mistake bounds.
- PAC learning uses batch training followed by prediction, unlike the repeated predict-then-learn schedule of online learning.