A Parameter-Free Best-of-Both-Worlds Policy for Queueing Bandits

Jongyeong Lee, Chansoo Kim

We study online channel scheduling for a single queue served by $K$ channels under bandit feedback. We propose a simple best-of-both-worlds policy that explores when the queue is empty. During busy periods, it selects the empirical best channel while the prescribed conditions hold and, if any condition is violated, switches to a robust bandit policy to clear the queue. For arbitrary arrivals and services determined by an oblivious adversary, our policy achieves $\tilde{\mathcal{O}}(\sqrt{K L_T})$ worst-case queue length regret with high probability, where $L_T$ is the longest busy-period length. This result improves the previous $T^{3/4}$ dependence and matches the worst-case lower bound up to logarithmic factors. Under bounded i.i.d. stochastic models with a unique best stabilizing channel, we show that the cumulative queue length regret converges to a finite problem-dependent constant, and further establish the logarithmic expected worst-case queue length regret bound.