调度算法研究者可以关注这个将队列长度遗憾率提升至理论最优的成果，CQB-η-2的三阶段设计思路值得借鉴。
本文针对上下文队列调度问题，提出CQB-η-2算法，将队列长度遗憾从O(T^{-1/4})提升至O(T^{-1/2})，达到理论最优。算法分为三个阶段：纯随机探索构建初始估计、η随机探索结合UCB规则维持负漂移、纯UCB决策。关键创新在于仅在截止轮前进行随机探索，之后利用已积累样本进行确定性调度。作者还证明了Ω(T^{-1/2})的极小化下界，表明该算法在T的依赖上达到最优。
Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret
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^{-1/4})$ queue length regret, defined as the expected difference between the learner's and oracle's queue lengths at horizon $T$. In this paper, we improve this rate to $\widetilde{\mathcal{O}}(T^{-1/2})$. The key observation is that random exploration is needed only up to a carefully chosen cutoff round, rather than throughout the entire horizon. We propose CQB-$η$-2, a three-phase algorithm: (i) pure random exploration to construct an initial estimator, (ii) $η$-random exploration combined with a UCB rule to continue learning while maintaining negative drift, and (iii) pure UCB after the exploration cutoff. Our proof decomposes the queue length regret at the cutoff round. Before the cutoff, negative drift suppresses queue length differences caused by suboptimal choices. After the cutoff, the first two phases provide sufficient random exploration samples, ensuring that UCB decisions incur small departure-rate gaps. Combining these two bounds yields queue length regret of order $\widetilde{\mathcal{O}}(T^{-1/2})$. We further prove a minimax lower bound of order $Ω(T^{-1/2})$. The proof constructs two hard instances that are statistically indistinguishable up to the final service decision, and uses a queue-specific coupling argument to convert the resulting testing error into queue length regret. Together, our upper and lower bounds characterize the minimax dependence on the horizon $T$ up to logarithmic factors.