悔值分析 (Regret analysis) 在在线交互学习中被广泛采用。然而，为什么在线学习要使用悔值最小化，而不是像批量学习 (Batch Learning) 等其他学习任务那样使用成本最小化？在这篇短文中，我们将提供一个示例，说明通过最小化悔值，学习者可以获得更好的收益。
最坏情况成本与最坏情况悔值成本
考虑定义为 的函数 ，其中 为任意函数。定义如下的优化问题：
可以被视为最坏情况下的优化问题，其中 被称为最坏情况成本 (worst-case cost)。
考虑一个场景：设 表示在策略 和环境 下，将汽车从一个地方开到另一个地方所需的时间。在此情境中， 代表驾驶员的驾驶方式（包括调整车速、选择车道等决策），而 代表指示当前是否下雨的二元条件（ 表示下雨， 表示未下雨）。该函数综合反映了驾驶决策和天气条件对行程时间的影响。
众所周知，雨天开车的花费时间往往更长。因此，。根据定义，函数 目前表示在雨天驾驶所需的时间。
现在，我们定义 。我们将 称为最坏情况悔值成本 (worst-case regret cost)。与最坏情况成本不同，悔值成本衡量的是过去几天的决策中能够改进的最大幅度。例如，如果驾驶员因类风湿性关节炎而在雨天无法驾驶，那么对于任意 和 ， 与 之间将没有差异，从而使得 。没有任何悔值！因为在最坏情况下没有任何可以改进的空间。
最小化悔值成本能带来更好策略的示例
考虑如下定义的函数 ：
在此示例中，最坏情况成本 对于任意 均满足 。因此：
然而对于最坏情况悔值成本，有 且 。因此：
数据关联性
标准离线机器学习的核心假设是，收集到的数据独立同分布（I.I.D.）地来自于某个未知的概率分布 (Vapnik, 1999)。然而在在线学习领域，这一假设很容易受到破坏 (Shalev-Shwartz, 2011)。例如，再次考虑那位雨天不驾车的驾驶员场景：在一小时时间段内，数据点（表示行车所需时间）的采集概率可能低至 ；相反，一小时之后的数据点采集概率可能大于 。这意味着在不同日期收集的数据遵循不同的分布。这种区别凸显了传统离线学习与在线学习之间的关键差异。
Shalev-Shwartz, S. (2011). Online Learning and Online Convex Optimization. Foundations and Trends in Machine Learning, 4(2), 107–194.
Vapnik, V. N. (1999). An overview of statistical learning theory. IEEE Transactions on Neural Networks, 10(5), 988–999.