# On Learning the cμ Rule in Single and Parallel Server Networks

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Feb 2018.

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

- [Job Dispatching Policies for Queueing Systems with Unknown Service Rates](https://mlsanity.com/paper/2106.04707/) (2021)
- [Learning While Scheduling in Multi-Server Systems with Unknown Statistics: MaxWeight with Discounted UCB](https://mlsanity.com/paper/2209.01126/) (2022)
- [On Preemption and Learning in Stochastic Scheduling](https://mlsanity.com/paper/2205.15695/) (2022)
- [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)
- [Scheduling Jobs with Stochastic Holding Costs](https://mlsanity.com/paper/2105.13655/) (2021)
- [Learning to Admit Optimally in an M/M/k/k+N Queueing System with Unknown Service Rate](https://mlsanity.com/paper/2202.02419/) (2022)
- [Finding Optimal Policy for Queueing Models: New Parameterization](https://mlsanity.com/paper/2206.10073/) (2022)
- [Learning to Schedule in Parallel-Server Queues with Stochastic Bilinear Rewards](https://mlsanity.com/paper/2112.06362/) (2021)
- [Demonstration of effective UCB-based routing in skill-based queues on real-world data](https://mlsanity.com/paper/2506.20543/) (2025)
- [Learning While Scheduling Jobs under Context-Dependent Service Rates: An Anytime Rate-Optimal Algorithm](https://mlsanity.com/paper/2610.06006/) (2026)

## Abstract (arXiv)

We consider learning-based variants of the c μ rule for scheduling in single and parallel server settings of multi-class queueing systems. In the single server setting, the c μ rule is known to minimize the expected holding-cost (weighted queue-lengths summed over classes and a fixed time horizon). We focus on the problem where the service rates μ are unknown with the holding-cost regret (regret against the c μ rule with known μ) as our objective. We show that the greedy algorithm that uses empirically learned service rates results in a constant holding-cost regret (the regret is independent of the time horizon). This free exploration can be explained in the single server setting by the fact that any work-conserving policy obtains the same number of samples in a busy cycle. In the parallel server setting, we show that the c μ rule may result in unstable queues, even for arrival rates within the capacity region. We then present sufficient conditions for geometric ergodicity under the c μ rule. Using these results, we propose an almost greedy algorithm that explores only when the number of samples falls below a threshold. We show that this algorithm delivers constant holding-cost regret because a free exploration condition is eventually satisfied.