Search

We consider quantile optimization of black-box functions that are estimated with noise. We propose two new iterative three-timescale local search algorithms. The first algorithm uses an appropriately modified finite-difference-based gradient estimator that requires $2d$ + 1 samples of the black-box function per iteration of the algorithm, where $d$ is the number of decision variables (dimension of the input vector). For higher-dimensional problems, this algorithm may not be practical if the black-box function estimates are expensive. The second algorithm employs a simultaneous-perturbation-based gradient estimator that uses only three samples for each iteration regardless of problem dimension. Under appropriate conditions, we show the almost sure convergence of both algorithms. In addition, for the class of strongly convex functions, we further establish their (finite-time) convergence rate through a novel fixed-point argument. Simulation experiments indicate that the algorithms work well on a variety of test problems and compare well with recently proposed alternative methods.

Incompatibility between patient and donor is a major barrier in kidney transplantation (KT). The increasing shortage of kidney donors has driven the development of desensitization techniques to overcome this immunological challenge. Compared with compatible KT, patients undergoing incompatible KTs are more likely to experience rejection, infection, malignancy, and graft loss. We study the optimal acceptance of possibly incompatible kidneys for individual end-stage kidney disease patients. To capture the effect of incompatibility, we propose a Markov Decision Process (MDP) model that explicitly includes compatibility as a state variable. The resulting higher-dimensional model makes it more challenging to analyze, but under suitable conditions, we derive structural properties including control limit-type optimal policies that are easy to compute and implement. Numerical examples illustrate the behavior of the optimal policy under different mismatch levels and highlight the importance of explicitly incorporating the incompatibility level into the acceptance decision when desensitization therapy is an option.

In this paper we study simulation-based methods for estimating gradients in stochastic networks. We derive a new method of calculating weak derivative estimator using importance sampling transform, and our method has less computational cost than the classical method. In the context of M/M/1 queueing network and stochastic activity network, we analytically show that our new method won't result in a great increase of sample variance of the estimators. Our numerical experiments show that under same simulation time, the new method can yield a narrower confidence interval of the true gradient than the classical one, suggesting that the new method is more competitive.

In solving simulation-based stochastic root-finding or optimization problems that involve rare events, such as in extreme quantile estimation, running crude Monte Carlo can be prohibitively inefficient. To address this issue, importance sampling can be employed to drive down the sampling error to a desirable level. However, selecting a good importance sampler requires knowledge of the solution to the problem at hand, which is the goal to begin with and thus forms a circular challenge. We investigate the use of adaptive importance sampling to untie this circularity. Our procedure sequentially updates the importance sampler to reach the optimal sampler and the optimal solution simultaneously, and can be embedded in both sample average approximation and stochastic approximation-type algorithms. Our theoretical analysis establishes strong consistency and asymptotic normality of the resulting estimators. We also demonstrate, via a minimax perspective, the key role of using adaptivity in controlling asymptotic errors. Finally, we illustrate the effectiveness of our approach via numerical experiments.

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 optimally allocates a limited computing budget to maximize a lower bound on the probability of correctly selecting the best action at each node. Compared to widely used Upper Confidence Bound (UCB) tree policies, the new tree policy presents a more balanced approach to manage the exploration and exploitation trade-off when the sampling budget is limited. Furthermore, UCB assumes that the support of reward distribution is known, whereas our algorithm relaxes this assumption. Numerical experiments demonstrate the efficiency of our algorithm in selecting the best action at the root., Comment: Submitted to IEEE Transactions on Automatic Control

Since the onset of the COVID-19 outbreak in Wuhan, China, numerous forecasting models have been proposed to project the trajectory of coronavirus infection cases. We propose a new discrete-time Markov chain transition matrix model that directly incorporates stochastic behavior and for which parameter estimation is straightforward from available data. Using such data from China's Hubei province (for which Wuhan is the provincial capital city), the model is shown to be flexible, robust, and accurate. As a result, it has been adopted by the first Shanghai assistance medical team in Wuhan's Jinyintan Hospital, which was the first designated hospital to take COVID-19 patients in the world. The forecast has been used for preparing medical staff, intensive care unit (ICU) beds, ventilators, and other critical care medical resources and for supporting real-time medical management decisions. Empirical data from China's first two months (January/February) of fighting COVID-19 was collected and used to enhance the model by embedding NPI efficiency into the model. We applied the model to forecast Italy, South Korea, and Iran on March 9. Later we made forecasts for Spain, Germany, France, US on March 24. Again, the model has performed very well, proven to be flexible, robust, and accurate for most of these countries/regions outside China.

We consider option pricing using a discrete-time Markov switching stochastic volatility with co-jump model, which can model volatility clustering and varying mean-reversion speeds of volatility. For pricing European options, we develop a computationally efficient method for obtaining the probability distribution of average integrated variance (AIV), which is key to option pricing under stochastic-volatility-type models. Building upon the efficiency of the European option pricing approach, we are able to price an American-style option, by converting its pricing into the pricing of a portfolio of European options. Our work also provides constructive guidance for analyzing derivatives based on variance, e.g., the variance swap. Numerical results indicate our methods can be implemented very efficiently and accurately.

We consider estimating an expected infinite-horizon cumulative discounted cost/reward contingent on an underlying stochastic process by Monte Carlo simulation. An unbiased estimator based on truncating the cumulative cost at a random horizon is proposed. Explicit forms for the optimal distributions of the random horizon are given, and explicit expressions for the optimal random truncation level are obtained, leading to a full analysis of the bias-variance tradeoff when comparing this new class of randomized estimators with traditional fixed truncation estimators. Moreover, we characterize when the optimal randomized estimator is preferred over a fixed truncation estimator by considering the tradeoff between bias and variance. This comparison provides guidance on when to choose randomized estimators over fixed truncation estimators in practice. Numerical experiments substantiate the theoretical results., Comment: 35 pages, 5 figures

Under a Bayesian framework, we formulate the fully sequential sampling and selection decision in statistical ranking and selection as a stochastic control problem, and derive the associated Bellman equation. Using value function approximation, we derive an approximately optimal allocation policy. We show that this policy is not only computationally efficient but also possesses both one-step-ahead and asymptotic optimality for independent normal sampling distributions. Moreover, the proposed allocation policy is easily generalizable in the approximate dynamic programming paradigm., Comment: 15 pages, 8 figures, to appear in IEEE Transactions on Automatic Control

In this note, we introduce a new finite difference approximation called the Black-Box Logarithmic Expansion Numerical Derivative (BLEND) algorithm, which is based on a formal logarithmic expansion of the differentiation operator. BLEND capitalizes on parallelization and provides derivative approximations of arbitrarily precision, i.e., our analysis can be used to determine the number of terms in the series expansion to guarantee a specified number of decimal places of accuracy. Furthermore, in the vector setting, the complexity of the resulting directional derivative is independent of the dimension of the parameter.