RPB 论文解读 | 赵海亮

RPB 将“对预测的信任”变成一项需要记账的资源。只有相对于最优鲁棒在线基线积累了足够预算，算法才允许预测改变淘汰决策。由此，完美预测可以带来离线最优性能，任意错误预测也不会导致失控的最坏情况代价。

1-consistency下一次到达时间预测完全准确时，达到离线最优。

\(H_k+O(1)\) 鲁棒性最坏竞争比达到最优量级，仅相差加性常数。

对数平滑性性能随归一化预测误差逐步退化，而非突然失效。

1. 问题是什么

缓存最多容纳 \(k\) 个页面，请求序列 \(\sigma=\langle p_1,\ldots,p_n\rangle\) 在线到达。每次缺页产生单位代价，并可能需要淘汰一个已有页面。Belady 策略会淘汰未来最晚再次访问的页面，但它必须预知完整请求序列。

竞争性能 \[ \operatorname{cost}(A,\sigma) \leq \alpha\,\operatorname{cost}(\mathrm{OPT},\sigma)+c. \] 经典随机分页算法能够达到最优竞争比 \(H_k=\sum_{i=1}^{k}1/i\)。学习增强算法的目标，是在预测准确时靠近 OPT，在预测错误时仍保留同等级别的上界。

需要同时回答三个问题

一致性

预测完全准确时，竞争比应尽可能小。RPB-OM 达到 \(1\)，也就是离线最优。

鲁棒性

预测任意错误时，代价仍需被可靠在线算法约束。RPB-OM 达到 \(H_k+O(1)\)。

平滑性

当误差为 \(\eta_1\) 时，性能应逐步变差。RPB-OM 达到 \(O(1+\log(\eta_1/\operatorname{cost}(\mathrm{OPT})))\)。

根本矛盾

预测淘汰可以改善一致性，也可能让缓存偏离鲁棒基线。算法必须为这种偏离付出可分析的代价。

2. 以往的信任规则为什么仍有缺口

已有方法也会限制预测的使用，但记账方式较粗。全局切换只看累计代价，可能错过局部仍然可靠的预测；固定长度的淘汰链阈值，则可能在误差较大时过度信任预测，在误差较小时又过早停用预测。

预测质量具有局部性。同一预测器可能在一段淘汰链上很准确，在下一段突然失效，仅靠全局分数无法表达这种变化。
信任必须有参照物。有意义的参照不是经过了多少时间，而是可靠基线在相同状态下取得了多少进展。
偏离基线必须付费。预测决策会扩大两个缓存状态之间的差异，因此需要消耗一种能进入理论分析的资源。

3. 相对预测预算

RPB 建立在 ONOPT 之上。ONOPT 利用工作函数的分层结构，始终维护一个有效缓存配置。其高效实例 OnlineMin（OM）与最优竞争随机算法保持相同的配置分布，每次请求只需 \(O(\log k)\) 的更新时间。

算法维护一个非负预算 \(B\)。请求落入零层 \(L_0\) 时，意味着当前不确定性最大。此时若发生缺页，RPB 按预测执行淘汰，并将 \(B\) 重置为常数 \(\tau\)。之后遇到惰性对手请求时，算法比较此前预测淘汰与 OM 基线的实际进展，再判断是否赚到新的预算。

一次 RPB-OM 决策循环

请求到达确定其工作函数层，并构造 OM 候选集。

\(L_0\) 缺页按预测的下一次到达顺序淘汰，并令 \(B\leftarrow\tau\)。

衡量进展记录上次缺页后未揭示层数 \(U(\omega)\) 的变化。

预算门控仅当
\(U(\omega)\leq\)
\((Y+2)/e-2\)
时赚取一个单位。

选择淘汰若 \(B>0\)，采用预测并消耗一点预算；否则跟随 OM。

这里的预算不是预测器给出的置信度，而是算法在线观察到的证据：近期预测淘汰相对于鲁棒基线确实有效。

为什么用未揭示层数做门控

令 \(U(\omega)=k-|R(\omega)|\) 表示未揭示的工作函数层数。惰性请求逐步揭示这些层时，OM 的势函数至少按调和量下降。门控条件据此判断，基线是否已经积累足够进展，从而为下一次预测偏离付费。算法无需显式模拟 OM 的完整缓存分布，就能把预测有效性与鲁棒性精细关联起来。

4. 证明为什么成立

证明没有单独估算预测淘汰的代价，而是把三部分放进同一个势函数：

RPB-OM 的势函数 \[ \Phi(\omega)=\phi(\omega)+D(\omega)+B(\omega). \] 其中 \(\phi\) 是 OM 面对后续惰性对手时的期望代价，\(D\) 是 RPB-OM 与 OM 的期望缓存差异，\(B\) 是尚未花费的预测预算。

在 \(L_0\) 缺页时，算法可能同时增加缓存差异与预算，但相对于 OM 的 \(H_k-1\) 势函数变化，只多出 \(O(1)\)。后续惰性请求中，预测缺页会消耗预算，跟随 OM 的缺页则会缩小缓存差异，两种情况的摊还代价都不为正。将这些不等式累加，便得到最坏情况结论。

“接近最优”具体指什么？ 若要求严格的 \(H_k\) 鲁棒性，算法必须完全跟随经典最优在线算法，无法真正使用预测。RPB-OM 达到 \(H_k+O(1)\)，对使用预测的算法而言，仅留下一个加性常数。

5. 实验回答了什么

论文在 SPEC CPU 2006 内存轨迹上同时使用合成对数正态噪声，以及 PLECO、POPU 两个真实预测器。下表为论文报告的平均结果，代价比越低越好，命中率越高越好。

真实下一次到达预测器上的平均结果
方法	PLECO		POPU
方法	代价比	命中率	代价比	命中率
BlindOracle	1.404	15.92	1.261	21.75
BlindOracle & LRU	1.286	20.53	1.230	23.10
ONOPT-OM	1.253	22.42	1.237	23.76
RPB-OM，\(\tau=1\)	1.249	22.75	1.220	24.34
RPB-OM，\(\tau=2\)	1.252	22.70	1.215	24.49
RPB-OM，\(\tau=4\)	1.254	22.64	1.213	24.55

1.249PLECO 上的最佳平均代价比，由 \(\tau=1\) 的 RPB-OM 取得。

1.213POPU 上的最佳平均代价比，由 \(\tau=4\) 的 RPB-OM 取得。

对 \(\tau\) 不敏感从 \(1\) 调整到 \(4\) 时结果变化很小，降低了实际调参负担。

合成噪声实验回答的是另一层问题：预测越差，完全依赖预测的方法退化越明显，而 RPB-OM 的代价始终受到控制。两类实验共同说明，理论保证并非只起防守作用，算法仍能从真实预测器中获得实际收益。

6. 可以迁移的设计思想

这项工作最值得迁移的，是一种在线记账原则：学习信号不能凭置信度直接获得决策权，而要凭相对于安全基线的可观测进展赚取决策权。这一思路还可用于调度、准入控制、资源分配等预测有价值但失效代价必须受控的系统问题。

Towards Optimal Robustness in Learning-Augmented Paging