BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/613
DTSTAMP:20230914T125931Z
SUMMARY:Ordinal Optimization - Empirical Large Deviations Rate Estimators\,
and Stochastic Multi-armed Bandits
DESCRIPTION:Speaker: Sandeep K Juneja\n\nAbstract: \nAbstract: Consider the
ordinal optimization problem of finding a population amongst many with th
e 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 probabilit
y 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 assoc
iated large deviations rate function via simulation. We show that such gua
rantees are misleading. Enroute\, we identify the large deviations princip
le followed by the empirically estimated large deviations rate function th
at may also be of independent interest. Further\, we show a negative resul
t that when populations have unbounded support\, any policy that asympto
tically identifies the correct population with probability at least $1-\\d
elta$ for each problem instance requires more than $O(\\log(1/\\delta))$
samples in making such a determination in any problem instance. This sug
gests that some restrictions are essential on populations to devise $O(\\l
og(1/\\delta))$ algorithms with $1 - \\delta$ correctness guarantees. We n
ote 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.\n
URL:https://www.tcs.tifr.res.in/web/events/613
DTSTART;TZID=Asia/Kolkata:20150810T143000
DTEND;TZID=Asia/Kolkata:20150810T153000
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR