Fixed Budget Ranking and Selection with Streaming Input Data
Fixed Budget Ranking and Selection with Streaming Input Data
复制标题
DOI：
10.1109/wsc57314.2022.10015327
复制
发表时间：
2022-12
期刊：
影响因子：
--
通讯作者：
Yuhao Wang;Enlu Zhou
中科院分区：
文献类型：
--
作者：
Yuhao Wang;Enlu Zhou
我们考虑一个固定的预算排名和选择问题的输入不确定性，未知的输入分布可以估计使用输入数据到达批次的大小随时间的推移。每次批次到达时，输入分布都会更新，并且可以使用给定的模拟预算运行其他模拟。在每个时间段内，我们应用大偏差理论计算率函数的概率与输入分布的错误选择（PFS），并制定了一个优化问题，以最大化的PFS的衰减率。利用导出的最优性条件，我们设计了一个动态的最优预算分配过程，顺序更新的输入分布下的流输入数据。我们证明了该过程的一致性和渐近最优性，数值计算表明，我们的过程相比，平等的分配规则和一个简单的扩展的最优计算预算分配（OCBA）算法的高效率。
We consider a fixed budget ranking and selection problem with input uncertainty, where unknown input distributions can be estimated using input data arriving in batches of varying sizes over time. Each time a batch arrives, the input distribution is updated and additional simulations can be run with a given simulation budget. Within each time stage, we apply the large deviations theory to compute the rate function of the probability of false selection (PFS) with input distribution and formulate an optimization problem to maximize the decay rate of PFS. With the derived optimality condition, we design a dynamic optimal budget allocation procedure with sequentially updated input distributions under streaming input data. We prove the consistency and asymptotic optimality of the procedure, and numerically show the high efficiency of our procedure compared to the equal allocation rule and a simple extension of the Optimal Computing Budget Allocation (OCBA) algorithm.