Before revision:  The key insight that allows such a constant regret bound is that a work-conserving scheduling policy in this setting allows explore-free learning, where no penalty is incurred for exploring and learning server rates. We next consider the multi-server setting. We show that in general, the c \mu rule is not stabilizing (i.e. there are stabilizable arrival and service rate parameters for which the multi-server c \mu rule results in unstable queues ) .
After revision:  The key insight that allows such a constant regret bound is that a work-conserving policy obtains the same number of samples in a busy cycle. In the parallel server setting, we show that the c \mu rule is not stabilizing (i.e. there are stabilizable arrival and service rate parameters for which the multi-server c \mu rule results in unstable queues ) .