  This paper introduces the first asymptotically optimal strategy for a multi
armed bandit (MAB) model under side constraints. The side constraints model
situations in which bandit activations are limited by the availability of
certain resources that are replenished at a constant rate. The main result
involves the derivation of an asymptotic lower bound for the regret of feasible
uniformly fast policies and the construction of policies that achieve this
lower bound, under pertinent conditions. Further, we provide the explicit form
of such policies for the case in which the unknown distributions are Normal
with unknown means and known variances, for the case of Normal distributions
with unknown means and unknown variances and for the case of arbitrary discrete
distributions with finite support.
