Learning Unknown Service Rates in Queues: A Multiarmed Bandit Approach
Learning Unknown Service Rates in Queues: A Multiarmed Bandit Approach
复制标题
学习队列中的未知服务率：多臂老虎机方法
DOI：
10.1287/opre.2020.1995
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
S. Shakkottai
中科院分区：
文献类型：
--
作者：
Subhashini Krishnasamy;Rajat Sen;Ramesh Johari;S. Shakkottai
传统的随机调度问题假设系统的统计参数是先验已知的。在“Learning unknown service rates in queues：A multiarmed bandit approach”中，Krishnasamy、Sen、Johari和Shakkottai考虑了统计参数未知时并行服务器系统中的在线调度问题。他们在随机多臂强盗框架中以队列长度为性能目标研究了这个问题。与经典的随机多臂土匪问题，遗憾的规模随时间的推移，作者表明，队列遗憾（土匪算法和精灵政策之间的预期队列长度的差异）表现出更复杂的行为。它在初始阶段呈几何增长，最终几乎与时间成反比地衰减。这一显着的行为解释通过分析再生周期长度，缩短随着时间的推移，强盗算法学会稳定的队列。
Traditional scheduling problems in stochastic queueing systems assume that the statistical parameters are known a priori. In ''Learning unknown service rates in queues: A multiarmed bandit approach'', Krishnasamy, Sen, Johari, and Shakkottai consider the problem of online scheduling in a parallel-server system when the statistical parameters are unknown. They study this question in the stochastic multiarmed bandits framework with the queue length as the performance objective. In contrast to the classic stochastic multiarmed bandits problem, where the regret scales logarithmically with time, the authors show that the queue regret (difference in expected queue length between a bandit algorithm and a genie policy) exhibits a more complex behavior. It grows logarithmically in the initial stage and eventually decays almost inversely with time. This remarkable behavior is explained through the analysis of regenerative cycle lengths, which shorten with time as the bandit algorithm learns to stabilize the queues.