Executive Summary : | Markov Decision Processes (MDPs) have been very useful in a wide variety of applications in artificial intelligence, businesses, scheduling. They aid in making decisions under uncertainty by considering long term effects. When all the parameters of the MDP are known, the optimal policy is typically computed using algorithms such as value iteration, policy iteration algorithm or with linear programming. In the last decade studies have been performed on uncertain MDPs wherein some of the parameters including rewards of decisions are unknown. Then one constructs an ambiguity set to capture all possible values of the parameters and aims to find an optimal policy that maximizes the worst case long term reward (worst over all possible configurations of the uncertain parameters). Thus such a policy is ‘robust’ to uncertainties in the model. However this optimal worst case policy is known to be efficiently computable only under some forms on the ambiguity set, although methods have been provided only for further restricted classes. In this proposal we seek to investigate various types of ambiguity sets wherein the optimal policy is known to be efficiently computable in theory and propose efficient algorithms. We also seek to enhance the robustness of MDPs by incorporating some forecast information available in the environment. The questions we state are motivated from applications in scheduling in ports, inventory control in businesses and agriculture. We seek to all study the effectiveness of such policies in the context of these applications. |