One intuitive explanation could be that the search space is much bigger when you allow to look at points as often as you want. The bigger the search space, the lower loss you can achieve.
Take a look at an online implementation of kSVMs and especially at the kernel perceptron algorithm (Aizerman et al., 1964). As you can see, the support vectors can be added only once, and therefore, the set of support vectors will be highly dependent on the order of arrival of the data.
Likewise, with online decision trees (or random forests), in some implementations (see per example the one below), points are accumulated into leaves, until leaves contains enough point and a (high enough) gain can be achieved by splitting this leaf. On the other hand, training a decision tree on a complete dataset and "choosing the best split" will intuitively provide a better fit.
Saffari, A., Leistner, C., Santner, J., Godec, M., & Bischof, H. (2009, September). On-line random forests. In Computer Vision Workshops (ICCV Workshops), 2009 IEEE 12th International Conference on (pp. 1393-1400). IEEE.
Regarding the first two, online and incremental learning, some authors underline that
On-line has to discard a sample after learning (no memory) and unlike to
incremental learning is not allowed to store it. Source: this paper
Best Answer
"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