Queue Length Regret Bounds for Contextual Queueing Bandits¶
会议: ICLR 2026
OpenReview: https://openreview.net/forum?id=bBPOcj5dOg
代码: 待确认
领域: 学习理论 / 在线学习 / 排队赌博机
关键词: 上下文排队赌博机、队列长度遗憾、策略切换队列、耦合论证、Logistic 赌博机
一句话总结¶
这篇论文提出"上下文排队赌博机"框架——在线学习未知服务率的同时给带异质上下文特征的任务做调度，并通过"策略切换队列 + 耦合"把队列长度遗憾分解开来，证明随机上下文下算法 CQB-ε 达到 \(\tilde{O}(T^{-1/4})\) 的衰减遗憾、对抗上下文下 CQB-Opt 达到 \(O(\log^2 T)\) 的多项式对数遗憾。
研究背景与动机¶
领域现状：云调度、推荐、网约车、呼叫中心、大模型推理等服务平台本质都是排队系统：任务排队等待，调度器把任务分配给服务器。当服务率未知时，"边调度边学"成了核心问题，主流做法是把它建成多臂赌博机（queueing bandits），并用队列长度遗憾（queue length regret）衡量策略好坏——即本策略与最优策略在队列长度上的差距。
现有痛点：已有的队列长度遗憾工作（Krishnasamy 2016 等）都假设所有任务同质，不考虑单个任务的上下文特征；而现代平台里任务天然异质（任务大小、用户画像、兼容设备各不相同）。最接近的 Kim & Oh (2024) 虽引入上下文，但要求固定数量的离散队列、同一队列内所有任务共享同一上下文，无法支持任意异质上下文；而且他们优化的是 MaxWeight 的累计权重，并不是真正的队列长度遗憾。
核心矛盾：一旦允许每个任务带不同的上下文特征，就出现一个本质性的分析障碍——队列状态错位（queue state misalignment）。本策略 \(\pi\) 和最优策略 \(\pi^*\) 可能以不同顺序处理任务，导致同一时刻两边队列里"剩下的任务特征列表"完全不同。已有分析全都依赖 \(\mathcal{X}_t^* = \mathcal{X}_t\)（两边队列状态一致）这个前提，一旦特征异质这个前提就崩了，遗憾根本无法逐时刻直接对比。
本文目标：(1) 建立支持异质上下文的排队赌博机框架；(2) 给出在队列状态错位下仍然可分析的队列长度遗憾分解工具；(3) 在随机和对抗两种上下文下分别设计算法并给出可证明的衰减/多项式对数遗憾界。
核心 idea：用一族"先跟本策略、某轮起切到最优策略"的策略切换队列做望远镜式拆分，再用耦合把相邻两条切换队列对齐，把整体遗憾化成"单轮次优选择的瞬时误差 × 该轮分歧对终点队列差的长期影响"的乘积之和，从而绕开队列状态错位。
方法详解¶
整体框架¶
问题设定：单队列、\(K\) 台服务器、离散时间 \(t\in[T]\)。每轮 agent 观察队列状态 \(X_t\subset\mathbb{R}^d\)（队列中剩余任务的特征向量集合），选一个任务 \(x_t\in X_t\) 并匹配一台服务器 \(k_t\)。是否完成服务由 logistic 模型决定：离开率为 \(\mu(x_t^\top\theta^*_{k_t})\)，其中 \(\mu(z)=(1+e^{-z})^{-1}\)，\(\theta^*_k\) 是服务器 \(k\) 的未知参数。队列按
演化（\(A(t)\) 是均值 \(\lambda\) 的到达、\(D(t)\) 是离开）。目标是控制队列长度遗憾 \(R_T=\mathbb{E}[Q(T)-Q^*(T)]\)，其中 \(\pi^*\) 是知道所有 \(\theta^*_k\)、每轮选离开率最大的任务-服务器对的最优策略。
整篇论文的"方法"由两条线构成：一条是通用的分析框架（策略切换队列 + 耦合 + 遗憾分解），它把队列长度遗憾化简成一个可控的乘积求和；另一条是两个具体算法（随机上下文的 CQB-ε、对抗上下文的 CQB-Opt），它们在这个框架下分别凑出衰减界和多项式对数界。分析框架是核心创新（解决队列状态错位），两个算法是把框架"用起来"的载体。
关键设计¶
1. 策略切换队列 + 耦合论证：把错位的两条队列对齐再逐项拆分
这是全文的命门，专治队列状态错位。直接比较 \(Q(t)\) 与 \(Q^*(t)\) 行不通，因为两策略处理顺序不同、队列里剩的特征不一样。作者定义策略切换队列 \(Q(t_1,t_2)\)：从 \(t=1\) 到 \(t_1\) 跟本策略、从 \(t_1+1\) 起切到最优策略，看 \(t_2\) 时刻的队列长度。它两端恰好退化成 \(Q(t_2-1,t_2)=Q(t_2)\) 和 \(Q(0,t_2)=Q^*(t_2)\)，于是队列长度遗憾被裂成望远镜和：
每一项只是"切换时刻相差一轮"的两条队列之差。为了比较这相邻两条队列，作者再构造一个耦合过程：对每轮的到达和离开各抽一个共享均匀随机数 \(U_{i,1},U_{i,2}\sim\text{Unif}(0,1)\)，让两条耦合队列 \(Q^+,Q^-\) 共用同样的到达判定、同样的离开阈值判定。耦合保持边际分布不变，于是 \(R_T=\sum_{t=1}^{T-1}\mathbb{E}[Q^+(t)-Q^-(t)]\)。由于两条耦合队列在第 \(t-1\) 轮前完全同策略，它们在 \(t\) 时刻状态一致——错位被"对齐"了。定义 \(\psi(t,T):=Q^+(t)-Q^-(t)\)，可证 \(\psi(t,T)\in\{-1,0,1\}\)（引理 4.1），且其期望被拆成两个因子的乘积（引理 4.2）：
\(m_t\) 是这一轮选了次优任务-服务器对造成的瞬时误差，\(\delta_t\) 是这轮分歧对终点队列差的长期影响。于是 \(R_T\le\sum_t m_t\delta_t\)。这个分解本身具有独立价值——它把"短期错配"和"长期波及"清晰解耦。
2. CQB-ε 两阶段算法：用单调性 + Chebyshev 求和不等式榨出 \(\tilde{O}(T^{-1/4})\) 衰减界
光有 \(R_T\le\sum m_t\delta_t\) 还不够：若直接用 Cauchy-Schwarz + 椭圆势引理只能得到 \(\tilde{O}(\sqrt T)\)，这是典型上下文赌博机的量级，但不衰减。关键观察是两个因子有相反的单调趋势：随着估计越来越准，\(m_t\)（瞬时误差）应当随 \(t\) 减小；而早期的一次分歧会在剩下 \(T-t-1\) 轮的相同最优策略下被"磨平"，所以 \(\delta_t\)（长期影响）应当随 \(t\) 增大。作者据此设计 CQB-ε——纯探索阶段先来 \(\tau=O(d\log T/(\sigma_0^4\epsilon^2))\) 轮，每来一个新任务就轮转（round-robin）地分给各服务器，把每台服务器的不确定项 \(\|x\|_{V^{-1}_{t-1,k}}\) 压到均匀可控（引理 5.2）；ε-探索阶段则以概率 \(\varepsilon=T^{-1/2}\) 随机探索、否则按 UCB 规则 \((x_t,k_t)=\arg\max\,\mu(x^\top\hat\theta_{t-1,k})+\beta_{t-1,k}\|x\|_{V^{-1}_{t-1,k}}\) 乐观选择。logistic 参数 \(\hat\theta_{t,k}\) 用正则化交叉熵 + 投影估计、置信半径 \(\beta_{t,k}=O(\sqrt{d\log T})\)（沿用 Faury et al. 2020）。
有了这套算法，作者证明 \(m_t\le M_t\)（\(\{M_t\}\) 不增）且 \(\delta_t\le\Delta_t\)（\(\{\Delta_t\}\) 不增的反面——不减）。对"一个不增序列 × 一个不减序列"求和，正好可用 Chebyshev 求和不等式：
再分别证 \(\sum M_t=\tilde O(T^{3/4})\)（前 \(\tau\) 轮贡献 \(\tau\)，之后 \(M_t=\tilde O(T^{-1}+\sqrt\varepsilon+1/\sqrt{\varepsilon t})\)，取 \(\varepsilon=T^{-1/2}\) 得 \(\tilde O(T^{3/4})\)）、\(\sum\Delta_t=O(\log T)\)（一个几何和被 \(O(1/\epsilon^3)\) 卡住），两者乘起来除以 \(T-1\)，得到定理 5.5 的衰减界，主导项是 \(\tilde O(T^{-1/4})\)。这说明随 \(T\) 增大，本策略与最优策略的队列长度差会消失。
3. CQB-Opt 应对抗上下文：数坏轮 + 加权过程换来 \(O(\log^2 T)\)
对抗设定下上下文由对手选，去掉 i.i.d. 假设 3.3。这时设计 2 的核心前提——"纯探索 \(\tau\) 轮后不确定项均匀有界"——失效了：坏轮（bad round，定义为 \(\|x_t\|_{V^{-1}_{t-1,k_t}}>\epsilon/(4\beta_{t-1,k_t})\) 即不确定项偏大）可能一直延续到接近终点，\(m_t\) 无法获得单调性，Chebyshev 那条路走不通。作者改走两步：一是数坏轮总数而非逐轮控制——用计数版椭圆势引理证 \(|B'|\le O(d^2\log^2 T/\epsilon^2)\)（命题 6.1）；二是处理"某轮是否坏轮"的随机性——定义 \(\mathcal{G}_t\)-可测的加权过程 \(V(t)=\alpha^{-B'(t-1)}e^{\eta Q(t)}\)（\(\alpha>1,\eta>0\)），借它给 \(Q(t)\) 拿到尾界，从而知道策略切换那一轮积压了多少任务。回到分解框架，对抗设定改用 Cauchy-Schwarz：\(R_T\le\sqrt{\sum m_t^2}\sqrt{\sum\delta_t^2}\)，其中 \(\sum m_t^2=O(d\log T)\)（始终乐观选择，离开率差被 2 倍 bonus 控住 + 椭圆势引理），\(\sum\delta_t^2\) 用基于坏轮数的阈值轮 \(\omega'=O(d^2\log^2 T/\epsilon^3)\) 控住（引理 6.2）。最终定理 6.3 给出 \(R_T=O\!\big(d^2\log^2 T/\epsilon^{1.5}+d\log T/\epsilon^2\big)\)，即多项式对数级遗憾，代价是比随机设定多了对数因子。
实验关键数据¶
主实验¶
随机实例参数 \(\lambda=0.7,\epsilon=0.1,K=5,d=5,\kappa=10\)；特征 \(x\) 与服务器参数 \(\theta^*_k\) 均从 \(\text{Unif}(-1,1)\) 采样；每算法跑 \(N=10\) 个实例、\(T=5000\) 轮，报告终点平均队列长度 ± 1 标准差。
| 策略 | 队列长度行为 | 说明 |
|---|---|---|
| 随机策略 | 线性增长 | 不学习，队列发散 |
| 最优策略 \(\pi^*\) | 最低基线 | 已知 \(\theta^*_k\) |
| CQB-ε（本文） | 先平台后骤降，趋近最优 | 纯探索后切 ε-greedy |
| CQB-Opt（本文） | 衰减趋近最优 | 适配对抗上下文 |
| 4 个额外 baseline | 见附录 A | 对比对象 |
两个本文算法在若干轮后都向最优队列长度收敛，而随机策略持续线性增长，验证了理论的衰减结论。
消融实验¶
| 配置 | 关键观察 | 说明 |
|---|---|---|
| CQB-ε，\(\epsilon\in\{0.05,0.1,0.15\}\) | \(\epsilon\) 越小纯探索越长，随后骤降 | \(\tau\) 随 \(\epsilon\) 反比变长 |
| CQB-Opt，\(\epsilon\in\{0.05,0.1,0.15\}\) | \(\epsilon\) 越大收敛越快 | 负载越低越快趋最优 |
（这里的 \(\epsilon\) 是假设 3.4 的流量松弛量 traffic slack，不是 ε-greedy 的探索率 \(\varepsilon=T^{-1/2}\)。）
关键发现¶
- \(\epsilon\)（流量松弛/系统负载裕度）越大，两个算法越快收敛到最优队列长度，和理论中 \(\tau,\omega'\) 关于 \(\epsilon\) 的依赖一致——负载越轻越容易稳定。
- CQB-ε 的曲线呈"先平台（纯探索期队列积压）后骤降"形态，直观印证了两阶段结构：探索期 \(\tau\) 由 \(\epsilon\) 决定，\(\epsilon\) 小则探索期长。
- 随机策略的线性发散反衬出"边学边调度"的必要性：不学习就无法稳定队列。
亮点与洞察¶
- 策略切换队列把"不可比"变"可比"：望远镜式拆分让你只需比较"切换时刻差一轮"的相邻队列，再配耦合把两条队列在分歧点前对齐，这是绕开队列状态错位的关键一招，对任何"两策略处理顺序不同导致状态发散"的在线决策问题都有借鉴意义。
- 短期/长期解耦的乘积分解：\(R_T\le\sum m_t\delta_t\) 把"这一轮选错"的瞬时代价和"这轮选错波及未来"的长期代价干净拆开，作者自评其具有独立价值。
- 用单调性 + Chebyshev 求和不等式拿衰减界：识别出 \(m_t\) 不增、\(\delta_t\) 不减这对相反趋势，正是 Chebyshev 求和不等式的用武之地，把朴素分析的 \(\tilde O(\sqrt T)\) 一举压成衰减的 \(\tilde O(T^{-1/4})\)——这个"识别单调性再套求和不等式"的套路很可迁移。
- 随机 vs 对抗用两套技术：随机设定靠"不确定项平滑过渡 → 两阶段 + 单调性"，对抗设定靠"数坏轮 + 加权过程处理随机性 → Cauchy-Schwarz"，清晰展示了同一分解框架下因假设不同而切换证明工具的思路。
局限与展望¶
- 单队列假设：当前框架只处理单队列，作者把多队列扩展列为未来方向，多队列下的状态错位会更复杂。
- 缺下界：只给了上界，是否 \(\tilde O(T^{-1/4})\)、\(O(\log^2 T)\) 已最优尚不清楚，作者明确把建立队列长度遗憾下界列为开放问题。
- 依赖较强结构假设：logistic 服务模型、流量松弛 \(\epsilon>0\)（假设 3.4 保证稳定）、随机设定下的协方差下界 \(\sigma_0^2>0\)（假设 3.3）等都较强；界对 \(\epsilon,\sigma_0\) 的多项式依赖（如 \(1/(\sigma_0^8\epsilon^5)\)）在重载或病态协方差下会变得很差。
- 未含运营约束：没有最大等待时间等实际约束，作者把"加入排队时间上限约束"列为未来工作。
- 实验规模偏小：\(d=K=5\)、\(T=5000\)、合成数据，距离真实平台（大模型推理调度等）尚有距离。
相关工作与启发¶
- vs 经典排队赌博机（Krishnasamy 2016 等）：他们开创队列长度遗憾并给出衰减界，但任务同质、无上下文，从而 \(\mathcal{X}_t^*=\mathcal{X}_t\) 始终成立、不存在状态错位；本文允许异质上下文，引入策略切换队列 + 耦合专门解决错位，是首个在上下文排队赌博机下给出队列长度遗憾衰减率的工作。
- vs Kim & Oh (2024)：他们也做上下文感知调度（基于 multinomial logit），但限制离散上下文向量数量、且优化 MaxWeight 的累计权重这一代理目标，缺真正的队列长度遗憾分析；本文支持任意异质上下文并直接分析队列长度遗憾。
- vs Logistic 赌博机（Filippi 2010、Faury 2020 等）：本文借用了他们的 logistic 参数估计与置信半径，但有两点本质差异——logistic 赌博机的动作集是外生且各策略共享的，而本文动作集内生且依赖策略（过去动作影响当前队列状态，导致错位）；且本文优化队列长度遗憾而非累计奖励遗憾，故已有 logistic 赌博机分析无法直接搬用，需要新技术。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首个上下文排队赌博机框架 + 全新的策略切换队列/耦合分解技术，解决了状态错位这一本质障碍。
- 实验充分度: ⭐⭐⭐ 合成数据、规模偏小，主要起验证理论作用，无真实平台与大规模验证。
- 写作质量: ⭐⭐⭐⭐ 挑战-技术-定理的脉络清晰，证明思路（单调性 + Chebyshev、数坏轮 + 加权过程）讲得到位。
- 价值: ⭐⭐⭐⭐ 把异质上下文引入队列长度遗憾分析，理论工具对在线决策/排队学习有迁移价值。