Monte Carlo simulation is a commonly used tool for evaluating the performance of complex stochastic systems. In practice, simulation can be expensive, especially when comparing a large number of alternatives, thus motivating the need to intelligently allocate simulation replications. Given a finite set of alternatives whose means are estimated via simulation, we consider the problem of determining the subset of alternatives that have means smaller than a fixed threshold. A dynamic sampling procedure that possesses not only asymptotic optimality, but also desirable finite-sample properties is proposed. Theoretical results show that there is a significant difference between finite-sample optimality and asymptotic optimality. Numerical experiments substantiate the effectiveness of the new method. Summary of Contribution: Simulation is an important tool to estimate the performance of complex stochastic systems. We consider a feasibility determination problem of identifying all those among a finite set of alternatives with mean smaller than a given threshold, in which the means are unknown but can be estimated by sampling replications via stochastic simulation. This problem appears widely in many applications, including call center design and hospital resource allocation. Our work considers how to intelligently allocate simulation replications to different alternatives for efficiently finding the feasible alternatives. Previous work focuses on the asymptotic properties of the sampling allocation procedures, whereas our contribution lies in developing a finite-budget allocation rule that possesses both asymptotic optimality and desirable finite-budget properties.

Distortion risk measure, defined by an integral of a distorted tail probability, has been widely used in behavioral economics and risk management as an alternative to expected utility. The sensitivity of the distortion risk measure is a functional of certain distribution sensitivities. We propose a new sensitivity estimator for the distortion risk measure that uses generalized likelihood ratio estimators for distribution sensitivities as input and establish a central limit theorem for the new estimator. The proposed estimator can handle discontinuous sample paths and distortion functions.

We propose a dynamic sampling allocation and selection paradigm for finding the alternative with the optimal quantile in a Bayesian framework. Myopic allocation policies (MAPs), analogous to existing methods in classic ranking and selection for selecting the alternative with the optimal mean, and computationally efficient selection policies are derived for selecting the alternative with the optimal quantile. Under certain conditions, we prove that the proposed MAPs and selection procedures are consistent, which means that the best quantile would be eventually correctly selected as the sample size goes to infinity. Numerical experiments demonstrate that the proposed schemes can significantly improve the performance.

Estimating the latent dynamics underlying biological processes is a central problem in computational biology. State-space models with Gaussian statistics are widely used for estimation of such latent dynamics and have been successfully utilized in the analysis of biological data. Gaussian statistics, however, fail to capture several key features of the dynamics of biological processes (e.g., brain dynamics) such as abrupt state changes and exogenous processes that affect the states in a structured fashion. Although Gaussian mixture process noise models have been considered as an alternative to capture such effects, data-driven inference of their parameters is not well-established in the literature. The objective of this paper is to develop efficient algorithms for inferring the parameters of a general class of Gaussian mixture process noise models from noisy and limited observations, and to utilize them in extracting the neural dynamics that underlie auditory processing from magnetoencephalography (MEG) data in a cocktail party setting. We develop an algorithm based on Expectation-Maximization to estimate the process noise parameters from state-space observations. We apply our algorithm to simulated and experimentally-recorded MEG data from auditory experiments in the cocktail party paradigm to estimate the underlying dynamic Temporal Response Functions (TRFs). Our simulation results show that the richer representation of the process noise as a Gaussian mixture significantly improves state estimation and capturing the heterogeneity of the TRF dynamics. Application to MEG data reveals improvements over existing TRF estimation techniques, and provides a reliable alternative to current approaches for probing neural dynamics in a cocktail party scenario, as well as attention decoding in emerging applications such as smart hearing aids. Our proposed methodology provides a framework for efficient inference of Gaussian mixture process noise models, with application to a wide range of biological data with underlying heterogeneous and latent dynamics.

Motivated by models of human decision making proposed to explain commonly observed deviations from conventional expected value preferences, we formulate two stochastic multi-armed bandit problems with distorted probabilities on the cost distributions: the classic K-armed bandit and the linearly parameterized bandit. In both settings, we propose algorithms that are inspired by Upper Confidence Bound (UCB) algorithms, incorporate cost distortions, and exhibit sublinear regret assuming Holder continuous weight distortion functions. For the K-armed setting, we show that the algorithm, called W-UCB, achieves problem-dependent regret O(L2 M2 log n / Δ(2/α – 1), where n is the number of plays, Δ is the gap in distorted expected value between the best and next best arm, L and alpha are the Holder constants for the distortion function, and M is an upper bound on costs, and a problem-independent regret bound of O((KL2M2)(α/2) n(2 – α)/2)). We also present a matching lower bound on the regret, showing that the regret of W-UCB is essentially unimprovable over the class of Holder-continuous weight distortions. For the linearly parameterized setting, we develop a new algorithm, a variant of the Optimism in the Face of Uncertainty Linear bandit (OFUL) algorithm called WOFUL (Weight-distorted OFUL), and show that it has regret O(d√n polylog(n)) with high probability, for sub-Gaussian cost distributions.

Cumulative prospect theory (CPT) is known to model human decisions well, with substantial empirical evidence supporting this claim. CPT works by distorting probabilities and is more general than the classic expected utility and coherent risk measures. We bring this idea to a risk-sensitive reinforcement learning (RL) setting and design algorithms for both estimation and control. The RL setting presents two particular challenges when CPT is applied: estimating the CPT objective requires estimations of the entire distribution of the value function and finding a randomized optimal policy. The estimation scheme that we propose uses the empirical distribution to estimate the CPT-value of a random variable. We then use this scheme in the inner loop of a CPT-value optimization procedure that is based on the well-known simulation optimization idea of simultaneous perturbation stochastic approximation (SPSA). We provide theoretical convergence guarantees for all the proposed algorithms and also empirically demonstrate the usefulness of our algorithms.

We formulate the statistical selection problem in a general dynamic framework comprising fully sequential sampling allocation and optimal design selection. Because the traditional probability of correct selection measure is not sufficient to capture both aspects in this more general framework, we introduce the integrated probability of correct selection to better characterize the objective. As a result, the usual selection policy of choosing the design with the largest sample mean as the estimate of the best is no longer necessarily optimal. Rather, the optimal selection policy is to choose the design that maximizes the posterior integrated probability of correct selection, which is a function of the posterior mean and the correlation structure induced by the posterior variance. Because determining the optimal selection policy is generally intractable, we also devise an approximation scheme to efficiently approximate the optimal selection policy. For the allocation policy, we study an asymptotic policy called general Bayesian budget allocation, which is comprised of a sampling statistic and a sequential rule. The optimal computing budget allocation algorithm can be interpreted as a special case of the asymptotical sampling statistics. Numerical examples are provided to illustrate the potential performance improvements, especially in small sample behavior.

Traditional regression assumes that the only data available are measurements of the value of the dependent variable for each combination of values for the independent variable. However, in many settings in stochastic (Monte Carlo) simulation, directly estimated derivative information is also available via techniques such as perturbation analysis or the likelihood ratio method. In this paper, we investigate potential modeling improvements that can be achieved by exploiting this additional gradient information in the regression setting. Using least squares and maximum likelihood estimation, we propose various direct gradient augmented regression (DiGAR) models that incorporate direct gradient estimators, starting with a one-dimensional independent variable and then extending to multidimensional input. For some special settings, we are able to characterize the variance of the estimated parameters in DiGAR and compare them analytically with the standard regression model. For a more typical stochastic simulation setting, we investigate the potential effectiveness of the augmented model by comparing it with standard regression in fitting a functional relationship for a simple queueing model, including both one-dimensional and four-dimensional examples. The preliminary empirical results are quite encouraging, as they indicate how DiGAR can capture trends that the standard model would miss. Even in queueing examples where there is a high correlation between the output and the gradient estimators, the basic DiGAR model that does not explicitly account for these correlations performs significantly better than the standard regression model.

We consider a make-to-order business that serves customers in multiple priority classes. Orders from customers in higher classes bring greater revenue, but they expect shorter lead times than customers in lower classes. In making lead time promises, the firm must recognize preexisting order commitments, uncertainty over future demand from each class, and the possibility of supply chain disruptions. We model this scenario as a Markov decision problem and use reinforcement learning to determine the firm's lead time policy. In order to achieve tractability on large problems, we utilize a sequential decision-making approach that effectively allows us to eliminate one dimension from the state space of the system. Initial numerical results from the sequential dynamic approach suggest that the resulting policies more closely approximate optimal policies than static optimization approaches.

We consider a class of the subset selection problem in ranking and selection. The objective is to identify the top m out of k designs based on simulated output. Traditional procedures are conservative and inefficient. Using the optimal computing budget allocation framework, we formulate the problem as that of maximizing the probability of correctly selecting all of the top-m designs subject to a constraint on the total number of samples available. For an approximation of this correct selection probability, we derive an asymptotically optimal allocation and propose an easy-to-implement heuristic sequential allocation procedure. Numerical experiments indicate that the resulting allocations are superior to other methods in the literature that we tested, and the relative efficiency increases for larger problems. In addition, preliminary numerical results indicate that the proposed new procedure has the potential to enhance computational efficiency for simulation optimization.

We consider the problem of efficiently allocating simulation replications in order to maximize the probability of selecting the best design under the scenario in which system performances are sampled in the presence of correlation. In the case of two designs, we are able to derive the optimal allocation exactly, and find that in the presence of positive correlation, unless the variance of one design is significantly larger than that of the other, the number of simulation replications should be identical. In extending to a general number of competing designs, an approximation for the asymptotically optimal allocation is obtained. The approximation coincides with the independent case derived previously in the limit as the correlation vanishes and also agrees with the two-design exact solution. Furthermore, the allocations prescribed by the results seem to match intuition, in terms of the relationship to correlations and relative variances between designs, again suggesting that equal allocation is optimal for sufficiently high positive correlation. An allocation algorithm based on the approximation is proposed and tested on several numerical examples.

This paper presents a new randomized search method called evolutionary random policy search (ERPS) for solving infinite-horizon discounted-cost Markov-decision-process (MDP) problems. The algorithm is particularly targeted at problems with large or uncountable action spaces. ERPS approaches a given MDP by iteratively dividing it into a sequence of smaller, random, sub-MDP problems based on information obtained from random sampling of the entire action space and local search. Each sub-MDP is then solved approximately by using a variant of the standard policy-improvement technique, where an elite policy is obtained. We show that the sequence of elite policies converges to an optimal policy with probability one. Some numerical studies are carried out to illustrate the algorithm and compare it with existing procedures.

Probably one of the most successful interfaces between operations research and computer science has been the development of discrete-event simulation software. The recent integration of optimization techniques into simulation practice, specically into commercial software, has become nearly ubiquitous, as most discrete-event simulation packages now include some form of “optimization” routine. The main thesis of this article, how-ever,is that there is a disconnect between research in simulation optimization—which has addressed the stochastic nature of discrete-event simulation by concentratingon theoretical results of convergence and specialized algorithms that are mathematically elegant—and the recent software developments, which implement very general algorithms adopted from techniques in the deterministic optimization metaheuristic literature (e.g., genetic algorithms, tabu search, artificial neural networks). A tutorial exposition that summarizes the approaches found in the research literature is included, as well as a discussion contrasting these approaches with the algorithms implemented in commercial software. The article concludes with the author's speculations on promising research areas and possible future directions in practice.

Optimal structured feedback control policies for rate-based flow control of available bit rate service in asynchronous transfer mode networks are obtained in the presence of information and propagation delays, using a numerically efficient two-timescale simultaneous perturbation stochastic approximation (SPSA) algorithm. Models comprising both a single bottleneck node and a network with multiple bottleneck nodes are considered. A convergence analysis of the algorithm is presented. Numerical experiments demonstrate fast convergence even in the presence of significant delays. We also illustrate performance comparisons with the well-known explicit rate indication for congestion avoidance (ERICA) algorithm and describe another algorithm (based on ERICA) that does not require estimating available bandwidth (as in ERICA).