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.

本文考虑了带障碍的多臂赌博机问题中，包含组合优化的情况下解决局部最优策略的方法。我们扩展了现有模型，使得多个手臂可以按照可行性约束同时进行决策。本文提出了一种自然的贪心算法，并针对其在多种情况下的表现给出了严格的理论保证。