提出渐近误差控制框架,提升非参数环境下最优选项识别效率
Exploration in the Limit
- 采用渐近有效置信序列,实现灵活非参数下的误差控制
- 在弱信号场景下样本复杂度逼近高斯情形最优水平
- 适合需长周期实验与个体特征融合的现实决策场景
在固定置信度的最佳臂识别(BAI)中,目标是在误差概率低于给定阈值的前提下快速识别最优选项。尽管已有众多BAI算法,但现有方法在实际应用中常受限于严格的精确误差控制,需依赖宽松的尾部不等式或参数假设。为此,本文引入一种放松的公式:要求误差控制在最小样本量下渐近成立,这更契合弱信号、高显著性要求及事后推断等现实场景。该设定允许获得更紧的最优性,并能灵活处理非参数结果分布和个体级上下文信息。我们提出了新的渐近任意时有效性置信序列,用于设计适用于该渐近框架的新型BAI算法。该方法可灵活融入协变量以降低方差,并在完全非参数设置下保证近似误差控制。在温和收敛假设下,我们给出了样本复杂度的渐近界,证明其最坏情况下的样本复杂度与已知方差下高斯情形最优解的最好情况相当。实验表明,该方法在保持误差控制的同时显著降低平均样本复杂度。
原文摘要 · Abstract (English)
In fixed-confidence best arm identification (BAI), the objective is to quickly identify the optimal option while controlling the probability of error below a desired threshold. Despite the plethora of BAI algorithms, existing methods typically fall short in practical settings, as stringent exact error control requires using loose tail inequalities and/or parametric restrictions. To overcome these limitations, we introduce a relaxed formulation that requires valid error control asymptotically with respect to a minimum sample size. This aligns with many real-world settings that often involve weak signals, high desired significance, and post-experiment inference requirements, all of which necessitate long horizons. This allows us to achieve tighter optimality, while better handling flexible nonparametric outcome distributions and fully leveraging individual-level contexts. We develop a novel asymptotic anytime-valid confidence sequences over arm indices, and we use it to design a new BAI algorithm for our asymptotic framework. Our method flexibly incorporates covariates for variance reduction and ensures approximate error control in fully nonparametric settings. Under mild convergence assumptions, we provide asymptotic bounds on the sample complexity and show the worst-case sample complexity of our approach matches the best-case sample complexity of Gaussian BAI under exact error guarantees and known variances. Experiments suggest our approach reduces average sample complexities while maintaining error control.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。