Ordinal Optimization - Empirical Large Deviations Rate Estimators, and Stochastic Multi-armed Bandits

Abstract: Consider the ordinal optimization problem of finding a population amongst many with the smallest mean when these means are unknown but population samples can be generated via simulation. Typically, by selecting a population with the smallest sample mean, it can be shown that the false selection probability decays at an exponential rate. Lately researchers have sought algorithms that guarantee that this probability is restricted to a small $\delta$  in order $\log(1/\delta)$  computational time by estimating the associated large deviations rate function via simulation. We show that such guarantees are misleading. Enroute, we identify the large deviations principle followed by the empirically estimated large deviations rate function that may also be of independent interest. Further, we show a negative result that when populations have unbounded support,  any policy that asymptotically identifies the correct population with probability at least $1-\delta$ for each problem instance requires more than $O(\log(1/\delta))$  samples in making such a determination in any problem instance. This suggests that some restrictions are essential on populations to devise $O(\log(1/\delta))$ algorithms with $1 - \delta$ correctness guarantees. We note that under restriction on population moments, such methods are easily designed. We also observe that  sequential methods from stochastic multi-armed bandit literature can be adapted to devise such algorithms.