In online learning, cumulative regret compares the total loss of sequential choices with the best fixed action that could have been chosen in hindsight: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 and , always choosing the second has loss two, while the best fixed action has loss one, giving regret one.
A bound 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.
New to topics? Read the docs here!