针对单峰结构的老虎机问题，提出高效算法精准识别最优选项。
Best-Arm Identification in Unimodal Bandits
- 利用单峰特性设计跟踪停止与顶二算法，聚焦关键臂
- 理论证明算法渐近最优，且在高斯分布下逼近最坏情况极限
- 适合需快速准确选最优策略的场景，如推荐系统优化
我们研究单峰老虎机中的固定置信度最优臂识别问题，其中各臂均值先随索引递增至峰值后递减。推导了任意算法停止时间的两个下界：实例相关下界表明，仅三个臂主导置信度相关的成本；而最坏情况下的下界显示，置信度无关成本中线性依赖臂数不可避免。本文提出改进的Track-and-Stop与顶二算法，充分挖掘单峰结构。两种版本的Track-and-Stop对一参数指数族分布渐近最优；顶二算法在高斯分布下渐近近似最优，并给出了匹配最坏情况下界的非渐近保证。算法实现高效，实验验证其具有竞争力的性能。
原文摘要 · Abstract (English)
We study the fixed-confidence best-arm identification problem in unimodal bandits, in which the means of the arms increase with the index of the arm up to their maximum, then decrease. We derive two lower bounds on the stopping time of any algorithm. The instance-dependent lower bound suggests that due to the unimodal structure, only three arms contribute to the leading confidence-dependent cost. However, a worst-case lower bound shows that a linear dependence on the number of arms is unavoidable in the confidence-independent cost. We propose modifications of Track-and-Stop and a Top Two algorithm that leverage the unimodal structure. Both versions of Track-and-Stop are asymptotically optimal for one-parameter exponential families. The Top Two algorithm is asymptotically near-optimal for Gaussian distributions and we prove a non-asymptotic guarantee matching the worse-case lower bound. The algorithms can be implemented efficiently and we demonstrate their competitive empirical performance.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。