技术摘要：$\Omega(\log(N)/N)$ 的前瞻时间足以限制过载损失网络的成本

1. 问题陈述

本文研究了具有可重用资源的过载损失网络中在线准入控制策略的性能。该模型由 $N$ 个服务器组成，为两类客户提供服务：高类型（$H$）客户支付溢价，低类型（$L$）客户支付折扣。系统处于过载状态，即总到达率超过了服务能力（$\lambda_H + \lambda_L > \mu$），但容量足以处理高优先级的 $H$ 类流量（$\lambda_H < \mu$）。因此，控制器必须拒绝部分 $L$ 类任务，以保留容量供未来的 $H$ 类任务使用。

核心挑战在于第一类错误（拒绝了一个本不会挤占 $H$ 类任务的 $L$ 类任务）与第二类错误（接受了一个会挤占未来 $H$ 类任务的 $L$ 类任务）之间的权衡。Xie 等人（2025）的前期工作已经确定，随着 $N \to \infty$，遗憾值（流近似上界与最优在线策略之间的差异）按 $\Theta(\log N)$ 的比例缩放。

文献中存在一个关键的歧义，即这种 $\Theta(\log N)$ 成本的来源。目前尚不清楚该成本是源于：

1. 变异性（Variability）： 到达过程和服务时间固有的随机波动，即使在拥有完美未来知识的情况下也会持续存在。
2. 不确定性（Uncertainty）： 对这些过程未来实现情况的知识缺失。

本文旨在分解这些成本，并确定限制运营成本所需的最小未来信息量（前瞻时间/lookahead）。

2. 研究方法

作者采用了一个分解框架，并构建了特定的算法来界定不同组成部分的遗憾值。

遗憾值分解

本文定义了四种奖励基准：

• $R^N_{fluid}$：流近似（确定性线性规划）。
• $R^N_{off}$：离线最优（已知所有未来的到达和处理时间）。
• $R^N_{W}$：具有 $W$ 小时前瞻窗口的最优策略。
• $R^N_{on}$：最优在线策略（无前瞻）。

总差距被分解为：
$$R^N_{fluid} - R^N_{on} = \underbrace{(R^N_{fluid} - R^N_{off})}_{\text{变异性成本 } (C^N_{vol})} + \underbrace{(R^N_{off} - R^N_{W})}_{\text{长期不确定性成本 } (C^N_{long})} + \underbrace{(R^N_{W} - R^N_{on})}_{\text{短期不确定性成本 } (C^N_{short})}$$

算法方法

为了分析这些成本，本文引入了两种基于“未来空闲承诺”（Promise of Future Idleness, PFI）概念的具体策略：

1. 未来空闲承诺 (PFI)： 该算法使用无限前瞻来决定是否准入。它仅在满足以下条件时接受 $L$ 类任务：在假设拒绝所有未来 $L$ 类任务（同时接受所有 $H$ 类任务）的过程中，空闲服务器计数在达到 $\lfloor \sqrt{N} \rfloor$ 之前不会跌破 1。该策略作为离线最优的代理，用于界定变异性成本。
2. 单次短传感器 (Single Short Sensor, SSS)： 该算法使用有限的前瞻窗口 $W$。如果满足以下条件，则接受 $L$ 类任务：在假设的“拒绝所有 $L$ 类”场景下，空闲服务器计数在至少 $W$ 小时内保证保持在 1 以上。窗口大小设定为 $W = \Omega(\log(N)/N)$。

分析工具

证明过程依赖于将系统的无限维状态空间简化为有限状态马尔可夫链。

• 马尔可夫约简（Markovian Reduction）： 作者定义了一组辅助变量（例如：自上次拒绝以来的时间、自上次接受以来的时间、剩余服务时间等），以捕捉未来事件的条件分布。
• 更新奖励定理（Renewal Reward Theorem）： 将时间划分为独立的“历元”（epoch，即特定状态重置，如空闲服务器计数降至 1 之间的时期）。通过界定这些历元内的预期空闲量和拒绝率来分析长期平均奖励。
• 耦合与随机游走（Coupling and Random Walks）： 通过将空闲服务器过程与具有特定漂移率的随机游走进行比较来界定其行为，利用切尔诺夫界（Chernoff bounds）来建立偏差的指数尾概率。

3. 主要贡献与结果

定理 1：有界的变异性成本

本文证明了变异性成本是有界的：
$$C^N_{vol} = R^N_{fluid} - R^N_{off} = O(1) \quad \text{当 } N \to \infty \text{ 时。}$$
意义： 这一结果确立了流近似与离线最优在渐近意义上是等价的。Xie 等人（2025）确定的 $\Theta(\log N)$ 差距并非由于系统的固有波动性引起的。即使拥有完美的未来知识，系统也无法获得显著高于流上界的奖励。这种“过剩”的波动性被拒绝的 $L$ 类任务的盈余所吸收，从而平滑了到达和离开过程的不规则性。

推论 1：对数级不确定性成本

由于总差距为 $\Theta(\log N)$ 且变异性成本为 $O(1)$，因此总不确定性成本必须为：
$$C^N_{long} + C^N_{short} = \Theta(\log N).$$

定理 2：有界的长期不确定性成本

本文展示了大小为 $W = \Omega(\log(N)/N)$ 的有限前瞻窗口足以限制长期不确定性成本：
$$C^N_{long} = R^N_{off} - R^N_{W} = O(1) \quad \text{当 } W \geq \Omega\left(\frac{\log N}{N}\right) \text{ 时。}$$
意义： 这意味着在线系统的整个 $\Theta(\log N)$ 遗憾值完全源于短期不确定性（即在接下来的 $O(\log N / N)$ 小时内发生的事件）。预见接下来的 $O(\log N)$ 个客户（因为每小时到达 $\Theta(N)$ 个）足以实现与离线最优相当的性能。

推论 2：对数级短期不确定性成本

因此，短期不确定性成本（有限前瞻策略与在线策略之间的差距）为：
$$C^N_{short} = \Theta(\log N).$$

4. 重要性与主张

本文声称解决了关于过载损失网络中遗憾值来源的歧义。

1. 成本归因： 主要贡献在于将 $\Theta(\log N)$ 的性能差距完全归因于不确定性而非变异性。系统不需要为了应对内在波动而准备大量的空闲服务器缓冲；如果未来情况已知，一个有界的缓冲就足够了。
2. 短前瞻的充分性： 本文确立了 $\Omega(\log(N)/N)$ 的前瞻窗口足以限制运营成本。这是一个重要的实际洞察，表明在具有预订制度的行业中（如酒店、手术调度），即使是相对较短的预测时界也能消除大部分与不确定性相关的性能差距。
3. 与单次使用资源的区别： 本文将可重用资源与单次使用资源（动态随机背包）进行了对比。在后者中，离线-在线差距是 $O(1)$（有界的）。在可重用资源中，由于服务时间的复合性质以及无法“重置”资源，差距是无界的（$\Theta(\log N)$）。然而，本文表明这种无界差距是由信息的缺乏驱动的，而非资源本身的性质。
4. 方法论进展： 这项工作将量化未来信息需求（此前已应用于 M/M/1 排队论）的范式扩展到了更复杂的损失网络设置中。在损失网络中，状态（服务中的任务数）会影响服务率，且空闲服务器计数的漂移会发生符号切换，这使得分析难度显著增加。

总之，本文认为无需通过“平滑”波动来解决问题；相反，“预见”一段时间内的波动便足以限制成本。$\Theta(\log N)$ 的遗憾值是对看不见近期未来的惩罚，而不是系统固有波动性的根本限制。