New Algorithms and Analyses for Partially Observable Markov Decision Processes

点击翻译按钮获取中文摘要

Partially observable Markov decision process (POMDP) is a mathematical model for a dynamic system whose state cannot be fully observed by the controller (or decision maker). The decision maker can only control the system based on some imperfect signals of the underlying state. A classic example is the following machine maintenance problem: the actual state of a machine is not readily observable albeit it is partially reflected by the quality of its outputs; the machine state can be revealed through costly inspection or be reset to its best value through expensive replacement; and the goal is to find an optimal maintenance plan that maximizes the total value of the outputs (with good quality) minus the maintenance costs. The POMDP model has wide potential applications in many disciplines such as operations research & management science, computer science, economics, and healthcare management. Although various POMDP problems have been studied over the last 30 years by researchers in operations research and computer science, they remain difficult to solve numerically or analytically, which hinders their applications in the real world. It is this difficulty with the POMDP model that motivates this proposal. A recent work (Zhang, H. 2010, Partially observable Markov decision processes: A geometric technique and analysis, Operations Research 58(1) 214-228) outlines a new framework to tackle POMDP problems, and this proposed research program strives to further develop this line of inquiry. This program consists of two parallel projects, aiming at both the analytical and numerical fronts of the POMDP research. The first project focuses on general algorithms for moderate-sized problems, commonly seen in computer science, for which computational efficiency is most important. The second project targets small-sized problems often found in economics (e.g., the dynamic pricing and learning problem), healthcare (e.g., the mammography screening problem), and operations research & management science (e.g., the machine maintenance problem), where properties of the optimal policy and managerial insights are of the primary concern. These two projects complement each other and are both vital to a better understanding of POMDPs. The proposed program is poised to advance the POMDP research and stimulate its applications. The outputs of this program can benefit the academia, practitioners, policy makers, and the general public.