# Learning While Scheduling in Multi-Server Systems with Unknown Statistics: MaxWeight with Discounted UCB

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 28 references that are in the map.
- First posted on arXiv 2 Sep 2022.

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

- [Combinatorial Sleeping Bandits with Fairness Constraints](https://mlsanity.com/paper/1901.04891/) (2019)
- [An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints](https://mlsanity.com/paper/2102.05295/) (2021)
- [Learning Unknown Service Rates in Queues: A Multi-Armed Bandit Approach](https://mlsanity.com/paper/1604.06377/) (2016)
- [Job Dispatching Policies for Queueing Systems with Unknown Service Rates](https://mlsanity.com/paper/2106.04707/) (2021)
- [On Learning the cμ Rule in Single and Parallel Server Networks](https://mlsanity.com/paper/1802.06723/) (2018)
- [Augmenting Max-Weight with Explicit Learning for Wireless Scheduling with Switching Costs](https://mlsanity.com/paper/1808.01618/) (2018)

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

- [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)
- [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)
- [Adversarial Network Optimization under Bandit Feedback: Maximizing Utility in Non-Stationary Multi-Hop Networks](https://mlsanity.com/paper/2408.16215/) (2024)
- [Near-Optimal Regret-Queue Length Tradeoff in Online Learning for Two-Sided Markets](https://mlsanity.com/paper/2510.14097/) (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)

## Abstract (arXiv)

Multi-server queueing systems are widely used models for job scheduling in machine learning, wireless networks, crowdsourcing, and healthcare systems. This paper considers a multi-server system with multiple servers and multiple types of jobs, where different job types require different amounts of processing time at different servers. The goal is to schedule jobs on servers without knowing the statistics of the processing times. To fully utilize the processing power of the servers, it is known that one has to at least learn the service rates of different job types on different servers. Prior works on this topic decouple the learning and scheduling phases which leads to either excessive exploration or extremely large job delays. We propose a new algorithm, which combines the MaxWeight scheduling policy with discounted upper confidence bound (UCB), to simultaneously learn the statistics and schedule jobs to servers. We prove that under our algorithm the asymptotic average queue length is bounded by one divided by the traffic slackness, which is order-wise optimal. We also obtain an exponentially decaying probability tail bound for any-time queue length. These results hold for both stationary and nonstationary service rates. Simulations confirm that the delay performance of our algorithm is several orders of magnitude better than previously proposed algorithms.