**Date & Time:** October 14, 2015, 16:00-17:00.

**Venue:** Ramanujan Hall

**Title:** Large deviations, selecting the best population and multi-armed bandit methods

**Speaker:** Sandeep Juneja, TIFR Mumbai

**Abstract:** Consider the problem of finding a population amongst many with the
smallest mean when these means are unknown but population samples can be
generated. 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. Further, under similar
restrictions, sequential methods from multi-armed bandit literature can
also be adapted to devise such algorithms.