Regret Analysis
The order matters: prediction first, environment response second, and loss after the response. Repeating this order over many rounds produces the cumulative losses that regret analysis compares.
The Repeated Prediction Setting
Regret analysis studies a repeated prediction problem. Instead of making one prediction and stopping, the learner makes a prediction at each time step. The environment then supplies a domain element, and the learner incurs a loss determined by the learner's chosen vector and that element. The central question is not whether one individual prediction was perfect. It is how the learner's total loss compares with the total loss of a competing hypothesis.
The order matters: prediction first, environment response second, and loss after the response. Repeating this order over many rounds produces the cumulative losses that regret analysis compares.
Tracing a Round
What do you think happens?
Suppose the learner has chosen a prediction vector. What must happen before the learner's loss for that round is determined?
Reveal answer
The environment provides a domain element, and the loss is then determined from the learner's chosen vector and that element.
The online interaction proceeds from the learner's prediction to the environment's response and then to the incurred loss.
A Three-Round Abstract Trace
Track the interaction when a learner makes one prediction on each of three rounds.
- 1Round 1
The learner chooses a vector from the hypothesis class. The environment provides a domain element. The learner then incurs the loss determined by that vector and element.
- 2Round 2
The same prediction-response-loss sequence occurs again. This round contributes another loss to the learner's running total.
- 3Round 3
The learner makes a third prediction, receives the environment's response, and incurs the third loss.
- 4After the rounds
The losses from all three rounds are considered together. Regret analysis compares this cumulative algorithm loss with the cumulative loss of a competing vector.
A round is one prediction-response-loss cycle; regret is evaluated over the accumulated result of repeated cycles.
This trace separates two ideas that are easy to blur together. The loss from one round describes what happened immediately after one response. Cumulative loss combines the losses across the repeated problem. Regret uses the second idea, because it compares performance over the whole sequence rather than judging the learner from only one round.
Convexity Requirements
An online convex optimization problem has three defining ingredients: a convex hypothesis class, a domain, and a loss function that is convex in its first argument. The first argument is the learner's predicted vector. Together, these assumptions describe a setting in which the available hypotheses form a convex set and the loss behaves convexly as the learner changes its prediction.
The convexity assumptions matter because the framework permits reasoning about combinations of hypotheses or predictions rather than treating every hypothesis as an isolated choice. The hypothesis class supplies the allowed prediction vectors, while convexity of the loss concerns how the loss changes in the learner's predicted vector. Both requirements belong to the definition of the online convex optimization setting.
Two Vectors in the Comparison
At each round, the learner chooses a prediction vector from the hypothesis class. Regret analysis also names a competing vector, written as w-star in ordinary prose. The learner's vector may be chosen anew as the online process proceeds, whereas the competing vector is the reference used to evaluate the learner's cumulative performance. These vectors play different roles: one produces the algorithm's losses, and the other supplies the comparison losses.
Separating the Roles
Identify which object supplies each side of a regret comparison.
- 1Learner side
For every round, use the vector selected by the learner to determine that round's algorithm loss.
- 2Competing side
Use the competing vector w-star as the reference hypothesis when evaluating the losses used for comparison.
- 3Cumulative comparison
Aggregate the learner-side losses and the competing-side losses over the repeated sequence.
The prediction vector selected during the online process and the competing vector used in regret analysis are distinct roles in the comparison.
Building Cumulative Regret
Regret is the difference between two cumulative quantities: the algorithm's cumulative loss and the cumulative loss of a competing vector in the hypothesis class. The comparison is therefore made after considering the repeated sequence of rounds. A learner can have a low loss on one round and still have a larger cumulative loss overall, or have a high loss on one round while comparing favorably across the full sequence.
A Numerical Illustration
Suppose the learner's losses over three rounds are 4, 2, and 3, while the chosen competing vector would have losses 3, 2, and 2 on those same rounds.
- 1Accumulate the learner's losses
The algorithm's cumulative loss is the total of 4, 2, and 3, which is 9.
- 2Accumulate the competing losses
The competing vector's cumulative loss is the total of 3, 2, and 2, which is 7.
- 3Compare the totals
Regret is the algorithm's cumulative loss minus the competing vector's cumulative loss, so the difference is 2.
In this generated illustration, the learner's cumulative loss exceeds the competing vector's cumulative loss by 2.
Common Interpretation Errors
Common mistake Treating the competing vector as the learner's prediction on the current round.
What it looks likeThe learner selects one vector, but the analysis is described as though that vector were automatically the competing vector w-star.
Why it failsThe learner's prediction and the competing vector serve different roles. Regret evaluates the learner relative to a competing vector in the hypothesis class.
Do this insteadTrack the learner's selected vector as the source of algorithm loss, and track w-star as the comparison reference.
Common mistake Defining regret from only one round's loss.
What it looks likeA learner's loss on the latest round is called its regret.
Why it failsRegret uses cumulative losses over the repeated prediction problem.
Do this insteadAccumulate the algorithm losses and the competing losses across the rounds, then compare the two totals.
Common mistake Forgetting the environment response.
What it looks likeThe learner's prediction is treated as producing a loss immediately, without an environment-provided domain element.
Why it failsThe online interaction proceeds from prediction to environment response to incurred loss.
Do this insteadWrite the round as a three-part sequence: learner prediction, environment response, and loss.
Common mistake Using convexity to describe only the loss function.
What it looks likeThe hypothesis class is ignored while the loss is described as convex.
Why it failsThe online convex optimization setting requires both a convex hypothesis class and a loss function convex in its first argument.
Do this insteadCheck the set of available hypotheses and the loss's dependence on the learner's predicted vector separately.
Practice the Comparison
A learner incurs losses 5, 1, and 4 over three rounds. A competing vector in the hypothesis class would incur losses 4, 2, and 3 over those same rounds. Describe the learner's cumulative loss, the competing cumulative loss, and the resulting regret in words.
Hints
- Add the learner's three losses first.
- Add the competing vector's three losses separately.
- Regret is the difference between the two cumulative totals.
Explain the difference between these two statements: the learner chooses a vector from the hypothesis class at a round, and regret is evaluated relative to a competing vector w-star in the hypothesis class.
Hints
- Focus on when each vector is used.
- One vector produces the learner's round-by-round losses; the other is the reference for cumulative comparison.
Key Takeaways
- 1Each online round follows the sequence learner prediction, environment response, and incurred loss.
- 2Online convex optimization uses a convex hypothesis class and a loss function convex in the learner's predicted vector.
- 3The learner's prediction vector is distinct from the competing vector w-star used as the reference in regret analysis.
- 4Regret compares cumulative algorithm loss with cumulative loss for the competing vector, not merely one round's loss.
- 5The purpose of the comparison is to interpret how the learner performed over the repeated prediction sequence relative to a hypothesis in the class.
At a glance
- An online convex optimization problem repeats a prediction-response-loss interaction.
- The hypothesis class must be convex, and the loss must be convex in the learner's prediction.
- The learner's round-by-round vector and the competing vector w-star have different roles.
- Regret is the difference between cumulative algorithm loss and cumulative competing loss.