制定复杂决策(第17章).ppt

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