打字猴:1.700539183e+09
1700539183 图11.3 迭代过程
1700539184
1700539185 首先,初始化所有状态的价值V(s)=0。然后,在每一轮迭代中,对每个状态s依次执行以下步骤。
1700539186
1700539187  
1700539188
1700539189
1700539190 逐一尝试{上、下、左、右}四个动作a,记录到达状态s′和奖励r。 计算每个动作的价值q(s,a)=r+V(s′)。 从四个动作中选择最优的动作。 更新s状态价值。 在第一轮迭代中,由于初始状态V(s)均为0,因此对除宝藏所在位置外的状态s均有V(s)=r+V(s′)=−1+0=−1,即从当前位置出发走一步获得奖励r=−1。
1700539191
1700539192 在第二轮迭代中,对于和宝藏位置相邻的状态,最优动作为一步到达V(s′)=0的状态,即宝藏所在的格子。因此,V(s)更新为r+V(s′)=−1+0=−1;其余只能一步到达V(s′)=−1的状态,V(s)更新为r+V(s′)=−1+(−1)=−2。
1700539193
1700539194 第三轮和第四轮迭代如法炮制。可以发现,在第四轮迭代中,所有V(s)更新前后都没有任何变化,价值迭代已经找到了最优策略。最终,只需要从马里奥所在位置开始,每一步选择最优动作,即可最快地找到宝藏。
1700539195
1700539196 上面的迭代过程实际上运用了贝尔曼方程(Bellman Equation),来对每个位置的价值进行更新
1700539197
1700539198
1700539199
1700539200
1700539201 (11.1)
1700539202
1700539203 贝尔曼方程中状态s的价值V(s)由两部分组成:
1700539204
1700539205  
1700539206
1700539207 采取动作a后带来的奖励r。 采取动作a后到达的新状态的价值V(s′)。 问题3 根据图11.1给定的马里奥的位置以及宝藏的位置,从策略迭代来考虑,如何找到一条最优路线?
1700539208
1700539209 难度:★★☆☆☆
1700539210
1700539211 分析与解答
1700539212
1700539213 本节介绍马尔可夫决策过程的另一种求解方法——策略迭代。什么叫策略?策略就是根据当前状态决定该采取什么动作。以场景中的马里奥寻找宝箱为例,马里奥需要不断朝着宝藏的方向前进:当前状态如果在宝藏左侧,策略应该是朝右走;当前状态如果在宝藏上方,策略应该是朝下走。
1700539214
1700539215 如何衡量策略的好坏?这就需要介绍策略评估(Policy Evaluation)。给定一个策略π,我们可以计算出每个状态的期望价值 V(s)。策略迭代可以帮助我们找到更好的策略,即期望价值更高的策略,具体步骤如下。
1700539216
1700539217 (1)初始化:随机选择一个策略作为初始值。比如“不管什么状态,一律朝下走”,即P(A = 朝下走 | St=s)= 1,P(A = 其他 | St=s)= 0。
1700539218
1700539219
1700539220
1700539221 (2)进行策略评估:根据当前的策略计算。
1700539222
1700539223
1700539224
1700539225 (3)进行策略提升:计算当前状态的最优动作,更新策略。
1700539226
1700539227 (4)不停地重复策略评估和策略提升,直到策略不再变化为止。
1700539228
1700539229 在马里奥寻找宝藏问题中,策略迭代过程如图11.4所示。
1700539230
1700539231
1700539232
[ 上一页 ]  [ :1.700539183e+09 ]  [ 下一页 ]