1. 策略梯度算法

强化学习有3个组成部分：演员（actor）、环境和奖励函数。环境与奖励函数不是我们可以控制的，它们是在开始学习之前给定的。我们唯一需要做的就是调整演员里面的策略，使得演员可以得到最大的奖励

策略一般记作π\pi。假设我们使用深度学习来做强化学习，策略就是一个网络。网络里面有一些参数，我们用θ\theta来代表π\pi的参数。网络的输入是智能体看到的东西，输出是我们可以执行的动作，有几个动作，输出层就有几个神经元

我们把初始状态记作s1s_1，把第一次执行的动作记作a1a_1，把第一次执行动作以后得到的奖励记作r1r_1。不同的人有不同的记法，有人觉得在s1s_1执行a1a_1得到的奖励应该记为r2r_2，这两种记法都可以

一场游戏称为一个回合。将这场游戏里面得到的所有奖励都加起来，就是总奖励（total reward），也就是回报，我们用RR来表示它

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

τ={s1,a1,s2,a2,⋯ ,st,at}\tau = \{ s_1, a_1, s_2, a_2, \cdots, s_t, a_t \}

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

pθ(τ)=p(s1)pθ(a1∣s1)p(s2∣s1,a1)pθ(a2∣s2)⋯=p(s1)∏t=1Tpθ(at∣st)p(st+1∣st,at)\begin{aligned} p_\theta \left( \tau \right) &= p\left( s_1 \right) p_\theta \left( a_1 | s_1 \right) p\left( s_2|s_1,a_1 \right) p_\theta \left( a_2 | s_2 \right)\cdots \\ &= p\left( s_1 \right) \prod_{t=1}^T p_\theta \left( a_t | s_t \right) p\left( s_{t+1}|s_t,a_t \right) \end{aligned}

p(st+1∣st,at)p\left( s_{t+1}|s_t,a_t \right)代表的是环境，通常我们无法控制环境，因为环境是设定好的。我们能控制的是pθ(at∣st)p_\theta \left( a_t | s_t \right)

我们把轨迹所有的奖励rr都加起来，就得到了R(τ)R\left( \tau \right)，其代表某一个轨迹τ\tau的奖励。我们要做的就是调整演员内部的参数θ\theta，使得R(τ)R\left( \tau \right)的值越大越好。但实际上R(τ)R\left( \tau \right)并不只是一个标量（scalar），它是一个随机变量。因为演员在同样的状态下采取的动作有随机性；环境产生的观测也有随机性的。我们能够计算的是R(τ)R\left( \tau \right)的期望值。我们可以根据θ\theta算出某一个轨迹R(τ)R\left( \tau \right)出现的概率，接下来计算τ\tau的总奖励。对所有τ\tau的总奖励使用出现的概率进行加权求和就是期望值

Eτ∼pθ(τ)[R(τ)]=∑τR(τ)pθ(τ)=Rˉθ\mathbb{E}_{\tau \sim p_{\theta}\left( \tau \right)} \left[ R\left( \tau \right) \right] = \sum_\tau R\left( \tau \right) p_\theta \left( \tau \right) = \bar{R}_\theta

因为我们要最大化期望奖励，所以可以使用梯度上升（gradient ascent）。我们先要计算期望奖励Rˉθ\bar{R}_\theta的梯度

∇Rˉθ=∑τR(τ)∇pθ(τ)\nabla \bar{R}_\theta = \sum_\tau R\left( \tau \right) \nabla p_\theta \left( \tau \right)

因为计算的是关于θ\theta的梯度，其中只有pθ(τ)p_\theta \left( \tau \right)与θ\theta有关，因此只对其计算梯度

一般地，根据对数函数f(x)=log⁡xf \left( x \right) = \log x的导数为1x\frac{1}{x}，可以将函数的梯度计算公式构造为

∇f(x)=f(x)∇f(x)f(x)=f(x)∇log⁡f(x)\nabla f \left( x \right) = f \left( x \right) \frac{\nabla f \left( x \right)}{f \left( x \right)} = f \left( x \right) \nabla \log f \left( x \right)

特别地，对于对∇pθ(τ)\nabla p_\theta \left( \tau \right)有

∇pθ(τ)=pθ(τ)∇log⁡pθ(τ)\nabla p_\theta \left( \tau \right) = p_\theta \left( \tau \right) \nabla \log p_\theta \left( \tau \right)

于是我们可以进一步计算期望奖励Rˉθ\bar{R}_\theta的梯度

∇Rˉθ=∑τR(τ)∇pθ(τ)=∑τR(τ)pθ(τ)∇log⁡pθ(τ)=Eτ∼pθ(τ)[R(τ)∇log⁡pθ(τ)]\begin{aligned} \nabla \bar{R}_\theta &= \sum_\tau R\left( \tau \right) \nabla p_\theta \left( \tau \right) \\ &= \sum_\tau R\left( \tau \right) p_\theta \left( \tau \right) \nabla \log p_\theta \left( \tau \right) \\ &= \mathbb{E}_{\tau \sim p_{\theta}\left( \tau \right)} \left[ R\left( \tau \right) \nabla \log p_\theta \left( \tau \right) \right] \end{aligned}

实际上期望值Eτ∼pθ(τ)[R(τ)∇log⁡pθ(τ)]\mathbb{E}_{\tau \sim p_{\theta}\left( \tau \right)} \left[ R\left( \tau \right) \nabla \log p_\theta \left( \tau \right) \right]无法计算，我们需要使用采样的方式来得到梯度的期望值

Eτ∼pθ(τ)[R(τ)∇log⁡pθ(τ)]≈1N∑n=1NR(τn)∇log⁡pθ(τn)\mathbb{E}_{\tau \sim p_{\theta}\left( \tau \right)} \left[ R\left( \tau \right) \nabla \log p_\theta \left( \tau \right) \right] \approx \frac{1}{N} \sum^N_{n=1} R\left( \tau^n \right) \nabla \log p_\theta \left( \tau^n \right)

∇log⁡pθ(τ)\nabla \log p_\theta \left( \tau \right)可以继续展开为

∇log⁡pθ(τ)=∇(log⁡p(s1)+∑t=1Tlog⁡pθ(at∣st)+∑t=1Tlog⁡pθ(st+1∣st,at))=∇log⁡p(s1)+∇∑t=1Tlog⁡pθ(at∣st)+∇∑t=1Tlog⁡p(st+1∣st,at)=∇∑t=1Tlog⁡pθ(at∣st)=∑t=1T∇log⁡pθ(at∣st)\begin{aligned} \nabla \log p_\theta \left( \tau \right) &= \nabla \left( \log p\left( s_1 \right) + \sum^T_{t=1} \log p_{\theta} \left( a_t | s_t \right) + \sum^T_{t=1} \log p_{\theta} \left( s_{t+1} | s_t , a_t \right)\right) \\ &= \nabla \log p\left( s_1 \right) + \nabla\sum^T_{t=1} \log p_{\theta} \left( a_t | s_t \right) + \nabla \sum^T_{t=1} \log p \left( s_{t+1} | s_t , a_t \right)\\ &= \nabla\sum^T_{t=1} \log p_{\theta} \left( a_t | s_t \right)\\ &= \sum^T_{t=1} \nabla \log p_{\theta} \left( a_t | s_t \right) \end{aligned}

因为p(s1)p\left( s_1 \right)和p(st+1∣st,at)p \left( s_{t+1} | s_t , a_t \right)由环境决定，因此对θ\theta的梯度为0

最终，期望的梯度公式可以写为

∇Rˉθ=∑τR(τ)∇pθ(τ)=∑τR(τ)pθ(τ)∇log⁡pθ(τ)=Eτ∼pθ(τ)[R(τ)∇log⁡pθ(τ)]≈1N∑n=1NR(τn)∇log⁡pθ(τn)=1N∑n=1N∑t=1TnR(τn)∇log⁡pθ(atn∣stn)\begin{aligned} \nabla \bar{R}_\theta &= \sum_\tau R\left( \tau \right) \nabla p_\theta \left( \tau \right) \\ &= \sum_\tau R\left( \tau \right) p_\theta \left( \tau \right) \nabla \log p_\theta \left( \tau \right) \\ &= \mathbb{E}_{\tau \sim p_{\theta}\left( \tau \right)} \left[ R\left( \tau \right) \nabla \log p_\theta \left( \tau \right) \right] \\ &\approx \frac{1}{N} \sum^N_{n=1} R\left( \tau^n \right) \nabla \log p_\theta \left( \tau^n \right) \\ &= \frac{1}{N} \sum^N_{n=1} \sum^{T_n}_{t=1} R\left( \tau^n \right) \nabla \log p_{\theta} \left( a^n_t | s^n_t \right) \end{aligned}

直观理解为：能够使获得的期望增大的参数变化方向（期望的梯度）与最终的奖励和使对应状态-动作对出现的概率增大的参数变化方向（策略的梯度）有关。即我们在sts_t执行ata_t，最终的奖励为正，我们就要增加在sts_t执行ata_t的概率

关键点如下

  1. ∇pθ(τ)\nabla p_\theta \left( \tau \right)无法计算，需要将求梯度操作变换到pθ(at∣st)p_\theta \left( a_t | s_t \right)即神经网络函数上去

  2. 通过引入log运算，将pθ(τ)p_\theta \left( \tau \right)展开后的乘法变为加法

  3. 通过求期望操作来消除式中的pθ(τ)p_\theta \left( \tau \right)，并使用采样的方式来计算期望值

我们在得到期望的梯度公式后可以使用梯度上升来更新参数，使得期望值最大。参数更新公式如下

θ→θ+η∇Rˉθ\theta \rightarrow \theta + \eta \nabla \bar{R}_{\theta}

η\eta为学习率，需要要调整，可用Adam、RMSProp等方法来调整学习率

整个过程为

  1. 我们要用参数为θ\theta的智能体与环境多次交互，将交互的数据记录下来
  2. 遍历交互数据中的每一个ss与aa的对，求对数概率（log probability），然后取梯度并在前面乘上奖励，对每个结果求和并取平均值
  3. 使用梯度上升来更新参数

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

我们可以把强化学习想成一个分类问题，这个分类问题就是输入一个图像，输出某个类。在一般的分类问题里面，我们在实现分类的时候，目标函数都会写成最小化交叉熵（cross entropy），最小化交叉熵就是最大化对数似然（log likelihood）。强化学习与分类问题唯一不同的地方是损失前面乘一个权重————整场游戏得到的总奖励R(τ)R\left( \tau \right)

2. 策略梯度实现技巧

2.1 添加基线

第一个技巧：添加基线（baseline）。但在很多情况下面，奖励总是正的，最低都是 0。假设我们在某一个状态有3个动作，虽然奖励总是正，参数的更新方向总是使得概率提高，但是获得的奖励不同导致权重不同，概率提高便有大有小。所以提高少的，在做完归一化（normalize）以后，动作出现的概率就是下降的；提高多的，该动作的概率才会上升

这是一个理想的情况，但是实际上，我们是在做采样，所以有一些动作可能从来都没有被采样到。其他动作的奖励都是正的，这些动作的奖励为0，经过归一化后概率就会下降。因此我们希望奖励不总是正的

我们可以把奖励减bb，即

∇Rˉθ=1N∑n=1N∑t=1Tn(R(τn)−b)∇log⁡pθ(atn∣stn)\nabla \bar{R}_\theta = \frac{1}{N} \sum^N_{n=1} \sum^{T_n}_{t=1} \left( R\left( \tau^n \right) - b \right) \nabla \log p_{\theta} \left( a^n_t | s^n_t \right)

其中，bb称为基线。这样就可以让R(τn)−bR\left( \tau^n \right) - b有正有负，如果R(τn)>bR\left( \tau^n \right) > b，那么状态-动作对概率上升；反之亦然。

2. 策略梯度的推导

策略梯度算法的推导过程如下

\begin{aligned} \end{aligned}