Blocking Bandits
This addresses resource allocation problems in areas like recommendation systems and scheduling, but it is incremental as it extends existing bandit frameworks with blocking constraints.
The paper tackles the problem of stochastic multi-armed bandits where playing an arm blocks it for a fixed number of time slots, modeling scenarios like product recommendations or job scheduling, and shows that a simple greedy algorithm is asymptotically (1-1/e) optimal, with a UCB-based algorithm achieving c log T + o(log T) cumulative regret when rewards are unknown.
We consider a novel stochastic multi-armed bandit setting, where playing an arm makes it unavailable for a fixed number of time slots thereafter. This models situations where reusing an arm too often is undesirable (e.g. making the same product recommendation repeatedly) or infeasible (e.g. compute job scheduling on machines). We show that with prior knowledge of the rewards and delays of all the arms, the problem of optimizing cumulative reward does not admit any pseudo-polynomial time algorithm (in the number of arms) unless randomized exponential time hypothesis is false, by mapping to the PINWHEEL scheduling problem. Subsequently, we show that a simple greedy algorithm that plays the available arm with the highest reward is asymptotically $(1-1/e)$ optimal. When the rewards are unknown, we design a UCB based algorithm which is shown to have $c \log T + o(\log T)$ cumulative regret against the greedy algorithm, leveraging the free exploration of arms due to the unavailability. Finally, when all the delays are equal the problem reduces to Combinatorial Semi-bandits providing us with a lower bound of $c' \log T+ ω(\log T)$.