Combinatorial Blocking Bandits with Stochastic Delays
Combinatorial Blocking Bandits with Stochastic Delays
复制标题
DOI：
--
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
Alexia Atsidakou;O. Papadigenopoulos;S. Basu;C. Caramanis;S. Shakkottai
中科院分区：
文献类型：
--
作者：
Alexia Atsidakou;O. Papadigenopoulos;S. Basu;C. Caramanis;S. Shakkottai
最近的工作考虑了多臂强盗问题的自然变化，其中每条手臂的奖励分布是自上次拉起的时间的特殊函数。在这个方向上，一个简单的（但广泛适用的）模型是阻挡土匪，其中手臂在每次比赛后的确定数量的回合中不可用。在这项工作中，我们在两个方向上扩展了上述模型：(i)我们考虑了一般的组合设置，即在可行性约束下，每轮可以玩不止一个手臂。（ii）我们允许每个臂的阻塞时间是随机的。我们首先研究上述设置的计算/无条件硬度，并确定问题变得易于处理（甚至在近似意义上）的必要条件。基于这些条件，我们对自然贪婪启发式算法的近似保证进行了严密的分析，该算法总是在可用（非阻塞）臂中发挥最大期望奖励可行子集。当手臂的期望奖励未知时，我们将上述启发式算法改编为基于UCB的强盗算法，我们提供了次线性（近似）后悔保证，在没有延迟的极限情况下匹配理论下界。
Recent work has considered natural variations of the multi-armed bandit problem, where the reward distribution of each arm is a special function of the time passed since its last pulling. In this direction, a simple (yet widely applicable) model is that of blocking bandits, where an arm becomes unavailable for a deterministic number of rounds after each play. In this work, we extend the above model in two directions: (i) We consider the general combinatorial setting where more than one arms can be played at each round, subject to feasibility constraints. (ii) We allow the blocking time of each arm to be stochastic. We first study the computational/unconditional hardness of the above setting and identify the necessary conditions for the problem to become tractable (even in an approximate sense). Based on these conditions, we provide a tight analysis of the approximation guarantee of a natural greedy heuristic that always plays the maximum expected reward feasible subset among the available (non-blocked) arms. When the arms' expected rewards are unknown, we adapt the above heuristic into a bandit algorithm, based on UCB, for which we provide sublinear (approximate) regret guarantees, matching the theoretical lower bounds in the limiting case of absence of delays.