Stochastic Dynamic Optimization Under Ambiguity

Abstract

Stochastic dynamic optimization methods are powerful mathematical tools for informing sequential decision-making in environments where the outcomes of decisions are uncertain. For instance, the Markov decision process (MDP) has found success in many application areas, including the evaluation and design of treatment and screening protocols for medical decision making. However, the usefulness of these models is only as good as the data used to parameterize them, and multiple competing data sources are common in many application areas. Unfortunately, the recommendations that result from the optimization process can be sensitive to the data used and thus, susceptible to the impacts of ambiguity in the choices regarding the model's construction.

To address the issue of ambiguity in MDPs, we introduce the Multi-model MDP (MMDP) which generalizes a standard MDP by allowing for multiple models of the rewards and transition probabilities. The solution of the MMDP is a policy that considers the performance with respect to the different models and allows for the decision-maker (DM) to explicitly trade-off conflicting sources of data. In this thesis, we study this problem in three parts.

In the first part, we study the weighted value problem (WVP) in which the DM’s objective is to find a single policy that maximizes the weighted value of expected rewards in each model. We identify two important variants of this problem: the non-adaptive WVP in which the DM must specify the decision-making strategy before the outcome of ambiguity is observed and the adaptive WVP in which the DM is allowed to adapt to the outcomes of ambiguity. To solve these problems, we develop exact methods and fast approximation methods supported by error bounds. Finally, we illustrate the effectiveness and the scalability of our approach using a case study in preventative blood pressure and cholesterol management that accounts for conflicting published cardiovascular risk models.

In the second part, we leverage the special structure of the non-adaptive WVP to design exact decomposition methods for solving MMDPs with a larger number of models. We present a branch-and-cut approach to solve a mixed-integer programming formulation of the problem and a custom branch-and-bound approach. Numerical experiments show that a customized implementation of branch-and-bound significantly outperforms branch-and-cut and allows for the solution of MMDPs with larger numbers of models.

In the third part, we extend the MMDP beyond the WVP to consider other objective functions that are sensitive to the ambiguity arising from the existence of multiple models. We modify the branch-and-bound procedure to solve these alternate formulations and compare the resulting policies to policies found using tractable heuristics. Using two case studies, we show that the solution to the mean value problem, wherein all parameters take on their mean values, can perform quite well with respect to several measures of performance under ambiguity.

In summary, in this dissertation, we present new methods for stochastic dynamic optimization under ambiguity. We represent ambiguity through multiple plausible models of the MDP. We analyze alternative forms of the problems, develop solution methods, and identify properties of the optimal solutions that provide insight into the effects of ambiguity on optimal policies. Although we illustrate our methods on decision-making for medical treatment and machine maintenance, the methods we present in this thesis can be applied to other domains in which optimal sequential decision-making uncertainty is clouded by ambiguity.