Before revision:  We focus on the setting where the service rates \mu are unknown , and are interested in the holding-cost regret -- the difference in the expected holding-costs between that induced by a learning-based rule (that learns \mu) and that from the c \mu rule (which has knowledge of the service rates) over any fixed time horizon. 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 .
After revision:  We focus on the setting where the service rates \mu are unknown , and are interested in the holding-cost regret -- the difference in the expected holding-costs between that induced by a learning-based rule (that learns \mu) and that from 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 regret of holding-cost that does not depend on the time horizon .