第七章：回合更新策略梯度方法

在前几章的算法中，求解最优策略都是试图估计最优价值函数，这些算法称为最优价值算法（optimal value algorithm）。本章开始介绍试图用含参函数近似最优策略，并通过迭代更新参数值，这类算法称为策略梯度算法（optimal gradient algorithm）。

一、策略梯度算法的原理

用函数近似方法估计最优策略 $\pi(a \mid s)$ 的基本思想是用含参函数 $\pi(a \mid s; \Bbb\theta)$ 来近似最优策略，由于任意策略都需要满足对于任意的状态 $s \in \mathcal S$ ，均有 $\displaystyle \sum_a \pi(a \mid s) = 1$ ，为此引入动作偏好函数（action preference function）$h(s,a;\theta)$ ，其 softmax 的值为 $\pi(a \mid s; \theta)$ ，即：

动作偏好函数可以具有线性组合、人工神经网络等多种形式，其参数 $\theta$ 通常使用基于梯度的迭代算法更新，所以动作偏好函数往往需要对参数 $\theta$ 可导，另外还需要知道期望回报对参数 $\theta$ 的梯度，这样就能沿着梯度方向更新 $\theta$ 而使得期望回报增大；而策略梯度定理（policy gradient theorem）给出了期望回报和策略梯度之间的关系，是策略梯度方法的基础。

在回合制任务中，策略梯度定理给出了策略 $\pi(\theta)$ 的期望回报 $E_{\pi(\theta)}[G_0]$ 对策略参数 $\theta$ 的梯度为：

证明：对策略 $\pi(\theta)$ 的 Bellman 期望方程分别求梯度，有：

将 $\nabla q_{\pi(\theta)}(s,a)$ 代入到 $\nabla v_{\pi(\theta)}(s)$ 中，并对 $\nabla v_{\pi(\theta)}(s)$ 求期望，有：

这样就得到了从 $E[\nabla v_{\pi(\theta)}(S_t)]$ 到 $E[\nabla v_{\pi(\theta)}(S_{t+1})]$ 的递推式，再注意到最终关注的梯度值 $\nabla E_{\pi(\theta)}[G_0]$ ，有：

二、同策回合更新策略梯度算法

由式 $\eqref{eq:2}$ 可直接得到一个策略梯度算法——简单的策略梯度算法（Vanilla Policy Gradient, VPG），其每一步的更新式为：

这样迭代完一个回合轨迹就实现了 $\displaystyle \theta \leftarrow \theta + \alpha \sum_{t=0}^{+\infty} \gamma^t G_t \nabla \ln \pi(A_t \mid S_t; \theta)$ 。R. Willims 在文章《Simple statistical gradient-following algorithms for connectionist reinforcement learning》中给出该算法，并称为 “REward Increment = Nonnegative Factor $\times$ Offset Reinforcement $\times$ Characteristic Eligibility”（REINFORCE），表示增量 $\alpha \gamma^t G_t \nabla \ln \pi(A_t \mid S_t; \theta_t)$ 是由三个部分的积组成的。当采用自动微分的软件包来学习参数时，可定义单步损失为 $-\gamma^t G_t \ln \pi(A_t \mid S_t; \theta)$ ，然后让软件包自动处理，具体算法如下：

回合更新的方法没有用到自益，不会引入偏差，但往往有非常大的方差。为了降低方差，引入基线函数 $B(s),\;s \in \mathcal S$ 对简单的策略梯度算法进行改进——带基线的简单的策略梯度算法（REINFORCE with baselines），基线函数可以是任意随机函数或确定函数，他可以与状态 $s$ 有关，但不能和动作 $a$ 有关，满足这些条件后，基线函数自然满足：

证明：

基线函数可以任意选择，例如：

• 选择基线函数为由轨迹确定的随机变量 $\displaystyle B(S_t)=-\sum_{\tau=1}^{t-1} \gamma^{\tau-t}R_\tau$ ，这时有 $\displaystyle \gamma^t(G_t-B(S_t))=\sum_{\tau=0}^{+\infty}\gamma^{\tau+t}R_{t+\tau+1}+$ $\displaystyle \sum_{\tau=1}^{t-1}\gamma^\tau R_\tau=\sum_{\tau=0}^{+\infty}\gamma^\tau R_{\tau+1}=G_0$ ，那么梯度的形式为 $E[G_0 \nabla \ln \pi(A_t \mid S_t; \theta)]$ 。
• 选择基线函数为 $B(S_t)=\gamma^t v_*(S_t)$ ，这时梯度形式为 $E[\gamma^t(G_t-v_*(S_t))\nabla \ln \pi(A_t \mid S_t; \theta)]$ 。

但在实际选择基线时，应当参照以下两点：

• 基线的选择应当有效降低方差。但能不能降低方差不容易在理论上判别，往往需要通过实践获知。
• 基线函数应当是可以得到的。例如虽然不知道最优价值函数，但是可以得到最优价值函数的估计。

一个能有效降低方差的基线是状态价值函数的估计，其对应的算法如下：

下面分析一下什么样的基线函数能最大程度地减小方差。考虑 $E[\gamma^t(G_t-B(S_t))\nabla\ln\pi(A_t \mid S_t;\theta)]$ 的方差，并对 $B(S_t)$ 求偏导有：

假设 $E\left[B(S_t)[\nabla\ln\pi(A_t \mid S_t;\theta)]^2\right] = E[B(S_t)]E\left[[\nabla\ln\pi(A_t \mid S_t;\theta)]^2\right]$ ，即两者相互独立，并令上述偏导为 0 ，则有：

这意味着，最佳的基线函数应当接近回报 $G_t$ 以 $[\nabla\ln\pi(A_t \mid S_t;\theta)]^2$ 为权重加权平均的结果，但是实际应用中，无法事先知道这个值，所以无法使用这样的基线函数。值得一提的是，当策略参数和价值参数同时需要学习的时候，算法的收敛性需要通过双时间轴 Robbins-Monro 算法（two timescale Robbins-Monro algorithm）来分析。

三、异策回合更新策略梯度算法

在简单的策略梯度算法的基础上引入重要性采样，即可得到对应的异策算法。记行为策略为 $b(a \mid s)$ ，有：

所以采用重要性采样的离线算法，只需要修改更新式 $\eqref{eq:3}$ 中期望回报的梯度表达式即可，得到的具体算法如下：

重要性采样虽然使得可利用其他策略的样本来更新策略参数，但可能会带来较大的偏差，算法稳定性比同策算法差。

四、策略梯度更新与极大似然估计的关系

以上算法都是通过更新策略参数 $\theta$ 以试图增大形如 $E[\Psi_t\ln\pi(A_t \mid S_t;\theta)]$ 的目标（单个条目则为 $\Psi_t\ln\pi(A_t \mid S_t;\theta)$ ），其中 $\Psi_t$ 可取 $G_0$ 、$G_t$ 等值。从监督学习的角度来看，如果已经有一个表达式未知的策略 $\pi$ ，当要用策略 $\pi(\theta)$ 来近似它时，可以考虑用最大似然的方法来估计策略参数 $\theta$ 。具体而言，未知策略 $\pi$ 的许多样本对于策略 $\pi(\theta)$ 的对数似然值正比于 $E(\ln\pi(A_t \mid S_t;\theta))$ ，这时使用这些样本进行有监督学习，则是更新 $\theta$ 以增大 $E(\ln\pi(A_t \mid S_t;\theta))$（单个条目则为 $\ln\pi(A_t \mid S_t;\theta)$ ），可以看出这里是目标 $E[\Psi_t\ln\pi(A_t \mid S_t;\theta)]$ 中取 $\Psi_t=1$ 时得到的，在形式上具有想相似性。事实上，策略梯度算法在学习过程中巧妙地利用观测到的奖励信号决定每步对数似然值 $\ln\pi(A_t \mid S_t;\theta)$ 对策略奖励的贡献，为其加权为 $\Psi_t$ ，使得表现好的行为策略更新幅度大，更加倾向于出现；表现很差的行为策略更新幅度很小，更加倾向于不出现；最终使得整个策略 $\pi(\theta)$ 变得越来越好。

五、案例：车杆平衡（CartPole-v0）

使用 Gym 库里的车杆平衡问题（CartPole-v0）作为案例分析。该问题的环境为一个小车（cart）上连着一根杆（pole），目的是控制小车左右移动，使得杆保持直立；环境的观测值、动作值、奖励值、起始状态、回合结束标志在源代码中有描述，此处不再赘述。

在使用书中的同策策略梯度算法求解最优策略的代码时，经多次测试发现该代码的收敛性较差，训练智能体过程的回合奖励值变化大多呈下降趋势，在尝试调节学习率后，最好的情况也是呈现波动趋势，且测试结果的平均奖励值不超过 50 。经调试，造成该结果的可能原因是书中代码直接将 $\Psi_t\pi(A_t \mid S_t;\theta)$ 作为输出结果进行训练，而实际上网络输出层的激活函数是 softmax ，输出的应该是 $\pi(A_t \mid S_t;\theta)$ 。

具体而言就是，假设以 $\Psi_t\pi(A_t \mid S_t;\theta)$ 作为输出结果来训练，由于训练网络的损失函数为交叉熵函数，网络各个输出结果的值域为 $[0,1]$ ，为了使损失函数降低，训练会使网络的输出结果趋向于 0 或 1 ，即与环境交互得到新样本的 $\Psi_t\pi(A_t \mid S_t;\theta)$ 值趋向于 0 或 1 ，这样损失函数才会越来越小；但实际上在该环境中得到的新样本的 $\Psi_t$ 值基本上都是大于 1 的，那么以上的训练过程就只会导致 $\Psi_t$ 越来越小，且尽可能的接近 1 ，最终导致算法无法收敛或甚至发散。修改前的代码如下：

xxxxxxxxxx
2
1
y = np.eye(self.action_n)[df["action"]] * df["psi"].values[:, np.newaxis]
2
self.policy_net.fit(x, y, verbose=0)

解决办法是在训练时，将 $\Psi_t$ 作为样本权重，$\pi(A_t \mid S_t;\theta)$ 作为输出结果；即 $\Psi_t$ 大的样本，其权重也大，更新幅度越大，这样才符合算法的思想。另外，在每个回合后直接使用整个回合的样本作为 batch 进行训练，其效果有时候会非常好，对应函数为 train_on_batch ，可能是因为这样的更新方式是直接符合更新式 $\displaystyle \theta \leftarrow \theta + \alpha \sum_{t=0}^{+\infty} \gamma^t G_t \nabla \ln \pi(A_t \mid S_t; \theta)$ 的，而不需要通过更新式 $\eqref{eq:3}$ 来间接更新参数 $\theta$ 。修改后的代码如下：

xxxxxxxxxx
3
1
sample_weight = df["psi"].values[:, np.newaxis]
2
y = np.eye(self.action_n)[df["action"]]
3
self.policy_net.train_on_batch(x, y, sample_weight=sample_weight)

因为在异策代码中使用的损失函数不同，所以上述不收敛的问题在异策代码中并不存在，但同样也可以使用被修改后的代码进行训练，其思想是一致的。根据书中源代码，将同策异策智能体整合，并对 $\Psi_t$ 做标准化处理保证网络训练的稳定性，以及将行为策略指定为随机策略，最终修改后的智能体类代码如下：

xxxxxxxxxx
54
1
class VPG():
2
    def __init__(self, env, policy_kwargs, baseline_kwargs=None, gamma=0.99, offpolicy=False):
3
        self.action_n = env.action_space.n
4
        self.gamma= gamma
5
        self.trajectory = []
6
​
7
        if not offpolicy:
8
            self.random_behavior = False
9
            policy_loss = keras.losses.categorical_crossentropy
10
        else:
11
            self.random_behavior = True
12
            policy_loss = lambda y_true, y_pred: -tf.reduce_sum(y_true * y_pred, axis=-1)
13
​
14
        self.policy_net = self.build_network(output_size=self.action_n, \
15
                output_activation=tf.nn.softmax, loss=policy_loss, **policy_kwargs)
16
        if baseline_kwargs:
17
            self.baseline_net = self.build_network(output_size=1, **baseline_kwargs)
18
​
19
    def build_network(self, hidden_sizes, output_size, activation=tf.nn.relu, \
20
            output_activation=None, loss=keras.losses.mse, learning_rate=0.01):
21
        model = keras.Sequential()
22
        for hidden_size in hidden_sizes:
23
            model.add(keras.layers.Dense(units=hidden_size, activation=activation))
24
        model.add(keras.layers.Dense(units=output_size, activation=output_activation))
25
        model.compile(loss=loss, optimizer=keras.optimizers.Adam(lr=learning_rate))
26
        return model
27
​
28
    def choose_action(self, state):
29
        probs = self.policy_net.predict(state[np.newaxis])[0]
30
        return np.random.choice(self.action_n, p=probs)
31
​
32
    def learn(self, state, action, reward, done):
33
        self.trajectory.append((state, action, reward))
34
​
35
        if done:
36
            df = pd.DataFrame(self.trajectory, columns=["state", "action", "reward"])
37
            df["discount"] = self.gamma ** df.index.to_series()
38
            df["psi"] = (df["discount"] * df["reward"])[::-1].cumsum()
39
​
40
            x = np.stack(df["state"])
41
            if hasattr(self, "baseline_net"):
42
                df["return"] = df["psi"] / df["discount"]
43
                y = df["return"].values[:, np.newaxis]
44
                self.baseline_net.train_on_batch(x, y)
45
                df["baseline"] = self.baseline_net.predict(x)
46
                df["psi"] -= (df["discount"] * df["baseline"])
47
            if self.random_behavior:
48
                df["psi"] *= self.action_n
49
​
50
            df["psi"] = (df["psi"] - df["psi"].mean()) / df["psi"].std()
51
            sample_weight = df["psi"].values[:, np.newaxis]
52
            y = np.eye(self.action_n)[df["action"]]
53
            self.policy_net.train_on_batch(x, y, sample_weight=sample_weight)
54
            self.trajectory = []

（由于学习率参数和探索随机性的影响，并不能保证每次运行的指定回合数的训练都能收敛，或者往好的趋势发展；可以尝试多次运行、调节学习率或增加训练回合数，也可以修改代码，在训练后保存模型，然后在下次训练前读取模型并调节学习率继续训练。）