Convergence Rate Analysis for Optimal Computing Budget Allocation Algorithms
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Mirror Descent Algorithms for Risk Budgeting Portfolios
This paper introduces and examines numerical approximation schemes for computing risk budgeting portfolios associated to positive homogeneous and sub-additive risk measures. We employ Mirror Descent algorithms to determi…
Large-scale benchmarking of multi-objective soft-computing metaheuristics for redundancy allocation in repairable k-out-of-n systems
This paper presents a large-scale budget-aware benchmark of multi-objective soft-computing metaheuristics for a bi-objective redundancy allocation problem in repairable k-out-of-n systems. The problem combines cost minim…
n-Step Temporal Difference Learning with Optimal n
We consider the problem of finding the optimal value of n in the n-step temporal difference (TD) learning algorithm. Our objective function for the optimization problem is the average root mean squared error (RMSE). We f…
Stochastic OptimizationSelection of the Most Probable Best
We consider an expected-value ranking and selection (R&S) problem where all k solutions' simulation outputs depend on a common parameter whose uncertainty can be modeled by a distribution. We define the most probable bes…
An Optimal Computing Budget Allocation Tree Policy for Monte Carlo Tree Search
We analyze a tree search problem with an underlying Markov decision process, in which the goal is to identify the best action at the root that achieves the highest cumulative reward. We present a new tree policy that opt…