《人工智能原理》-P3C8-决策理论规划

某某大学某某学院某某某2第8章决策理论规划上一章的时空关联规划基于如下假设条件：确定性、完全可观测、可达性目标。本章将讨论在上述假设之外如何进行规划的问题，即决策理论规划（Decision-TheoreticPlanning）。决策理论规划的应用非常广泛，例如：高端机器人控制、医药治疗、灾害救援、等等。因为不同的行动会有不同的结果，某些动作可能更有利，因此需要对实现目标的潜力、风险、以及成本做出决策。第8章决策理论规划引言3第8章决策理论规划目录4决策理论规划概述马尔科夫模型马尔科夫决策过程的优化控制动态规划决策理论是一种决策的理论框架，用于衡量行动方案的优劣。决策理论的基础概率论（Gametheory）用于在给定的状态下求得某个行动可能结果的概率分布、以及合理性偏好函数。效用论（Utilitytheory）采用效用函数，使得智能主体偏好的规划具有更高的预期效用最大期望效用（maximumexpectedutility,MEU）决策理论规划概述决策理论（Decisiontheory）5但是，决策理论并未涉猎如何构建具有高期望效用的规划。决策理论规划

=决策理论+人工智能规划形式框架：马尔科夫决策过程（Markovdecisionprocess）优化控制：动态规划（Dynamicprogramming）、线性规划（Linearprogramming）决策理论规划≒不确定性环境规划（planningunderuncertainty）从环境接收的信息是不完全或不完备的动作并非总是得到同样的结果需要在规划的不同结果之间做出权衡马尔科夫决策过程∈马尔科夫模型（Markovmodels）决策理论规划概述决策理论规划（Decision-TheoreticPlanning）6杰罗姆·费尔德曼（JeromeFeldman）和罗伯特·斯普劳尔（RobertSproull）

是最早从事决策理论规划研究的学者第8章决策理论规划目录7决策理论规划概述马尔科夫模型马尔科夫决策过程的优化控制动态规划概述一种统计模型，用于对随机变化的系统进行建模。性质马尔科夫模型的下一个状态只依赖于当前的状态，而与之前发生的事件无关。马尔科夫模型马尔科夫模型（Markovmodels）8

完全可观测（fullyobservable）部分可观测（partiallyobservable）自主

（autonomous）马尔科夫过程

（Markovprocess）隐马尔科夫模型

（HiddenMarkovmodel）控制（controlled）马尔科夫决策过程

（Markovdecisionprocess）部分可观测马尔科夫决策过程

（PartiallyobservableMarkovdecisionprocess）四种马尔科夫模型以俄罗斯数学家安德烈·马尔科夫（AndreyMarkov）的名字命名。定义马尔科夫模型随机过程（Stochasticprocess,SP）9

随机过程的实例细菌种群的增长、由于热噪声或气体分子的移动而导致电流波动等。随机过程的应用生物学、化学、生态学、神经科学、物理学、以及工程和技术领域，如：图像处理、信号处理、信息论、计算机科学、密码学、电信等；此外，还被广泛用于金融领域。随机过程是针对随机变化的现象而建立的系统的数学模型定义马尔科夫模型马尔科夫性质（Markovproperty）10

所有的马尔科夫模型都具有马尔科夫性质。无记忆性质（memory-lessproperty）采用马尔科夫模型的领域：预测建模（predicatemodeling）、概率预报（probabilisticforecasting）等。回置抽样vs无回置抽样马尔科夫模型马尔科夫性质（Markovproperty）11对于一个随机过程，回置抽样（samplingwithoutreplacement）具备马尔科夫性质，而无回置抽样（samplingwithreplacement）则不具备马尔科夫性质。例：一个坛子里有三个鸡蛋，两个红皮的，一个白皮的。昨天拿出一个，今天再拿出一个，问：明天拿出的鸡蛋的颜色？若只知道今天拿出的鸡蛋是红皮的，而不知道昨天拿出鸡蛋的颜色时，则明天拿出的最后一个鸡蛋颜色的概率是红白各占二分之一；只有既知道昨天、又知道今天拿出的鸡蛋的颜色时，才能判断明天拿出的最后一个鸡蛋的颜色。显然，这种观察鸡蛋颜色的随机过程问题不具有马尔科夫性质。

这是一个无回置抽样的实例。回置抽样vs无回置抽样马尔科夫模型马尔科夫性质（Markovproperty）12对于一个随机过程，回置抽样（samplingwithoutreplacement）具备马尔科夫性质，而无回置抽样（samplingwithreplacement）则不具备马尔科夫性质。例：用一个操纵杆控制一个玩具车，可操控玩具车朝前、后、左、右方向行进，记录仪可显示玩具车当前的方向。当记录仪显示玩具车处于前进方向时，操纵杆向左，问：玩具车的行进方向？这个问题的答案不言自明。

这是一个回置抽样的实例。定义马尔科夫模型马尔科夫过程（Markovprocess,MP）13

马尔科夫过程是具有马尔科夫性质的随机过程安德烈·马尔科夫早在1900年就研究了马尔科夫过程，并于1906年就此发表了论文。离散时间的马尔科夫过程马尔科夫模型马尔科夫过程（Markovprocess,MP）14

马尔科夫过程是一类重要的随机过程，是随机模拟方法的基础，例如：机动车辆的巡航控制系统、机场旅客的队列、货币兑换率、存储系统、某些物种的增长、搜索引擎、等等。离散时间的马尔科夫过程马尔科夫模型马尔科夫过程（Markovprocess,MP）15布朗运动过程（Brownianmotionprocess）一维泊松过程（Poissonprocess）例：赌徒破产（gambler'sruin）一个赌博成瘾的赌徒，每次赌博获胜时就将下一次赌注提高到固定比例的金额，但在输掉时不会减少。即使是每次下注都有赢钱的预期，但最终该赌徒不可避免地会输得精光。连续时间的马尔科夫过程定义马尔科夫模型马尔科夫链（Markovchain）16

吉布斯采样（Gibbssampling）和马尔科夫链蒙特卡罗（MarkovChainMonteCarlo,MCMC），被用于模拟具有特定概率分布的随机对象，并且已经在贝叶斯统计中得到广泛应用。用马尔科夫链表示某股票市场一周内的牛市、熊市或停滞的市场趋势。定义马尔科夫模型马尔科夫决策过程（Markovdecisionprocess,MDP）17

马尔科夫决策过程是有限离散事件的马尔科夫过程的扩展，

在自主式马尔科夫过程的基础上增加了改变状态的动作、以及环境的奖惩（reward）等。作用马尔科夫模型马尔科夫决策过程（Markovdecisionprocess,MDP）18是决策理论规划的形式化方法是一种离散时间随机控制过程（discretetimestochasticcontrolprocess）是构建序贯决策（sequentialdecision-making）方法的理论框架马尔科夫决策过程中主体与环境之间的状态、奖惩、以及动作的交互过程。定义马尔科夫模型隐马尔科夫模型（HiddenMarkovmodel）19隐马尔科夫模型可以表示为简单的动态贝叶斯网络（dynamicBayesiannetwork），

在机器学习中发挥了重要作用，而与规划问题没有直接关系。是一种基于统计学的马尔科夫模型，用于描述一个含有隐含未知参数的马尔科夫过程。其状态可通过观测向量序列观察到，每个观测向量都是通过某些概率密度分布表现出的状态，形成一个具有相应概率密度分布的状态序列。隐马尔科夫模型是一个双重随机过程，即具有一定状态数的隐马尔科夫链并显示随机函数集。定义马尔科夫模型部分可观测马尔科夫决策过程

（PartiallyobservableMarkovdecisionprocess,POMDP20

部分可观测马尔科夫决策过程是马尔科夫决策过程在部分可观测环境下的扩展。第8章决策理论规划目录21决策理论规划概述马尔科夫模型马尔科夫决策过程的优化控制动态规划定义马尔科夫决策过程的优化控制策略（Policy）22确定性策略（deterministicpolicy）随机策略（stochasticpolicy）

马尔科夫决策过程优化控制的核心问题是找到一个策略。马尔科夫决策过程的优化控制策略（Policy）23

该策略由智能主体加以实施，其目的是控制被建模为马尔科夫决策过程的环境。

定义马尔科夫决策过程的优化控制奖惩（Reward）24

片段是主体与环境进行反复交互的过程中形成一些子序列。具有这种片段的任务被称为片段化任务（episodictasks）。片段在终止状态（terminalstate）下结束。片段（episodes）定义马尔科夫决策过程的优化控制折扣（Discounting）25考虑折扣：

马尔科夫决策过程的优化控制价值函数（valuefunction）26

马尔科夫决策过程的优化控制算法通过价值函数来计算最优策略。马尔科夫决策过程的优化控制贝尔曼公式（Bellmanequation）27

上述公式被称为贝尔曼最优化方程（Bellmanoptimalityequation）。它表明，最优策略下的状态值必须等于该状态最佳动作的预期回报。马尔科夫决策过程的优化控制贝尔曼公式（Bellmanequation）28

最优状态值是：

最优动作选择可以表示为：

马尔科夫决策过程的优化控制优化控制方法29

主要方法：基于模型（Model-based）、模型无关（Model-free）。基于模型的方法就是动态规划（Dynamicprogramming）。其基本假设是已知一个MDP模型，并且可以使用贝尔曼公式来计算价值函数和策略，大多数方法是计算状态价值函数（statevaluefunctions）。用动态规划对马尔科夫决策过程进行优化控制，属于决策理论规划的范畴→本章。模型无关的方法就是强化学习（Reinforcementlearning）。它通过与环境的互动形成模拟策略，生成状态转换和奖惩样本，再将这些样本用于估计状态-动作价值函数（state-actionvaluefunctions）。用强化学习对马尔科夫决策过程进行优化控制，属于机器学习的范畴→第11章。基于模型vs模型无关动态规划

vs强化学习第8章决策理论规划目录30决策理论规划概述马尔科夫模型马尔科夫决策过程的优化控制动态规划动态规划动态规划（DynamicProgramming）31将DynamicProgramming译成动态规划，是因为Programming的含义使然1950年代初，美国数学家理查德·贝尔曼（RichardBellman）在研究多步决策过程（multistepdecisionprocess）的优化问题时，将多步过程转化为一系列单步问题，利用各阶段之间的关系逐个加以解决，从而创立了动态规划理论（TheoryofDynamicProgramming）。在决策理论规划中，动态规划被用于对马尔科夫决策过程进行优化控制，计算马尔科夫决策过程的最优策略。动态规划的两个核心方法：策略迭代（Policyiteration）和价值迭代（Valueiteration），分别由罗纳德·霍华德（RonaldAHoward）和理查德·贝尔曼提出。ItwasfirstcoinedbyRichardBellmaninthe1950s,atimewhencomputerprogrammingwasanesotericactivitypracticedbysofewpeopleastonotevenmeritaname.Backthenprogrammingmeant“planning,”and“dynamicprogramming”wasconceivedtooptimallyplanmultistageprocesses.动态规划策略迭代（Policyiteration）32策略迭代算法：1）策略评估（policyevaluation），计算当前策略的价值函数；2）策略改进（policyimprovement），通过价值函数的最大化来计算改善的策略；3）重复上述操作，直到收敛于一个最优策略。动态规划策略评估（policyevaluation）33已知贝尔曼公式：