  In this paper, we introduce the constrained best mixed arm identification
(CBMAI) problem with a fixed budget. This is a pure exploration problem in a
stochastic finite armed bandit model. Each arm is associated with a reward and
multiple types of costs from unknown distributions. Unlike the unconstrained
best arm identification problem, the optimal solution for the CBMAI problem may
be a randomized mixture of multiple arms. The goal thus is to find the best
mixed arm that maximizes the expected reward subject to constraints on the
expected costs with a given learning budget $N$. We propose a novel,
parameter-free algorithm, called the Score Function-based Successive Reject
(SFSR) algorithm, that combines the classical successive reject framework with
a novel score-function-based rejection criteria based on linear programming
theory to identify the optimal support. We provide a theoretical upper bound on
the mis-identification (of the the support of the best mixed arm) probability
and show that it decays exponentially in the budget $N$ and some constants that
characterize the hardness of the problem instance. We also develop an
information theoretic lower bound on the error probability that shows that
these constants appropriately characterize the problem difficulty. We validate
this empirically on a number of average and hard instances.
