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