= Cumulative regret
{title2=$R_T$}
In <online learning>, <cumulative regret> compares the total loss of sequential choices $a_t$ with the best fixed action that could have been chosen in hindsight:
$$
R_T=\sum_{t=1}^T\ell_t(a_t)-\min_{a\in A}\sum_{t=1}^T\ell_t(a).
$$
The comparator uses one action for every round; comparing with a different best action at each round defines a stronger benchmark. For two actions whose losses over three rounds are $(0,1,0)$ and $(1,0,1)$, always choosing the second has loss two, while the best fixed action has loss one, giving regret one.
A bound $R_T=o(T)$ means average regret tends to zero. It does not promise zero loss or identify a true data-generating <probability distribution>; even adversarial loss sequences can be studied this way. In a <multi-armed bandit>, only the chosen action's reward is observed, making information gathering part of the decision problem.
Back to article page
