2021/06/10 by Tuhinangshu Choudhury, Gauri Joshi, Weina Wang +1 · 19 citations
Computer Science · Decision Sciences · Engineering · Mathematics · #Advanced Bandit Algorithms Research #Advanced Wireless Network Optimization #Bulk queue #Computer network #Computer science #Distributed computing #Economics #Fork–join queue #Mathematical optimization #Mathematics #Operations research #Queue #Queue management system #Queueing theory #Real-time computing #Regret #Server #Service (business) #Set (abstract data type) #Smart Grid Energy Management #cs.LG #cs.SY #eess.SY
paper · pdf · doi:10.1145/3466772.3467047
arxiv created 2021/06/10 · arxiv updated 2021/06/11 · openalex publication_date 2021/06/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
In multi-server queueing systems where there is no central queue holding all incoming jobs, job dispatching policies are used to assign incoming jobs to the queue at one of the servers. Classic job dispatching policies such as join-the-shortest-queue and shortest expected delay assume that the service rates and queue lengths of the servers are known to the dispatcher. In this work, we tackle the problem of job dispatching without the knowledge of service rates and queue lengths, where the dispatcher can only obtain noisy estimates of the service rates by observing job departures. This problem presents a novel exploration-exploitation trade-off between sending jobs to all the servers to estimate their service rates, and exploiting the currently known fastest servers to minimize the expected queueing delay. We propose a bandit-based exploration policy that learns the service rates from observed job departures. Unlike the standard multi-armed bandit problem where only one out of a finite set of actions is optimal, here the optimal policy requires identifying the optimal fraction of incoming jobs to be sent to each server. We present a regret analysis and simulations to demonstrate the effectiveness of the proposed bandit-based exploration policy.