第四章：回合更新（Monte Carlo update）价值迭代

本章开始介绍无模型的强化学习算法。无模型强化学习算法在没有环境的数学描述的情况下，只依靠经验（例如轨迹样本）学习出给定策略的价值函数和最优策略。

本章介绍的回合更新算法只能用于回合制任务，它在每个回合结束后更新价值函数，与有模型迭代更新类似，也是先学习策略评估，再学习最优策略求解。回合更新的策略评估的基本思路是用 Monte Carlo 方法来估计价值函数的期望值，所以回合更新的英文为 Monte Carlo update 。

由第二章内容可以知道在有模型的情况下，借助于动力 $p$ 的表达式，状态价值函数可以表示动作价值函数；借助于策略 $\pi$ 的表达式，动作价值函数可以表示状态价值函数。但对于无模型情况下，$p$ 的表达式是未知的，因此不能用状态价值表示动作价值，只能用动作价值表示状态价值；而策略改进可仅由动作价值函数确定，故动作价值函数往往更加重要。

在同一个回合中，同一个状态（或状态动作对）可能会被多次访问；若采用回合内全部的样本值更新价值函数，则称为每次访问回合更新（every visit Monte Carlo update）；若每个回合只采用第一次访问的样本更新价值函数，则称为首次访问回合更新（first visit Monte Carlo update）；它们都能收敛到真实的价值函数。

回合更新算法包括同策回合更新算法和异策回合更新算法。同策回合更新算法是指采样（生成轨迹）的策略和被评估或被优化的策略是同一个策略；异策回合更新算法则允许两者的策略是不同的策略。

一、同策回合更新

同策的每次访问回合更新策略评估算法，即可以评估策略的状态价值；也可以评估策略的动作价值，然后使用 Bellman 期望方程求得状态价值。同策的每次访问回合更新策略评估算法如下：

与有模型迭代更新类似，算法 4-1 中可以用参数来控制回合更新的回合数，例如，使用最大回合数 $k_{max}$ 或者精度指标 $\delta_{max}$ 。该算法采用逆序更新价值函数，是因为使用了 $G_t = R_{t+1} + \gamma G_{t+1}$ 来更新 $G$ 值，以减小计算复杂度。

另外，算法 4-1 中更新价值部分的例子是使用了增量法来实现 Monte Carlo 方法的，因此需使用计数器 $c(\cdot)$ 来记录状态动作对（或状态）出现的次数，以实现增量法（增量法还可以从 Robbins-Monro 算法的角度理解，从该角度看，强化学习算法的核心在于 Robbins-Monro 算法的根基——随机近似（Stochastic Approximation）理论，此处略）。

首次访问回合更新策略评估是比每次访问回合更新策略评估更为历史悠久、更为全面研究的算法。算法 4-2 给出了同策的首次访问回合更新策略评估算法，相对于算法 4-1 不同点在于，在每次得到轨迹样本后，需要先找出各个状态分别在哪些步骤首次访问，然后在后续更新过程中，只在那些首次访问的步骤更新价值函数的估计值。

在算法 4-1 和算法 4-2 的更新价值估计后，进行策略改进，那么就会得到新的策略，这样不断更新，就有希望找到最优策略，这就是同策回合更新的基本思想。

但如果只是简单地将回合更新策略评估的算法移植为同策回合更新算法，时长会困于局部最优而找不到全局最优策略。例如同策算法可能会从一个并不好的策略出发，只经过那些较优的状态，然后只为那些较优的状态更新动作价值，而那些最优状态的动作价值没有更新仍然为 0；基于这些动作价值更新策略，只会使得策略去寻找较优的状态，而无法寻找最优的状态；更新后的策略依旧只选择那些较优的状态，反复如此，就陷入了局部最优。

为解决以上问题，提出了起始探索（exploring start）这一概念，让所有可能的状态动作对都成为可能的回合起点，这样就不会遗漏任何状态动作对，但是在理论上，目前并不清楚该带起始探索的同策回合更新算法是否总能收敛到最优策略。

带起始探索的回合更新算法也有每次访问和首次访问，算法 4-3 给出了每次访问的算法，首次访问的算法可以参照算法 4-2 在算法 4-3 的基础上修改得到，此处略。

在很多环境中，并不是任意状态都能作为回合的起始状态，例如电动游戏往往有着相对固定的起始状态，因此需要新的办法来解决陷入局部最优的问题——基于柔性策略的回合更新算法。

柔性策略（soft policy）：对于某个策略 $\pi$ ，它对任意的 $s \in \mathcal S, a \in \mathcal A(s)$ 均有 $\pi(a \mid s)>0$ 。因此柔性策略理论上是可以覆盖所有的状态或状态动作对的。

$\large{\pmb{\varepsilon}}$ 柔性策略（$\large{\pmb{\varepsilon}}$ - soft policy）：对于任意策略 $\pi$ 和正数 $\varepsilon$ ，在任意 $s \in \mathcal S, a \in \mathcal A(s)$ 下，均有 $\displaystyle \pi(a \mid s) > \frac{\varepsilon}{|\mathcal A(s)|}$ 。对于给定的环境上的某个确定性策略，在所有的 $\varepsilon$ 柔性策略中有一个策略最接近这个确定性策略，这个策略称为 $\large{\pmb{\varepsilon}}$贪心策略（$\varepsilon$ - greedy policy）。具体而言，对于确定性策略：

对应的 $\varepsilon$ 贪心策略是：

用 $\varepsilon$ 贪心策略的表达式更新策略仍然满足策略改进定理。（证明：略）

算法 4-4 给出了基于柔性策略的每次访问同策回合更新算法，基于首次访问的算法同理可以参照前面的算法来修改算法 4-4 得到，此处略。值得一提的是，算法中策略改进的操作不一定要在每步更新价值函数后就立即进行，当回合步数较长，但是状态较少时，可以在价值函数完全更新完毕后统一进行；或者也可以不显式维护策略，而是在采样过程中决定动作时用动作价值函数隐含的 $\varepsilon$ 柔性策略来决定动作，这样就不需要存储 $\pi(a \mid s)$ 了。

二、异策回合更新

在统计学上，重要性采样（importance sampling）是一种用一个分布生成的样本来估计另一个分布的统计量的方法。异策回合更新算法就是基于重要性采样的：在异策学习中，将要学习的策略 $\pi$ 称为目标策略（target policy），将用来生成行为的另一策略 $b$ 称为行为策略（behavior policy），重要性采样可以用行为策略生成的轨迹样本生成目标策略的统计量。

考虑从 $t$ 开始的轨迹 $S_t,A_t,R_{t+1},S_{t+1},\cdots,S_{T-1},A_{T-1},R_T,S_T$ ，在给定 $S_t$ 下，采用策略 $\pi$ 和策略 $b$ 生成这个轨迹的概率分别为：

这两个概率的比值定义为重要性采样比率（importance sample ratio）：

可以看到这个比率只与轨迹和策略有关，而与动力无关。为了让这个比率对不同轨迹总是有意义，需要使得任何满足 $\pi(a \mid s)>0$ 的 $s \in \mathcal S, a \in \mathcal A(s)$ ，均有 $b(a \mid s)>0$ ，记为 $\pi \ll b$ 。对于给定状态动作对 $(S_t,A_t)$ 的条件概率也有类似的分析，其概率的比值为：

同策回合更新采样 $c$ 个回报 $g_1,g_2,\cdots,g_c$ 后，用平均值 $\displaystyle \frac{1}{c} \sum_{i=1}^c g_i$ 来作为价值函数的估计，这样的方法实际上默认了这 $c$ 个回报是等概率出现的。同样的，异策略用行为策略 $b$ 得到的采样结果相对于行为策略 $b$ 也是等概率出现的；但对于目标策略 $\pi$ 而言，各样本的出现概率是各轨迹的重要性采样比率，这样我们可以用加权平均来完成 Monte Carlo 估计。具体而言，若 $\rho_i \; (1 \le i \le c)$ 是回报样本 $g_i$ 对应的权重（即轨迹的重要性采样比率），可以有以下两种加权方法：

• 加权重要性采样（weighted importance sampling）：$\displaystyle \frac{\displaystyle \sum_{i=1}^{c} \rho_i g_i}{\displaystyle \sum_{i=1}^{c} \rho_i}$ 。
• 普通重要性采样（ordinary importance sampling）：$\displaystyle \frac{1}{c} \sum_{i=1}^{c} \rho_i g_i$ 。

对于加权重要性采样，如果某个权重 $\rho_i=0$ ，那么它不会让对应的 $g_i$ 参与平均，并不影响整体的平均值；对于普通重要性采样，如果某个权重 $\rho_i=0$ ，那么它会让 $0$ 参与平均，使得平均值变小。（两者使用时的具体区别请参考《Reinforcement Learning: An Introduction Second Edition》，Richard S,sutton 等著，第五章 5.5 节。）

基于重要性采样，可以得出每次访问加权重要性采样回合更新策略评估算法 4-5 ，算法中的行为策略 $b$ 可以每个回合都单独设计，也可以为整个算法设计同一个行为策略。在该算法上略作修改，即可得到首次访问的算法、普通重要性采样的算法和估计状态价值的算法，此处略。

因为算法是逆序更新评估动作价值，根据其重要性采样比率表达式 $\eqref{eq:4}$ 可知，权重值初始化为 1 ，同时根据该表达式来更新权重，如果某次权重值变为 0 ，那么之后循环的权重也都为 0 ，因此此时可以终止循环。

（该算法存在的问题：考虑只有一种结局的环境，且在该环境下，存在一种策略无法到达该环境的结局，例如一个唯一出口的迷宫，如果确定性目标策略 $\pi$ 来回打转无法走出迷宫，即无法结束环境的一个回合到达终止状态 $S_T$ ，那么对于采样的任意轨迹都有 $\displaystyle \frac{\pi(A_{T-1} \mid S_{T-1})}{b(A_{T-1} \mid S_{T-1})}=0$ ，此时永远都只能更新终止状态的前一个状态。再推广到多结局环境，只要存在一种策略无法到达该环境的结局，且目标策略为这种策略，那么该算法都只能更新终止状态的前一个状态。另外该算法显然会在很多情况下提前终止，使得很多采样轨迹未被完全使用，与同策算法相同迭代次数下，更新价值的次数更少，因此可能需要更多的迭代次数才能够更好的收敛。）

在评估策略动作价值的基础上加上策略改进即可得到求解最优策略的算法 4-6 。由于使用了确定性策略 $\pi$ ，所以存在一个状态使得 $\pi(a \mid s)=1$ ；若 $A_t \ne \pi(S_t)$ ，意味着 $\pi(A_t \mid S_t)=0$ ，否则为 $\pi(A_t \mid S_t)=1$ ；据此就可以得到步骤 2.4.4 和 2.4.5 了。对该算法稍加修改，即可得到首次访问的算法和普通重要性采样的算法，此处略。

（该算法存在与算法 4-5 类似的问题：假设环境为一条从左到右拥有 n 个状态的直线迷宫，那么只有在终点前一个状态时往右走，才能到达终点走出迷宫结束回合。设到达终点奖励为 10 ，记为 $R_t(10)$ ，其他奖励都为 0 ，记为 $R_t(0)$ ，往左走记为 $A_t(1)$ ，往右走记为$A_t(2)$ ，状态 $i$ 记为 $S_t(i)$ ，下标 $t$ 表示采样轨迹的时间步；对于任意一回合轨迹，最后一次动作的采样数据为 $S_{T-1}(n-1),A_{T-1}(2),R_T(10),S_T(n)$ ，根据以上算法，可以设定该初始化 $q(S(n-1), A(1))=100$ ，$q(S(n-1), A(2))=20$ ，那么第一回合轨迹的逐步更新循环

只使用了最后一次动作轨迹就直接结束了，然后对于第二回合的任意轨迹，其最后一次动作轨迹依旧相同，那么无论循环多少次，改变的只有权重和 $c(S(n-1),A(2))$ 的值，而 $q(S(n-1),A(2))$ 与 $\pi(S(n-1))$ 的值则一直不变，那么其他动作状态对永远无法更新。只有当初始化时 $q(S(n-1), A(1))$ 小于更新后 $q(S(n-1), A(2))$ 的值时，逐步更新循环才能进行第二次循环，在对于第二次循环的过程中，也存在类似的问题。）

三、案例：21 点游戏（Blackjack-v0）

使用 gym 库中的纸牌游戏 “21点”（Blackjack-v0）作为案例分析，为其实现游戏 AI。该游戏规则可百度或者查看源代码，另外使用学习代码中的 run_episode 函数也能够助于理解该游戏过程。

由于该游戏具有以下特点：

• 在一个轨迹中不可能出现重复的状态，因此不需要区分首次访问和每次访问。
• 在一个轨迹中只有最后的一个奖励值是非零值。
• （游戏过程不会涉及算法 4-5 和 4-6 所存在的问题，实现算法时不做额外考虑。）

因此当限定 $\gamma=1$ 时，算法中的回报更新部分可以去掉，直接使 $G=R_T$ ，且在更新时能够进行顺序更新。那么采样轨迹只需要记录状态和动作以及最后一个奖励值，可将书中源代码的采样轨迹部分提取，作为一个单独的用来采样轨迹的函数 explore_sampling ，并返回需要记录的值即可：

xxxxxxxxxx
11
1
def explore_sampling(env, policy):
2
    state_actions = []
3
    state = env.reset()
4
    while True:
5
        state = (state[0], state[1], int(state[2]))
6
        action = np.random.choice(env.action_space.n, p=policy[state])
7
        state_actions.append((state, action))
8
        state, reward, done, _ = env.step(action)
9
        if done:
10
            break
11
    return state_actions, reward

然后在实现算法时，采样部分改为调用该函数即可。例如使用算法 4-1 实现策略评估：

xxxxxxxxxx
10
1
def evaluate_action_monte_carlo(env, policy, episode_num=500000):
2
    q = np.zeros_like(policy)
3
    c = np.zeros_like(policy)
4
    for _ in range(episode_num):
5
        state_actions, reward = explore_sampling(env, policy)
6
        g = reward
7
        for state, action in state_actions:
8
            c[state][action] += 1.
9
            q[state][action] += (g - q[state][action]) / c[state][action]
10
    return q

根据该游戏规则，可以知道当玩家点数小于等于 11 点时，再要一张牌肯定不会超过 21 点，因此玩家点数在 12~21 点是更加值得去关注的状态。下面使用算法 4-3 来实现玩家起始点数为 12~21 点的最优策略求解，由于该环境下相同总点数的玩家持牌都是等价的，因此只需任意指定一种玩家的持牌即可：

xxxxxxxxxx
36
1
def monte_carlo_with_exploring_start(env, episode_num=500000):
2
    policy = np.zeros((22, 11, 2, 2))
3
    policy[:, :, :, 1] = 1.
4
    q = np.zeros_like(policy)
5
    c = np.zeros_like(policy)
6
    for _ in range(episode_num):
7
        state = (np.random.randint(12, 22), \
8
                 np.random.randint(1, 11), \
9
                 np.random.randint(2))
10
        action = np.random.randint(2)
11
        env.reset()
12
        if state[2]:
13
            env.player = [1, state[0] - 11]
14
        else:
15
            if state[0] == 21:
16
                env.player = [10, 9, 2]
17
            else:
18
                env.player = [10, state[0] - 10]
19
        env.dealer[0] = state[1]
20
        state_actions = []
21
        while True:
22
            state_actions.append((state, action))
23
            state, reward, done, _ = env.step(action)
24
            if done:
25
                break
26
            state = (state[0], state[1], int(state[2]))
27
            action = np.random.choice(env.action_space.n, p=policy[state])
28
​
29
        g = reward
30
        for state, action in state_actions:
31
            c[state][action] += 1.
32
            q[state][action] += (g - q[state][action]) / c[state][action]
33
            a = q[state].argmax()
34
            policy[state] = 0.
35
            policy[state][a] = 1.
36
    return policy, q

其他的最优策略求解算法也是类似的，这里不再展示代码，具体可查看代码目录下的 4.Blackjack-v0.py 。在得到最优策略后可对最优策略进行测试，函数 test_policy 在指定回合数下与庄家进行游戏，并统计输赢和平局回合数。

xxxxxxxxxx
12
1
def test_policy(env, policy, episode_num=50000):
2
    win, tied, lost = 0, 0, 0
3
    for _ in range(episode_num):
4
        score = run_episode(env, policy)
5
        if score == 1:
6
            win += 1
7
        elif score == 0:
8
            tied += 1
9
        elif score == -1:
10
            lost += 1
11
    print("AI win {} round, tied {} round, lost {} round, in {} round, against dealer."\
12
            .format(win, tied, lost, episode_num))