证明了固定预算下最优选臂问题存在无法突破的性能极限。
Fundamental Limitations of Fixed-Budget Best-Arm Identification
- 提出理论下界，揭示任何算法都无法在所有情形下达到最优误差衰减率。
- 对任意3个及以上臂，误差衰减率最多为静态最优策略的1/(1+logK/8)倍。
- 解决开放问题，适用于强化学习与统计决策中的选优场景。
在固定预算的最优选臂识别问题中，算法需在K个臂之间分配采样预算，每次采样提供关于对应臂均值的噪声反馈，目标是识别出均值最大的臂。常用的性能基准是静态最优策略：一种非自适应方法，预先知晓各臂均值，通过固定采样比例来最大化错误识别概率的指数衰减速率。已有若干自适应算法被设计，使其采样比例收敛于静态最优比例。然而，是否存在算法能在所有问题实例中均匀匹配静态最优的误差衰减率，仍是未解之谜。本文给出否定回答：对于任意K≥3，且奖励服从任意单参数自然指数族分布，任何算法均存在至少一个实例，其错误衰减速率不超过静态最优的(1 + log(K)/8)^(-1)倍。该结果也解答了Qin（2022）提出的开放问题，表明固定预算最优选臂识别不具有统一复杂度。
原文摘要 · Abstract (English)
In fixed-budget best-arm identification, also known as ranking and selection, an algorithm has a sampling budget to distribute across $K$ arms. Each sample provides noisy feedback about that arm's mean, and the goal is to identify the arm with the largest mean. A common performance benchmark is the static oracle: a non-adaptive strategy that knows the means in advance and chooses fixed sampling proportions to maximize the exponential decay rate of the probability of incorrect identification. Several adaptive algorithms have been constructed such that their sampling proportions converge to the static oracle proportions. However, it has remained open whether any algorithm could match the static oracle's error decay rate uniformly across all problem instances. We answer this in the negative. For any $K\ge 3$ and for rewards drawn from any one-parameter natural exponential family, we show that for any algorithm, there is at least one instance where the error decay rate is at most $\left(1 + \frac{\log(K)}{8}\right)^{-1}$ times that of the static oracle. This also answers the open question posed by Qin (2022), showing that fixed-budget best-arm identification does not admit a complexity.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。