针对奖励方差随时间减小的老虎机问题，提出两种高效识别最优臂的策略。
Fixed-Confidence Best Arm Identification with Decreasing Variance
- 先等待再采样，或周期性采样并用加权平均判断最优臂
- 理论保证在减少采样次数的同时仍能快速识别最优臂
- 适合方差递减场景，优于传统方法
我们研究随机多臂老虎机中最佳臂识别的问题，其中各臂奖励的方差随时间逐渐减小。我们将臂的奖励建模为均值固定、方差随时间下降的高斯变量。学习者的成本由识别最优臂所需时间与采样次数的加权和构成。该成本函数激励学习者在初始阶段减少采样，但不采样又会延长终止时间，增加成本。这种权衡需要新的采样策略。我们提出了两种策略：第一种在初始阶段无采样，随后持续采样；第二种周期性采样，并使用观测奖励的加权平均来识别最优臂。我们为两种策略提供了性能的理论保证，并通过仿真验证了其在经典最佳臂识别任务中优于当前最优策略。
原文摘要 · Abstract (English)
We focus on the problem of best-arm identification in a stochastic multi-arm bandit with temporally decreasing variances for the arms' rewards. We model arm rewards as Gaussian random variables with fixed means and variances that decrease with time. The cost incurred by the learner is modeled as a weighted sum of the time needed by the learner to identify the best arm, and the number of samples of arms collected by the learner before termination. Under this cost function, there is an incentive for the learner to not sample arms in all rounds, especially in the initial rounds. On the other hand, not sampling increases the termination time of the learner, which also increases cost. This trade-off necessitates new sampling strategies. We propose two policies. The first policy has an initial wait period with no sampling followed by continuous sampling. The second policy samples periodically and uses a weighted average of the rewards observed to identify the best arm. We provide analytical guarantees on the performance of both policies and supplement our theoretical results with simulations which show that our polices outperform the state-of-the-art policies for the classical best arm identification problem.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。