在线算法与竞争分析 — 计算理论

绝大多数算法课教的是这样一个世界：输入摆在你面前，你可以从容读完再决定怎么做。

现实系统很少有这种奢侈。缓存要在不知道下一次访问什么的情况下决定淘汰谁；调度器要在不知道后续任务的情况下派活；云平台要在不知道明天流量的情况下决定扩不扩容；广告系统要在用户点击的那一瞬间决定投给谁，而预算是有限的。

这类问题的共同结构是：请求一个接一个到来，每个决策必须在看到后续请求之前做出，而且不可撤销。 它们被称为在线问题，而衡量在线算法好坏的尺子，与离线算法完全不同。

破除误解：竞争比不是"跟最优解差多少"那么简单

第一，比较对象是一个作弊的对手。 竞争分析把在线算法的代价与离线最优解（OPT，事先知道整个请求序列的最优决策）相比。若对任意请求序列都有

$\mathrm{ALG}(\sigma) \le c \cdot \mathrm{OPT}(\sigma) + b$

则称算法是 $c$-竞争的。关键在于 OPT 拥有在线算法原理上不可能拥有的信息——未来。因此竞争比衡量的不是"算法有多笨"，而是不知道未来这件事本身要付出多少代价。一个 2-竞争的算法可能已经是理论最优，再聪明也无法更好。

第二，它是最坏情况分析，且对手会针对你。 竞争比要求对所有请求序列成立，而分析中的对手可以看着你的算法构造最恶毒的输入。这解释了一个常见困惑：为什么 LRU 在理论上的竞争比很差，实践中却表现优异？因为真实访问序列有局部性，而对手构造的序列没有。竞争比给出的是保证，不是预测。

第三，随机化在这里带来的收益是本质性的。 对确定性算法，对手知道你的每一步，可以精确地反着来；一旦引入随机，对手只能针对你的分布而非具体选择。这个差距往往是指数级的——从"与缓存大小成正比"降到"与缓存大小的对数成正比"。随机化在这里不是为了平均更快，而是为了让对手无从下手。

核心一：三个把直觉训练出来的问题

滑雪租赁问题。 滑雪板租一天 1 元，买断 $B$ 元。你不知道这个雪季还会滑几天，每天都要决定租还是买。

最优的确定性策略是：先租 $B-1$ 天，第 $B$ 天买。若之后不再滑雪，你花了 $2B-1$，而事后诸葛的最优是 $B$，竞争比约为 2；可以证明没有确定性算法能做得更好。引入随机化后，最优竞争比降到 $\frac{e}{e-1} \approx 1.58$ 。

这个玩具问题的形状在真实系统里到处出现：要不要为一次可能持续也可能不持续的负载去买预留实例、建缓存、开新连接。 "先付租金，累计到与买断相当时再买"是一条被反复重新发现的工程直觉，而竞争分析告诉你它恰好是最优的。

分页与缓存置换。 缓存能放 $k$ 页，请求的页不在缓存中就要换出一页。Sleator 与 Tarjan 在 1985 年的论文中提出竞争分析框架，并证明：LRU 与 FIFO 都是 $k$-竞争的，而且任何确定性在线算法的竞争比都不可能优于 $k$——对手只需在每次你换出某页后立刻请求它。

这个 $k$ 看起来是个坏消息，却是理论最有价值的部分：它说明 LRU 的"差"不是设计缺陷，而是信息缺失的必然代价。随机化的标记算法（marking algorithm）可以把竞争比降到 $O(\log k)$ ，这是随机化威力的教科书例证。

秘书问题。 $n$ 位候选人依次面试，每次面试后必须立刻决定录用或永久放弃，目标是选中最好的那一位。最优策略是：先观察前 $n/e$ 位只看不选，之后录用第一个优于此前所有人的候选人，成功概率约 $1/e \approx 37\%$ 。

这个 $1/e$ 是在线决策理论中最优雅的常数之一，也是"探索—利用"权衡在最简形式下的解。

核心二：k-服务器问题——领域的中心猜想

把上述问题一般化：度量空间中有 $k$ 个服务器，请求在空间中的某点出现，你必须移动某个服务器去响应，代价是移动距离。分页是它在均匀度量下的特例。

Manasse、McGeoch 与 Sleator 在 1988 年提出 k-服务器猜想：任意度量空间上都存在 $k$-竞争的确定性在线算法。这个猜想至今未被证明也未被推翻，是在线算法领域的中心问题。目前最好的一般性结果来自 Koutsoupias 与 Papadimitriou（1995）：工作函数算法是 $(2k-1)$-竞争的——把上界拉到了正确的数量级，但那个因子 2 三十年来无人消除。

k-服务器之所以重要，不只因为难，还因为它是度量任务系统这一大类问题的核心：任何"维持一组资源的配置、按需重配置并支付移动成本"的问题都能归到这个框架——数据副本放置、虚拟机迁移、CDN 内容调度都是它的变体。

核心三：在线匹配与一个价值千亿的定理

1990 年，Karp、Vazirani 与 Vazirani 研究了在线二部图匹配：图的一侧顶点事先已知，另一侧顶点逐个到来并暴露其邻边，必须立即决定与谁匹配。

他们证明了 RANKING 算法——事先给已知一侧的顶点随机排一个序，每个到来的顶点匹配给它可用邻居中排名最靠前的那个——达到 $1 - 1/e \approx 0.632$ 的竞争比，并且这是任何在线算法的上界。

十几年后，这个理论结果成了搜索广告的数学基础：广告主有预算（已知一侧），搜索查询逐个到来（在线一侧），平台必须即时决定展示谁的广告。AdWords 问题及其后续变体（带预算、带权重、随机到达模型）构成了在线算法少有的、直接支撑起数百亿美元产业的应用。这也是"纯理论问题在二十年后变成基础设施"的典型样本。

核心四：走出最坏情况——带预测的算法

竞争分析的批评由来已久：它太悲观，无法区分"在真实负载下表现优异"与"在真实负载下同样糟糕"的两个算法。多年来有三条修补路线。

资源增强：给在线算法比 OPT 更多的资源（更大的缓存、更快的机器），再比较代价。Sleator 与 Tarjan 早就注意到，缓存加倍的 LRU 相对原始缓存的 OPT 竞争比是常数——这远比 $k$-竞争更贴近实际观察。

平滑分析：对最坏输入加入小扰动后再分析，用于解释单纯形法等"理论差、实践好"的算法。

带预测的算法（learning-augmented algorithms），2018 年后的主流方向：给算法一个可能不准的预测器（例如用机器学习预测下一次访问时间、任务时长、未来负载），要求算法同时满足两个性质——一致性（预测准时接近最优）与鲁棒性（预测任意错时不比经典在线算法差太多）。

这条路线之所以重要，是因为它精确刻画了工程界一直在做但说不清的事：用机器学习指导系统决策，同时保证学错了也不会崩。 滑雪租赁、缓存置换、调度与排队都已有形式化的一致性—鲁棒性权衡曲线，而这条曲线本身是可证明的：想要更好的一致性，就必须接受更差的鲁棒性上界，反之亦然。这把"要不要信任模型"从工程直觉变成了可以标价的设计参数。

代价与争议

竞争比在系统社区的接受度一直不高。 一个 $k$-竞争的界对缓存工程师几乎没有指导意义，而理论社区花了很多年才承认这一批评的正当性。带预测的算法与资源增强正是这场长期分歧催生的和解产物。

对手模型的选择影响结论。 随机化算法面对"遗忘型对手"（事先固定序列）与"自适应对手"（看着你的随机选择实时构造）的竞争比可以差很多，而文献中不总是说清用的是哪一种。这是阅读在线算法结果时最常见的隐含前提。

预测器的来源被理论回避了。 带预测框架把预测器当作黑盒，不追问它从哪来、训练分布是否匹配、预测误差是否与请求序列相关。而在实践中，预测器失效的时刻往往恰好就是负载异常的时刻——也就是最需要它准确的时刻。这个相关性目前几乎没有被建模。

未知的边界

k-服务器猜想是否成立？$(2k-1)$ 与 $k$ 之间那个因子 2 是分析技术的不足，还是真实的下界？
带预测算法的一致性—鲁棒性权衡，在多大范围内存在统一的刻画？现有结果多是逐问题定制的。
能否形式化"预测误差与请求难度正相关"这一现实特征，并给出相应的保证？
在线学习（后悔最小化）与在线算法（竞争分析）是两套平行发展的理论，二者的统一框架是否存在？
对带切换成本的在线凸优化，最优的一般性算法是什么？这直接对应云资源的弹性伸缩。
分布式与并发环境下的在线决策（多个决策者、信息不完全共享）缺乏可比拟的理论，这与真实系统的形态差距最大。

跨域连接

近似算法理论：两者都在"无法达到最优"的前提下量化差距，但受限的资源不同——近似算法受限于计算时间，在线算法受限于信息。一个问题可以在线难而计算易，也可以反过来；把两种受限叠加（多项式时间的在线算法）才最贴近真实系统，而这类结果远少于单独受限的情形。
缓存策略：LRU 的 $k$-竞争下界解释了一个重要的工程事实——缓存命中率的提升不可能靠更聪明的置换算法无限榨取，收益的天花板由信息缺失决定。这正是工业界把力气转向预取、分层与工作集感知的理论依据：那些手段改变的是信息条件，而不是决策规则。
随机化算法：在线场景是随机化威力最纯粹的展示——它带来的不是常数因子的加速，而是竞争比从 $k$ 到 $\log k$ 的数量级改善，原因不是概率上的平均更好，而是隐藏信息使对手失去针对性。这与密码学中随机数的作用同源：随机性在这里是对抗性场景下的资源。
强化学习：探索—利用权衡与在线决策处理的是同一族问题，但假设不同：强化学习通常假设环境是（可能随机的）固定过程，可以从中学习；竞争分析假设环境是对抗的，不可学习。带预测的算法正是这两套假设的接缝——用学习获得的信号驱动决策，用最坏情况保证兜住学习失败。
风险与不确定性：秘书问题与滑雪租赁在决策论中有直接对应，而竞争分析提供了一种与期望效用不同的评价准则——不问"平均会怎样"，而问"最坏情况下相对于事后最优损失多少"。这恰好对应奈特意义上不可概率化的不确定性：当你无法给未来赋予分布，最小最大后悔就成了唯一还站得住的准则，而竞争比正是它的算法版本。

参考文献

Sleator, D. D. & Tarjan, R. E. Amortized Efficiency of List Update and Paging Rules. Communications of the ACM 28(2), 202–208, 1985.
Manasse, M., McGeoch, L. & Sleator, D. Competitive Algorithms for On-line Problems. STOC 1988.
Koutsoupias, E. & Papadimitriou, C. On the k-Server Conjecture. Journal of the ACM 42(5), 971–983, 1995.
Karp, R. M., Vazirani, U. V. & Vazirani, V. V. An Optimal Algorithm for On-line Bipartite Matching. STOC 1990.
Lykouris, T. & Vassilvitskii, S. Competitive Caching with Machine Learned Advice. ICML 2018.

破除误解：竞争比不是"跟最优解差多少"那么简单#

核心一：三个把直觉训练出来的问题#

核心二：k-服务器问题——领域的中心猜想#

核心三：在线匹配与一个价值千亿的定理#

核心四：走出最坏情况——带预测的算法#

代价与争议#

未知的边界#

跨域连接#

参考文献#

延伸阅读#