Talk by Y. Narahari: Ballooning Multi-Armed Bandits

Location: CSA Seminar Hall (Room No. 254, First Floor)

Department of Computer Science and Automation
CSA Faculty Colloquium

Speaker : Prof. Y. Narahari
Professor
Dept. of CSA
IISc

Title : Ballooning Multi-Armed Bandits

Date : Friday, January 03, 2020

Time : 4:00 PM

Venue : CSA Seminar Hall (Room No. 254, First Floor)

Abstract

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