统计与数据科学系系列学术报告之四百一十八期

时间：2023年12月25日（周一）14:00-15:00

地点：史带楼502室

主持人：复旦大学管理学院统计与数据科学系朱仲义教授

报告人：尤为博士香港科技大学

题目：纯粹探索问题的算法设计

摘要：We consider pure-exploration problems in the context of stochastic sequential adaptive experiments with a finite set of alternative options. The goal of the decision-maker is to accurately answer a query question regarding the alternatives with high confidence with minimal measurement efforts. A typical query question is to identify the alternative with the best performance, leading to ranking and selection problems, or best-arm identification in the machine learning literature. We focus on the fixed-precision setting and derive a sufficient condition for optimality in terms of a notion of strong convergence to the optimal allocation of samples. By including the dual variables directly, we characterize the necessary and sufficient conditions for an allocation to be optimal. Remarkably, these optimality conditions enable an extension of top-two algorithm design principle (Russo, 2020), initially proposed for best-arm identification. We outline the broad contexts where our algorithmic approach can be implemented. We establish that, paired with information-directed selection, top-two Thompson sampling is (asymptotically) optimal for Gaussian best-arm identification, solving a glaring open problem in the pure exploration literature. In addition, our algorithm is optimal for epsilon-best-arm identification and thresholding bandit problems. Moreover, our analysis also leads to a general principle to guide adaptations of Thompson sampling for pure-exploration problems. Numerical experiments highlight the exceptional efficiency of our proposed algorithms relative to existing ones.

https://arxiv.org/abs/2310.19319

个人简介：尤为现供职于香港科技大学工业工程与决策分析学系，任助理教授。他2019年于哥伦比亚大学工业工程与运筹学系取得博士学位，主要研究方向包括应用概率论，统计学习，排队论及运营服务系统的应用。