State Clustering in Markov Decisions Processes with an Application in Information Sharing

This research examines state clustering in Markov Decision processes, specifically addressing the problem referred to as Markov Decision process with restricted observations. The general problem is a special case of a Partially Observable Markov Decision process where the state space is partitioned into mutually exclusive sets representing the observable portion of the process. The goal is to find an optimal policy defined over the partition of the state space that minimizes (maximizes) some performance objective. Algorithms presented to solve this problem for the infinite horizon undiscounted average cost case have largely been based on enumerative procedures. A heuristic solution procedure based on Howard's (1960) policy iteration method is presented. Applications of Markov decision processes with restricted observations exist in networks of queues, retrial queues, maintenance problems and queuing networks with server control. A new application area is proposed in the field of information sharing to measure the value of information sharing in a supply chain under optimal control. This is achieved by representing a model of full information sharing as a completely observable Markov Decision process (MDP), while no information sharing is represented as an MDP with restricted observations. Solution procedures are presented for the general Markov Decision process with restricted observations. Heuristic solutions are evaluated against the optimal solution obtained via total enumeration. Both random Markov Decision processes and information sharing problems are studied. The value of sharing information in a two-stage supply chain system is studied. The influence of capacity, demand, cost and retailer policy on the value of information sharing is considered. Insight on the structure of the optimal policy with and without information sharing is provided.