Dual-Directed Algorithm Design for Efficient Pure Exploration

• 成果类型: Article; Early Access
• 署名作者: Qin, Chao; You, Wei
• 署名单位: Stanford University; Hong Kong University of Science & Technology
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2023.0590
• 发表日期: 2025
• 关键词: pure exploration; ranking and selection; best-arm identification; adaptive experimentation; top-two algorithms; Thompson sampling

摘要

Although experimental design often focuses on selecting the single best alternative from a finite set (e.g., in ranking and selection or best-arm identification), many pureexploration problems pursue richer goals. Given a specific goal, adaptive experimentation aims to achieve it by strategically allocating sampling effort, with the underlying sample complexity characterized by a maximin optimization problem. By introducing dual variables, we derive necessary and sufficient conditions for an optimal allocation, yielding a unified algorithm design principle that extends the top-two approach beyond best-arm identification. This principle gives rise to information-directed selection, a hyperparameterfree rule that dynamically evaluates and chooses among candidates based on their current informational value. We prove that, when combined with information-directed selection, top-two Thompson sampling attains asymptotic optimality for Gaussian best-arm identification, resolving a notable open question in the pure-exploration literature. Furthermore, our framework produces asymptotically optimal algorithms for pure-exploration thresholding bandits and epsilon-best-arm identification (i.e., ranking and selection with probability-ofgood-selection guarantees), and more generally establishes a recipe for adapting Thompson sampling across a broad class of pure-exploration problems. Extensive numerical experiments highlight the efficiency of our proposed algorithms compared with existing methods.