skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Posterior-Based Stopping Rules for Bayesian Ranking-and-Selection Procedures
Sequential ranking-and-selection procedures deliver Bayesian guarantees by repeatedly computing a posterior quantity of interest—for example, the posterior probability of good selection or the posterior expected opportunity cost—and terminating when this quantity crosses some threshold. Computing these posterior quantities entails nontrivial numerical computation. Thus, rather than exactly check such posterior-based stopping rules, it is common practice to use cheaply computable bounds on the posterior quantity of interest, for example, those based on Bonferroni’s or Slepian’s inequalities. The result is a conservative procedure that samples more simulation replications than are necessary. We explore how the time spent simulating these additional replications might be better spent computing the posterior quantity of interest via numerical integration, with the potential for terminating the procedure sooner. To this end, we develop several methods for improving the computational efficiency of exactly checking the stopping rules. Simulation experiments demonstrate that the proposed methods can, in some instances, significantly reduce a procedure’s total sample size. We further show these savings can be attained with little added computational effort by making effective use of a Monte Carlo estimate of the posterior quantity of interest. Summary of Contribution: The widespread use of commercial simulation software in industry has made ranking-and-selection (R&S) algorithms an accessible simulation-optimization tool for operations research practitioners. This paper addresses computational aspects of R&S procedures delivering finite-time Bayesian statistical guarantees, primarily the decision of when to terminate sampling. Checking stopping rules entails computing or approximating posterior quantities of interest perceived as being computationally intensive to evaluate. The main results of this paper show that these quantities can be efficiently computed via numerical integration and can yield substantial savings in sampling relative to the prevailing approach of using conservative bounds. In addition to enhancing the performance of Bayesian R&S procedures, the results have the potential to advance other research in this space, including the development of more efficient allocation rules.  more » « less
Award ID(s):
2035086
PAR ID:
10412970
Author(s) / Creator(s):
;
Date Published:
Journal Name:
INFORMS Journal on Computing
Volume:
34
Issue:
3
ISSN:
1091-9856
Page Range / eLocation ID:
1711 to 1728
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, Proceedings of the Winter Simulation Conference)
    Bae, K-H; Feng, B; Kim, S; Lazarova-Molnar, S; Zheng, Z; Roeder, T; Thiesing, R (Ed.)
    Cheap parallel computing has greatly extended the reach of ranking & selection (R&S) for simulation optimization. In this paper we present an evaluation of bi-PASS, a R&S procedure created specifically for parallel implementation and very large numbers of system designs. We compare bi-PASS to the state-ofthe- art Good Selection Procedure and an easy-to-implement subset selection procedure. This is one of the few papers to consider both computational and statistical comparison of parallel R&S procedures. 
    more » « less
  2. ; ; (, International Journal for Uncertainty Quantification)
    The formulation of Bayesian inverse problems involves choosing prior distributions; choices that seem equally reason-able may lead to significantly different conclusions. We develop a computational approach to understand the impact of the hyperparameters defining the prior on the posterior statistics of the quantities of interest. Our approach relies on global sensitivity analysis (GSA) of Bayesian inverse problems with respect to the prior hyperparameters. This, however, is a challenging problem-a naive double loop sampling approach would require running a prohibitive number of Markov chain Monte Carlo (MCMC) sampling procedures. The present work takes a foundational step in making such a sensitivity analysis practical by combining efficient surrogate models and a tailored importance sampling approach. In particular, we can perform accurate GSA of posterior statistics of quantities of interest with respect to prior hyperparameters without the need to repeat MCMC runs. We demonstrate the effectiveness of the approach on a simple Bayesian linear inverse problem and a nonlinear inverse problem governed by an epidemiological model. 
    more » « less
  3. ; (, Naval Research Logistics (NRL))
    Evaluating two‐terminal network reliability is a classical problem with numerous applications. Because this problem is #P‐Complete, practical studies involving large systems commonly resort to approximating or estimating system reliability rather than evaluating it exactly. Researchers have characterized signatures, such as the destruction spectrum and survival signature, which summarize the system's structure and give rise to procedures for evaluating or approximating network reliability. These procedures are advantageous if the signature can be computed efficiently; however, computing the signature is challenging for complex systems. With this motivation, we consider the use of Monte Carlo (MC) simulation to estimate the survival signature of a two‐terminal network in which there are two classes of i.i.d. components. In this setting, we prove that each MC replication to estimate the signature of a multi‐class system entails solving a multi‐objective maximum capacity path problem. For the case of two classes of components, we adapt a Dijkstra's‐like bi‐objective shortest path algorithm from the literature for the purpose of solving the resulting bi‐objective maximum capacity path problem. We perform computational experiments to compare our method's efficiency against intuitive benchmark approaches. Our computational results demonstrate that the bi‐objective optimization approach consistently outperforms the benchmark approaches, thereby enabling a larger number of MC replications and improved accuracy of the reliability estimation. Furthermore, the efficiency gains versus benchmark approaches appear to become more significant as the network increases in size. 
    more » « less
  4. ; ; (, Operations Research)
    We consider a simulation-based ranking and selection (R&S) problem with input uncertainty, in which unknown input distributions can be estimated using input data arriving in batches of varying sizes over time. Each time a batch arrives, additional simulations can be run using updated input distribution estimates. The goal is to confidently identify the best design after collecting as few batches as possible. We first introduce a moving average estimator for aggregating simulation outputs generated under heterogenous input distributions. Then, based on a sequential elimination framework, we devise two major R&S procedures by establishing exact and asymptotic confidence bands for the estimator. We also extend our procedures to the indifference zone setting, which helps save simulation effort for practical usage. Numerical results show the effectiveness and necessity of our procedures in controlling error from input uncertainty. Moreover, the efficiency can be further boosted through optimizing the “drop rate” parameter, which is the proportion of past simulation outputs to discard, of the moving average estimator. 
    more » « less
  5. ; ; ; (, Proceedings of the 36th International Conference on Machine Learning)
    We present a novel technique for tailoring Bayesian quadrature (BQ) to model selection. The state-of-the-art for comparing the evidence of multiple models relies on Monte Carlo methods, which converge slowly and are unreliable for computationally expensive models. Although previous research has shown that BQ offers sample efficiency superior to Monte Carlo in computing the evidence of an individual model, applying BQ directly to model comparison may waste computation producing an overly-accurate estimate for the evidence of a clearly poor model. We propose an automated and efficient algorithm for computing the most-relevant quantity for model selection: the posterior model probability. Our technique maximizes the mutual information between this quantity and observations of the models’ likelihoods, yielding efficient sample acquisition across disparate model spaces when likelihood observations are limited. Our method produces more-accurate posterior estimates using fewer likelihood evaluations than standard Bayesian quadrature and Monte Carlo estimators, as we demonstrate on synthetic and real-world examples. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email