Regret

Imagine choosing among several slot machines, each with an unknown payout rate. Regret measures the reward you missed because you did not consistently choose the best machine in hindsight—not because every individual choice was wrong.

What regret measures
In a multi-armed bandit, an agent selects one action, or arm, each round and sees only that arm’s reward. After T rounds, cumulative regret compares the agent’s total reward with what it would have earned by repeatedly choosing the single best arm from the start. If the best arm has expected reward μ* and the chosen arm at round t has mean μ_{A_t}, expected regret is the accumulated gap: Σ_t=1^T(μ* − μ_{A_t).

The comparison is deliberately fair: the agent is not judged against an impossible oracle that knows each random outcome in advance. It is judged against the best fixed choice that knowledge of the reward distributions would reveal afterward.}

Exploration has a price—and a purpose
Trying an uncertain arm can produce immediate regret if a known arm pays better. But never trying it can be worse: the agent might remain stuck with a merely decent arm while missing an excellent one. Good bandit algorithms accept early regret to reduce much larger future regret:

UCB tries arms whose reward estimates or uncertainty bounds are high.
Thompson sampling samples plausible reward rates and acts according to those samples.

A strong algorithm achieves sublinear regret, such as growing roughly with log T rather than proportionally to T. Then average regret per decision shrinks toward zero: learning pays off over time.

Why it matters in practice
For a news site choosing article variants, regret is the lost engagement relative to always showing the best variant. It captures the central reinforcement-learning constraint: actions generate both reward and data. Pure supervised learning receives labels for every option; a bandit sees feedback only for what it chose. Regret therefore evaluates not just whether an agent eventually identifies a good action, but how much reward it sacrificed while learning to do so.

Regret is the cumulative reward lost by a learning algorithm compared with the best action or policy available in hindsight. In a multi-armed bandit, it is the gap between the reward obtained by the chosen arms and that of always selecting the best arm. Low regret measures effective exploration and exploitation: it shows that the learner quickly identifies and uses rewarding actions.

Imagine choosing a new café each morning. Some have great coffee, some do not, and you only learn by trying them. Regret is the cost of not having always chosen the best café from the start.

In AI decision-making, regret measures how much reward was missed compared with the best choice the system could have made in hindsight. It is not an emotion: the software does not feel bad. It is a score for judging its decisions over time. A good learner may make a few disappointing choices early on to discover what works, but its regret should grow slowly as it learns to choose better.