Timezone: »
This paper studies the problem of adaptively sampling from K distributions (arms) in order to identify the largest gap between any two adjacent means. We call this the MaxGap-bandit problem. This problem arises naturally in approximate ranking, noisy sorting, outlier detection, and top-arm identification in bandits. The key novelty of the MaxGap bandit problem is that it aims to adaptively determine the natural partitioning of the distributions into a subset with larger means and a subset with smaller means, where the split is determined by the largest gap rather than a pre-specified rank or threshold. Estimating an arm’s gap requires sampling its neighboring arms in addition to itself, and this dependence results in a novel hardness parameter that characterizes the sample complexity of the problem. We propose elimination and UCB-style algorithms and show that they are minimax optimal. Our experiments show that the UCB-style algorithms require 6-8x fewer samples than non-adaptive sampling to achieve the same error.
Author Information
Sumeet Katariya (UW-Madison and Amazon)
Ardhendu Tripathy (University of Wisconsin - Madison)
Robert Nowak (University of Wisconsion-Madison)
More from the Same Authors
-
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 -
2022 : Panel »
Mayee Chen · Alexander Ratner · Robert Nowak · Cody Coleman · Ramya Korlakai Vinayak -
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: One for All: Simultaneous Metric and Preference Learning over Multiple Users »
Gregory Canal · Blake Mason · Ramya Korlakai Vinayak · Robert Nowak -
2022 Poster: Task-Agnostic Graph Explanations »
Yaochen Xie · Sumeet Katariya · Xianfeng Tang · Edward Huang · Nikhil Rao · Karthik Subbian · Shuiwang Ji -
2021 Poster: Probabilistic Entity Representation Model for Reasoning over Knowledge Graphs »
Nurendra Choudhary · Nikhil Rao · Sumeet Katariya · Karthik Subbian · Chandan Reddy -
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: Finding All $\epsilon$-Good Arms in Stochastic Bandits »
Blake Mason · Lalit Jain · Ardhendu Tripathy · Robert Nowak -
2019 Poster: Learning Nearest Neighbor Graphs from Noisy Distance Samples »
Blake Mason · 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