Regret of Queueing Bandits
Regret of Queueing Bandits
复制标题
排队强盗的遗憾
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
S. Shakkottai
中科院分区：
文献类型：
--
作者：
Subhashini Krishnasamy;Rajat Sen;Ramesh Johari;S. Shakkottai
我们考虑一个变种的多臂强盗问题的工作队列的服务，和不同的服务器的服务率可能是未知的。我们研究的算法，最大限度地减少了deletregret：（预期）之间的差异，由算法获得的deletregret长度，和那些获得的“精灵”辅助匹配算法，知道确切的服务率。这个问题的一个天真的观点认为，后悔应该增长几何：因为后悔不能大于经典的遗憾，标准的MAB问题的结果给出的算法，确保后悔增加不超过几何的时间。我们的论文显示了令人惊讶的更复杂的行为。特别是，只要强盗算法的队列具有相对较长的再生周期，这种天真的直觉就是正确的：在这种情况下，后悔类似于累积后悔，并且（本质上）是数学上的。然而，我们表明，这个“早期阶段”的抢劫强盗最终让位于“后期阶段”，其中最佳的抢劫后悔缩放是O（1/t）。我们证明了一个算法，（顺序）实现了这种渐近的遗憾，也表现出接近最佳的切换时间从早期阶段到后期阶段。
We consider a variant of the multiarmed bandit problem where jobs queue for service, and service rates of different servers may be unknown. We study algorithms that minimize queueregret: the (expected) difference between the queue-lengths obtained by the algorithm, and those obtained by a “genie”-aided matching algorithm that knows exact service rates. A naive view of this problem would suggest that queue-regret should grow logarithmically: since queue-regret cannot be larger than classical regret, results for the standard MAB problem give algorithms that ensure queue-regret increases no more than logarithmically in time. Our paper shows surprisingly more complex behavior. In particular, the naive intuition is correct as long as the bandit algorithm’s queues have relatively long regenerative cycles: in this case queue-regret is similar to cumulative regret, and scales (essentially) logarithmically. However, we show that this “early stage” of the queueing bandit eventually gives way to a “late stage”, where the optimal queue-regret scaling is O(1/t). We demonstrate an algorithm that (order-wise) achieves this asymptotic queue-regret, and also exhibits close to optimal switching time from the early stage to the late stage.