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
1700539233
1700539234
图11.4 策略迭代过程
1700539235
1700539236
1700539237
初始化策略为：不论马里奥处于哪个状态，一律朝下走。根据这一策略进行策略评估不难发现，只有宝藏正上方的状态可以到达宝藏，期望价值为到宝藏的距离（−2，−1和0）；其余状态不能通过当前策略到达宝藏，期望价值为负无穷。然后根据当前的期望价值进行策略提升：对于宝藏正上方的状态，策略已经最优，保持不变；对于不在宝藏正上方的状态，根据策略更新公式，最优策略为横向移动一步。
1700539238
1700539239
1700539240
通过上一轮的策略提升，这一轮的策略变为：对于宝藏正上方的状态，向下移动；对于不在宝藏正上方的状态，横向移动一步。根据当前策略进行策略评估，更新各状态期望价值：宝藏正上方的状态价值期望不变，仍等于到宝藏的距离；不在宝藏正上方的状态期望价值更新为 ，即横向移动一步的奖励与目标状态的期望价值之和。然后根据更新后的期望价值进行策略提升：不难发现，对于所有状态，当前策略已经最优，维持不变，中止策略提升过程。
1700539241
1700539242
最终，马里奥只需从初始状态（1,1）开始，按照当前位置的最优策略进行行动，即向右行动一步，然后一直向下行动，即可最快找到宝藏。
1700539243
1700539244
1700539245
1700539246