Department of Computer Science and Automation
CSA Faculty Colloquium
Speaker : Prof. Y. Narahari
Dept. of CSA
Title : Ballooning Multi-Armed Bandits
Date : Friday, January 03, 2020
Time : 4:00 PM
Venue : CSA Seminar Hall (Room No. 254, First Floor)
Many common web-based applications such as online q&A forums and online review portals need a scientific way of identifying high quality answers or opinions and distinguishing them from ordinary ones. To tackle this problem, we introduce a new model which we call “ballooning multi-armed bandits” (B-MAB), a novel extension to the classical stochastic MAB model. In the BMAB model, the set of available arms grows (or balloons) over time. In contrast to the classical MAB setting where the regret is computed with respect to the best arm overall, the regret in a BMAB setting is computed with respect to the best available arm at each time. We first observe that the existing stochastic MAB algorithms are not regret-optimal for the B-MAB model. In fact, if the best arm is equally likely to arrive at any time, a sublinear regret cannot be achieved, irrespective of the arrival of other arms. We next present our main result that if the best arm is more likely to arrive in the early rounds, one can achieve sub-linear regret. Making reasonable assumptions on the arrival distribution of the best arm in terms of the thinness of the distribution’s tail, we prove that the proposed algorithm achieves sub-linear, instance-independent regret. We further quantify explicit dependence of regret on the arrival distribution parameters. Application to online Q&A forums, online review platforms, and many other settings is immediate.
(Joint work with Ganesh Ghalme, Swapnil Dhamal, Shweta Jain, and Sujit Gujar)
Biography of the speaker
Y. Narahari is currently a Professor at the Department of Computer Science and Automation, Indian Institute of Science, Bangalore, India. He is also the chairman of the Division of EECS (Electrical, Electronics, and Computer Sciences) at IISc. The focus of his current research is on exploring problems at the interface of computer science and game theory. He is the author of a textbook entitled “Game Theory and Mechanism Design” brought out by the IISc Press and the World Scientific Publishing Company.
Host Faculty : Prof. Sunil L Chandran & Prof. Shalabh Bhatnagar
ALL ARE WELCOME