New Algorithms and Analyses for Partially Observable Markov Decision Processes

部分可观察马尔可夫决策过程（POMDP）是针对控制器（或决策者）不能完全观察到动态系统状态的数学模型。决策者只能基于底层状态的一些不完善信号来控制系统。一个典型的例子是下面的机器维护问题：一台机器的实际状态是不容易观察到的，尽管它的输出质量部分地反映了它；机器状态可以通过昂贵的检查显示，也可以通过昂贵的更换恢复到最佳值；目标是找到一个最优的维护计划，使输出的总价值（具有良好质量）减去维护成本最大化。POMDP模型在运筹学与管理科学、计算机科学、经济学和医疗保健管理等许多学科中具有广泛的应用潜力。尽管在过去的30年里，运筹学和计算机科学的研究人员已经研究了各种各样的POMDP问题，但它们仍然难以用数值或分析方法解决，这阻碍了它们在现实世界中的应用。正是POMDP模型的这种困难激发了这个提议。最近的一项工作（Zhang， H. 2010，部分可观察马尔可夫决策过程：一种几何技术和分析，运筹学58(1)214-228）概述了一个解决POMDP问题的新框架，这个拟议的研究计划努力进一步发展这条探究线。该计划包括两个并行项目，旨在POMDP研究的分析和数值前沿。第一个项目侧重于中等规模问题的通用算法，通常在计算机科学中看到，其中计算效率是最重要的。第二个项目的目标是经常在经济学（例如，动态定价和学习问题）、医疗保健（例如，乳房x光检查问题）以及运筹学和管理科学（例如，机器维护问题）中发现的小型问题，其中最优策略和管理见解的属性是主要关注的问题。这两个项目相辅相成，对于更好地理解pomdp都至关重要。该计划旨在推进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.