Sandeep Juneja
School of Technology and Computer Science, Tata Institute of Fundamental Research
Given a vector of 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 study this as a pure exploration problem in multi armed bandit settings and develop sample complexity bounds on the total mean number of samples required for identifying the correct partition with high probability. This framework subsumes well studied problems in the literature such as finding the best arm or the best few arms. The partitions considered include half spaces, polytopes or their complements, or more generally, convex sets or their complements. In these settings, exploiting problem geometry, we characterise the lower bounds on mean number of samples for each arm. Further, we propose algorithms that can match these bounds asymptotically with decreasing probability of error. Applications of this framework are diverse. We briefly discuss one associated with nested Monte Carlo and its applications to finance.