On Learning the cμ Rule: Single and Multiserver Settings
On Learning the cμ Rule: Single and Multiserver Settings
复制标题
关于学习 cμ 规则：单服务器和多服务器设置
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
S. Shakkottai
中科院分区：
文献类型：
--
作者：
Subhashini Krishnasamy;A. Arapostathis;Ramesh Johari;S. Shakkottai
我们考虑基于学习的变种的$c mu$规则-一个经典的和研究充分的调度策略-在单服务器和多服务器设置多类的调度系统。在单服务器设置中，$c mu$规则被称为最小化期望的持有成本（在类和时间上的加权平均长度之和）。我们专注于设置服务率$mu$是未知的，并感兴趣的持有成本的遗憾-在预期持有成本之间的差异引起的学习为基础的规则（学习$mu$）和从$c mu$规则（其中有知识的服务率）在任何固定的时间范围。我们首先表明，经验学习的服务率，然后调度使用这些学到的值的结果在一个遗憾的持有成本，不依赖于时间范围。允许这种持续遗憾边界的关键见解是，这种设置中的工作保存调度策略允许免探索学习，其中不会因为探索和学习服务器速率而受到惩罚。
接下来我们考虑多服务器设置。我们表明，在一般情况下，$c mu$规则是不稳定的（即有稳定的到达和服务率参数的多服务器$c mu$规则的结果在不稳定的队列）。然后，我们表征稳定性的充分条件（以及在忙碌期间的浓度）。使用这些结果，我们表明，基于学习的变体的$cmu$规则再次导致一个恒定的遗憾（即不依赖于时间范围）。这一结果取决于（i）多服务器$c mu$规则的忙碌期集中度，以及（ii）我们的基于学习的规则旨在动态探索服务器速率，但最终满足无探索条件。
We consider learning-based variants of the $c mu$ rule -- a classic and well-studied scheduling policy -- in single and multi-server settings for 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 both over classes and time). 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. 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). We then characterize sufficient conditions for stability (and also concentrations on busy periods). Using these results, we show that learning-based variants of the $cmu$ 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.