We study the problem of best-item identification from choice-based feedback. In this problem, a company sequentially and adaptively shows display sets to a population of customers and collects their choices. The objective is to identify the most preferred item with the least number of samples and at a high confidence level. We propose an elimination-based algorithm, namely Nested Elimination (NE), which is inspired by the nested structure implied by the information-theoretic lower bound. NE is simple in structure, easy to implement, and has a strong theoretical guarantee for sample complexity. Specifically, NE utilizes an innovative elimination criterion and circumvents the need to solve any complex combinatorial optimization problem. We provide an instance-specific and non-asymptotic bound on the expected sample complexity of NE. We also show NE achieves high-order worst-case asymptotic optimality. Finally, numerical experiments from both synthetic and real data corroborate our theoretical findings.

从基于选择的反馈中最佳项目的识别问题出发，我们提出了一种名为Nested Elimination（NE）的消除算法，它受到信息论下界所隐含的嵌套结构的启发。NE在结构上简单且易于实现，并且在样本复杂性方面具有强大的理论保证。特别是，NE利用了一种创新的消除准则，避免了解决任何复杂的组合优化问题。我们提供了关于NE预期样本复杂性的具体实例特定的非渐近界限，并且还显示NE实现了高阶最坏情况渐近最优性。最后，来自合成和真实数据的数值实验支持了我们的理论发现。

嵌套消除算法：基于选择反馈的最佳项目识别的简单算法