Before revision:  Using these results, we show that learning-based variants of the c\mu rule again result in a constant regret (i. e. does not depend on the time horizon). This result hinges on (i) the busy period concentrations of the multi-server c \mu rule, and that (ii) our learning-based rule is designed to dynamically explore server rates, but in such a manner that it eventually satisfies an explore-free condition .
After revision:  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 .