Multistage decisions and risk in Markov decision processes: Towards effective approximate dynamic programming architectures

The scientific domain of this thesis is optimization under uncertainty for discrete event stochastic systems. In particular, this thesis focuses on the practical implementation of the Dynamic Programming (DP) methodology to discrete event stochastic systems. Unfortunately DP in its crude form suffers from three severe computational obstacles that make its implementation to such systems an impossible task. This thesis addresses these obstacles by developing and executing practical Approximate Dynamic Programming (ADP) techniques.;Specifically, for the purposes of this thesis we developed the following ADP techniques. The first one is inspired from the Reinforcement Learning (RL) literature and is termed as Real Time Approximate Dynamic Programming (RTADP). The RTADP algorithm is meant for active learning while operating the stochastic system. The basic idea is that the agent while constantly interacts with the uncertain environment accumulates experience, which enables him to react more optimal in future similar situations. While the second one is an off-line ADP procedure. Both approaches are developed for discrete event stochastic systems and their main focus is the controlled exploration of the state space circumventing in such a way one of the severe computational obstacles of DP that is related with the cardinality of the state space.;These ADP techniques are demonstrated on a variety of discrete event stochastic systems such as: (i) a three stage queuing manufacturing network with recycle, (ii) a supply chain of the light aromatics of a typical refinery and (iii) several stochastic shortest path instances with a single starting and terminal state.;Moreover, this work addresses, in a systematic way, the issue of multistage risk within the DP framework by exploring the usage of single-period and multi-period risk sensitive utility functions. In this thesis we propose a special structure for a single-period utility and compare the derived policies in several multistage instances. Finally, we briefly attempt to intergrade the developed ADP procedures with the proposed utility to yield ADP risk sensitive policies.