Budget-Constrained and Deadline-Driven Multi-Armed Bandits with Delays

Many extensions of the Multi-Armed Bandit (MAB) problem were studied recently offering a strong theoretical basis for applications that require active learning. The Budget-Constrained and Deadline-Driven MAB with Delay (BD-MAB) variation introduces a novel scenario in which a player must pull from K arms, each associated with reward, delay, and cost distributions. To the best of our knowledge, this is the first work that combines budget constraints with time delays in an MAB problem. The model involves three phases. The first phase comprises pulling arms, while incurring random cost, and observing rewards. This phase ends when the budget is depleted. The second phase includes observing some of the delayed rewards. The third phase starts at a fixed termination deadline, marking the end of reward observation, where any rewards returned after this phase are not observed and are considered dead. We present a novel solution to this problem by developing a new Upper Confidence Bound (UCB)-based algorithm. The name of the algorithm is Budget-Constrained and Deadline-Driven UCB with Delay (BD-UCB) algorithm. We provide extensive regret analysis that confirms the efficiency of our approach in managing these complexities. Lastly, we provide numerical simulations which further demonstrate the effectiveness of our proposed solution.