Does no-regret mean zero cumulative regret?

Usually not. Cumulative regret can grow sublinearly while regret per round tends to zero.

Can regret be negative?

Yes. A changing learner can outperform every single fixed action on a particular sequence.

Does a short successful trial establish a no-regret algorithm?

No. A trial measures that sequence; a guarantee requires analysis under specified assumptions.

AI Glossary / Graphs and symbolic AI / Intermediate

No-regret learning

Definition

No-regret learning is a way of making repeated decisions so that the learner's average performance approaches that of a specified hindsight benchmark. In the common external-regret setting, the benchmark is the single fixed action that would have performed best over the observed sequence. A no-regret guarantee makes the excess average loss vanish, or become no worse than zero, as the horizon grows under stated assumptions.

What it means

The learner chooses before seeing the current outcome, receives feedback, and adjusts future choices. After many rounds, its cumulative loss is compared with what it would have incurred by using one fixed alternative throughout those same rounds.

“No regret” does not mean every choice is correct, every round is profitable, or the learner never loses. It describes performance relative to a comparator over time. The comparator is central: matching the best fixed action is a weaker requirement than matching an oracle that changes to the best action on every round.

How it works

For losses, external regret after T rounds is the learner's cumulative loss minus the smallest cumulative loss of any fixed action. A typical no-regret result bounds this excess by a sublinear function of T, such as a quantity proportional to √T under suitable conditions. Dividing by T gives a bound that tends to zero.

Algorithms may maintain weights over actions, increase the relative influence of better-performing alternatives, and randomize their choices. Full-information feedback reveals losses for all actions; bandit feedback reveals only the chosen action's outcome and requires different estimation and exploration techniques.

Guarantees depend on loss bounds, feedback, randomization, and what an adversary can observe or influence. Expected-regret and high-probability guarantees are different statements. A good average bound also does not necessarily mean the learner's final action or current strategy has converged.

Three practical examples

Expert selection: combine or choose among prediction methods while comparing cumulative performance with the best fixed method afterward.
Repeated routing experiments: adapt among allowed routes using feedback, with a clearly defined benchmark and observation model.
Game learning: update play over repeated interactions and study average behavior using the appropriate regret notion.

Think of it this way

Think of trying several work routines over many days and comparing your total effort with the effort of the best single routine chosen in hindsight. The goal is to learn without falling far behind that fixed benchmark.

The analogy does not promise the foresight to choose each day's best routine. It also assumes that the comparison is meaningful: your choices may affect future conditions, in which case a simple fixed sequence of alternative losses needs careful interpretation.

Worked example

Consider four rounds with two actions, A and B. Their loss sequences are A=(0,1,0,1) and B=(1,0,1,0). Each fixed action has total loss two. Suppose a learner selects A, A, B, B and therefore incurs losses 0,1,1,0, also totaling two.

Its external regret on this sequence is 2−min(2,2)=0, and its average external regret is zero. Nevertheless, an oracle choosing the better action separately each round would incur zero total loss. Zero external regret therefore does not imply matching that switching oracle.

Now imagine a different learner selects A, B, A, B and incurs zero. Its external regret is 0−2=−2: it outperforms every fixed action on this particular sequence. Negative realized regret is possible because the learner is allowed to change actions.

Neither four-round result proves that an algorithm is no-regret. That property concerns a guarantee over horizons and permitted loss sequences. For illustration, a cumulative upper bound of 5√T would give average regret at most 5/√T: 0.5 at T=100 and 0.05 at T=10,000. Those numbers illustrate a hypothetical bound, not a claim about an implemented learner.

Illustrative case study

Fictional case: an analytics team rotates between forecasting methods and reports low external regret against the best fixed method. A stakeholder interprets the result as proof that the system always chooses the most accurate method for the current week.

The team revises the report to show cumulative loss, the fixed comparator, and the difference from a stronger switching benchmark. It also separates retrospective evaluation from any theorem applying to the deployed update rule. The fictional case illustrates correct interpretation of a learning objective, not an observed forecasting result.

Common misconceptions and mistakes

No-regret is not the absence of emotional regret or a guarantee of good absolute performance. If every available action performs poorly, matching the best fixed action can still yield poor outcomes.

Do not confuse external regret with internal or swap regret. Those stronger comparison structures ask different counterfactual questions and support different equilibrium conclusions. In general games, external no-regret learning does not automatically make the players' current strategies converge to a Nash equilibrium.

Finally, adaptive environments deserve care. Comparing losses along the realized history is not always equivalent to asking what would have happened if a different policy had changed the environment's subsequent behavior.

Business use

No-regret methods can support repeated allocation or selection tasks when feedback and comparison losses are well defined. Begin by stating the action set, loss scale, horizon, feedback type, and comparator. These details determine what a performance claim actually means.

Track both relative regret and absolute task quality. A small gap to a weak benchmark may be operationally unhelpful. Where switching costs or delayed feedback matter, include them in the model or choose an analysis that covers them rather than assuming a basic guarantee still applies unchanged.

Check your understanding

A learner's cumulative loss is 23 and the best fixed action's loss is 20 after ten rounds. What are cumulative and average external regret?

Answer: Cumulative regret is three, and average regret is 0.3 per round.

Related terms

Online learning
external regret
internal regret
swap regret
multiplicative weights
bandit feedback
adversarial learning
correlated equilibrium

Learn next

calculate regret for a small loss table using both fixed and switching comparators. Then study a weighted-experts algorithm and identify precisely which feedback its update needs.

Sources

Avrim Blum's Carnegie Mellon lecture material explains no-regret objectives, fixed-action benchmarks, feedback models, and game-theoretic limits: https://www.cs.cmu.edu/~avrim/ML08/lect0414.pdf

The four-round sequences, hypothetical bound, and fictional forecasting case are original illustrations. The main definition here is external regret; other regret notions are explicitly distinguished.

Previous: No-reference metric Next: No-U-turn sampler