在保证高置信度的前提下，用最少的损失找到最优选择。
Best Arm Identification with Minimal Regret
- 用双置信区间随机选动作，平衡探索与利用。
- 理论证明累积损失下限，揭示性能瓶颈。
- 适合需要高效决策的在线实验场景。
为应对需负责任实验的真实场景，我们提出最小化遗憾的最佳臂识别（BAI）问题。该问题融合了多臂赌博机中的两个核心目标：遗憾最小化与最佳臂识别。具体而言，智能体需以指定置信度δ识别出最优臂，同时最小化停止时刻前的累积遗憾。针对单参数指数族分布，我们运用信息论方法建立了实例相关的累积遗憾下界。此外，我们提出一个不可能性结果，揭示固定置信度下累积遗憾与样本复杂度之间的内在矛盾。互补地，我们设计并分析了Double KL-UCB算法，该算法在置信度δ趋于零时达到渐近最优。该算法通过两个不同置信区间以随机方式指导臂的选择。研究结果为遗憾最小化与最佳臂识别间的内在联系提供了新视角。
原文摘要 · Abstract (English)
Motivated by real-world applications that necessitate responsible experimentation, we introduce the problem of best arm identification (BAI) with minimal regret. This variant of the multi-armed bandit problem elegantly amalgamates two of its most ubiquitous objectives: regret minimization and BAI. More precisely, the agent's goal is to identify the best arm with a prescribed confidence level $δ$, while minimizing the cumulative regret up to the stopping time. Focusing on single-parameter exponential families of distributions, we leverage information-theoretic techniques to establish an instance-dependent lower bound on the expected cumulative regret. Moreover, we present an impossibility result that underscores the tension between cumulative regret and sample complexity in fixed-confidence BAI. Complementarily, we design and analyze the Double KL-UCB algorithm, which achieves asymptotic optimality as the confidence level tends to zero. Notably, this algorithm employs two distinct confidence bounds to guide arm selection in a randomized manner. Our findings elucidate a fresh perspective on the inherent connections between regret minimization and BAI.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。