  We consider a constrained, pure exploration, stochastic multi-armed bandit
formulation under a fixed budget. Each arm is associated with an unknown,
possibly multi-dimensional distribution and is described by multiple attributes
that are a function of this distribution. The aim is to optimize a particular
attribute subject to user-defined constraints on the other attributes. This
framework models applications such as financial portfolio optimization, where
it is natural to perform risk-constrained maximization of mean return. We
assume that the attributes can be estimated using samples from the arms'
distributions and that these estimators satisfy suitable concentration
inequalities. We propose an algorithm called \textsc{Constrained-SR} based on
the Successive Rejects framework, which recommends an optimal arm and flags the
instance as being feasible or infeasible. A key feature of this algorithm is
that it is designed on the basis of an information theoretic lower bound for
two-armed instances. We characterize an instance-dependent upper bound on the
probability of error under \textsc{Constrained-SR}, that decays exponentially
with respect to the budget. We further show that the associated decay rate is
nearly optimal relative to an information theoretic lower bound in certain
special cases.
