Agnostic PAC Model
Regret measures how much worse an online algorithm performed than a fixed reference predictor.
When Perfect Prediction Is Unavailable
In an unrealizable online-learning setting, we do not assume that some hypothesis labels every example correctly. That makes a perfect-prediction question unsuitable: the learner may have no perfectly correct hypothesis to discover. Regret provides a different standard. It asks whether the online algorithm performed nearly as well as a fixed predictor that could have been followed throughout the same sequence.
Comparing with One Fixed Hypothesis
Suppose an online algorithm A makes predictions over a sequence of T examples. Choose one named hypothesis h as the reference predictor. Regret relative to h measures how much more loss A accumulated than h on that same sequence. The comparison is made after recording both performances. Algorithm A does not need to copy h while the sequence unfolds.
Regret Relative to h
On the same sequence of examples, algorithm A has loss 10 and the fixed hypothesis h has loss 8. What is A's regret relative to h?
Use the same sequence: Both losses must describe performance on the same sequence of T examples.
Compare the losses: Algorithm A accumulated loss 10, while h accumulated loss 8.
Find the difference: A accumulated 2 more units of loss than h.
The regret of A relative to h is 2.
Changing the Comparator to a Class
The phrase relative to h identifies one particular benchmark. If the benchmark changes, the regret value can change because the comparison loss changes. Regret relative to a hypothesis class H uses a stronger benchmark: instead of choosing one named hypothesis in advance, compare the algorithm with the best fixed predictor available within H.
Class Regret
Algorithm A has loss 10. A hypothesis class H contains fixed predictors, and the best one has loss 8. What is the regret relative to H?
Search the class conceptually: The class comparator is the best fixed predictor available within H, not an arbitrary named member.
Identify the benchmark loss: The best fixed predictor in H has loss 8.
Compare with A: Algorithm A has loss 10, so it accumulated 2 more units of loss than the class benchmark.
The regret relative to H is 2.
Accumulating Loss Across Rounds
Regret is based on total loss, so the individual losses from successive rounds must first be accumulated. On each round, record the algorithm's loss and the fixed comparator's loss. After the final round T, compare the two totals. The difference between those totals is the regret for that comparator.
| Round | Algorithm A loss | Comparator h loss | Cumulative A loss | Cumulative h loss |
|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 0 |
| 2 | 0 | 1 | 1 | 1 |
| 3 | 1 | 0 | 2 | 1 |
Generated bookkeeping example showing how per-round losses become total losses.
In this bookkeeping example, A's total loss is 2 and h's total loss is 1. The regret relative to h is therefore 1. The important discipline is to compare totals from the same three rounds, rather than comparing a round from one record with a different round from the other.
Mistakes in Regret Comparisons
Assuming the unrealizable setting contains a perfectly correct hypothesis.
The unrealizable setting does not assume that any hypothesis labels every example correctly.
Fix:
Judge the algorithm by how competitive it is with a fixed predictor.Comparing losses from different example sequences.
Regret is defined by comparing performances on the same sequence of T examples.
Fix:
Record both losses on the same sequence before taking their difference.Confusing one-hypothesis regret with class regret.
Class regret uses the best fixed predictor available within H.
Fix:
First identify the best fixed predictor in H, then compare A with it.Thinking the algorithm must have followed the comparator.
The comparison is retrospective; A makes its own online predictions while the sequence unfolds.
Fix:
Compare the recorded total losses after the sequence is complete.
When calculating regret, write down three items in order: the sequence being evaluated, the algorithm's total loss, and the comparator's total loss. Only then compute the difference. If the comparator is a class, identify its best fixed predictor before comparing totals.
Check Your Understanding
Algorithm A has total loss 13 on a sequence of T examples. A named hypothesis h has total loss 11 on that same sequence. A hypothesis class H contains h and other fixed predictors, and the best fixed predictor in H has total loss 9. Determine A's regret relative to h and A's regret relative to H. Then explain why the two values differ.
Hints
- For regret relative to h, compare 13 with 11.
- For regret relative to H, use the best fixed loss, which is 9.
- The comparator changes, so the difference can change.
What do you think happens?
Using the practice values, what is A's regret relative to the class H?
Reveal answer
Answer: 4
The best fixed predictor in H has loss 9, while A has loss 13. The class comparison therefore gives a difference of 4.
The Regret Perspective
- In the unrealizable setting, no hypothesis is assumed to label every example correctly.
- Regret measures how much more loss the online algorithm accumulated than a fixed comparator on the same sequence.
- Relative to one hypothesis h, the comparator is that named fixed predictor.
- Relative to a class H, the comparator is the best fixed predictor available within H.
- To calculate regret, accumulate each party's losses over the same T examples and compare the resulting totals.
Key Takeaways
- Regret replaces the demand for perfect prediction with a comparison to a fixed predictor.
- Regret relative to h compares the algorithm with one named hypothesis.
- Regret relative to H compares the algorithm with the best fixed predictor in the class.
- All losses must be measured on the same sequence of examples.
- Regret is obtained from the difference between the algorithm's total loss and the comparator's total loss.