序贯决策是人类在生产和生活中时刻都会遇到的问题,也是人工智能和控制领域的热点研究内容。部分可观察马尔可夫决策过程(Partially Observable Markov Decision Process, POMDP)是一种描述不确定环境下序贯决策问题的概率模型。POMDP的精确值迭代算法利用动态规划在整个信念状态空间上更新值函数,无法解决现实中大规模的POMDP问题。因此,对POMDP近似求解算法的研究具有重要的理论价值和现实意义。近几年来,基于点的值迭代算法成为POMDP模型主流的近似求解方法。基于点的算法只利用少量可以到达的信念状态更新值函数,其中如何选择用于更新值函数的信念状态和如何确定信念状态上值函数的更新顺序是基于点的值迭代算法的两个关键问题。然而现有算法在这两个方面仍然存在一定的不足,提出更好的信念状态选择算法是提高POMDP值函数收敛速度的重要因素,这正是本文的主要研究内容之一。另外,在医学领域中,动态治疗方案规划是一种不确定环境下的多阶段决策问题。动态序贯干预是中医临床过程中治疗慢性疾病的基本方法。以患者为轴心的治疗原则和医生的个体性特点,使得中医动态序贯干预过程中包含多样化的治疗方案。临床专家往往试图通过这种无外部对照的、大量的临床数据获得疗效较好的治疗方案,进而逐步形成固化、有效的经验知识。但是,利用传统经验整理方式形成有效治疗方案是一个较为漫长的过程。如何从大规模、复杂的多维临床数据中发现较优的动态序贯治疗方案,成为有效临床方案形成的重要课题,也是辨证论治临床评价研究的关键问题。针对这一问题,本文提出用POMDP模型对中医临床观察性数据建模的方法,并从来自临床实际的大规模数据中发现优化的动态治疗方案,为中医辨证论治过程中的动态治疗方案规划和疗效评价提供一种有力的工具。针对以上问题,本文的主要工作如下：1.系统地归纳和总结了近几年POMDP模型近似解法中基于点的值迭代算法的有关理论与方法,特别是对信念状态的选择和信念状态上值函数的更新顺序两个方面进行了深入的分析。这些内容将是本文工作的基础。2.提出了一种基于信念状态不确定性的信念状态选择算法UBBS。UBBS算法每次扩充信念状态集合时,首先选择不确定性较小并且到已选信念状态集合的1-范数距离大于一定阈值的信念状态。我们采用两种方法描述信念状态的不确定性：一种方法用信息论中的熵来衡量信念状态的不确定性,另一种方法利用信念状态本身最大概率元素与最小概率元素的间隔来计算信念状态的不确定性。实验结果表明,UBBS方法通过较少数量的信念状态就可以得到与其他算法相近的最优值函数。3.提出了一种基于最短哈密顿通路产生用于更新POMDP值函数的信念状态轨迹的算法SHP-VI。SHP-VI方法是一种基于试探的POMDP值迭代算法,用计算最短哈密顿通路的近似算法求解一个最优行动序列,并利用该序列模拟Agent与环境的交互来探索信念状态空间从而得到一条信念状态轨迹,然后沿着信念状态轨迹反向更新值函数。实验结果表明,SHP-VI算法明显地提高了基于试探的算法中用于更新值函数的信念状态轨迹的计算效率,并减少了求解POMDP问题最优值函数的迭代次数。4.如何从大规模的复杂多维临床数据里发现中医临床实际中较优的动态序贯诊疗方案,是辨证论治临床评价研究的关键问题。针对这一问题,提出了一种利用POMDP模型发现优化的动态治疗方案的方法。这是首次在中医领域里探讨用POMDP方法解决治疗方案规划问题,并且模型的所有参数均由实际临床数据计算得出。我们把中医临床专家可以直接观测到的症状体征作为观察变量,将健康状态数设置在一个适合的范围之内并通过K-均值聚类算法从临床数据中得到健康状态。利用大规模的临床数据来估计POMDP模型中的状态转移概率和观察函数,并用加权的症状改善作为治疗措施疗效的评价。实验中,对中医治疗2型糖尿病的临床数据建立了POMDP模型,并利用PBVI和UBBS算法求解并发现了临床数据中优化的处方治疗方案。实验表明,POMDP模型可以用于挖掘临床数据中较优的序贯治疗方案,能够为中医辨证论治有效动态干预方案的形成和临床验证提供参考知识。同时,实验也验证了我们提出的UBBS算法在解决实际问题时的有效性。