制定复杂决策.pptx
延续式决策问题延续式决策问题 延续式决策问题：智能体的效用值取决于一个决策序列。效用函数不是由单一状态决定，取决于环境历史的一个状态序列。+1-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的概率第1页/共17页马尔可夫决策过程：使用马尔可夫链转移模型和累加回报的延续式决策过程（MDP）MDP不确定环境的延续式决策问题通过指定行动的概率结果的转移模型和指定每个状态回报的回报函数来定义。初始状态S0，转移模型,回报函数。策略：MDP问题的解，即指定在智能体可能到达的任何状态下，智能体应当采取的行动。(s):策略为状态s推荐的行动。最优策略*：产生最高期望效用的策略.回报：智能体在一个状态s中得到的一个可正可负的有限值，即回报R(s)。延续式决策问题第2页/共17页延续式决策问题（例）延续式决策问题（例）最优策略：+1-1+1-1+1-1+1-1+1-1平衡风险和回报是MDP问题的关键。R(s)-1.63-0.43R(s)-0.09-0.02R(s)0第3页/共17页延续式决策问题中的最优化延续式决策问题中的最优化有限期决策：决策在有限时间内进行，决策应根据时间、状态来决定，给定状态的最优行动会随时间变化，即最优决策是非稳态的。无限期决策：决策没有固定的时间期限，同一个状态没有必要在不同时间采用不同决策，其最优决策是稳态的。效用函数：Uh(s0,s1,sn)第4页/共17页延续式决策问题中的最优化（稳态）延续式决策问题中的最优化（稳态）假设智能体在状态序列之间的偏好是稳态的：若s0,s1,和s0,s1,以同样的状态起始，则两个序列的偏好次序和状态序列s1,s2,和s1,s2,的偏好次序是一致的。计算状态序列的效用值，稳态性假设下的两种方法：累加回报：状态序列的效用值是各状态回报的累加和。Uh(s0,s1,sn)=R(s0)+R(s1)+折扣回报：状态序列的效用值是各状态回报的加权（折扣因子）累加和。折扣因子用于描述智能体对于当前与未来回报的偏好。第5页/共17页延续式决策问题中的最优化延续式决策问题中的最优化无限期决策，效用值的计算的三种方法:1、折扣回报：状态序列的效用值是各状态回报的加权(折扣因子）累加和。2、适当策略：确保能够达到终止状态的策略，可使用累积回报。3、平均回报：每一个时间步回报的平均数。策略的值是所得到的折扣回报的期望和。最优策略:第6页/共17页价值迭代价值迭代基本思想：计算每个状态的效用，以选出每个状态中的最优行动。选择使后续状态的期望效用最大的行动：*(s)=argmax a s T(s,a,s)*U(s)价值迭代算法：把每个状态的效用与其邻接状态的效用关联起来：（贝尔曼方程）即当智能体选择最优行动，状态的效用值是在该状态得到的立即回报加上在下一个状态的期望折扣效用值。状态的效用值：可能跟随它出现的所有状态序列的期望效用值。第7页/共17页价值迭代价值迭代 价值迭代法总是收敛到贝尔曼方程组的唯一解上。而对应的策略是最优的。贝尔曼更新迭代求解：+1-1第8页/共17页策略迭代策略：指定智能体在可能达到的任何状态下智能体应采取的行动。最优策略：就是产生最高期望效用值的策略。策略迭代：交替执行用当前策略计算状态的效用和用当前的效用改进当前的策略。策略评价：对拟执行的策略i 进行评价，计算Ui=Ui，即该策略被执行后每个状态的效用值。策略改进：通过Ui，计算新的MEU策略i+1。每次迭代都将产生更好的策略。直到效用值不变，算法终止。则该效用值也是贝尔曼方程组的解，i 一定是最优策略。第9页/共17页策略评价 n n个状态有个状态有n n个方程和个方程和n n个未知量，可用线性代数方法求解。个未知量，可用线性代数方法求解。也可用价值迭代计算效用值的近似：也可用价值迭代计算效用值的近似：修正策略迭代异步策略迭代：每次迭代只更新部分选中的状态。+1-1第10页/共17页部份可观察的部份可观察的MDPMDP（POMDPPOMDP）智能体并不知道自己所处的状态，也不能给出其转移模型，所以无法执行(s)为该状态推荐的行动。安全策略：尽量向减少不确定的方向移动。+1-1第11页/共17页部份可观察的部份可观察的MDPMDP（POMDPPOMDP）观察模型O(s,o):指定在状态s感知到o的概率。信度状态b：所有可能状态上的概率分布。例如：3个状态的环境，b(s):信度状态赋予实际状态s的概率。更新信度状态：最优策略：最优行动取决于当前智能体的信度状态，*(b).第12页/共17页POMDP智能体决策过程：（1）给定当前的信度状态b，执行行动a=*(b).（2）得到观察o（3）更新信度状态为Forward(b,a,o)，重复上述步骤。给定行动a，从b到b的概率：信度状态空间的转移模型信度状态空间的回报函数：求解POMDP可归约为信度状态空间上求解MDP第13页/共17页决策智能体的设计决策智能体的设计1 1、用、用动态贝动态贝叶斯叶斯网网表示表示转转移和移和观观察模型。察模型。2 2、用、用决决策和效用策和效用节节点点扩扩展展动态贝动态贝叶斯叶斯网网，产产生生动态动态决决策策网网络络(DDN)(DDN)。3 3、用、用滤滤波算法把每波算法把每个个新的感知信息新的感知信息与与行行动结动结合起合起来来，对对信度信度状状态态表示表示进进行更新。行更新。4 4、通、通过过向前投影可能的行向前投影可能的行动动序列序列选择选择最佳行最佳行动动制定制定决决策。策。第14页/共17页决策智能体决策智能体At-2Xt-1Rt-1Et-1At-1XtRtEtAtXt+1Et+1At+2Xt+3Et+2Ut+3Xt+2At+1Rt+1Rt+2Et+3第15页/共17页第16页/共17页谢谢您的观看！第17页/共17页
