Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret¶

会议: NeurIPS 2026
arXiv: 2606.09668
论文: https://arxiv.org/abs/2606.09668
领域: 优化/理论
关键词: 排队老虎机, 上下文老虎机, 队列长度遗憾, 速率最优, 阶段截断探索

一句话总结¶

针对未知服务率下的异构任务调度问题，提出三阶段算法 CQB-$\eta$-2，通过在临界轮次截断随机探索并转向纯 UCB 调度，将随机上下文排队老虎机的队列长度遗憾从 $\widetilde{\mathcal{O}}(T^{-1/4})$ 提升至速率最优的 $\widetilde{\mathcal{O}}(T^{-1/2})$，并建立了匹配的 $\Omega(T^{-1/2})$ 极大极小下界。

研究背景与动机¶

排队系统是现代云计算、大规模在线服务系统、呼叫中心乃至多大语言模型（Multi-LLM）智能调度平台的基础设施。在这些系统中，任务随时间动态到达，服务资源容量有限，系统必须在服务速率未知的情况下在线决策：为当前队列中的任务匹配合适的服务节点，既要快速学习未知服务参数，又要维持队列的长期稳定。传统排队老虎机（Queueing Bandits）通常假设服务节点的离去概率与任务本身的特征无关，无法刻画具有强异构上下文特征的实际负载。上下文排队老虎机（Contextual Queueing Bandits, CQB）通过逻辑斯蒂回归等广义线性模型刻画“任务上下文-服务节点”对的离去概率，成功扩展了模型能力。

然而，现有随机上下文排队老虎机理论存在一个显著的理论瓶颈：前序工作所能达到的最优队列长度遗憾界仅为 $\widetilde{\mathcal{O}}(T^{-1/4})$。传统老虎机以累积奖励遗憾（Cumulative Regret）为优化指标，经典界通常为 $\mathcal{O}(\sqrt{T})$；但排队系统关注的是终端视界 $T$ 处的队列长度差距 $\mathbb{E}[Q(T) - Q^*(T)]$。直觉上，由于队列自带负漂移（Negative Drift）的几何消减记忆效应，历史次优决策对远期队列长度的影响应随时间指数衰减，终端队列遗憾理应具备达到 $\widetilde{\mathcal{O}}(T^{-1/2})$ 的潜力。现有工作之所以受困于 $T^{-1/4}$，根源在于算法设计和证明技术的耦合缺陷：旧方案为了在全时程上保证设计矩阵的特征值连续增长，必须在整个视界 $T$ 内自始至终执行随机探索，而持续的随机扰动不可避免地向队列注入了不必要的额外排队积压。

本文抓住这一核心矛盾，提出全新的探索范式：随机探索仅在学习初始参数与累积足够样本的前中期是必需的，一旦收集到 $\Theta(T)$ 个高质量特征样本，参数估计精度便足以支撑纯贪心/UCB 决策，此时必须坚决截断随机探索。核心 idea：设计纯随机探索、$\eta$-混合探索与纯 UCB 调度三阶段算法 CQB-$\eta$-2，在保证队列负漂移的同时适时截断随机探索，并利用耦合过程在截断点解耦误差传播与离去率间隙，首次实现速率最优的 $\widetilde{\mathcal{O}}(T^{-1/2})$ 队列长度遗憾。

方法详解¶

整体框架¶

算法考虑单队列、多服务器（$K$ 台）离散时间系统。每轮 $t$，外部按概率 $\lambda$ 独立到达新任务，其上下文特征 $x^{(t)} \sim \mathcal{D}$；若队列非空，调度器从当前队列状态 $\mathcal{X}_t$ 中选取任务-服务器对 $(x_t, a_t)$ 投入服务，其离去服从参数为 $\boldsymbol{\theta}^*$ 的逻辑斯蒂模型 $\mu(\langle \boldsymbol{\phi}(x_t, a_t), \boldsymbol{\theta}^* \rangle)$。系统的核心挑战是在平衡队列漂移与参数探索的前提下，平滑度过不同学习阶段。

CQB-$\eta$-2 算法显式划分三个运行阶段：在 $t \leq \tau_1$ 时为第一阶段（纯随机探索），强制所有到达任务随机分配服务器以构建正则化协方差矩阵的基底；在 $\tau_1 < t \leq \tau_2$ 时为第二阶段（$\eta$-混合探索），新到达任务以固定概率 $\eta = \epsilon/4$ 随机探索，其余情况采用 UCB 规则，既利用 UCB 的高离去率维持负漂移，又持续收集 $\Theta(T)$ 阶探索样本；在 $t > \tau_2$ 时为第三阶段（纯 UCB 调度），彻底截断随机探索，仅依靠前期累积的高精度置信球选择 UCB 最大的任务-服务器对。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["轮次开始：观察队列状态与新到达任务"] --> B["阶段划分判断与探索概率配置"]
    B --> C["阶段一：纯随机探索<br/>快速累积初始样本，确保特征多样性"]
    B --> D["阶段二：η-混合探索与漂移控制<br/>以 ε/4 概率探索并保持队列负漂移"]
    B --> E["阶段三：截断探索与纯 UCB 调度<br/>停止随机探索，依靠高精度模型贪心清空队列"]
    C --> F["执行服务决策并观察二进制离去反馈"]
    D --> F
    E --> F
    F --> G["正则化逻辑斯蒂 MLE 与自适应置信球更新<br/>更新参数估计与逆协方差设计矩阵"]

关键设计¶

1. 阶段划分与探索截断机制：从持续扰动到精准切断 以往算法之所以在全时程维持探索，是为了满足策略切换解耦引理对单调估计误差的要求。CQB-$\eta$-2 打破了这种保守性，精准设计了两个相变切断点 $\tau_1$ 和 $\tau_2$。$\tau_1$ 确定了纯探索所需的最少轮次，确保设计矩阵最小特征值跨越燃烧期（Burn-in），使得第二阶段开始时 UCB 的预测不确定度缩减至流量裕度（Traffic Slackness）$\epsilon$ 的可控量级（即 $2\beta_{t-1} \|\boldsymbol{\phi}\|_{\mathbf{V}_{t-1}^{-1}} \leq \epsilon/4$）。而第二阶段的终止点 $\tau_2 = T - \frac{4\tau_1}{\epsilon} - \frac{128\log(T)}{\epsilon^2} - 1$ 则保证了两项关键性质：一方面在 $[\tau_1, \tau_2]$ 区间内收集至少 $\Theta(T)$ 个随机探索样本，使得进入第三阶段时最小特征值满足 $\lambda_{\min}(\mathbf{V}_{\tau_2}) = \Omega(T)$；另一方面预留给第三阶段纯 UCB 调度的剩余时长为 $\Theta(\tau_1/\epsilon + \log(T)/\epsilon^2)$，使得无随机扰动下的排队系统能够以最优速率消除此前产生的排队偏差。

2. 负漂移约束下的混合探索：在学习收益与排队积压间构建平衡 如果在学习初期直接执行 UCB，尚未收敛的参数可能导致调度器连续选择劣质服务节点，造成队列漂移反转为正甚至无限发散。为此，第二阶段引入了精确校准的 $\eta$-探索率 $\eta = \epsilon/4$。假设系统存在流量松弛度 $\epsilon$（即最优离去概率满足 $\mu^* \geq \lambda + \epsilon$），当且仅当发生新任务到达时才触发伯努利硬币 $E(t-1) \sim \text{Bern}(\epsilon/4)$。在该设计下，条件预期离去概率为： $$ \mathbb{E}[D(t) \mid \mathcal{F}_t] \geq \mu^* - \eta - \frac{\epsilon}{4} \geq \lambda + \epsilon - \frac{\epsilon}{4} - \frac{\epsilon}{4} = \lambda + \frac{\epsilon}{2} $$ 这保证了条件净漂移 $\mathbb{E}[A(t) - D(t) \mid \mathcal{F}_t] \leq -\epsilon/2$ 严格恒负。通过将漂移控制显式纳入探索概率的参数化设计中，排队系统在不破坏稳定性的前提下，安全地为阶段三储备了充足的协方差样本。

3. 解耦误差传播的双尺度上界分析：时间分割技巧 在分析队列长度遗憾 $R_T = \sum_{t=1}^{T-1} \mathbb{E}[\psi_t(T)]$ 时，传统方法将单步影响拆为 $\sqrt{\mathbb{E}[(\text{gap}_t)^2]} \cdot \sqrt{\mathbb{E}[\widetilde{\psi}_t(T)]}$，并对两项在全视界套用统一收缩界。本文在临界点 $\tau_2$ 进行巧妙的时间截断：对于前期 $t \leq \tau_2$，直接使用平凡离去率间隙上界 $\text{gap}_t \leq 1$，但由于距终端 $T$ 尚有至少 $\Omega(\epsilon^{-2}\log T)$ 轮负漂移步数，排队扰动存活概率呈指数衰减，得出 $\sqrt{\mathbb{E}[\widetilde{\psi}_t(T)]} \leq \mathcal{O}(T^{-2})$，前期总和直接收敛至 $\mathcal{O}(T^{-1})$；对于后期 $t > \tau_2$，扰动存活因子放缩为平凡上界 $1$，但此时依托阶段二累积的 $\Theta(T)$ 样本，离去率间隙由置信椭球半径除以特征值下界严格控制为 $\mathcal{O}(T^{-1/2})$。两个区间的乘积积分最终成功打破瓶颈，达到 $\widetilde{\mathcal{O}}(T^{-1/2})$。

4. 匹配的极小化极大下界构造：双实例假设检验与排队耦合 为了确立该速率的理论极限，定理 10 证明了任意策略在满足特征多样性与流量松弛的实例类上必然承受 $\Omega(T^{-1/2})$ 的队列长度遗憾。证明构造了一对统计上极难区分的硬实例 $\nu_T^+$ 与 $\nu_T^-$，两者的最优服务器集合呈互补对称结构，离去率差距仅为 $\Delta_T = \Theta(T^{-1/2})$。通过 Bretagnolle-Huber 不等式与 KL 散度链式法则，在倒数第二轮 $T-2$ 发生任务到达的条件下，调度器在第 $T-1$ 轮做出错误分配的检验错误概率有恒定常数下界 $e^{-1/6}/2$。结合排队状态转移的单步耦合分析，错误分配必然以正概率导致最终队列长度多出 1 个任务，从而严密论证了 $T^{-1/2}$ 的不可超越性。

损失函数 / 训练策略¶

算法使用带 $\ell_2$ 正则化的对数似然损失更新模型参数估计 $\widehat{\boldsymbol{\theta}}_t$： $$ \widehat{\boldsymbol{\theta}}t = \arg\min|_2^2 $$ 协方差矩阵按秩 1 累加更新 } \in \Theta} \sum_{i=1}^t \left[ -D(i)\log \mu(\langle \boldsymbol{\phi}_i, \boldsymbol{\theta} \rangle) - (1 - D(i))\log(1 - \mu(\langle \boldsymbol{\phi}_i, \boldsymbol{\theta} \rangle)) \right] + \frac{\lambda_0}{2} |\boldsymbol{\theta$\mathbf{V}_t = \mathbf{V}_{t-1} + \boldsymbol{\phi}_t \boldsymbol{\phi}_t^\top$（初始为 $\lambda_0 \mathbf{I}$）。置信椭球半径 $\beta_t$ 严格定义为： $$ \beta_t = \kappa \sqrt{0.5 d \log(1 + t/(\kappa \lambda_0 d)) + 0.5 \log(1/\delta)} + S \sqrt{\kappa \lambda_0} $$ 在实践中，设置信度参数 $\delta = T^{-4}$（实验中取 $\delta = T^{-1}$ 并配以常数缩放因子 $0.1$），保证置信边界在整个时程内以极大概率包络真实参数。

实验关键数据¶

主实验¶

实验在合成上下文排队系统上进行评测。系统配置为时程 $T=2000$，特征维度 $d=10$，服务器数量 $K=5$，到达率 $\lambda=0.7$，松弛度 $\epsilon=0.1$，逻辑斯蒂非线性常数 $\kappa=50$。各策略在 10 次独立重复实验下的终端队列长度遗憾表现对比如下：

算法策略	算法机制特征	理论遗憾速率	终端遗憾 $\mathbb{E}[Q(T)-Q^*(T)]$	稳定性表现
CQB-$\eta$-2 (本文)	三阶段截断探索 (0.2T / 0.3T)	$\widetilde{\mathcal{O}}(T^{-1/2})$	0.42 ± 0.15	最优，收敛迅速且方差极小
CQB-$\varepsilon$	持续固定概率探索 ($\tau=0.2T$)	$\widetilde{\mathcal{O}}(T^{-1/4})$	0.95 ± 0.28	次优，后期受残存随机探索扰动
ACQB	随时间衰减探索 $\mathcal{O}(1/\sqrt{t})$	$\widetilde{\mathcal{O}}(T^{-1/4})$	2.18 ± 0.62	衰减初期探索不足致漂移轻微受损
FIFO + Random	最早到达任务优先 + 随机服务节点	$\Omega(T)$	14.85 ± 2.10	缺乏特征学习，队列严重积压
Pure Random	完全随机选择任务与服务器	$\Omega(T)$	28.60 ± 3.45	严重拥塞，队列持续线性膨胀

消融实验¶

针对 CQB-$\eta$-2 的核心机制与环境超参数进行参数敏感度与消融分析（以基准环境 $T=2000$ 为基础）：

配置 / 变体	核心变动设置	终端遗憾 $R_T$	关键机制影响说明
CQB-$\eta$-2 基准	$\epsilon = 0.10, K = 5, \tau_2 = 0.3T$	0.42 ± 0.15	完整三阶段，负漂移与精确截断协同
流量裕度宽松 ($\epsilon=0.15$)	服务容量更加充裕	0.26 ± 0.10	负漂移增强，历史扰动衰减速率加快
流量裕度吃紧 ($\epsilon=0.05$)	服务容量接近临界到达率	0.88 ± 0.32	负漂移较弱，历史差异存活时间延长
多服务器扩展 ($K=3$)	候选服务器较少	0.38 ± 0.12	动作空间小，特征覆盖迅速完成
多服务器扩展 ($K=10$)	候选服务器较多	0.49 ± 0.18	空间扩大，但探索截断机制依然稳定
无阶段三 (持续 $\eta$-探索)	移除截断，持续探索至 $T$	1.12 ± 0.35	证实后期无节制探索会损害终态遗憾

关键发现¶

阶段三截断的决定性作用：对比 CQB-$\eta$-2 与无截断的 CQB-$\varepsilon$，终端队列遗憾降低了 50% 以上。实验曲线清晰表明，在 $t > 0.3T$ 截断探索后，CQB-$\eta$-2 的平均队列长度迅速下探并紧贴 Oracle 轨迹，消除了持续探索带来的不可逆队列波动。
流量松弛度 $\epsilon$ 对收敛的支配性：随着 $\epsilon$ 从 0.05 增至 0.15，队列遗憾呈现急剧下降趋势，这与理论上 $\exp(-\epsilon^2(T-t)/32)$ 的指数收敛因子高度吻合，说明充足的服务冗余能够快速冲刷掉探索期带来的次优排队积压。
服务器规模可扩展性良好：从 $K=3$ 扩展到 $K=10$ 时，终端遗憾仅轻微上升（0.38 → 0.49），证明基于特征多样性假设下的随机均匀采样能够高效覆盖多服务器空间。

亮点与洞察¶

跳出“持续探索”的思维定势：排队系统的马尔可夫演化具备自发恢复性，前期造成的排队误差只要有负漂移存在就会指数级“自愈”。作者敏锐意识到这一特性与传统累积遗憾问题的根本不同，果断在有限时间内切断随机探索，成为突破 $T^{-1/4}$ 理论壁垒的破局点。
排队耦合分析与统计下界的结合：在证明极小化极大下界时，巧妙避开了状态全轨迹的复杂遍历分析，聚焦于 $T-2$ 与 $T-1$ 轮的边缘差分事件，将信息论下界通过单步单任务离去概率与排队耦合单调性无损转化为排队长度遗憾。
算法设计理念对分布式调度的启示：这一“启动期探索、成熟期纯贪心”的范式非常适合工业级 LLM 集群路由调度系统，在冷启动期对异构模型进行轻量试探，模型画像稳定后直接转入纯确定性最优吞吐路由。

局限与展望¶

理论下界在维度与非线性参数上尚未紧致：作者在结论中明确指出，当前的 $\Omega(T^{-1/2})$ 下界仅精确表征了视界 $T$ 的紧依赖，在维度 $d$ 以及逻辑斯蒂极小导数倒数 $\kappa$ 的依赖上与上界相比仍留有理论间隙。
相变切断点需要预知视界 $T$ 与松弛度 $\epsilon$：参数 $\tau_1$ 与 $\tau_2$ 的闭式解依赖于全局视界 $T$ 及流量松弛下界 $\epsilon$。在动态长周期运行或流量参数随时间未知的无视界（Anytime / Horizon-free）自适应场景下，如何自适应确定截断时刻仍有待探索。
单队列单任务服务模型与批处理场景的差距：系统模型设定为单队列、每轮仅单任务被分配服务，尚未涵盖并发服务、成批到达或网络化排队系统（Network of Queues）。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次打破上下文排队老虎机 $T^{-1/4}$ 长期停滞，建立速率最优的 $T^{-1/2}$ 遗憾界并构造匹配下界。
实验充分度: ⭐⭐⭐⭐ 仿真实验紧扣理论预期，验证了截断探索的有效性与参数敏感性，若能补充真实系统 trace 表现将更加完善。
写作质量: ⭐⭐⭐⭐⭐ 理论推导清晰优美，策略切换耦合与分段积分证明逻辑层层递进，动机阐述极其透彻。
价值: ⭐⭐⭐⭐⭐ 为排队控制与在线学习的交叉前沿树立了新的理论标杆，对大模型推理池动态路由调度极具实际借鉴价值。

算法策略	算法机制特征	理论遗憾速率	终端遗憾 \(\mathbb{E}[Q(T)-Q^*(T)]\)	稳定性表现
CQB-\(\eta\)-2 (本文)	三阶段截断探索 (0.2T / 0.3T)	\(\widetilde{\mathcal{O}}(T^{-1/2})\)	0.42 ± 0.15	最优，收敛迅速且方差极小
CQB-\(\varepsilon\)	持续固定概率探索 (\(\tau=0.2T\))	\(\widetilde{\mathcal{O}}(T^{-1/4})\)	0.95 ± 0.28	次优，后期受残存随机探索扰动
ACQB	随时间衰减探索 \(\mathcal{O}(1/\sqrt{t})\)	\(\widetilde{\mathcal{O}}(T^{-1/4})\)	2.18 ± 0.62	衰减初期探索不足致漂移轻微受损
FIFO + Random	最早到达任务优先 + 随机服务节点	\(\Omega(T)\)	14.85 ± 2.10	缺乏特征学习，队列严重积压
Pure Random	完全随机选择任务与服务器	\(\Omega(T)\)	28.60 ± 3.45	严重拥塞，队列持续线性膨胀

配置 / 变体	核心变动设置	终端遗憾 \(R_T\)	关键机制影响说明
CQB-\(\eta\)-2 基准	\(\epsilon = 0.10, K = 5, \tau_2 = 0.3T\)	0.42 ± 0.15	完整三阶段，负漂移与精确截断协同
流量裕度宽松 (\(\epsilon=0.15\))	服务容量更加充裕	0.26 ± 0.10	负漂移增强，历史扰动衰减速率加快
流量裕度吃紧 (\(\epsilon=0.05\))	服务容量接近临界到达率	0.88 ± 0.32	负漂移较弱，历史差异存活时间延长
多服务器扩展 (\(K=3\))	候选服务器较少	0.38 ± 0.12	动作空间小，特征覆盖迅速完成
多服务器扩展 (\(K=10\))	候选服务器较多	0.49 ± 0.18	空间扩大，但探索截断机制依然稳定
无阶段三 (持续 \(\eta\)-探索)	移除截断，持续探索至 \(T\)	1.12 ± 0.35	证实后期无节制探索会损害终态遗憾