On Learning the $c\mu$ Rule in Single and Parallel Server Networks

Understand

We consider learning-based variants of the $c \mu$ rule for scheduling in single and parallel server settings of multi-class queueing systems.

• In the single server setting, the $c \mu$ 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 $\mu$ are unknown with the holding-cost regret (regret against the $c \mu$ rule with known $\mu$) 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).