UCB算法在非高斯分布的大规模选优中仍有效,突破了传统假设限制。
UCB for Large-Scale Pure Exploration: Beyond Sub-Gaussianity
- 设计元UCB框架,用样本均值加自身样本量的探索项选择最优项。
- 证明在方差有界下,算法能实现采样最优,即使分布非高斯。
- 适用于大规模选优问题,尤其适合重尾分布场景下的研究者。
从有限选项中选出最优解是排序与选择(R&S)和最佳臂识别(BAI)的核心目标。传统方法多依赖高斯或次高斯分布假设,限制了其在非次高斯、特别是重尾分布问题中的应用。在大规模问题中,这种分布假设的敏感性更为突出。本文受上置信界(UCB)算法在序列决策中的广泛应用启发,研究其在大规模非次高斯R&S设置下的表现。考虑最简单的UCB类算法:每个选项的UCB值为样本均值加上仅依赖于自身样本量的探索奖励。我们将此抽象为元UCB算法,并提出在停止时选择样本量最大的选项作为最优解。首先推导出正确选择概率的无分布下界;基于该下界,在容忍区设定下证明元UCB算法——因此也是一大类UCB算法——在方差一致有界条件下达到采样最优。进一步将采样最优扩展至均值差距多项式衰减的非容忍区情形,同样在方差有界假设下成立。结果表明,UCB算法可广泛适用于非次高斯的大规模选优问题。数值实验验证了理论结果,并揭示了元UCB框架内外算法的比较行为。
原文摘要 · Abstract (English)
Selecting the best alternative from a finite set is the central objective of ranking and selection (R&S) and best arm identification (BAI). Traditional R&S or BAI approaches have predominantly relied on Gaussian or sub-Gaussian assumptions on the performance distributions of all alternatives, which limit their applicability to non-sub-Gaussian---especially heavy-tailed---problems. The need to move beyond sub-Gaussianity may become even more critical in large-scale problems, which tend to be especially sensitive to distributional specifications. In this paper, motivated by the widespread use of upper confidence bound (UCB) algorithms in sequential decision making, we investigate their performance in large-scale, non-sub-Gaussian R&S settings. We consider the simplest category of UCB algorithms, where the UCB value for each alternative is defined as the sample mean plus an exploration bonus that depends only on its own sample size. We abstract this into a meta-UCB algorithm and propose letting it select the alternative with the largest sample size as the best upon stopping. For this meta-UCB algorithm, we first derive a distribution-free lower bound on the probability of correct selection. Building on this bound, we first study the indifference-zone formulation and show that the meta-UCB algorithm---and therefore a broad class of UCB algorithms---achieves sample optimality as long as the variances are uniformly bounded. We then extend sample optimality to a non-indifference-zone configuration with polynomially shrinking mean gaps under the same variance assumption. These results demonstrate the applicability of UCB algorithms to large-scale R&S problems with non-sub-Gaussian distributions. Numerical experiments support our results and provide additional insights into the comparative behaviors of UCB algorithms within and beyond our meta-UCB framework.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。