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的研究并刺激其应用。这项计划的成果可以惠及学术界、实践者、政策制定者和普通公众。

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.