Multi-Armed Bandits with Censored Consumption of Resources
This addresses resource-constrained decision-making in online learning, but it is incremental as it adapts existing bandit methods to a new variant.
The paper tackles a resource-aware multi-armed bandit problem where rewards are censored if resource consumption exceeds a limit, introducing a regret measure that balances reward optimality and resource allocation. It proposes a UCB-inspired algorithm with a theoretical regret bound and shows in simulations that it outperforms standard extensions.
We consider a resource-aware variant of the classical multi-armed bandit problem: In each round, the learner selects an arm and determines a resource limit. It then observes a corresponding (random) reward, provided the (random) amount of consumed resources remains below the limit. Otherwise, the observation is censored, i.e., no reward is obtained. For this problem setting, we introduce a measure of regret, which incorporates the actual amount of allocated resources of each learning round as well as the optimality of realizable rewards. Thus, to minimize regret, the learner needs to set a resource limit and choose an arm in such a way that the chance to realize a high reward within the predefined resource limit is high, while the resource limit itself should be kept as low as possible. We propose a UCB-inspired online learning algorithm, which we analyze theoretically in terms of its regret upper bound. In a simulation study, we show that our learning algorithm outperforms straightforward extensions of standard multi-armed bandit algorithms.