Timezone: »

 
Poster
Finding All $\epsilon$-Good Arms in Stochastic Bandits
Blake Mason · Lalit Jain · Ardhendu Tripathy · Robert Nowak

Tue Dec 08 09:00 AM -- 11:00 AM (PST) @ Poster Session 1 #246
in Poster Session 2 »
The pure-exploration problem in stochastic multi-armed bandits aims to find one or more arms with the largest (or near largest) means. Examples include finding an $\epsilon$-good arm, best-arm identification, top-$k$ arm identification, and finding all arms with means above a specified threshold. However, the problem of finding \emph{all} $\epsilon$-good arms has been overlooked in past work, although arguably this may be the most natural objective in many applications. For example, a virologist may conduct preliminary laboratory experiments on a large candidate set of treatments and move all $\epsilon$-good treatments into more expensive clinical trials. Since the ultimate clinical efficacy is uncertain, it is important to identify all $\epsilon$-good candidates. Mathematically, the all-$\epsilon$-good arm identification problem is presents significant new challenges and surprises that do not arise in the pure-exploration objectives studied in the past. We introduce two algorithms to overcome these and demonstrate their great empirical performance on a large-scale crowd-sourced dataset of $2.2$M ratings collected by the New Yorker Caption Contest as well as a dataset testing hundreds of possible cancer drugs.

Author Information

Blake Mason (University of Wisconsin - Madison)

Blake Mason is Doctoral Student at the University of Wisconsin-Madison studying Electrical and Computer Engineering under the advisement of Professor Robert Nowak. Prior to his graduate studies, he completed his bachelors in electrical engineering at the University of Southern California.

Lalit Jain (University of Washington)
Ardhendu Tripathy (Missouri University of Science & Technology)
Robert Nowak (University of Wisconsion-Madison)

More from the Same Authors