Analysis of Sequential Decision Making Processes Under Exogenous Uncertainty

Abstract

In this dissertation, we consider sequential optimization decision making problems, which entail making optimal decisions at specified epochs of time to maximize or minimize the specific objective of the decision maker. The system in question evolves in a probabilistic manner through time. This means that the evolution of uncertainty is revealed in a sequential manner as and when the random events occur. The decision maker bases decisions as the uncertainty evolves, up to the point of the decision epoch, and known information about its probabilistic evolution through distributions. The class of problems we focus on in this research is multistage sequential decision making problems where the uncertainty is purely exogenous in nature. We consider the aforementioned class of research problems and provide an overview of the various methodologies used in solving them. Specifically, we compare the two important existing paradigms which are used to model problems that have the above attributes, namely multistage stochastic programming (MSP) and Markov decision processes (MDP). The need to make this comparison arises from the fact that research communities use these two approaches to solve sequential decision making problems even though, both these approaches have historically evolved from different pedagogical views. The ideas and algorithms used to solve these problems could potentially be useful to both communities working on these problems. As far as we have looked, there have been few attempts in the literature which consider problems that are solved using either methodologies and then compare and contrast the two approaches which would then give an insight into which method might be computationally more efficient to use for a given problem. By and large, traditionally there is a set of problems which are solved using either methods, and usually they are used to obtain a robust and tractable solution to the problem. It remains to be seen if using an alternate method would provide comparable results and are computationally as/more viable. This research effort intends to bridge this gap in the current literature and make an attempt to draw some inferences into the suitability of using one method versus the other as applied to specific problem instances. \\We describe these approaches and draw an equivalence between these methods while highlighting subtle differences in both these methodologies using a numerical example. We then extend this research to solve a large scale sequential routing problem for Unmanned Aerial Vehicles (UAV) for reconnaissance patrolling missions, formulated as a two stage stochastic integer program with a single recourse action and present the results. We then propose an extension of the above problem to include multiple recourse actions and shall attempt to use standard heuristic techniques such as progressive hedging- a scenario-based decomposition technique well-suited to solving stochastic mixed-integer programs, to formulate and solve this sequential routing UAV problem with multiple recourse actions. In addition we also propose an alternative MDP formulation of the same problem posed as a multi-stage sequential decision making problem. The ultimate goal of this research is to investigate the cross applicability of algorithms used in each of these methodologies to more efficiently solve large scale sequential decision making problems. In essence this research effort attempts to shed new light into the cross applicability of various standard methodologies into solving the above mentioned class of problems. We expect to contribute to the literature by suggesting ways to solve specific instances of sequential decision making problems using appropriate techniques which are tractable and computationally efficient to derive optimal policies to address these problems.