在线算法与竞争分析

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

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

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

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

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

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

还有一层常被忽略的细节：竞争比允许一个与输入无关的加性常数 $b$。真正关心的是渐近倍率 $c$，而不是小实例上的绝对差距。工程读论文时若把"2-竞争"误读成"永远多花一倍钱"，会把可部署的算法当成不可用；反过来，若只盯平均案例而完全丢掉竞争保证，又会在对抗性负载（恶意爬虫、突发热点、缓存毒化）上没有下限。竞争分析的价值恰在于它强迫你先问：在信息永久缺失时，最坏能差多少——再决定要不要用分布假设去换更好的期望。

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

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

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

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

把滑雪租赁再推一步：若"买断价"本身会随时间变（预留实例打折窗口、硬件折旧、合同阶梯价），确定性策略仍可按累计租金与当前买断价的交叉点做决策，但最优竞争比不再是干净的 2，而取决于价格路径的形状。随机化策略则要把买断时刻抽成一个分布，使期望代价对任意持续天数都尽量贴近事后最优——这正是后来"带切换成本的在线决策"与云弹性伸缩共用的骨架。

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

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

分页还有一个常被工程师忽视的推论：确定性下界 $k$ 与随机化上界 $O(\log k)$ 之间的鸿沟，并不能用"把 LRU 调得更聪明"来填平。任何确定性规则——无论是时钟、LFU 变体还是带启发式的混合——在对抗序列下都逃不出 $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 内容调度都是它的变体。

工作函数算法的直觉并不神秘：每一步它都选择一个配置，使"到目前为止已付的移动代价 + 到该配置的最小未来补齐代价"最小——也就是始终盯着一个与历史一致的潜在离线最优。难点在证明：这个近视选择不会在长期被对手拉开到超过 $2k-1$ 倍。三十年来，改进的尝试多落在特殊度量（树、线、有限度量）上取得 $k$-竞争，一般度量仍卡在因子 2。对工程读者，这意味着：在近似均匀的资源池上可以更乐观，在异构、高延迟拓扑上则应预期更接近一般上界。

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

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

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

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

后续工作把 RANKING 扩展到带权重与预算的情形：广告主有每日预算上限，展示有质量分与出价，平台要在线决定是否展示、展示谁。原始—对偶（primal-dual）方法成为主流武器——为每个广告主维护一个对偶变量（可理解为预算消耗的影子价格），到来的查询按"质量调整后的剩余价值"贪心匹配。竞争比仍常落在 $1-1/e$ 附近，但分析从组合计数转向了连续对偶更新。对系统实现者，这意味着：预算节流不应是事后砍流量，而应是在线更新的价格信号。

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

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

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

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

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

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

一个可操作的例子是带预测的缓存：若预测器给出"下一访问时间"，算法可优先驱逐预测最远的页；但若预测任意错，必须平滑退回到类似标记算法的随机化保证。形式化后得到一条曲线——一致性参数 $\alpha$ 与鲁棒性参数 $\beta$ 不可同时任意好。部署时你选的是曲线上的一点：模型置信高就偏向 $\alpha$，流量异常检测触发就滑向 $\beta$。这比"模型准确率 90% 所以信任它"远更可审计。

代价与争议#

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

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

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

此外，竞争分析与后悔最小化（regret minimization）长期各说各话。前者问"相对事后最优差几倍"，后者问"相对最好固定策略累计差多少"。云调度、广告竞价、内容推荐往往同时需要两者：短期突发要竞争保证，长期策略选择要低后悔。把两套语言接起来的工作仍稀缺，导致同一系统的不同模块用不同尺子，跨模块调参时缺少共同语义。

未知的边界#

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

值得单独标出的是度量任务系统（metrical task systems）：状态有移动代价，任务到来后你必须转到某个状态并支付服务费。k-服务器是其子类。一般性的确定性竞争比与状态数相关，随机化可显著改善；但一旦加入预测或切换延迟，最优策略的结构仍不清晰。云中的"配置切换"（改副本数、换机型、迁可用区）几乎就是带延迟的度量任务系统——理论缺口直接对应运维手册里说不清的那类权衡。

跨域连接#

• 近似算法理论：两者都在"无法达到最优"的前提下量化差距，但受限的资源不同——近似算法受限于计算时间，在线算法受限于信息。一个问题可以在线难而计算易，也可以反过来；把两种受限叠加（多项式时间的在线算法）才最贴近真实系统，而这类结果远少于单独受限的情形。
• 缓存策略：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.

延伸阅读#

• Borodin, A. & El-Yaniv, R. Online Computation and Competitive Analysis. Cambridge University Press, 1998.
• Mehta, A. Online Matching and Ad Allocation. Foundations and Trends in Theoretical Computer Science, 2013.
• Roughgarden, T. (ed.). Beyond the Worst-Case Analysis of Algorithms. Cambridge University Press, 2021.
• Purohit, M., Svitkina, Z. & Kumar, R. Improving Online Algorithms via ML Predictions. NeurIPS 2018.