提出新算法，在组合探索中高效找出最优臂
An Algorithm for Fixed Budget Best Arm Identification with Combinatorial Exploration
- 将K个臂分成log₂K组，用似然比检测每组是否含最优臂
- 通过汉明解码唯一确定最优臂，错误率有理论保证
- 适合需组合采样且追求高精度识别的场景
我们研究了在K臂赌博机框架下的最佳臂识别（BAI）问题，但做出关键修改：每次可同时选择一组臂进行探索，而非单个臂。此时代理观察的是所选臂奖励的样本均值。该设定引发多重权衡——同时采样更多臂能获得更全面环境信息，但会稀释对个体奖励分布的观测精度；而将大量次优臂组合虽可降低组内方差，却可能抬升其均值，使其接近最优臂所在组。为解决此问题，我们提出一种算法，将臂划分为log₂K个组，对每组执行似然比检验以判断是否包含最优臂，再通过汉明解码确定唯一最优臂。我们基于新的难易度参数H₄推导出该算法的错误概率上界，并在若干条件下证明其优于单臂探索的现有最优算法。
原文摘要 · Abstract (English)
We consider the best arm identification (BAI) problem in the $K-$armed bandit framework with a modification - the agent is allowed to play a subset of arms at each time slot instead of one arm. Consequently, the agent observes the sample average of the rewards of the arms that constitute the probed subset. Several trade-offs arise here - e.g., sampling a larger number of arms together results in a wider view of the environment, while sampling fewer arms enhances the information about individual reward distributions. Furthermore, grouping a large number of suboptimal arms together albeit reduces the variance of the reward of the group, it may enhance the group mean to make it close to that containing the optimal arm. To solve this problem, we propose an algorithm that constructs $\log_2 K$ groups and performs a likelihood ratio test to detect the presence of the best arm in each of these groups. Then a Hamming decoding procedure determines the unique best arm. We derive an upper bound for the error probability of the proposed algorithm based on a new hardness parameter $H_4$. Finally, we demonstrate cases under which it outperforms the state-of-the-art algorithms for the single play case.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。