Consider the problem of finding a population amongst many with the smallestmean when these means are unknown but population samples can be generated.Typically, by selecting a population with the smallest sample mean, it canbe shown that the false selection probability decays at an exponentialrate. Lately researchers have sought algorithms that guarantee that thisprobability is restricted to a small d in order log(1/d) computational timeby estimating the associated large deviations rate function via simulation.We show that such guarantees are misleading. Enroute, we identify the largedeviations principle followed by the empirically estimated large deviationsnegative result that when populations have unbounded support, any policythat asymptotically identifies the correct population with probability atleast 1-d for each problem instance requires more than O(log(1/d)) samplesin making such a determination in any problem instance. This suggests thatsome restrictions are essential on populations to devise O(log(1/d))algorithms with 1-d correctness guarantees. We note that under restrictionon population moments, such methods are easily designed. Further, undersimilar restrictions, sequential methods from multi-armed bandit literature.
Prof. Sandeep Juneja is a Professor and Dean at the School of Technologyand Computer Science in Tata Institute of Fundamental Research in Mumbai.He received his M. S. in Statistics and Ph.D. in Operations Research fromStanford University (1993). He is currently on the editorial board ofStochastic Systems. Earlier he has been on editorial boards of Mathematicsof Operations Research, Management Science and ACM TOMACS. His researchinterests lie in applied probability including in mathematical finance,Monte Carlo methods, and game theoretic analysis of queues.