Why regret is used in online machine learning?

Is there any intuitive explanation about it?

Are there any other measurements to be optimized except the regret in online learning?

Thanks in advance.


1 Answer 1


"Regret" as a term that applies to online machine learning is one that lends itself very easily to an intuitive explanation.

Minimizing (or, alternatively, optimizing for) "regret" is simply reducing the number of actions taken which, in hindsight, it is apparent that there was a better choice. By minimizing regret, we are minimizing subobtimal actions by the algorithm.

Depending on the application of the online machine learning algorithm, there can be many, many other measurements to be optimized.

Several specific papers you may be interested discuss the topic in depth:

Learning, Regret minimization, and Equilibria - A. Blum and Y. Mansour

Optimization for Machine Learning - Hazan

Online Learning and Online Convex Optimization - Shalev-Shwartz

  • $\begingroup$ Can regret be negative? $\endgroup$
    – r4bb1t
    Commented Feb 6, 2020 at 22:38
  • 1
    $\begingroup$ No- you cannot do better than the best you can do. $\endgroup$ Commented Feb 7, 2020 at 4:32
  • 1
    $\begingroup$ In that case, I think what you're referring to is a mistake by one of the experts in the algorithm. Regret as a measure could be applied in at least two ways here: first, as a measure of the effectiveness of a single expert's predictions (with an appropriate cost function). That would give you a regret score- how much value the actions driven by an expert's predictions lose relative to the best possible outcome. Notably- this is equivalent to the backward-looking best possible outcome, not the forward-looking best outcome that possibly could have been predicted beforehand. $\endgroup$ Commented Feb 7, 2020 at 13:26
  • 1
    $\begingroup$ You could also apply that same scheme to the algorithm overall. $\endgroup$ Commented Feb 7, 2020 at 13:27
  • 1
    $\begingroup$ Regret is most often used as a metric that informs the training of reinforcement learning algorithms- if the experts were RL algorithms (or people genuinely interested in that form of feedback, I suppose) they could use the regret of their predictions to learn a new policy of producing predictions. $\endgroup$ Commented Feb 7, 2020 at 13:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.