Before revision:  We first show that empirically learning the service rates and then scheduling using these learned values results in a regret of holding-cost that does not depend on the time horizon . 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.
After revision:  We first show that empirically learning the service rates and then scheduling using these learned values results in a regret of holding-cost that does not depend on the time horizon ). This free exploration can be explained in the single server setting by the fact that any work-conserving scheduling policy in this setting allows explore-free learning, where no penalty is incurred for exploring and learning server rates.