MaxGap Bandit: Adaptive Algorithms for Approximate Ranking

摘要: This paper studies the problem of adaptively sampling from K distributions (arms) in order to identify largest gap between any two adjacent means. We call this MaxGap-bandit problem. arises naturally approximate ranking, noisy sorting, outlier detection, and top-arm identification bandits. The key novelty MaxGap bandit is that it aims determine natural partitioning into a subset with larger means smaller means, where split determined by rather than pre-specified rank or threshold. Estimating an arm’s requires its neighboring arms addition itself, dependence results novel hardness parameter characterizes sample complexity propose elimination UCB-style algorithms show they are minimax optimal. Our experiments require 6-8x fewer samples non-adaptive achieve same error.