BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/415
DTSTAMP:20230914T125923Z
SUMMARY:PAC Subset Selection in Stochastic Multi-armed Bandits
DESCRIPTION:Speaker: Dr. Shivaram Kalyanakrishnan (Yahoo! Research and Deve
 lopment Pvt. Limited\nTorrey Pines Embassy Golf Links Business Park\nOff K
 oramangala-Indiranagar Intermediate Ring Road\nBangalore 560071)\n\nAbstra
 ct: \nAbstract: We consider the problem of selecting\, from among n real-v
 alued random variables\, a subset of size m of those with the highest mean
 s\, based on efficiently sampling the random variables. This problem\, whi
 ch we denote Explore-m\, finds application in a variety of areas\, such as
  stochastic optimization\, simulation and industrial engineering\, and on-
 line advertising. The theoretical basis of our work is an extension of a p
 revious formulation using multi-armed bandits that is devoted to identifyi
 ng just the single best of n random variables (Explore-1). Under a PAC set
 ting\, we provide algorithms for Explore-m and bound their sample complexi
 ty.\n\nOur main contribution is the $LUCB$ algorithm\, which\, interesting
 ly\, bears a close resemblance to the well-known $UCB$ algorithm for regre
 t minimization.  We derive an expected sample complexity bound for $LUCB$
  that is novel even for single-arm selection. We then improve the problem-
 dependent constant in this bound through a novel algorithmic variant calle
 d $KL-LUCB$.  Experiments affirm the relative efficiency of $KL-LUCB$ ove
 r other algorithms for Explore-m. Our contributions also include a lower b
 ound on the worst case sample complexity of such algorithms.\n\nBio: Shiva
 ram Kalyanakrishnan is a scientist at Yahoo Labs Bangalore. His primary re
 search interests lie in the fields of artificial intelligence and machine 
 learning\, spanning areas such as reinforcement learning\, agents and mult
 iagent systems\, humanoid robotics\, multi-armed bandits\, and on-line adv
 ertising. He obtained his Ph.D. in Computer Science from the University of
  Texas at Austin (2011)\, and his B.Tech. in Computer Science and Engineer
 ing from the Indian Institute of Technology Madras (2004). He has extensiv
 ely used robot soccer as a test domain for his research\, and has actively
  contributed to initiatives such as RoboCup and the Reinforcement Learning
  competitions.\n \n
URL:https://www.tcs.tifr.res.in/web/events/415
DTSTART;TZID=Asia/Kolkata:20131101T110000
DTEND;TZID=Asia/Kolkata:20131101T120000
LOCATION:AG-66 (Lecture Theatre)
END:VEVENT
END:VCALENDAR