强化学习基础巩固（五）——策略梯度

之前介绍的 Q-learning、DQN 及 DQN 改进算法都是基于价值（value-based）的方法，其中 Q-learning 是处理有限状态的算法，而 DQN 可以用来解决连续状态的问题。在强化学习中，除了基于值函数的方法，还有一支非常经典的方法，那就是基于策略（policy-based）的方法。对比两者，基于值函数的方法主要是学习值函数，然后根据值函数导出一个策略，学习过程中并不存在一个显式的策略；而基于策略的方法则是直接显式地学习一个目标策略。策略梯度是基于策略的方法的基础。

在一场游戏里面，我们把环境输出的$s$与演员输出的动作$a$全部组合起来，就是一个轨迹，即

$$\tau = \left \{s_1,a_1,s_2,a_2,\cdots,s_t,a_t \right \}$$

给定演员的参数$\theta$，我们可以计算某个轨迹$\tau$发生的概率为

$$\begin{aligned} p_\theta(\tau) &= p(s_1)p_\theta(a_1|s_1)p(s_2|s_1,a_1)p_\theta(a_2|s_2)p(s_3|s_2,a_2)\cdots \\ &=p(s_1)\prod^T_{t=1} p_\theta(a_t|s_t)p(s_{t+1}|s_t,a_t) \end{aligned}$$

我们把轨迹所有的奖励$r$都加起来，就得到了$R(\tau)$，其代表某一个轨迹$\tau$的奖励。
在某一场游戏的某一个回合里面，我们会得到$R(\tau)$。我们要做的就是调整演员内部的参数$\theta$，使得$R(\tau)$的值越大越好。但实际上$R(\tau)$并不只是一个标量，它是一个随机变量，因为演员在给定同样的状态下会采取什么样的动作，这是有随机性的。环境在给定同样的观测时要采取什么样的动作，要产生什么样的观测，本身也是有随机性的，所以$R(\tau)$是一个随机变量。我们能够计算的是$R(\tau)$的期望值。给定某一组参数$\theta$，我们可计算$r_\theta$的期望值为

$$\begin{aligned} \bar{R_\theta} &= \sum_r R(\tau)p_\theta(\tau) \\ &= \mathbb{E}_{\tau \sim p_\theta(\tau)} [R(\tau)] \end{aligned}$$

从分布$p_\theta(\tau)$采样一个轨迹$\tau$，计算$R(\tau)$的期望值，就是期望奖励。我们要最大化期望奖励。
因为我们要让奖励越大越好，所以可以使用梯度上升来最大化期望奖励。要进行梯度上升，我们先要计算期望奖励$\bar{R_\theta}$的梯度。我们对$\bar{R_\theta}$做梯度运算

$$\nabla{\bar{R_\theta}} = \sum_\tau R(\tau)\nabla p_\theta(\tau)$$

其中，只有$p_\theta(\tau)$与$\theta$有关。
奖励函数$R(\tau)$不需要是可微分的，这不影响我们解决接下来的问题。例如，如果在生成对抗网络里面，$R(\tau)$是一个判别器，它就算无法微分，我们还是可以做接下来的运算。

$$\begin{aligned} &\begin{aligned} \because f(x)\nabla\log f(x) &= f(x)\cdot \frac{\nabla f(x)}{f(x)} \\ &= \nabla f(x)\\ \end{aligned}\\ &\begin{aligned} \therefore \nabla p_\theta(\tau) &= p_\theta(\tau) \nabla \log p_\theta(\tau) \\ \rightarrow \frac {\nabla p_\theta(\tau)}{p_\theta(\tau)} &= \nabla \log p_\theta(\tau) \end{aligned} \end{aligned}$$

我们对$\tau$进行求和，把$R(\tau)$和$\log p_\theta(\tau)$这两项使用$p_\theta(\tau)$进行加权，既然使用$p_\theta(\tau)$进行加权 ，它们就可以被写成期望的形式。也就是我们从$p_\theta(\tau)$这个分布里面采样$\tau$， 去计算$R(\tau)$乘$\nabla \log p_\theta(\tau)$，对所有可能的$\tau$进行求和，就是期望的值。

$$\begin{aligned} \nabla \bar{R_\theta} &= \sum_r R(\tau)\nabla p_\theta(\tau) \\ &=\sum_r R(\tau)p_\theta(\tau)\frac{\nabla p_\theta(\tau)}{p_\theta(\tau)} \\ &=\sum_r R(\tau)p_\theta(\tau)\nabla \log p_\theta(\tau) \\ &=\mathbb{E}_{\tau \sim p_\theta(\tau)} [R(\tau)\nabla \log p_\theta(\tau)] \end{aligned}$$

实际上期望值$\mathbb{E}_{\tau \sim p_\theta(\tau)} [R(\tau)\nabla \log p_\theta(\tau)]$无法计算，所以我们用采样的方式采样$N$个$\tau$并计算每一个的值，把每一个的值加起来，就可以得到梯度，即

$$\begin{aligned} \mathbb{E}_{\tau \sim p_\theta(\tau)} [R(\tau)\nabla \log p_\theta(\tau)] &\approx \frac{1}{N}\sum^N_{n=1}R(\tau^n)\nabla \log p_\theta(\tau^n) \\ &= \frac{1}{N}\sum^N_{n=1}R(\tau^n)\nabla \left (\log p(s_1)+ \sum^{T_n}_{t=1}p_\theta(a_t|s_t) + \sum^{T_n}_{t=1}p(s_{t+1}|s_t,a_t) \right )\\ &= \frac{1}{N}\sum^N_{n=1}R(\tau^n)\left (\nabla \log p(s_1)+ \nabla\sum^{T_n}_{t=1}p_\theta(a_t|s_t) + \nabla\sum^{T_n}_{t=1}p(s_{t+1}|s_t,a_t)\right )\\ &= \frac{1}{N}\sum^N_{n=1}R(\tau^n)\nabla\sum^{T_n}_{t=1}p_\theta(a_t|s_t)\\ &= \frac{1}{N}\sum^N_{n=1} R(\tau^n) \sum^{T_n}_{t=1} \nabla \log p_\theta(a^n_t|s^n_t)\\ &=\frac{1}{N}\sum^N_{n=1} \sum^{T_n}_{t=1} R(\tau^n)\nabla \log p_\theta(a^n_t|s^n_t) \end{aligned}$$

我们可以直观地理解该式，也就是在我们采样到的数据里面，采样到在某一个状态$s_t$要执行某一个动作$a_t$，$(s_t,a_t)$是在整个轨迹$\tau$的里面的某一个状态和动作的对。假设我们在$s_t$执行$a_t$，最后发现$\tau$的奖励是正的，我们就要增加在$s_t$执行$a_t$的概率。反之，如果在$s_t$执行$a_t$会导致$\tau$的奖励变成负的，我们就要减少在$s_t$执行$a_t$的概率。这怎么实现呢？我们用梯度上升来更新参数，原来有一个参数$\theta$，把$\theta$加上梯度$\nabla\bar{R_\theta}$，当然我们要有一个学习率$\eta$，学习率也是要调整的，可用 Adam、RMSProp 等方法来调整学习率，即

$$\theta \leftarrow \theta + \eta \nabla\bar{R_\theta}$$

把每一个$s$与$a$的对拿进来，计算在某一个状态下采取某一个动作的对数概率$\log p_\theta(a^n_t|s^n_t)$。对这个概率取梯度，在梯度前面乘一个权重，权重就是这场游戏的奖励。我们计算出梯度后，就可以更新模型。

$$\nabla\bar{R_\theta}=\frac{1}{N}\sum^N_{n=1} \sum^{T_n}_{t=1} R(\tau^n)\nabla \log p_\theta(a^n_t|s^n_t)$$

更新完模型以后，我们要重新采样数据再更新模型。注意，一般策略梯度（policy gradient，PG）采样的数据只会用一次。我们采样这些数据，然后用这些数据更新参数，再丢掉这些数据。接着重新采样数据，才能去更新参数。

REINFORCE算法

REINFORCE 用的是回合更新的方式，它在代码上的处理上是先获取每个步骤的奖励，然后计算每个步骤的未来总奖励$G_t$，将每个$G_t$代入

$$\nabla\bar{R_\theta}\approx\frac{1}{N}\sum^N_{n=1} \sum^{T_n}_{t=1} G_t\nabla \log p_\theta(a^n_t|s^n_t)$$

优化每一个动作的输出。所以我们在编写代码时会设计一个函数，这个函数的输入是每个步骤获取的奖励，输出是每一个步骤的未来总奖励。因为未来总奖励可写为

$$\begin{aligned} G_t &= \sum^T_{k=t+1}\gamma^{k-t-1}r_k \\ &= r_{t+1} + \gamma G_{t+1} \end{aligned}$$

即上一个步骤和下一个步骤的未来总奖励的关系如式所示，所以在代码的计算上，我们是从后往前推，一步一步地往前推，先算$G_T$，然后往前推，一直算到$G_1$。

Q&A

Q：应该如何理解策略梯度的公式？
A：策略梯度的公式如下：

$$\begin{aligned} \mathbb{E}_{\tau \sim p_\theta(\tau)} [R(\tau)\nabla \log p_\theta(\tau)] &\approx \frac{1}{N}\sum^N_{n=1}R(\tau^n)\nabla \log p_\theta(\tau^n) \\ &=\frac{1}{N}\sum^N_{n=1} \sum^{T_n}_{t=1} R(\tau^n)\nabla \log p_\theta(a^n_t|s^n_t) \end{aligned}$$

$p_\theta(\tau)$里面有两项，$p(s_{t+1}|s_t,a_t)$来自环境，$p_\theta(a_t|s_t)$来自智能体。$p(s_{t+1}|s_t,a_t)$与$\theta$无关，故$\nabla p(s_{t+1}|s_t,a_t)=0$。

Q：手动推导策略梯度公式的计算过程。
A：首先我们的目的是最大化奖励函数，即调整$\theta$，使得期望回报最大，可以用公式表示如下：

$$\begin{aligned} J(\theta) &= \mathbb{E}_{\tau \sim p_\theta(\tau)}R(\tau) \\ &=\mathbb{E}_{\tau \sim p_\theta(\tau)}\left [ \sum_t r(s_t,a_t)\right] \end{aligned}$$

可以用梯度上升法求其最大值，即：

$$\theta^* = \theta + \alpha \nabla J(\theta)$$

即计算$J(\theta)$对$\theta$的梯度，即策略梯度。

$$\begin{aligned} \nabla_\theta J(\theta) &= \nabla_\theta \int p_\theta(\tau)R(\tau) d\tau\\ &= \int \nabla_\theta p_\theta(\tau)R(\tau) d\tau \\ &= \int p_\theta(\tau)\nabla_\theta \log p_\theta(\tau)R(\tau) d\tau \\ &=\mathbb{E}_{\tau \sim p_\theta(\tau)}\left [ \nabla_\theta \log p_\theta(\tau)R(\tau)\right] \end{aligned}$$

其中，

$$p_\theta(\tau)=p(s_1)p_\theta(a_1|s_1)p(s_2|s_1,a_1)\dots=p(s_1)\prod^T_{t=1}p_\theta(a_t|s_t)p(s_{t+1}|s_t,a_t)$$

取对数后有

$$\log p_\theta(\tau)=\log p(s_1) + \sum^T_{t=1}\log p_\theta(a_t|s_t) + \sum^T_{i=t}p(s_{t+1}|s_t,a_t)$$

其中第一项与第三项与$\theta$无关，导数为0。故

$$\nabla_\theta \log p_\theta(\tau)=\sum^T_{t=1}\nabla_\theta \log p_\theta(a_t|s_t)$$

带入前式可得

$$\begin{aligned} \nabla_\theta J(\theta) &= \mathbb{E}_{\tau \sim p_\theta(\tau)}\left [ \nabla_\theta \log p_\theta(\tau)R(\tau)\right]\\ &= \mathbb{E}_{\tau \sim p_\theta(\tau)}\left [ \sum^T_{t=1}\nabla_\theta \log p_\theta(a_t|s_t)R(\tau)\right]\\ &= \mathbb{E}_{\tau \sim p_\theta(\tau)}\left [ \sum^T_{t=1}\nabla_\theta \log p_\theta(a_t|s_t)\sum^T_{t=1}r(s_t,a_t)\right]\\ \end{aligned}$$

我们通过采样的方式计算该期望，则有

$$\nabla_\theta J(\theta) =\frac{1}{N}\sum^N_{i=1}\left [ \sum^T_{t=1}\nabla_\theta \log p_\theta(a_{i,t}|s_{i,t})\left (\sum^T_{t=1}r(s_{i,t},a_{i,t})\right )\right]$$

Q：基于策略梯度优化的技巧有哪些？
A：

1. 增加基线：为了防止所有奖励都为正，从而导致每一个状态和动作的变换，都会使得每一个变换的概率上升，我们把奖励减去一项$b$，称$b$为基线。当减去$b$以后，就可以让奖励$R(\tau^n)-b$有正有负。如果得到的总奖励$R(\tau^n)$大于$b$，就让它的概率上升。如果总奖励小于$b$，就算它是正的，值很小也是不好的，就需要让它的概率下降。如果总奖励小于$b$，就要让采取这个动作的奖励下降，这样也符合常理。但是使用基线会让本来奖励很大的“动作”的奖励变小，降低更新速率。
2. 指派合适的分数：首先，原始权重是整个回合的总奖励。现在改成从某个时间点$t$开始，假设这个动作是在时间点$t$被执行的，那么从时间点$t$，一直到游戏结束所有奖励的总和，才真的代表这个动作是好的还是不好的；接下来我们再进一步，把未来的奖励打一个折扣，这里我们称由此得到的奖励的和为折扣回报。
3. 综合以上两种技巧，我们将其统称为优势函数，用$A$来代表优势函数。优势函数取决于状态和动作，即我们需计算的是在某一个状态$s$采取某一个动作$a$的时候，优势函数有多大。