What is Regret?
Regret is a performance measure for sequential decisions that compares the reward or loss accumulated by a learner with the outcome of a specified comparator over the same horizon.
Quick Facts
| Specification | Official Specification |
|---|
How It Works
A regret number is meaningless without its comparator
For a stochastic K-armed bandit with means mu_i, pseudo-regret against the best fixed arm is the expected reward gap accumulated over selected arms. A contextual bandit may instead compare with the best policy in a declared class, while dynamic regret uses a changing comparator and requires a variation budget or related restriction. Lai and Robbins established a foundational asymptotic lower bound for specific stochastic allocation models.
Do not mix cumulative, simple, realized, and pseudo-regret
Cumulative regret rewards policies that learn while serving; simple regret evaluates the action recommended after exploration. Realized regret uses sampled outcomes and can fluctuate, whereas pseudo-regret compares expected rewards under the model. Instance-dependent bounds expose arm gaps or divergences; minimax bounds protect against the hardest environment in a class. The rates answer different questions and should not be ranked without a common setting.
Use regret in simulation and observable gates in production
True regret usually needs counterfactual rewards or known environment means, so it is directly available in simulators but not ordinary production logs. Online systems should report observed reward, randomized holdouts, off-policy estimates with uncertainty, exposure and safety metrics, plus regret only where the oracle is justified. Bubeck and Cesa-Bianchi develop stochastic and nonstochastic analyses and make the required payoff assumptions explicit.
Key Characteristics
- Measures a learner relative to a declared comparator
- Accumulates opportunity cost across a sequential horizon
- Changes meaning with stochastic, adversarial, or contextual assumptions
- Includes cumulative, simple, realized, pseudo, external, and dynamic forms
- Supports asymptotic, finite-time, instance-dependent, and minimax analyses
- Usually cannot be observed directly from unrandomized production feedback
Common Use Cases
- Comparing exploration policies in a controlled bandit simulator
- Proving finite-time behavior of online learning algorithms
- Separating serving performance from final best-arm identification
- Defining a policy-class benchmark for contextual decisions
- Stress-testing adaptation under drift with a dynamic comparator
Example
Loading code...Frequently Asked Questions
What is the difference between regret and loss?
Loss is the cost assigned to a prediction or action. Regret is a relative quantity: the learner's cumulative loss minus a comparator's cumulative loss, or the comparator's reward minus the learner's reward. The same observed loss sequence can produce different regret under different comparators.
What is the difference between cumulative regret and simple regret?
Cumulative regret scores every decision made during learning, so exploratory mistakes have immediate cost. Simple regret scores only the final recommended action after exploration. A pure-exploration method can have poor cumulative reward yet identify an excellent final arm.
What is pseudo-regret?
Pseudo-regret compares expected rewards under the assumed environment, typically summing mean gaps for selected actions. Realized regret compares sampled outcomes or reward sequences. Their expectations may be related in a valid stochastic model, but individual runs can differ substantially.
Does sublinear regret mean an algorithm is optimal?
It means average regret vanishes relative to the stated comparator as the horizon grows. It does not prove the comparator is socially desirable, constraints are satisfied, constants are practical, finite traffic is sufficient, or the environment matches the theorem.
Can production regret be calculated from ordinary logs?
Usually not exactly, because rewards for unchosen actions are missing and the best counterfactual action is unknown. Randomized experiments, simulators, or justified off-policy estimators can estimate policy value, but each introduces assumptions and uncertainty that must be reported.