# Learning Unknown Service Rates in Queues: A Multi-Armed Bandit Approach

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Apr 2016.

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

- [Learning and Information in Stochastic Networks and Queues](https://mlsanity.com/paper/2105.08769/) (2021)
- [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)
- [Online Learning and Optimization for Queues with Unknown Demand Curve and Service Distribution](https://mlsanity.com/paper/2303.03399/) (2023)
- [Bayesian Learning of Optimal Policies in Markov Decision Processes with Countably Infinite State-Space](https://mlsanity.com/paper/2306.02574/) (2023)
- [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)
- [To Analyze and Regulate Human-in-the-loop Learning for Congestion Games](https://mlsanity.com/paper/2501.03055/) (2025)
- [Learning to Schedule in Parallel-Server Queues with Stochastic Bilinear Rewards](https://mlsanity.com/paper/2112.06362/) (2021)
- [Learning to Stabilize Online Reinforcement Learning in Unbounded State Spaces](https://mlsanity.com/paper/2306.01896/) (2023)
- [MAB-Based Channel Scheduling for Asynchronous Federated Learning in Non-Stationary Environments](https://mlsanity.com/paper/2503.01324/) (2025)
- [Competitive Multi-armed Bandit Games for Resource Sharing](https://mlsanity.com/paper/2503.20975/) (2025)
- [Learning When to Automate: Queue Control in Human-AI Service Systems](https://mlsanity.com/paper/2607.06017/) (2026)
- [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)

Consider a queueing system consisting of multiple servers. Jobs arrive over time and enter a queue for service; the goal is to minimize the size of this queue. At each opportunity for service, at most one server can be chosen, and at most one job can be served. Service is successful with a probability (the service probability) that is a priori unknown for each server. An algorithm that knows the service probabilities (the "genie") can always choose the server of highest service probability. We study algorithms that learn the unknown service probabilities. Our goal is to minimize queue-regret: the (expected) difference between the queue-lengths obtained by the algorithm, and those obtained by the "genie." Since queue-regret cannot be larger than classical regret, results for the standard multi-armed bandit problem give algorithms for which queue-regret increases no more than logarithmically in time. Our paper shows surprisingly more complex behavior. In particular, as long as the bandit algorithm's queues have relatively long regenerative cycles, queue-regret is similar to cumulative regret, and scales (essentially) logarithmically. However, we show that this "early stage" of the queueing bandit eventually gives way to a "late stage", where the optimal queue-regret scaling is O(1/t). We demonstrate an algorithm that (order-wise) achieves this asymptotic queue-regret in the late stage. Our results are developed in a more general model that allows for multiple job classes as well.