3.6 实例讲解
本节以在5×5的网格世界中寻找宝藏为例，分别使用策略迭代和值迭代算法寻找最优策略，并比较两种算法在处理上的异同，以及两者的运行效率。
3.6.1 “找宝藏”环境描述
1．环境描述
首先构建寻宝环境的马尔可夫决策模型M=<S，A，P，R，γ>。
如图3-5所示为5×5的网格世界，其状态空间为S={0，1，…，24}，其中状态8为宝藏区。动作空间A={UP，RIGHT，DOWN，LEFT}，宝藏区回报为r=0，其他位置回报为r=-1。
图3-5 5×5网格世界
当智能体位于网格世界边缘位置时，任何使其离开网格世界的行为都会使其停留在当前位置。例如，当位于0位置时，采取向上的行为，a=UP，智能体获取-1的回报后，重新回到位置0。当智能体位于宝藏区时，则无论采取何种行为，均会产生0回报，且位置不变。当智能体位于其他位置时，采取任何一个行为，则会向相应的方向移动一格。状态转移概率
。折扣因子γ=1。
求解此网格世界寻找宝藏的最优策略。
2．环境代码
接下来基于gym构建寻找宝藏的环境，以下代码主要定义了寻宝藏MDP模型的状态空间、行为空间、状态转移概率和回报等信息。此环境代码较为简单，读者可结合注释，加深对此代码的理解。
3.6.2 策略迭代
1．算法详情
使用策略迭代法对此问题进行求解。假设初始策略为均匀随机策略：
π（UP|·）=0.25，π（RIGHT|·）=0.25，π（DOWN|·）=0.25，π（LEFT|·）=0.25
（1）首先评估给定随机策略下的值函数，使用贝尔曼期望方程迭代计算直至值函数收敛。
初始所有状态值函数全部为0。在对值函数进行迭代计算时，使用如下公式：
k=0时，随机策略下的值函数
为：
k=1时，随机策略下的值函数
为：
k=2时，随机策略下的值函数
为：
k=3时，随机策略下的值函数
为：
k=4时，随机策略下的值函数
为：
k=41时，随机策略下的值函数
为：
k=338时，随机策略下的值函数
收敛，收敛结果为：
对应代码如下。
V = np.zeros(env.nS)
i = 0
while True:
value_delta = 0
# 遍历各状态
for s in range(env.nS):
v = 0
# 遍历各行为的概率(上,右,下,左)
for a, action_prob in enumerate(policy[s]):
# 对于每个行为确认下个状态
# 四个参数: prob:概率,next_state: 下一个状态的索引, reward: 回报,
# done:是否是终止状态
for prob, next_state, reward, done in env.P[s][a]:
# 使用贝尔曼期望方程进行状态值函数的求解
v += action_prob * prob * (reward + discount_factor * V[next_state])
# 求出各状态和上一次求得状态的最大差值
value_delta = max(value_delta, np.abs(v - V[s]))
V[s] = v
（2）使用如下公式：
对收敛的值函数
，使用贪心算法进行策略改进，求取
对应的改进后的策略π1，则有π1：
对应代码如下：
# 评估当前的策略,输出为各状态的当前的状态值函数
V = policy_eval_fn(policy, env, discount_factor)
# 定义一个当前策略是否改变的标识
policy_stable = True
# 遍历各状态
for s in range(env.nS):
# 取出当前状态下最优行为的索引值
chosen_a = np.argmax(policy[s])
# 初始化行为数组[0,0,0,0]
action_values = np.zeros(env.nA)
for a in range(env.nA):
# 遍历各行为
for prob, next_state, reward, done in env.P[s][a]:
# 根据各状态值函数求出行为值函数
action_values[a] += prob * (reward + discount_factor * V[next_state])
# 输出一个状态下所有的可能性
best_a_arr, policy_arr = get_max_index(action_values)
if chosen_a not in best_a_arr:
policy_stable = False
policy[s] = policy_arr
（3）继续使用贝尔曼期望方程求取当前策略π1下的值函数，直至值函数收敛。计算过程与（1）相同。
经过5轮迭代，值函数收敛，得到
为：
（4）针对值函数
，进行第二次策略改善，得到π2。
（5）继续求取π2对应的值函数（策略评估），针对收敛的值函数
进行第三次策略改进，得到π3。经过三次策略改进，策略收敛。
对应最优值函数
为：
最优策略π*（π3）为：
代码如下。
if policy_stable:
return policy, V
policy_stable初始为True，策略未达到收敛时不会输出策略和值函数，只有达到最优收敛之后结束迭代时，才会输出最优策略和值函数。
2．核心代码
策略迭代算法主要包含两步，即策略评估和策略改进，重点包含了两个函数policy_eval方法和policy_improvement方法。
policy_eval方法是策略评估方法，输入要评估的策略policy，环境env，折扣因子discount_factor，阈值threshold。输出当前策略下收敛的值函数V。
policy_improvement是策略改进方法，输入为环境env，策略评估函数policy_eval，折扣因子discoun t_factor。输出为最优值函数和最优策略。
（1）首先展示策略评估方法：
（2）策略改进方法通过调用策略评估方法实现。
3.6.3 值迭代
1．算法详情
在进行一次策略评估（即求取当前策略下的值函数）之后就进行策略改进，这种方法称为值函数迭代算法。即，在每次进行值函数计算时，直接选择那个使得值函数最大的行为。
（1）初始值函数
为（k=0）：
代码如下。
V = np.zeros(env.nS)
（2）使用贝尔曼最优方程，直接使用当前状态的最大行为值函数更新当前状态值函数。
第一次迭代（k=1），得
为：
第二次迭代（k=2），得
为：
第三次迭代（k=3），得
为：
第七次之后各状态的最优行为值函数已经收敛，
为：
对应的最优策略为：
求取各状态下最大行为值函数代码如下：
V = np.zeros(env.nS)
while True:
# 停止条件
delta = 0
# 遍历每个状态
for s in range(env.nS):
# 计算当前状态的各行为值函数
q = one_step_lookahead(s, V)
# 找到最大行为值函数
best_action_value = np.max(q)
# 值函数更新前后求差
delta = max(delta, np.abs(best_action_value - V[s]))
# 更新当前状态的值函数,即将最大的行为值函数赋值给当前状态,用以更新当前状态的
# 值函数
V[s] = best_action_value
i_num += 1
# 如果当前状态值函数更新前后相差小于阈值,则说明已经收敛,结束循环
if delta < threshold:
break
求取最优策略的代码如下。
# 初始化策略
policy = np.zeros([env.nS,env.nA])
# 遍历各状态
for s in range(env.nS):
# 根据已经计算出的V,计算当前状态的各行为值函数
q = one_step_lookahead(s, V)
# 求出当前最大行为值函数对应的动作索引
# 输出一个状态下所有的可能性
best_a_arr, policy_arr = get_max_index(q)
# 将当前所有最优行为赋值给当前状态
policy[s] = policy_arr
2．核心代码
值迭代方法将策略改进视为值函数的改进，每一步都求取最大行为值函数，用最大行为值函数更新当前状态值函数。值迭代方法为value_iteration，输入为环境env，阈值threshold，折扣因子discount_factor。输出为最优值函数和最优策略。在进行值函数更新时，使用了最优贝尔曼方程。其中方法one_step_lookahead用以求取当前状态的所有行为值函数。
代码如下。
3.6.4 实例小结
本节分别使用策略迭代和值迭代解决同一个网格世界寻找宝藏的问题，均给出了最优策略。
从策略迭代的代码可以看到，进行策略改进之前需要得到收敛的值函数。值函数的收敛往往需要很多次迭代。例如，在第一次策略改进之前，进行了338次迭代。进行策略改进之前一定要等到策略值函数收敛吗？答案是不需要。依然以第一次策略改进之前策略评估为例，策略评估迭代41次和迭代338次所得到的贪心策略是一样的，可见策略迭代方法在效率方面存在问题。
相比而言，值迭代方法就高效得多，每一次都直接用最大的行为值函数更新当前状态的值函数，直至值函数收敛，输出最优策略，其解决同样的问题仅仅需要7次迭代。