提出可序列化累加的采样策略,让鲁棒排序选择更高效且保证正确率
Sequential Additivity in Distributionally Robust Ranking and Selection
- 通过自适应过程揭示采样应为累加而非乘积结构
- 新算法在有限预算下错误选择概率指数下降
- 无需识别真实最坏情况,适合实际系统优化
排序与选择(R&S)旨在从有限仿真方案中找出均值表现最佳的选项。其实际效用依赖于准确的输入建模,而有限数据常导致输入不确定性。分布鲁棒排序与选择(DRR&S)通过考虑多个可能的输入分布,选择在最差分布下表现最优的方案,但会带来乘积级的场景数量。现有静态与理想分析表明,高效采样应为累加型,仅聚焦少数关键场景。本文提出序列累加性,刻画自适应序贯过程如何催生此结构。首先建立算法无关的采样下界:任何一致的DRR&S方法必须无限次采样至少该数量的场景。随后研究一种抽象自实际设计的简化累加分配(AA)算法,利用边界穿越论证,推导出有限预算下错误选择的概率上界,并证明该概率随预算增长呈指数衰减。此外,AA恰好达到必要采样下界,说明累加性可在最强意义上实现。令人惊讶的是,无限次被采样的场景未必是真实最坏情况,表明最坏情况识别并非充分探索的必要条件。为进一步推广,引入通用累加分配(GAA)框架,模块化整合传统R&S的采样规则。在适当探索条件下,GAA方法保持了AA的核心性质。
原文摘要 · Abstract (English)
Ranking and selection (R&S) seeks to identify the alternative with the best mean performance from a finite collection of simulated alternatives. Its practical value depends on accurate simulation input modeling, which is often hindered by input uncertainty arising from limited data. Distributionally robust R&S (DRR&S) addresses this challenge by considering several plausible input distributions and selecting the alternative with the best worst-case mean performance, resulting in a multiplicative number of scenarios. Existing static and oracle analyses suggest that efficient sampling should instead be additive, concentrating on only a small number of critical scenarios. We introduce sequential additivity, which characterizes how this structure emerges from adaptive sequential procedures. We first establish an algorithm-independent sampling lower bound: any consistent DRR&S procedure must sample at least this additive number of scenarios infinitely often. We then study a simplified additive allocation (AA) procedure abstracted from practical sequential designs. Using boundary-crossing arguments, we derive a finite-budget upper bound on its probability of incorrect selection and show that this probability decays exponentially as the budget grows. Moreover, AA attains the necessary sampling lower bound exactly, showing that additivity can be achieved in the strongest possible sense. Surprisingly, the scenarios sampled infinitely often need not be the true worst-case scenarios, showing that worst-case scenario identification may not be necessary for sufficient exploration in DRR&S. To generalize these insights, we introduce a general additive allocation (GAA) framework that incorporates sampling rules from traditional R&S in a modular fashion. Under suitable exploration conditions, GAA procedures retain the key properties of AA.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。