在线算法若能预知未来，往往可以作出更好的决定；但预测一旦失准，也可能在最关键的时刻误导系统。这篇综述围绕这一矛盾展开，重点区分三个问题：预测器提供什么信息，算法以何种机制使用预测，以及定理究竟证明了什么。
1. 为什么不能只按应用领域梳理
经典在线算法在不知道未来的条件下作出决策。它们的最坏情况保证可靠，但面对高度可预测的负载时往往偏保守。纯学习策略则作出相反选择，利用历史规律追求平均性能，却未必能说明在分布变化甚至对抗性输入下会发生什么。
学习增强算法把可能出错的预测嵌入一个可证明的算法中。它并不等于“机器学习模型加一个兜底策略”。预测接口、误差定义、兜底状态和优化目标都属于证明的一部分。即便两项工作都预测下一次请求时间，如果误差归一化方式或比较基准不同，它们的结论也未必能够直接比较。
2. 基本契约：好预测应当有用，坏预测不能让代价失控
设 (I) 为问题实例，(hat y) 为预测结果，(y^*(I)) 为尚未知晓的真实目标，(eta(I,hat y)) 为任务相关的预测误差。学习增强算法 (A) 与离线最优解 (operatorname{OPT}(I)) 比较。综述用 (lambdain[0,1]) 表示事先选定的信任参数，(lambda) 越小，算法越信任预测。
这三项性质有关联，却不能彼此替代。一个随误差无限增长的平滑性上界，并没有给出与预测无关的鲁棒性；一致性只说明误差恰好为零时的表现，不能自动说明小误差下是否稳定；只有同一形式化模型中的下界排除了所有更优组合，一致性与鲁棒性的折中曲线才能称为紧致。
滑雪租赁问题把折中关系讲得最清楚
假设每天租雪具的成本为 1，直接购买的成本为 (B)，预测器给出滑雪天数。参数化算法在 (lambda) 较小时更相信预测。一类经典规则具有如下保证：
预测完全准确时，第二项给出 (1+lambda) 的一致性；无论预测错得多严重，第一项都把竞争比限制在 (1+1/lambda) 以内。更信任预测可以改善一致性，但会放宽最坏情况上界。
3. 选算法之前，先说明究竟预测什么
预测输出本身就是问题定义的一部分。综述区分四类常见任务对象，并把不确定性信息和语义表示视为额外的接口属性。
点预测
输出一个标量或向量，例如运行时长、作业规模或下一次请求时间。绝对误差和相对误差会导出不同结论。
分布预测
输出概率分布，并直接参与搜索或调度。定理必须明确分布距离及其正则条件。
序关系预测
输出排序或成对比较。此时真正有意义的误差可能是逆序数，而非数值距离。
结构预测
输出匹配、对偶解、边集等组合对象，供算法修复或作为优化的初始解。
误差度量不是论文中的附属指标，它决定定理认为哪些错误更昂贵。真实目标何时可观测也同样关键。如果误差只能在不可逆决策之后得到，它可以用于事后评估，却不能直接指导当下的信任调整。
4. 预测进入可证明算法的五种方式
综述的第一条分类轴不按应用领域划分，而是追问预测在构造中出现在哪里。五种机制并不互斥，同一篇论文可以同时具有多个标签。
- P1：基于信任的组合。 把预测驱动方法与不依赖预测的基线进行混合或插值。运行前一次性随机选择算法，与运行中动态切换算法并非同一机制；后者还要计算状态迁移成本。
- P2：预测引导的原始对偶方法。 预测用于初始化、引导或修复原始变量和对偶变量。证明真正依赖的是可行性与对偶不变量，单独给出一个预测对偶解并不会自动带来保证。
- P3：预测敏感的松弛与舍入。 预测先改善分数解，再由兼容的在线舍入定理得到整数决策。舍入因子可能主导最终竞争比，也可能使完美预测下的结果仍无法达到精确最优。
- P4：预测访问、组合与切换。 算法决定何时查询预测器，以及跟随哪个预测器或策略。替代损失上的低遗憾只有经过任务相关的代价归约、状态兼容分析和合理比较基准，才能转化为在线问题的性能结论。
- P5：分布预测。 预测分布直接改变搜索、调度或其他决策规则。误差相关结论始终依赖具体的分布距离与目标函数，不能把 Wasserstein 距离或某种风险度量直接泛化成通用的系统代价定理。
5. 第二条分类轴：别把“已有上界”和“达到极限”混为一谈
分类轴 B 独立记录定理层面的证据。E0 表示综述记录了已达到的上界，但在同一模型中没有配对记录匹配的下界。E1 表示在相同预测模型、误差度量、对手、比较基准和计算条件下，上下界具有匹配的渐近依赖关系。
| 代表性结果 | 构造机制 | 证据 | 含义 |
|---|---|---|---|
| 确定性滑雪租赁 | P1 | E1 | 该模型中的渐近折中关系已匹配 |
| 使用下一次到达预测的缓存算法 | P1 | E0 | 已知上下界之间仍有差距 |
| 使用分布预测的二分搜索 | P5 | E1 | 对分布误差的依赖关系已匹配 |
| 受限访问预测器的度量任务系统 | P4 | E0 | 已知下界仍留有对数因子 |
E0 不是对工作价值的否定，E1 也不是成熟度排名。紧致性不能跨不同模型移植。经验性的系统结果则单独标注，因为实测性能与竞争分析回答的是两类问题。
6. 同一套框架覆盖的是不同目标
综述沿着五类机制考察了在线优化、缓存与分页、学习型数据结构、图算法与网络，以及机制设计五个领域。跨领域梳理可以看出反复出现的证明工具，也提醒我们不能把所有结论排在同一把尺子上。不同问题关注的可能是竞争比、近似质量、查询复杂度、运行时间或社会福利。
例如，学习型索引可以围绕预测位置搜索一个经过认证的区间，从而保持查询正确性。这是很有价值的保证，但并不自动等价于针对更新延迟的一致性与鲁棒性定理。又如，机制设计除了满足可行性，还必须保持激励相容，因此其他领域的鲁棒化方法不能在不检查博弈模型的情况下直接照搬。
7. 从单个定理走向实际运行的系统
组件定理通常只分析一个预测接口和一个目标。真实部署则把预测、决策、执行和反馈串联起来，还可能共享计算资源和系统状态。综述把三个常被组件分析省略的问题单独提出：
- 预测不是免费的。 模型推理、查询、重训练和数据采集都消耗时间与资源，而经典竞争分析通常不会计入这些成本。
- 误差可能延迟出现，也可能由策略自身造成。 真值可能在行动之后才能得到，可能被行动遮蔽，也可能因为策略改变了未来观测而发生变化。
- 组件并非彼此独立。 上游输出会改变下游看到的实例、状态和离线最优基准，因此局部竞争比不能自动组合成系统级竞争比。
把预测成本计入目标后，原有结论会改变
如果一次预测调用在系统目标中折算为成本 (c)，算法共调用 (Q_A) 次，综述提出如下记账量：
若离线最优基准无需承担预测成本，而完美预测下算法仍然必须付出正的期望调用成本，那么精确的乘法型 1-一致性就不可能成立，除非模型允许加性项，或者重新定义比较基准。
组件组合需要接口事实，不能只拿局部竞争比相乘
综述为三种组合方式给出了有限的充分条件。加性组合要求各组件代价与离线基准能够在每条执行路径上统一分解；级联组合要求明确上游对下游基准造成多大扭曲；误差传播则要求每条连接边都具备合适的度量和类似 Lipschitz 的敏感性：
如果某条接口没有合理的度量、敏感性上界或扰动模型，这套推导就不能把上游平滑性转移到下游。
8. 当预测器开始输出自然语言
多数学习增强定理接收的是数值、排序、分布或组合结构，而基础模型可能输出自由文本。要让这类输出进入形式化算法，首先需要适配器把文本映射成类型明确的任务对象，再定义下游定理能够使用的误差。
作为预测器
输出时长、顺序等形式化对象。解析过程和定理要求的误差假设仍需成立。
作为适配器
从文本抽取结构化输入。验证机制必须覆盖适配器自身的失败方式。
作为策略生成器
提出规则或兜底策略。生成物仍然需要验证和部署控制。
作为解释器
为运维人员整理遥测信息。输出会影响行动，因此仍需标明来源与不确定性。
词元概率并不自动等于任务正确率，多个采样结果相互一致也只说明自洽性，不等于经过标签验证的准确率。语义推理可以提供有价值的信息，但若没有新的信息模型和证明，它不会自动改进已有的算法保证。
9. 接下来值得研究什么
综述最后提出四组相互关联的问题：如何在优化目标中给预测定价，如何建立更一般的组合演算，如何处理由策略引起的误差以及对抗性和策略性误差，如何让实验基准真正可比较。贯穿全文的方法论是，预测应被视为一种类型明确、可能出错并且具有成本的算法输入，而不是笼统的“智能”。任何保证都属于预测、决策、状态、目标与比较基准构成的完整契约。