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