New Algorithms and Analyses for Partially Observable Markov Decision Processes

部分可观测马尔可夫决策过程（POMDP）是一种动态系统的数学模型，其状态不能被控制器（或决策者）完全观测。决策者只能根据一些潜在状态的不完美信号来控制系统。一个典型的例子是以下机器维护问题：机器的实际状态不容易观察，尽管它部分地反映在其输出的质量上;机器状态可以通过昂贵的检查来揭示，或者通过昂贵的更换来重置到其最佳价值;并且目标是找到最优维护计划，该最优维护计划最大化输出（具有良好质量）的总价值减去维护成本。POMDP模型在运筹学与管理科学、计算机科学、经济学和医疗管理等学科中具有广泛的应用前景。尽管在过去的30年里，运筹学和计算机科学的研究人员已经研究了各种POMDP问题，但它们仍然难以用数值或解析方法求解，这阻碍了它们在真实的世界中的应用。正是POMDP模型的这种困难激发了这个提议。最近的工作（张，H。2010年，部分可观察马尔可夫决策过程：几何技术和分析，运筹学58（1）214-228）概述了一个新的框架来解决POMDP问题，这个拟议的研究计划致力于进一步发展这条调查线。该计划包括两个平行的项目，针对POMDP研究的分析和数值前沿。第一个项目侧重于中等规模问题的通用算法，这在计算机科学中很常见，计算效率是最重要的。第二个项目针对经济学中经常出现的小规模问题（例如，动态定价和学习问题），医疗保健（例如，乳房X线摄影筛查问题），以及运筹学和管理科学（例如，机器维护问题），其中最优策略和管理见解的属性是主要关注的。这两个项目相辅相成，对于更好地理解POMDPs都至关重要。拟议的计划是准备推进POMDP的研究和刺激其应用。该计划的产出可以使学术界，从业人员，政策制定者和公众受益。

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.