Tractable Sampling Strategies for Ordinal Optimization

• 成果类型: Article
• 署名作者: Shin, Dongwook; Broadie, Mark; Zeevi, Assaf
• 署名单位: Hong Kong University of Science & Technology; Columbia University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2018.1753
• 发表日期: 2018
• 页码: 1693-1712
• 关键词: multiarmed bandit; SELECTION PROCEDURES; Budget allocation; simulation; exploration; 2-stage

摘要

We consider a problem of ordinal optimization where the objective is to select the best of several competing alternatives (systems) when the probability distributions governing each system's performance are not known but can be learned via sampling. The objective is to dynamically allocate samples within a finite sampling budget to minimize the probability of selecting a system that is not the best. This objective does not possess an analytically tractable solution. We introduce a family of practically implementable sampling policies and show that the performance exhibits (asymptotically) near-optimal performance. Furthermore, we show via numerical testing that the proposed policies perform well compared with other benchmark policies.