题　目：Dual-Directed Algorithm Design for Efficient Pure Exploration

嘉　宾：尤为 助理教授 香港科技大学

主持人：许欢 教授 上海交通大学安泰经济与管理学院

时　间：2025年4月18日（周五）10:00-11:30

地　点：安泰楼A507室

内容简介：

We study pure-exploration problems in adaptive experiments with a finite set of alternatives. The goal is to allocate measurement effort in a wise way to answer a query about the alternatives correctly with high confidence - one canonical query is to identify a best-performing alternative, leading to best-arm identification problems in the machine learning literature, or ranking and selection problems in the simulation literature. For a general query, we formulate its problem complexity measure as a maximin optimization problem, and derive the necessary and sufficient conditions for an optimal allocation using the corresponding dual variables. Remarkably, these optimality conditions lead to the extension of top-two algorithm design principle, initially proposed for best-arm identification; moreover, by introducing the dual variable, our analysis yields a simple and effective selection rule, termed information-directed selection, that adaptively identifies and chooses from a candidate set of alternatives based on their current informational value. For canonical Gaussian best-arm identification, we establish that combining with information-directed selection, top-two Thompson sampling achieves asymptotic optimality, resolving a notable open question in the pure-exploration literature. Additionally, our algorithm attains asymptotic optimality for pure-exploration thresholding bandits and epsilon-best-arm identification (or ranking and selection with a probability of good selection guarantee). Furthermore, our results provide a general principle for adapting Thompson sampling to general pure-exploration problems. Extensive numerical experiments highlight the efficiency of our proposed algorithms compared to existing methods.

演讲人简介：

Wei You is an Assistant Professor of Industrial Engineering and Decision Analytics at the Hong Kong University of Science and Technology (HKUST). His primary research interests focus on the application of applied probability and stochastic modeling to service systems, online learning, bandit algorithms. Wei earned his Bachelor's degree in Mathematics from Nanjing University and received his Ph.D. in Operations Research from Columbia University.

欢迎广大师生参加！