制定复杂决策(第17章)

1、0871-50313012021年10月10日星期日1 / 信 息 学 院人工智能 一种现代方法第十七章第十七章 制定复杂决策制定复杂决策17.1 延续式决策问题17.2 价值迭代17.3 策略迭代17.4 部份可观察的MDP17.5 决策理论智能体0871-50313012021年10月10日星期日2 / 信 息 学 院人工智能 一种现代方法延续式决策问题延续式决策问题 延续式决策问题：智能体的效用值取决于一个延续式决策问题：智能体的效用值取决于一个决策序列。效用函数不是由单一状态决定，取决于决策序列。效用函数不是由单一状态决定，取决于环境历史的一个状态序列。环境历史的一个状态序列。+1-

2、1完全可观察环境完全可观察环境随机行为随机行为一阶马尔可夫转移一阶马尔可夫转移效用函数取决于状态序列效用函数取决于状态序列0.80.10.1up, up, right, right, right 0.85 = 0.32768成功概率：成功概率： 0.14*0.8+0.85 = 0.32776转移模型转移模型 T(s, a, s): 在状态在状态s完成行动完成行动a时到达状态时到达状态s的概率的概率0871-50313012021年10月10日星期日3 / 信 息 学 院人工智能 一种现代方法马尔可夫决策过程：使用马尔可夫链转移模型和累加回报的延续马尔可夫决策过程：使用马尔可夫链转移模型和累加回

3、报的延续式决策过程（式决策过程（MDP） MDP不确定环境的延续式决策问题通过指定行动的概率结果的不确定环境的延续式决策问题通过指定行动的概率结果的转移模型和指定每个状态回报的回报函数来定义。转移模型和指定每个状态回报的回报函数来定义。 初始状态初始状态S0，转移模型，转移模型, 回报函数。回报函数。策略策略：MDP问题的解，即指定在智能体可能到达的任何状态问题的解，即指定在智能体可能到达的任何状态下，智能体应当采取的行动。下，智能体应当采取的行动。(s):(s):策略策略为状态为状态s s推荐的行动。推荐的行动。最优策略最优策略* * ：产生最高期望效用的策略：产生最高期望效用的策略. .回

4、报：智能体在一个状态回报：智能体在一个状态s中得到的一个可正可负的中得到的一个可正可负的有限值，即回报有限值，即回报R(s)。延续式决策问题延续式决策问题0871-50313012021年10月10日星期日4 / 信 息 学 院人工智能 一种现代方法延续式决策问题（例）延续式决策问题（例）最优策略：最优策略：+1- 1+1- 1+1- 1+1- 1+1- 1平衡风险和回报是平衡风险和回报是MDP问题的关键。问题的关键。R(s)-1.63-0.43R(s)-0.09-0.02R(s)00871-50313012021年10月10日星期日5 / 信 息 学 院人工智能 一种现代方法延续式决策问题中

5、的最优化延续式决策问题中的最优化有限期决策：决策在有限时间内进行，决策应根据时间、状有限期决策：决策在有限时间内进行，决策应根据时间、状态来决定，给定状态的最优行动会随时间变化，即最优决策态来决定，给定状态的最优行动会随时间变化，即最优决策是非稳态的。是非稳态的。无限期决策：决策没有固定的时间期限，同一个状态没有必无限期决策：决策没有固定的时间期限，同一个状态没有必要在不同时间采用不同决策，其最优决策是稳态的。要在不同时间采用不同决策，其最优决策是稳态的。效用函数：效用函数：Uh(s0, s1, , sn) 0871-50313012021年10月10日星期日6 / 信 息 学 院人工智能 一

6、种现代方法延续式决策问题中的最优化（稳态）延续式决策问题中的最优化（稳态）假设智能体在状态序列之间的偏好是稳态的：假设智能体在状态序列之间的偏好是稳态的： 若若s0, s1, 和和s0, s1, 以同样的状态起始，则以同样的状态起始，则两个序列的偏好次序和状态序列两个序列的偏好次序和状态序列s1, s2, 和和s1, s2 , 的偏好次序是一致的。的偏好次序是一致的。)()()(),(1210210sRsRsRsssUh计算状态序列的效用值，稳态性假设下的两种方法：计算状态序列的效用值，稳态性假设下的两种方法： 累加回报：状态序列的效用值是各状态回报的累加和。累加回报：状态序列的效用值是各状态

7、回报的累加和。Uh(s0, s1, , sn)= R(s0)+R(s1)+ 折扣回报：状态序列的效用值是各状态回报的加权（折扣因子）折扣回报：状态序列的效用值是各状态回报的加权（折扣因子）累加和。折扣因子用于描述智能体对于当前与未来回报的偏好。累加和。折扣因子用于描述智能体对于当前与未来回报的偏好。0871-50313012021年10月10日星期日7 / 信 息 学 院人工智能 一种现代方法延续式决策问题中的最优化延续式决策问题中的最优化无限期决策，效用值的计算的三种方法无限期决策，效用值的计算的三种方法: 0*| )(maxargtttsRE1、折扣回报：状态序列的效用值是各状态回报的加权

8、、折扣回报：状态序列的效用值是各状态回报的加权(折扣因子）折扣因子）累加和。累加和。2、适当策略：确保能够达到终止状态的策略，可使用累积回报。、适当策略：确保能够达到终止状态的策略，可使用累积回报。3、平均回报：每一个时间步回报的平均数。、平均回报：每一个时间步回报的平均数。策略的值是所得到的折扣回报的期望和。策略的值是所得到的折扣回报的期望和。 最优策略最优策略:)1/()(),(0maxmax0210ttttthRRsRsssU0871-50313012021年10月10日星期日8 / 信 息 学 院人工智能 一种现代方法价值迭代价值迭代基本思想：计算每个状态的效用，以选出每个状态中基本思

9、想：计算每个状态的效用，以选出每个状态中的最优行动。的最优行动。) () ,(max)()(sasUsasTsRsU选择使后续状态的期望效用最大的行动：选择使后续状态的期望效用最大的行动：*(s) = argmax a s T(s, a, s) * U(s)价值迭代算法：把每个状态的效用与其邻接状态的效用关联起来：价值迭代算法：把每个状态的效用与其邻接状态的效用关联起来： （贝尔曼方程）（贝尔曼方程）即当智能体选择最优行动，状态的效用值是在该状态得到的立即即当智能体选择最优行动，状态的效用值是在该状态得到的立即回报加上在下一个状态的期望折扣效用值。回报加上在下一个状态的期望折扣效用值。00,|

10、 )()(tttsssREsU状态的效用值：可能跟随它出现的所有状态序列的期状态的效用值：可能跟随它出现的所有状态序列的期望效用值。望效用值。0871-50313012021年10月10日星期日9 / 信 息 学 院人工智能 一种现代方法价值迭代价值迭代 价值迭代法总是价值迭代法总是收敛收敛到贝尔曼方程组的到贝尔曼方程组的唯一唯一解上。而对应解上。而对应的策略是最优的。的策略是最优的。贝尔曼更新贝尔曼更新1) () ,(max)()(siaisUsasTsRsU迭代求解：迭代求解：)1 , 1 (1 . 0)2 , 1 (1 . 0) 1 , 2(8 . 0) 1 , 2(1 . 0) 1 ,

11、 1 (9 . 0),2 , 1 (1 . 0) 1 , 1 (9 . 0),1 , 1 (1 . 0) 1 , 2(1 . 0)2 , 1 (8 . 0max04. 0) 1 , 1 (UUUUUUUUUUU+1- 10871-50313012021年10月10日星期日10 / 信 息 学 院人工智能 一种现代方法策略迭代策略迭代策略：指定智能体在可能达到的任何状态下智能体策略：指定智能体在可能达到的任何状态下智能体应采取的行动。应采取的行动。最优策略：就是产生最高期望效用值的策略。最优策略：就是产生最高期望效用值的策略。策略迭代：交替执行用当前策略计算状态的效用和用当前的效策略迭代：交替执

12、行用当前策略计算状态的效用和用当前的效用改进当前的策略。用改进当前的策略。 策略评价：对拟执行的策略策略评价：对拟执行的策略i 进行评价，计算进行评价，计算Ui =Ui ，即该策，即该策略被执行后每个状态的效用值。略被执行后每个状态的效用值。 策略改进：通过策略改进：通过Ui，计算新的，计算新的MEU策略策略i +1。每次迭代都将产生更好的策略。直到效用值不变，算法终止。则每次迭代都将产生更好的策略。直到效用值不变，算法终止。则该效用值也是贝尔曼方程组的解，该效用值也是贝尔曼方程组的解， i 一定是最优策略一定是最优策略 。0871-50313012021年10月10日星期日11 / 信 息

13、学 院人工智能 一种现代方法策略评价策略评价) () ),(,()()(siiisUsssTsRsU n n个状态有个状态有n n个方程和个方程和n n个未知量，可用线性代数方法求解。个未知量，可用线性代数方法求解。也可用价值迭代计算效用值的近似：也可用价值迭代计算效用值的近似：1) () ),(,()()(siiisUsssTsRsU修正策略迭代修正策略迭代异步策略迭代：每次迭代只更新部分选中的状态。异步策略迭代：每次迭代只更新部分选中的状态。+1- 1)2 , 1 (2 . 0) 3 , 1 (8 . 0)2 , 1 () 1 , 1 (1 . 0) 1 , 2(1 . 0)2 , 1 (

14、8 . 0) 1 , 1 (iiiiiiiUUUUUUU0871-50313012021年10月10日星期日12 / 信 息 学 院人工智能 一种现代方法部份可观察的部份可观察的MDPMDP（POMDPPOMDP） 智能体并不知道自己所处的状态，也不能给出其智能体并不知道自己所处的状态，也不能给出其转移模型，所以无法执行转移模型，所以无法执行(s) 为该状态推荐的行动。为该状态推荐的行动。安全策略：安全策略： 尽量向减少不确定的方向移动。尽量向减少不确定的方向移动。+1- 10871-50313012021年10月10日星期日13 / 信 息 学 院人工智能 一种现代方法部份可观察的部份可观察

15、的MDPMDP（POMDPPOMDP）观察模型观察模型O(s, o): 指定在状态指定在状态s感知到感知到o的概率。的概率。信度状态信度状态b：所有可能状态上的概率分布。：所有可能状态上的概率分布。 例如：例如：3个状态的环境，个状态的环境，b(s): 信度状态赋予实际状态信度状态赋予实际状态s的概率。的概率。更新信度状态：更新信度状态：最优策略：最优策略： 最优行动取决于当前智能体的信度状态，最优行动取决于当前智能体的信度状态，* (b).),()() ,(), () ( oabForwardbsbsasTosOsbs0871-50313012021年10月10日星期日14 / 信 息 学

16、院人工智能 一种现代方法ossasbsasTosObaobPbaoPbaobPbabPbab)() ,(), (),| (),|(),| (),| () ,()() ,(), (),| (), ,|(),|(ssssbsasTosObasPbsaoPbaoPPOMDP智能体决策过程：智能体决策过程：（1） 给定当前的信度状态给定当前的信度状态b，执行行动，执行行动a = * (b).（2）得到观察）得到观察o（3）更新信度状态为）更新信度状态为Forward(b, a, o)，重复上述步骤。，重复上述步骤。给定行动给定行动a，从，从b到到b的概率：的概率：信度状态空间的转移模型信度状态空间的转

17、移模型)0, 1),| (),(否则若baobPoabForwardbssRsbb)()()(信度状态空间的回报函数：信度状态空间的回报函数：求解求解POMDP可归约为信度状态空间上求解可归约为信度状态空间上求解MDP0871-50313012021年10月10日星期日15 / 信 息 学 院人工智能 一种现代方法决策智能体的设计决策智能体的设计1 1、用、用动态贝动态贝叶斯叶斯网网表示表示转转移和移和观观察模型。察模型。2 2、用、用决决策和效用策和效用节节点点扩扩展展动态贝动态贝叶斯叶斯网网，产产生生动态决动态决策策网络网络(DDN)(DDN)。3 3、用、用滤滤波算法把每波算法把每个个新的感知信息新的感知信息与与行