精选理由
调度算法研究者可以关注这个将队列长度遗憾率提升至理论最优的成果，CQB-η-2的三阶段设计思路值得借鉴。
本文针对上下文队列调度问题，提出CQB-η-2算法，将队列长度遗憾从O(T^{-1/4})提升至O(T^{-1/2})，达到理论最优。算法分为三个阶段：纯随机探索构建初始估计、η随机探索结合UCB规则维持负漂移、纯UCB决策。关键创新在于仅在截止轮前进行随机探索，之后利用已积累样本进行确定性调度。作者还证明了Ω(T^{-1/2})的极小化下界，表明该算法在T的依赖上达到最优。
AI 翻译 · 中文
本文针对上下文队列调度问题，提出CQB-η-2算法，将队列长度遗憾从O(T^{-1/4})提升至O(T^{-1/2})，达到理论最优。算法分为三个阶段：纯随机探索构建初始估计、η随机探索结合UCB规则维持负漂移、纯UCB决策。关键创新在于仅在截止轮前进行随机探索，之后利用已积累样本进行确定性调度。作者还证明了Ω(T^{-1/2})的极小化下界，表明该算法在T的依赖上达到最优。
Contextual queueing bandits provide a framework for learning to schedule heterogeneous jobs under unknown context-dependent service rates. Under stochastic contexts, existing algorithms achieve $\widetilde{\mathcal{O}}(T…