arXiv:2601.19300cs.LG2026-01被引 2

提出新框架,让系统在学习服务速度中优化排队调度。

Queue Length Regret Bounds for Contextual Queueing Bandits

  • 基于上下文特征选择任务与服务器配对,动态学习服务速率。
  • 理论证明算法队列长度后悔值上界为 $\widetilde{\mathcal{O}}(T^{-1/4})$。
  • 适用于需要实时调度且服务率未知的场景,如云资源分配。

我们引入上下文感知排队带宽(contextual queueing bandits),一种在学习未知服务速率的同时进行调度的新框架。不同任务具有异质性上下文特征,代理根据这些特征选择任务并匹配服务器以最大化离开率。服务/离开率由上下文特征的逻辑回归模型决定,参数为服务器特有且未知。性能评估采用队列长度后悔值,即策略与最优策略间队列长度之差。主要挑战在于:由于处理顺序不同,各策略下队列中剩余任务特征列表可能不同。为此,我们提出策略切换队列与精巧耦合论证,建立新的队列长度后悔分解框架,可分析次优任务-服务器配对的短期影响及其对队列状态差异的长期作用。我们提出的算法CQB-$\varepsilon$实现 $\widetilde{\mathcal{O}}(T^{-1/4})$ 的后悔上界。针对对抗性上下文设置,第二个算法CQB-Opt达到 $\mathcal{O}(\log^2 T)$ 的后悔上界。实验验证了理论结果。

原文摘要 · Abstract (English)

We introduce contextual queueing bandits, a new context-aware framework for scheduling while simultaneously learning unknown service rates. Individual jobs carry heterogeneous contextual features, based on which the agent chooses a job and matches it with a server to maximize the departure rate. The service/departure rate is governed by a logistic model of the contextual feature with an unknown server-specific parameter. To evaluate the performance of a policy, we consider queue length regret, defined as the difference in queue length between the policy and the optimal policy. The main challenge in the analysis is that the lists of remaining job features in the queue may differ under our policy versus the optimal policy for a given time step, since they may process jobs in different orders. To address this, we propose the idea of policy-switching queues equipped with a sophisticated coupling argument. This leads to a novel queue length regret decomposition framework, allowing us to understand the short-term effect of choosing a suboptimal job-server pair and its long-term effect on queue state differences. We show that our algorithm, CQB-$\varepsilon$, achieves a regret upper bound of $\widetilde{\mathcal{O}}(T^{-1/4})$. We also consider the setting of adversarially chosen contexts, for which our second algorithm, CQB-Opt, achieves a regret upper bound of $\mathcal{O}(\log^2 T)$. Lastly, we provide experimental results that validate our theoretical findings.

排队调度在线学习后悔分析

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。