Partition identification using multi-armed bandits

Abstract: Given a vector of unknown probability distributions, or arms, each of which can be sampled independently, we consider the problem of identifying the partition to which this vector belongs from a finitely partitioned universe of such vector of distributions. We primarily consider partitions where the vector of means of arms lie either in a given set or its complement in a Euclidean space. The sets considered correspond to half spaces or where either the set or its complement is a polytope, or more generally, a convex set. In these settings, exploiting the problem geometry, we characterize the lower bounds on mean number of samples from each arm that any \delta-correct algorithm (algorithm that restricts wrong identification probability to a pre-specified \delta) must satisfy. Further, we propose \delta-correct algorithms that for small \delta can match these bounds.