On the Convergence Rates of a Class of Ranking and Selection Algorithms

一類排序與選擇算法的收斂速度分析

Student thesis: Doctoral Thesis

View graph of relations

Author(s)

Detail(s)

Awarding Institution
Supervisors/Advisors
Award date26 Jul 2022

Abstract

Ranking and selection (R&S) is a well-established problem in the field of stochastic simulation optimization. It aims to select the best design (i.e., the design with the largest mean performance) from a finite set of feasible designs, where the mean of each design is unknown and has to be learned by collecting samples. Great research efforts have been devoted to this problem in the literature for developing algorithms with superior empirical performance. However, many popular R&S algorithms still lack theoretical analysis, such as convergence properties and finite-time performance bounds. It will inevitably cause concerns about the effectiveness of the algorithms in practical applications. This thesis makes novel contributions to the theoretical findings as well as the development of popular R&S algorithms. With a deeper characterization of the theoretical performance, we can better understand the mechanisms of the algorithms, and gain insights into their further studies and applications.

First, we focus on a well-known method for R&S called 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 (PCS) for the best design. In Chapter 3, we investigate two popular OCBA algorithms. With known variances for samples of each design, we characterize their convergence rates with respect to commonly used performance measures. We first demonstrate that the two OCBA algorithms achieve the optimal convergence rate under measures of the PCS and expected opportunity cost (EOC). It fills the void of convergence analysis for OCBA algorithms. Next, we extend our analysis to the measure of cumulative regret, an important 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 for broader use of algorithms designed based on the OCBA optimality conditions.

Second, we consider another effective algorithm for R&S called knowledge gradient (KG). Due to the complex calculations of KG, theoretical analysis of this algorithm is difficult, and existing results are mostly about its asymptotic performance, e.g., consistency, asymptotic sample allocation, etc. In Chapter 4, we present new theoretical results about the finite-time performance of the KG Algorithm. Under the independent and normally distributed samples, we derive lower bounds and upper bounds for the probability of false selection (PFS, equals 1 − PCS) and EOC of the algorithm. With these bounds, existing asymptotic results become simple corollaries. We also show the performance of the algorithm for the multi-armed bandit (MAB) problem. These developments not only extend the analysis of KG but can also be used to analyze other improvement-based algorithms.

Third, we study the myopic algorithms, which were popular to address the R&S problem. They select the best design using a “naive” mechanism of iteratively and myopically improving an approximation of the objective measure. Although they are based on simple heuristics and lack theoretical support, they turned out highly effective and often achieved competitive empirical performance compared to algorithms that were proposed later and shown to be asymptotically optimal. In Chapter 5, we theoretically analyze these myopic algorithms and prove that they also satisfy the optimality conditions of R&S, just like some other popular R&S algorithms. It explains the good performance of myopic algorithms in various numerical tests and provides good insight into the structure of efficient R&S algorithms.

In addition to the theoretical analysis, we use numerical experiments to illustrate the convergence behaviors of the R&S algorithms under study and compare their empirical performance in solving R&S problems with different structures.