Bandits with Replenishable Knapsacks: the Best of both Worlds
Martino Bernasconi Matteo Castiglioni Andrea Celli Federico Fusco
The bandits with knapsack (BwK) framework models online decision-making
problems in which an agent makes a sequence of decisions subject to resource
consumption constraints. The traditional model assumes that each action
consumes a non-negative amount of resources and the process ends when the
initial budgets are fully depleted. We study a natural generalization of the
BwK framework which allows non-monotonic resource utilization, i.e., resources
can be replenished by a positive amount. We propose a best-of-both-worlds
primal-dual template that can handle any online learning problem with
replenishment for which a suitable primal regret minimizer exists. In
particular, we provide the first positive results for the case of adversarial
inputs by showing that our framework guarantees a constant competitive ratio
$\alpha$ when $B=\Omega(T)$ or when the possible per-round replenishment is a
positive constant. Moreover, under a stochastic input model, our algorithm
yields an instance-independent $\tilde{O}(T^{1/2})$ regret bound which
complements existing instance-dependent bounds for the same setting. Finally,
we provide applications of our framework to some economic problems of practical
relevance.