Ordinal optimization (OO) is a widely-studied technique for optimizing discrete-event dynamic systems (DEDS). It evaluates the performance of the system designs in a finite set by sampling and aims to correctly make ordinal comparison of the designs. A well-known method in OO is the optimal computing budget allocation (OCBA). It builds the optimality conditions for the number of samples allocated to each design, and the sample allocation that satisfies the optimality conditions is shown to asymptotically maximize the probability of correct selection for the best design. In this paper, we investigate two popular OCBA algorithms. With known variances for samples of each design, we characterize their convergence rates with respect to different performance measures. We first demonstrate that the two OCBA algorithms achieve the optimal convergence rate under measures of probability of correct selection and expected opportunity cost. It fills the void of convergence analysis for OCBA algorithms. Next, we extend our analysis to the measure of cumulative regret, a main measure studied in the field of machine learning. We show that with minor modification, the two OCBA algorithms can reach the optimal convergence rate under cumulative regret. It indicates the potential of broader use of algorithms designed based on the OCBA optimality conditions.
翻译:常规优化(OO)是优化离散活动动态系统(DEDS)的一种广泛研究的技术,它通过抽样评估了系统设计在一定限度内通过抽样评估的性能,目的是正确地对设计进行正态比较。在OO中,一个众所周知的方法是最佳计算预算拨款(OCBA),它为每个设计分配样本的数量建立了最佳条件,而符合最佳条件的样本分配则显示我们的分析无一例外地将正确选择最佳设计的最佳设计的可能性最大化。在本文中,我们调查了两种流行的OCBA算法。根据每种设计样本的已知差异,我们用不同的性能衡量其趋同率。我们首先表明,OCBA的两种算法在正确选择的可能性和预期机会成本的衡量下实现了最佳趋同率。它填补了对OCBA算法的趋同分析的空白。接着,我们将我们的分析扩大到累积遗憾的尺度,这是在机器学习领域研究的一项主要尺度。我们表明,经过微小的修改后,OCBA的两种算法可以达到以最优化的OCBA为主的趋同率。