We consider infinite-horizon Markov Decision Processes where parameters, such as transition probabilities, are unknown and estimated from data. The popular distributionally robust approach to addressing the parameter uncertainty can sometimes be overly conservative. In this paper, we utilize the recently proposed formulation, Bayesian risk Markov Decision Process (BR-MDP), to address parameter (or epistemic) uncertainty in MDPs. To solve the infinite-horizon BR-MDP with a class of convex risk measures, we propose a computationally efficient approach called approximate bilevel difference convex programming (ABDCP). The optimization is performed offline and produces the optimal policy that is represented as a finite state controller with desirable performance guarantees. We also demonstrate the empirical performance of the BR-MDP formulation and the proposed algorithm.

A digital twin is a virtual representation of the real system, designed to facilitate performance analysis and decision making of the actual system. At its core, a digital twin often incorporates a simulation model. However, the critical distinction from traditional simulation lies in the synchronization between the real system and its digital twin through streaming data and the frequent need for online decision making. Therefore, the increasing prevalence of digital twins poses new challenges to simulation analysis and optimization, calling for data-driven techniques that traditionally lack a significant presence in simulation literature. In this keynote, I will discuss these emerging challenges associated with simulation optimization and present some of our recent works that address these challenges, particularly in the setting where the system randomness is modeled by distributions that are estimated from streaming data.

Distributed Data Fusion (DDF), as a prevalent technique that empowers scalable, flexible, and robust information fusing, has been employed in various multi-sensor networks operating in uncertain and dynamic environments. This paper proposes a cognition difference-based mechanism to construct a dynamic trust network for real-time DDF, where the cognition difference is defined as the statistical difference between the sensors' estimated probability distributions. Distinguished by the mutual correlation between trust and cognition difference, two principles of determining trust are investigated, and their performances are analyzed by conducting simulations in the scenarios of source seeking. Our simulation and experiment results show that the proposed approach is effective in providing comprehensive and robust performance in general and unstructured environments.

We consider a robust reinforcement learning problem, where a learning agent learns from a simulated training environment. To account for the model mis-specification between this training environment and the true environment due to lack of data, we adopt a formulation of Bayesian risk MDP (BRMDP) with infinite horizon, which uses Bayesian posterior to estimate the transition model and impose a risk functional to account for the model uncertainty. Observations from the real environment that is out of the agent's control arrive periodically and are utilized by the agent to update the Bayesian posterior to reduce model uncertainty. We theoretically demonstrate that BRMDP balances the trade-off between robustness and conservativeness, and we further develop a multi-stage Bayesian risk-averse Q-learning algorithm to solve BRMDP with streaming observations from real environment. The proposed algorithm learns a risk-averse yet optimal policy that depends on the availability of real-world observations. We provide a theoretical guarantee of strong convergence for the proposed algorithm.

We consider selecting the top-m alternatives from a finite number of alternatives via Monte Carlo simulation. Under a Bayesian framework, we formulate the sampling decision as a stochastic dynamic programming problem and develop a sequential sampling policy that maximizes a value function approximation one-step look ahead. To show the asymptotic optimality of the proposed procedure, the asymptotically optimal sampling ratios that optimize the large deviations rate of the probability of false selection for selecting the top-m alternatives have been rigorously defined. The proposed sampling policy is not only proved to be consistent but also achieve the asymptotically optimal sampling ratios. Numerical experiments demonstrate superiority of the proposed allocation procedure over existing ones. History: Accepted by Bruno Tuffin, Area Editor for Simulation. Funding: This work was supported by the National Natural Science Foundation of China [Grants 72250065, 72293582, 72022001, and 71901003], and the National Science Foundation [Grant DMS-2053489], the major project of the National Natural Science Foundation of China [Grant 72293582], and the China Scholarship Council [Grant CSC202206010152]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2021.0333 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2021.0333 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

We investigate the role of noise in optimization algorithms for learning over-parameterized models. Specifically, we consider the recovery of a rank one matrix $Y^*\in R^{d\times d}$ from a noisy observation $Y$ using an over-parameterization model. Specifically, we parameterize the rank one matrix $Y^*$ by $XX^\top$, where $X\in R^{d\times d}$. We then show that under mild conditions, the estimator, obtained by the randomly perturbed gradient descent algorithm using the square loss function, attains a mean square error of $O(\sigma^2/d)$, where $\sigma^2$ is the variance of the observational noise. In contrast, the estimator obtained by gradient descent without random perturbation only attains a mean square error of $O(\sigma^2)$. Our result partially justifies the implicit regularization effect of noise when learning over-parameterized models, and provides new understanding of training over-parameterized neural networks.

Bayesian optimization (BO) is a sample-efficient approach for tuning design parameters to optimize expensive-to-evaluate, black-box performance metrics. In many manufacturing processes, the design parameters are subject to random input noise, resulting in a product that is often less performant than expected. Although BO methods have been proposed for optimizing a single objective under input noise, no existing method addresses the practical scenario where there are multiple objectives that are sensitive to input perturbations. In this work, we propose the first multi-objective BO method that is robust to input noise. We formalize our goal as optimizing the multivariate value-at-risk (MVaR), a risk measure of the uncertain objectives. Since directly optimizing MVaR is computationally infeasible in many settings, we propose a scalable, theoretically-grounded approach for optimizing MVaR using random scalarizations. Empirically, we find that our approach significantly outperforms alternative methods and efficiently identifies optimal robust designs that will satisfy specifications across multiple metrics with high probability.

We consider finite-horizon Markov Decision Processes where parameters, such as transition probabilities, are unknown and estimated from data. The popular distributionally robust approach to addressing the parameter uncertainty can sometimes be overly conservative. In this paper, we propose a new formulation, Bayesian risk Markov decision process (BR-MDP), to address parameter uncertainty in MDPs, where a risk functional is applied in nested form to the expected total cost with respect to the Bayesian posterior distributions of the unknown parameters. The proposed formulation provides more flexible risk attitudes towards parameter uncertainty and takes into account the availability of data in future time stages. To solve the proposed formulation with the conditional value-at-risk (CVaR) risk functional, we propose an efficient approximation algorithm by deriving an analytical approximation of the value function and utilizing the convexity of CVaR. We demonstrate the empirical performance of the BR-MDP formulation and proposed algorithms on a gambler’s betting problem and an inventory control problem.

Numerous empirical evidences have corroborated the importance of noise in nonconvex optimization problems. The theory behind such empirical observations, however, is still largely unknown. This paper studies this fundamental problem through investigating the nonconvex rectangular matrix factorization problem, which has infinitely many global minima due to rotation and scaling invariance. Hence, gradient descent (GD) can converge to any optimum, depending on the initialization. In contrast, we show that a perturbed form of GD with an arbitrary initialization converges to a global optimum that is uniquely determined by the injected noise. Our result implies that the noise imposes implicit bias towards certain optima. Numerical experiments are provided to support our theory.

We consider Bayesian optimization of objective functions of the form $\rho[ F(x, W) ]$, where $F$ is a black-box expensive-to-evaluate function and $\rho$ denotes either the VaR or CVaR risk measure, computed with respect to the randomness induced by the environmental random variable $W$. Such problems arise in decision making under uncertainty, such as in portfolio optimization and robust systems design. We propose a family of novel Bayesian optimization algorithms that exploit the structure of the objective function to substantially improve sampling efficiency. Instead of modeling the objective function directly as is typical in Bayesian optimization, these algorithms model $F$ as a Gaussian process, and use the implied posterior on the objective function to decide which points to evaluate. We demonstrate the effectiveness of our approach in a variety of numerical experiments.

For general multiobjective optimization problems, the usual goal is finding the set of solutions not dominated by any other solutions, that is, a set of solutions as good as any other solution in all objectives and strictly better in at least one objective. In this paper, we propose a novel performance metric called the domination measure to measure the quality of a solution, which can be intuitively interpreted as the probability that an arbitrary solution in the solution space dominates that solution with respect to a predefined probability measure. We then reformulate the original problem as a stochastic and single-objective optimization problem. We further propose a model-based approach to solve it, which leads to an ideal version algorithm and an implementable version algorithm. We show that the ideal version algorithm converges to a set representation of the global optima of the reformulated problem; we demonstrate the numerical performance of the implementable version algorithm by comparing it with numerous existing multiobjective optimization methods on popular benchmark test functions. The numerical results show that the proposed approach is effective in generating a finite and uniformly spread approximation of the Pareto optimal set of the original multiobjective problem and is competitive with the tested existing methods. The concept of domination measure opens the door for potentially many new algorithms, and our proposed algorithm is an instance that benefits from domination measure.

Numerous empirical evidence has corroborated that the noise plays a crucial rule in effective and efficient training of deep neural networks. The theory behind, however, is still largely unknown. This paper studies this fundamental problem through training a simple two-layer convolutional neural network model. Although training such a network requires to solve a non-convex optimization problem with a spurious local optimum and a global optimum, we prove that a perturbed gradient descent algorithm in conjunction with noise annealing is guaranteed to converge to a global optimum in polynomial time with arbitrary initialization. This implies that the noise enables the algorithm to efficiently escape from the spurious local optimum. Numerical experiments are provided to support our theory.

Residual Network (ResNet) is undoubtedly a milestone in deep learning. ResNet is equipped with shortcut connections between layers, and exhibits efficient training using simple first order algorithms. Despite of the great empirical success, the reason behind is far from being well understood. In this paper, we study a two-layer non-overlapping convolutional ResNet. Training such a network requires solving a non-convex optimization problem with a spurious local optimum. We show, however, that gradient descent combined with proper normalization, avoids being trapped by the spurious local optimum, and converges to a global optimum in polynomial time, when the weight of the first layer is initialized at 0, and that of the second layer is initialized arbitrarily in a ball. Numerical experiments are provided to support our theory.

Asynchronous momentum stochastic gradient descent algorithms (Async-MSGD) have been widely used in distributed machine learning, e.g., training large collaborative filtering systems and deep neural networks. Due to current technical limit, however, establishing convergence properties of Async-MSGD for these highly complicated nonoconvex problems is generally infeasible. Therefore, we propose to analyze the algorithm through a simpler but nontrivial nonconvex problems --- streaming PCA. This allows us to make progress toward understanding Aync-MSGD and gaining new insights for more general problems. Specifically, by exploiting the diffusion approximation of stochastic optimization, we establish the asymptotic rate of convergence of Async-MSGD for streaming PCA. Our results indicate a fundamental tradeoff between asynchrony and momentum: To ensure convergence and acceleration through asynchrony, we have to reduce the momentum (compared with Sync-MSGD). To the best of our knowledge, this is the first theoretical attempt on understanding Async-MSGD for distributed nonconvex stochastic optimization. Numerical experiments on both streaming PCA and training deep neural networks are provided to support our findings for Async-MSGD.

We extend the idea of model-based algorithms for deterministic optimization to simulation optimization over continuous space. Model-based algorithms iteratively generate a population of candidate solutions from a sampling distribution and use the performance of the candidate solutions to update the sampling distribution. By viewing the original simulation optimization problem as another optimization problem over the parameter space of the sampling distribution, we propose to use a direct gradient search on the parameter space to update the sampling distribution. To improve the computational efficiency, we further develop a two-timescale updating scheme that updates the parameter on a slow timescale and estimates the quantities involved in the parameter updating on the fast timescale. We analyze the convergence properties of our algorithms through techniques from stochastic approximation, and demonstrate the good empirical performance by comparing with two state-of-the-art model-based simulation optimization methods. The online supplement is available at https://doi.org/10.1287/ijoc.2017.0771 .

Many automation or manufacturing systems are large, complex, and stochastic. Since closed-form analytical solutions generally do not exist for such systems, simulation is the only faithful way for performance evaluation. From the practical engineering perspective, the designs (or solution candidates) with low complexity (called simple designs) have many advantages compared with complex designs, such as requiring less computing and memory resources, and easier to interpret and to implement. Therefore, they are usually more desirable than complex designs in the real world if they have good enough performance. Recently, Jia (IEEE Trans. Autom. Sci. Eng., vol. 8, no. 4, pp. 720-732, Oct. 2010) discussed the importance of design simplicity and introduced an adaptive simulation-based sampling algorithm to sequentially screen the designs until one simplest good enough design is found. In this paper, we consider a more generalized problem and introduce two algorithms OCBA-mSG and OCBA-bSG to identify a subset of m simplest and good enough designs among a total of K (K >; m) designs. By controlling the simulation allocation intelligently, our approach intends to find those simplest good enough designs using a minimum simulation time. The numerical results show that both OCBA-mSG and OCBA-bSG outperform some other approaches on the test problems.