Timezone: »

 
Poster
MaxGap Bandit: Adaptive Algorithms for Approximate Ranking
Sumeet Katariya · Ardhendu Tripathy · Robert Nowak

Wed Dec 11 05:00 PM -- 07:00 PM (PST) @ East Exhibition Hall B + C #4
in Algorithms -- Bandit Algorithms »

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.

Keywords: Bandit Algorithms · Algorithms · Algorithms -> Active Learning; Algorithms -> Adaptive Data Analysis; Algorithms -> Clustering; Algorithms · Ranking and Prefer
[ Paper]  [ Poster] 

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