自适应遗憾与漂移比较器

形式陈述

本页在在线学习协议中扩展固定比较器遗憾，并显式限制比较器随时间获得的额外自由。

标准外部遗憾将学习器累计损失与整段时间内最好的一个固定动作比较。若环境前半段适合动作 $a$ 、后半段适合动作 $b$ ，固定基准本身也会折中，低遗憾无法说明学习器是否迅速跟上了切换。要评价非平稳适应能力，必须加强比较器，同时为它允许的变化规定预算；否则逐轮挑最小损失动作可能强到任何因果学习器都无法接近。

本页区分三种常被混叫成“动态遗憾”的对象。它们回答不同问题，保证不能互相替换。

shifting regret

专家集合为 $[N]$ 。对比较序列 $i_{1:T}$ 定义

R_T(i_{1:T}) =\sum_{t=1}^T\widehat\ell_t -\sum_{t=1}^T\ell_{t,i_t}.

若限制切换次数

S(i_{1:T})=\sum_{t=2}^T\mathbf{1}_{\{i_t\ne i_{t-1}\}}\le K,

则最坏 shifting regret 是对所有至多切换 $K$ 次的序列取上确界。fixed-share 一类算法可得到形如

O\!\left(\sqrt{T\bigl((K+1)\log N+K\log(T/K)\bigr)}\right)

的界。 $K=0$ 回到最佳固定专家； $K$ 接近 $T$ 时基准过强，界可退化到线性。

adaptive regret

设动作集合为 $\mathcal K$ 。对任意时间区间 $I=[s,e]\subseteq[T]$ ，定义该区间相对最佳固定动作的遗憾

R_I=\sum_{t=s}^e\ell_t(a_t) -\min_{u\in\mathcal K}\sum_{t=s}^e\ell_t(u).

strongly adaptive regret 控制

\max_{I\subseteq[T]}R_I

，通常希望长度为 $|I|$ 的每个区间都有约 $\sqrt{|I|}$ 加对数项的保证。它不预先指定切换点，而要求任何观察窗口内都能与该窗口的固定最优者竞争。

区间保证可拼出 shifting regret：把比较序列的常值段分别看成区间并求和。但拼接会支付段数与对数开销；一个总区间上的低固定遗憾并不能反向推出所有子区间都低。

dynamic regret

在线凸优化中，允许比较器为动作路径 $u_{1:T}$ ：

R_T^{\mathrm{dyn}}(u_{1:T}) =\sum_{t=1}^T f_t(x_t)-\sum_{t=1}^Tf_t(u_t).

常用路径长度

P_T=\sum_{t=2}^T\|u_t-u_{t-1}\|

或函数变化量限制基准。若每轮 $u_t\in\arg\min_xf_t(x)$ 且 $P_T$ 小，目标是让界随 $P_T$ 平滑增长。没有任何变化约束时，对手可让逐轮最优动作不可预测地跳动，次线性 dynamic regret 一般不可能。

直觉

比较器越能随环境变化，基准越强，算法必须为它的切换数、路径长度或区间数量支付复杂度。变化预算既描述世界的非平稳程度，也决定算法应该保留多少历史、遗忘多快。

例子与边界

一个切换例子

服务器每天在“节能”与“高性能”两种策略中选择。前 60 天负载低，节能损失较小；随后活动流量持续上升，高性能更优。整个季度最佳固定策略可能只略胜学习器，使外部遗憾看似良好，却掩盖切换后一周的高延迟。shifting regret 以一次切换的比较器衡量是否跟上两个稳定阶段，adaptive regret 则还能检查任意一周窗口。

若负载每天随机翻转，声称存在一个“缓慢漂移的最佳策略”就不再符合数据。此时较大的 $K$ 或 $P_T$ 会如实使保证变松，而不是通过调一个常数继续给漂亮界。

算法机制

fixed-share 每轮把一小部分专家权重重新分散，防止曾经落后的专家永远无法复苏。区间专家方法为不同起点启动基础在线算法，再用元学习器组合它们，从而在每个区间保留一个“刚开始、未背负旧损失”的候选。dynamic regret 方法则常重启 OGD、使用预测梯度，或按路径长度自适应调整步长。

这些机制都在遗忘与稳定之间权衡。遗忘过慢追不上变化，过快则在稳定环境中反复丢掉积累的信息。变化预算不是装饰性的参数，而是决定合理遗忘尺度的比较器约束。

边界

adaptive regret 这里指时间区间上的遗憾，不是统计学习中“自适应选择模型”的泛化，也不同于 bandit 文献中特定的 adaptive adversary。使用术语时应同时写出比较器类和反馈协议。

任何动态界还要明确损失是凸、强凸还是一般有界，反馈是完整还是 bandit，以及对手能否看到当前随机动作。只报告 $O(\sqrt T)$ 而省略 $K$ 、 $P_T$ 或区间长度，会把问题中最重要的非平稳程度隐藏掉。

推论与应用

strongly adaptive 区间保证可以按比较器的常值段求和，从而导出 shifting regret；在线凸优化中的路径长度则把连续动作的漂移转成 dynamic regret。两条归约使用不同变化度量，不能只比较最终的 $T$ 次数。

概念漂移、负载切换和资产环境变化都可用这组基准评估，但反馈延迟、bandit 观测或预测梯度会改变可达速率。实践报告应同时给出静态遗憾与变化预算敏感的动态指标。

参考资料

Mark Herbster and Manfred Warmuth, “Tracking the Best Expert,” Machine Learning, 1998.
Martin Zinkevich, “Online Convex Programming and Generalized Infinitesimal Gradient Ascent,” ICML, 2003.
Elad Hazan and C. Seshadhri, “Adaptive Algorithms for Online Decision Problems,” Electronic Colloquium on Computational Complexity, Report TR07-088, 2007.

形式陈述 ​

shifting regret ​

adaptive regret ​

dynamic regret ​

一个切换例子 ​

算法机制 ​

边界 ​