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