Best policy improves queue scheduling for multiple channels
A Parameter-Free Best-of-Both-Worlds Policy for Queueing Bandits
Machine Learning
Summary
The paper looks at how to schedule jobs in a queue when you have multiple channels that can process them, but you only get limited feedback about each channel’s performance. The authors propose a new policy that cleverly balances exploring different channels when there’s no queue and exploiting the best-known channel when the queue is busy. This policy adapts dynamically to the situation and achieves much better performance guarantees than previous methods, handling both worst-case and typical random scenarios effectively. Their results improve on past work and match theoretical lower bounds in hard cases.
What this means in practice
- •For network schedulers: Optimize packet scheduling over multiple channels to reduce queue delays even with uncertain channel performance observed only via limited feedback.
- •For cloud service operators: Improve resource allocation in cloud systems by adaptively selecting among available servers to maintain low request queues under changing conditions.
Authors
Jongyeong Lee, Chansoo Kim
Abstract
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.