新武器不断出现时，如何高效选择最优策略？
Multi-Armed Bandits with Arriving Arms: Sequential Screening, Dynamic Regret, and Sublinear Guarantees
- 引入新武器前先预筛选，再竞争淘汰
- 动态遗憾可亚线性，适应武器随时间变化
- 适合持续更新选项的在线决策场景
我们研究一种随机多臂老虎机问题，其中可用的臂（选项）随时间增加。这在序列实验中常见——新方法或治疗方案在研究过程中陆续出现，此时以固定最优臂为基准的遗憾不再合适。我们改用当前可用最优臂作为基准，提出动态遗憾评估。为应对到达信息差异（AID）和基准漂移（DB）问题，提出UCB-AA算法：通过预筛选新到臂后再参与竞争，实现基于淘汰机制的在线决策。理论证明该算法的遗憾上界显式依赖于到达过程，在间隙演化满足正则性条件下可实现亚线性动态遗憾，并支持未知总时长的在线扩展。模拟结果表明，相比基线方法，UCB-AA减少了无效尝试次数，保持较小活跃臂集，同时维持良好遗憾表现。
原文摘要 · Abstract (English)
We study a stochastic multi-armed bandit problem in which the set of available arms expands over time. This setting arises in sequential experimentation when new actions or treatments become available during an ongoing study, making regret against a single best arm in hindsight inappropriate. We instead evaluate performance relative to the best arm currently available, leading to a dynamic-regret criterion for arriving-arm environments. To address the resulting challenges of arrival information discrepancy (AID) and a drifting benchmark (DB), we propose UCB for Arriving Arms (UCB-AA), an elimination-based procedure with an aiding preliminary screening step for newly arrived arms before full competition with incumbent arms. We show that UCB-AA attains regret bounds that depend explicitly on the arrival process, achieves sublinear dynamic regret under regularity conditions on gap evolution, and admits an online extension for unknown horizons. Simulation results show that UCB-AA reduces wasted pulls and maintains a smaller active arm set while preserving competitive regret performance.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。