Learning to Control Renewal Processes with Bandit Feedback
Learning to Control Renewal Processes with Bandit Feedback
复制标题
DOI：
10.1145/3309697.3331515
复制
发表时间：
2019-06
期刊：
影响因子：
--
通讯作者：
Semih Cayci;A. Eryilmaz;R. Srikant
中科院分区：
文献类型：
--
作者：
Semih Cayci;A. Eryilmaz;R. Srikant
我们考虑具有K个任务类型的强盗问题，控制器每次激活一个任务。每个任务都需要一个随机的、可能是重尾的完成时间，只有在任务完成后才能获得奖励。任务类型是相互独立的，并有不同的和未知的完成时间和奖励的分布。对于给定的时间范围τ，控制器的目标是自适应地调度任务，以便最大化收集的奖励，直到τ到期。此外，我们允许控制器中断一个任务并启动一个新的任务。除了传统的探索-利用困境之外，这种中断机制引入了一个新的困境：控制器应该完成任务并获得奖励，还是为了一个可能更短和更有回报的选择而中断任务？我们发现，对于所有重尾和一些轻尾完成时间分布，这种中断机制随着时间的推移线性提高奖励。从学习的角度来看，中断机制需要隐式学习统计数据超出截断观察的平均值。为此，我们提出了一个强大的学习算法命名为UCB-BwI的均值估计的基础上可能重尾奖励和完成时间分布。我们证明，在具有任意L个可能中断时间集的K臂强盗设置中，UCB-BwI实现了O（Kłog（τ）+KL）遗憾。我们还证明了在任何容许策略下的后悔是Kmega（Kmog（τ）），这意味着UCB-BwI是阶最优的.
We consider a bandit problem with K task types from which the controller activates one task at a time. Each task takes a random and possibly heavy-tailed completion time, and a reward is obtained only after the task is completed. The task types are independent from each other, and have distinct and unknown distributions for completion time and reward. For a given time horizon τ, the goal of the controller is to schedule tasks adaptively so as to maximize the reward collected until τ expires. In addition, we allow the controller to interrupt a task and initiate a new one. In addition to the traditional exploration-exploitation dilemma, this interrupt mechanism introduces a new one: should the controller complete the task and get the reward, or interrupt the task for a possibly shorter and more rewarding alternative? We show that for all heavy-tailed and some light-tailed completion time distributions, this interruption mechanism improves the reward linearly over time. From a learning perspective, the interrupt mechanism necessitates implicitly learning statistics beyond the mean from truncated observations. For this purpose, we propose a robust learning algorithm named UCB-BwI based on the median-of-means estimator for possibly heavy-tailed reward and completion time distributions. We show that, in a K-armed bandit setting with an arbitrary set of L possible interrupt times, UCB-BwI achieves O(Kłog(τ)+KL) regret. We also prove that the regret under any admissible policy is Ømega(Kłog(τ)), which implies that UCB-BwI is order optimal.