Timezone: »
Poster
Finding All $\epsilon$-Good Arms in Stochastic Bandits
Blake Mason · Lalit Jain · Ardhendu Tripathy · Robert Nowak
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
-
2021 Meetup: Rolla, MO »
Ardhendu Tripathy -
2022 : A Better Way to Decay: Proximal Gradient Training Algorithms for Neural Nets »
Liu Yang · Jifan Zhang · Joseph Shenouda · Dimitris Papailiopoulos · Kangwook Lee · Robert Nowak -
2023 Poster: Algorithm Selection for Deep Active Learning with Imbalanced Datasets »
Jifan Zhang · Shuai Shao · Saurabh Verma · Robert Nowak -
2023 Poster: Experimental Designs for Heteroskedastic Variance »
Justin Weltz · Tanner Fiez · Alexander Volfovsky · Eric Laber · Blake Mason · houssam nassif · Lalit Jain -
2023 Poster: Multi-task Representation Learning for Pure Exploration in Bilinear Bandits »
Subhojyoti Mukherjee · Qiaomin Xie · Josiah Hanna · Robert Nowak -
2022 : Panel »
Mayee Chen · Alexander Ratner · Robert Nowak · Cody Coleman · Ramya Korlakai Vinayak -
2022 Poster: Active Learning with Safety Constraints »
Romain Camilleri · Andrew Wagenmaker · Jamie Morgenstern · Lalit Jain · Kevin Jamieson -
2022 Poster: Efficient Active Learning with Abstention »
Yinglun Zhu · Robert Nowak -
2022 Poster: Active Learning with Neural Networks: Insights from Nonparametric Statistics »
Yinglun Zhu · Robert Nowak -
2022 Poster: Instance-optimal PAC Algorithms for Contextual Bandits »
Zhaoqi Li · Lillian Ratliff · houssam nassif · Kevin Jamieson · Lalit Jain -
2022 Poster: One for All: Simultaneous Metric and Preference Learning over Multiple Users »
Gregory Canal · Blake Mason · Ramya Korlakai Vinayak · Robert Nowak -
2022 Poster: Parameters or Privacy: A Provable Tradeoff Between Overparameterization and Membership Inference »
Jasper Tan · Blake Mason · Hamid Javadi · Richard Baraniuk -
2021 Poster: Practical, Provably-Correct Interactive Learning in the Realizable Setting: The Power of True Believers »
Julian Katz-Samuels · Blake Mason · Kevin Jamieson · Rob Nowak -
2021 Poster: Pure Exploration in Kernel and Neural Bandits »
Yinglun Zhu · Dongruo Zhou · Ruoxi Jiang · Quanquan Gu · Rebecca Willett · Robert Nowak -
2020 : Dataset Curation via Active Learning »
Robert Nowak -
2020 Poster: On Regret with Multiple Best Arms »
Yinglun Zhu · Robert Nowak -
2020 Poster: An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits »
Julian Katz-Samuels · Lalit Jain · zohar karnin · Kevin Jamieson -
2019 Poster: Learning Nearest Neighbor Graphs from Noisy Distance Samples »
Blake Mason · Ardhendu Tripathy · Robert Nowak -
2019 Poster: MaxGap Bandit: Adaptive Algorithms for Approximate Ranking »
Sumeet Katariya · Ardhendu Tripathy · Robert Nowak -
2017 Poster: Scalable Generalized Linear Bandits: Online Computation and Hashing »
Kwang-Sung Jun · Aniruddha Bhargava · Robert Nowak · Rebecca Willett -
2017 Poster: A KL-LUCB algorithm for Large-Scale Crowdsourcing »
Ervin Tanczos · Robert Nowak · Bob Mankoff -
2017 Poster: Learning Low-Dimensional Metrics »
Blake Mason · Lalit Jain · Robert Nowak