# Job Dispatching Policies for Queueing Systems with Unknown Service Rates

arXiv: https://arxiv.org/abs/2106.04707 · HTML: https://mlsanity.com/paper/2106.04707/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 29 references that are in the map.
- First posted on arXiv 8 Jun 2021.

## Builds on (most cited first, 2 of 2)

- [On Learning the cμ Rule in Single and Parallel Server Networks](https://mlsanity.com/paper/1802.06723/) (2018)
- [POND: Pessimistic-Optimistic oNline Dispatching](https://mlsanity.com/paper/2010.09995/) (2020)

## Built on by (most cited first, 12 of 12)

- [Learning While Scheduling in Multi-Server Systems with Unknown Statistics: MaxWeight with Discounted UCB](https://mlsanity.com/paper/2209.01126/) (2022)
- [Queue Length Regret Bounds for Contextual Queueing Bandits](https://mlsanity.com/paper/2601.19300/) (2026)
- [Learning-based Optimal Admission Control in a Single Server Queuing System](https://mlsanity.com/paper/2212.11316/) (2022)
- [Queue Scheduling with Adversarial Bandit Learning](https://mlsanity.com/paper/2303.01745/) (2023)
- [Bayesian Learning of Optimal Policies in Markov Decision Processes with Countably Infinite State-Space](https://mlsanity.com/paper/2306.02574/) (2023)
- [Learning payoffs while routing in skill-based queues](https://mlsanity.com/paper/2412.10168/) (2024)
- [Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret](https://mlsanity.com/paper/2606.09668/) (2026)
- [Learning to Admit Optimally in an M/M/k/k+N Queueing System with Unknown Service Rate](https://mlsanity.com/paper/2202.02419/) (2022)
- [Adversarial Network Optimization under Bandit Feedback: Maximizing Utility in Non-Stationary Multi-Hop Networks](https://mlsanity.com/paper/2408.16215/) (2024)
- [Learning Adaptive SED for heterogeneous load balancing](https://mlsanity.com/paper/2609.06881/) (2026)
- [Multi-Armed Bernoulli Bandits via Minimax Single-Arm Stopping](https://mlsanity.com/paper/2609.22690/) (2026)
- [Learning in Strategic Queuing with Geometric Recharge: From Bandits to Systems](https://mlsanity.com/paper/2610.19179/) (2026)

## Abstract (arXiv)

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.