arXiv:2510.00073stat.MLcs.AI2025-10

提出高效识别所有近优选项的算法,适用于高成本探索场景。

Identifying All ε-Best Arms in (Misspecified) Linear Bandits

  • 设计新算法 LinFACT,优化线性贝叶斯中近优臂识别
  • 理论证明样本复杂度逼近最优,减少实验次数
  • 适用于药物发现等实际场景,提升早期筛选效率

为应对药物发现等高试错成本任务中需高效识别多个候选方案的需求,本文提出一种近最优算法,用于识别所有ε-最优臂(即性能不超过ε次优的臂)。具体地,引入了LinFACT算法,旨在优化线性贝叶斯中所有ε-最优臂的识别。我们建立了该问题的信息论下界,并证明LinFACT在实例层面接近最优,其样本复杂度仅比下界大一个对数因子。关键创新在于将下界直接融入上界推导的缩放过程,从而确定终止轮次与样本复杂度。同时,分析扩展至模型误设及广义线性模型情形。数值实验包括合成数据与真实药物发现数据,结果表明LinFACT能以更少样本识别更多优质候选,显著提升计算效率,加速初期探索性实验。

原文摘要 · Abstract (English)

Motivated by the need to efficiently identify multiple candidates in high trial-and-error cost tasks such as drug discovery, we propose a near-optimal algorithm to identify all ε-best arms (i.e., those at most ε worse than the optimum). Specifically, we introduce LinFACT, an algorithm designed to optimize the identification of all ε-best arms in linear bandits. We establish a novel information-theoretic lower bound on the sample complexity of this problem and demonstrate that LinFACT achieves instance optimality by matching this lower bound up to a logarithmic factor. A key ingredient of our proof is to integrate the lower bound directly into the scaling process for upper bound derivation, determining the termination round and thus the sample complexity. We also extend our analysis to settings with model misspecification and generalized linear models. Numerical experiments, including synthetic and real drug discovery data, demonstrate that LinFACT identifies more promising candidates with reduced sample complexity, offering significant computational efficiency and accelerating early-stage exploratory experiments.

强化学习多臂赌博机药物发现

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。