提出新方法精准识别多臂赌博机中表现最优的臂。
Dominant Arm Identification with Mixing and Recycling Observed Samples
- 设计基于局部主导性的得分准则，判断哪条臂全局更优。
- 通过混合与回收样本，实现所有臂分布估计同步收敛。
- 算法在少量样本下就能准确找到最优臂，适合小样本场景。
我们研究多臂赌博机中的主导臂识别问题，目标是找出在所有其他动作的实现实时奖励之上具有最高超出概率的动作。传统基于均值和成对比较的算法常无法正确识别出具有最高实际回报的臂。为此，我们提出一种新的主导臂判定标准及具备理论保证的高效估计器。核心创新包括：(i) 基于划分奖励空间的局部主导性构建的主导得分准则；(ii) 联合混合与回收机制结合双重稳健估计器，确保所有臂的经验分布函数同时收敛。该方法实现了全局臂主导性的高效计算。所提出的消除算法以近似最优的样本复杂度识别出最佳主导臂。数值实验表明，该算法能持续实现对真实主导臂的精确恢复，优于现有基线方法。
原文摘要 · Abstract (English)
We study the problem of identifying the dominant arm in multi-armed bandits, where the objective is to find the action with the highest probability of exceeding the realized rewards of all other actions. Conventional mean-based and pairwise comparison-based algorithms often fail to identify the arm with the highest realized reward. To address this challenge, we introduce a novel dominant arm criterion and an efficient estimator with theoretical guarantees. Our approach relies on two key technical innovations: (i) a dominance score criterion that an arm beats the locally dominant over the partitioned reward space and (ii) a joint mixing and recycling mechanism coupled with a doubly robust estimator that guarantees simultaneous convergence of the empirical distribution functions for all arms. These key innovations pave a way to efficient computation of global arm dominance. Our proposed elimination algorithm identifies the best dominant arm with nearly optimal rate of sample complexity. Numerical experiments demonstrate that our algorithm consistently achieves exact recovery of the true dominant arm, outperforming existing baselines.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。