New Simulation-Based Approaches to Solving Markov Decision Processes

University Of Maryland, College Park, College Park MD

Investigators

Abstract

The research to be performed will develop simulation-based algorithms for numerical solution of Markov Decision Processes (MDPs), which can be used to model complex systems in manufacturing, telecommunications, and finance. Two new approaches that offer potential benefits not found in currently available methods will be explored. The first approach will use ordinal optimization (OO) for choosing actions in the backwards induction step for finite horizon problems, or in the policy iteration or value iteration step for infinite horizon problems. The second approach will use simultaneous perturbation stochastic approximation (SPSA) for optimizing high-dimensional parameterized MDPs. If successful, the results of the research will lead to dramatically more efficient algorithms for solving MDPs of practical interest in a number of application areas, from financial engineering to production systems. The impact of successfully applying high-dimensional solution methodologies to these problems would represent a major advance in developing computationally tractable methods for solving complex problems of sequential decision making under uncertainty. Furthermore, theoretical results are envisioned that would rigorously establish faster rates of convergence for the new algorithms over convergence rates from usual Monte Carlo simulation.