Is regret the same as disappointment about an outcome?

No. Technical regret is a defined comparison, which can be calculated without any emotional interpretation.

Does sublinear cumulative regret mean total regret decreases?

Not necessarily. A bound proportional to √T increases with T, while its per-round value decreases.

Can the comparator be a policy rather than an action?

Yes. The policy class and evaluation model must then be specified explicitly.

AI Glossary / Mathematics and optimization / Intermediate

Regret

Definition

Regret is the difference between a decision-maker's loss and the loss of a specified comparison strategy. In sequential learning, cumulative regret often compares the learner's total loss with that of the best fixed action chosen in hindsight over the same rounds.

What it means

The word has a technical meaning rather than an emotional one. It measures how much worse a learning procedure performed relative to a clearly defined benchmark. In reward language, the subtraction reverses: benchmark reward minus the learner's reward.

The comparison is essential. A fixed action used on every round, a policy that responds to context, and an oracle that always selects the best action for each round are different benchmarks. Their regret values can differ greatly on the same sequence.

Low regret is a relative achievement. If every action in the comparison class performs badly, matching the best one may still deliver poor business results. Regret must therefore be interpreted alongside absolute loss or reward and the suitability of the benchmark.

How it works

Let aₜ be the learner's action on round t and ℓₜ(a) the loss of action a on that round. A common fixed-action definition is Rₜotal=Σₜℓₜ(aₜ)−min over a of Σₜℓₜ(a). The comparator is selected after examining all rounds, but it must use the same action throughout.

A changing comparator instead has more freedom. Dynamic regret may compare against a sequence of actions, often with restrictions on how much that sequence can change. In reinforcement learning, comparisons between policies also need to account for how actions change future states.

A no-regret guarantee generally concerns an upper bound growing slower than the number of rounds. Consequently, the upper bound on average excess loss tends to zero. It does not promise zero mistakes, zero cumulative loss or superiority on each round.

Some results hold in expectation over randomness, others with high probability, and others under particular environmental assumptions. In bandit feedback, only the chosen action's outcome is observed, so evaluating an unchosen comparator requires care.

Three practical examples

A recommendation experiment compares a learning policy's cumulative reward with a documented fixed recommendation baseline.
An online forecasting system measures excess loss relative to the best fixed expert in a specified collection.
A research team distinguishes a bound against a stationary policy from a stronger comparison that adapts to changing conditions.

Think of it this way

Think of comparing your changing travel choices with the best single route you could have committed to for an entire week, after seeing that week's travel times.

That benchmark is different from choosing each day's fastest route with advance knowledge. Real travel choices may also affect congestion, so the analogy assumes the recorded route costs remain appropriate for the comparison.

Worked example

The benchmark changes the answer

Consider four rounds with two actions. Action A has losses (1,4,1,4), totaling 10. Action B has losses (3,1,3,1), totaling 8. The learner chooses A, A, B, B and incurs losses (1,4,3,1), totaling 9.

The best fixed action is B, so fixed-action regret is 9−8=1. Average regret over these four rounds is 1/4=0.25.

An oracle allowed to select the best action independently on each round would choose A, B, A, B and incur total loss 4. Relative to that stronger benchmark, the same learner has regret 9−4=5.

Conversely, a learner that happened to choose A, B, A, B would have fixed-action regret 4−8=−4. A changing sequence can outperform every fixed action, so realized regret against that comparator need not always be nonnegative. These arithmetic examples describe fully specified losses; they do not show how a learner could know future losses in advance.

Illustrative case study

A fictional publishing platform evaluates an online article-selection method. One report compares it with the best single article shown throughout the evaluation. Another compares it with the best article separately for every visit. The two teams obtain different regret numbers.

They reconcile the reports by documenting the comparator, time horizon and feedback available. They also separate directly observed rewards from estimates of what unshown articles would have achieved.

The platform then reports absolute engagement measures alongside regret. Beating a weak fixed baseline may be useful evidence, but it does not establish that the product meets its own quality objectives.

Common misconceptions and mistakes

Regret is ordinary prediction error. It is excess performance loss relative to a comparator.
No regret means no bad decisions. It usually describes a long-run relative guarantee.
Every regret value is nonnegative. A changing learner can beat a fixed hindsight comparator on a realized sequence.
The best fixed action is the best action on every round. These are different comparison classes.
An expected bound guarantees every run. Individual outcomes may differ from their expectation.

Business use

Regret provides a disciplined way to discuss learning while decisions are being made. Before accepting a claim, ask which actions or policies form the comparison class, how losses are measured and whether the benchmark is meaningful for the operating environment.

Also ask whether the reported value is measured, estimated or theoretically bounded. Unobserved alternatives cannot simply be filled with favorable hypothetical outcomes. Switching costs, delayed feedback and changes in the environment should be included in the setup when they affect the business decision. A guarantee outside those conditions may not answer the practical question.

Check your understanding

The learner's total loss is 9, the best fixed action loses 8, and a per-round oracle loses 4. Which regret is one?

Answer: Regret against the best fixed action. Regret against the per-round oracle is five; the benchmark must accompany the number.

Related terms

Learn next

Read multiarmed bandit and online learning. Recalculate the example after adding a cost of one whenever the learner switches actions, and decide whether the comparator should incur the same switching rule.

Sources

Aalto Dictionary of Machine Learning, regret: https://aaltodictionaryofml.github.io/ADictML_Main.pdf. Baseline-relative loss definition.

Han, Rakhlin and Sridharan, Competing With Strategies: https://proceedings.mlr.press/v30/Han13.pdf. Primary introduction and formal comparator definitions reviewed. The four-round losses and fictional platform are original illustrations.

Previous: Regressor chains Next: Regular expression