提出高效识别优质臂的新方法，兼顾快速与准确。
Reward Maximization for Pure Exploration: Minimax Optimal Good Arm Identification for Nonparametric Multi-Armed Bandits
- 结合奖励最大化采样与新型非参数序贯检验
- 在误差约束下实现最小化停止时间的最优解
- 适用于需要快速筛选优质选项的场景
在多臂赌博机中，奖励最大化与纯探索常相互冲突。本文聚焦于优质臂识别（GAI），目标是尽快识别均值高于阈值的臂。我们证明，通过将奖励最大化采样算法与新型非参数即时有效序贯检验相结合，可高效解决GAI问题。该序贯检验在高度非参数假设下保持误差控制，并渐近达到最小最大最优的e-功效（e-power）。将最小化后悔的采样策略与该检验结合，所提方法在误差概率约束下实现了最小最大最优的停止时间。实验结果表明，该方法在合成与真实数据上均显著提升效率，所有停止时间下的期望样本数均减少至少50%。
原文摘要 · Abstract (English)
In multi-armed bandits, the tasks of reward maximization and pure exploration are often at odds with each other. The former focuses on exploiting arms with the highest means, while the latter may require constant exploration across all arms. In this work, we focus on good arm identification (GAI), a practical bandit inference objective that aims to label arms with means above a threshold as quickly as possible. We show that GAI can be efficiently solved by combining a reward-maximizing sampling algorithm with a novel nonparametric anytime-valid sequential test for labeling arm means. We first establish that our sequential test maintains error control under highly nonparametric assumptions and asymptotically achieves the minimax optimal e-power, a notion of power for anytime-valid tests. Next, by pairing regret-minimizing sampling schemes with our sequential test, we provide an approach that achieves minimax optimal stopping times for labeling arms with means above a threshold, under an error probability constraint. Our empirical results validate our approach beyond the minimax setting, reducing the expected number of samples for all stopping times by at least 50% across both synthetic and real-world settings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。