标题： MaxGap 棒球：近似排序的自适应算法 显示英文标题

标题： MaxGap Bandit: Adaptive Algorithms for Approximate Ranking

摘要： 本文研究了从K个分布（臂）中自适应采样的问题，以确定任何两个相邻均值之间的最大差距。我们称这个问题为MaxGap-bandit问题。这个问题在近似排序、噪声排序、异常值检测和bandits中的最优臂识别中自然出现。MaxGap-bandit问题的关键创新之处在于，它旨在自适应地确定分布的自然划分，即较大均值的子集和较小均值的子集，其中划分是根据最大差距而不是预定义的排名或阈值来确定的。估计一个臂的差距需要对其相邻臂进行采样，除了其自身之外，这种依赖性导致了一个新的困难参数，该参数表征了问题的样本复杂度。我们提出了消除和UCB风格的算法，并证明它们是最小最大最优的。我们的实验表明，UCB风格的算法在达到相同误差的情况下所需的样本数比非自适应采样少6-8倍。 显示英文摘要

摘要： 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.