文档维护:Arvin

网页部署:Arvin

策略梯度算法

原理

强化学习由三部分组成:智能体环境奖励函数。**策略梯度(Policy Gradient)**模型是强化学习中的一个经典模型。它用来在某种环境下训练智能体。

智能体是在环境中实施行为的实体。它与环境的交互如下图所示。首先一个episode开始,环境初始化后将释放出一个状态信息s1s1,依据该信息做思考和决策,得到行为a1a_1。环境再根据智能体的行为a1a_1,释放信息s2s_2。智能体观测到状态信息s2s_2,经过自身决策得到行为a2a_2。该过程一直持续下去,直到该episode结束。

1

采用数学方式描述上述过程:

假设在一个episode中,智能体与坏境交互所产生的状态信息ss和行为aa形成一个集合,称为迹。

τ={s1,a1, s2,a2,,sTn,aTn}\tau=\left\{\mathrm{s}_{1}, \mathrm{a}_{1}, \mathrm{~s}_{2}, \mathrm{a}_{2}, \ldots, \mathrm{s}_{\mathrm{T}_{\mathrm{n}}}, \mathrm{a}_{\mathrm{T}_{\mathrm{n}}}\right\}

对于某一个迹而言,其发生的可能性可以表示为一系列条件概率的乘积。

pθ(τ)=p(s1)pθ(a1s1)p(s2s1,a1)pθ(a2s2)p(s3s2,a2)=p(s1)t=1Tpθ(atst)p(st+1st,at)\begin{array}{l} p_{\theta}(\tau) \\ =p\left(s_{1}\right) p_{\theta}\left(a_{1} \mid s_{1}\right) p\left(s_{2} \mid s_{1}, a_{1}\right) p_{\theta}\left(a_{2} \mid s_{2}\right) p\left(s_{3} \mid s_{2}, a_{2}\right) \ldots \\ =p\left(s_{1}\right) \prod_{t=1}^{T} p_{\theta}\left(a_{t} \mid s_{t}\right) p\left(s_{t+1} \mid s_{t}, a_{t}\right) \end{array}

先计算环境输出s1s_1的概率p(s1)p(s_1),在计算根据s1s_1执行a1a_1的概率pθ(a1s1)p_{\theta}(a_{1}|s_{1})pθ(a1s1)p_{\theta}(a_{1}|s_{1})是由智能体决策参数θ\theta(也可以当作智能体自己神经网路中的权重)所决定的。策略网络的输出是一个分布,演员根据这个分布进行采样,决定实际要采取的动作。接下来环境根据a1a_1s1s_1产生s2s_2,这样循环下去直到这个episode结束。总结一下就是,p(st+1st,at)p(s_{t+1}|s_{t}, a_{t})代表的是环境,因为环境是设定好的,所以通常我们无法控制环境,我们可以控制的是pθ(atst)p_{\theta}(a_{t}|s_{t})。给定一个sts_t,智能体要采取的ata_t取决于智能体的参数θ\theta,所以我们可以通过更改θ\theta(其实就是更改策略)来控制智能体的动作。智能体的动作不同,每个同样的轨迹就有不同的出现的概率。

除了环境和智能体以外,还有奖励函数,可以用它来衡量采取动作的好坏,而动作是由策略决定的,所以可以用奖励函数来衡量策略。采取不同的动作会得到不同的奖励分数,每个迹对应不同的奖励和R(τ)R(\tau),代表某一个轨迹τ\tau的奖励。所以我们可以将目标描述为训练智能体使其最大化在各个迹上的期望奖励。

Rˉθ=τR(τ)pθ(τ)\bar{R}_{\theta}=\sum_{\tau} \mathrm{R}(\tau) \mathrm{p}_{\theta}(\tau)

2

我们要穷举所有可能的轨迹τ\tau,每一条轨迹τ\tau都有一个概率。比如θ\theta对应的模型很强,如果有一个回合θ\theta很快就死掉了,因为这种情况很少会发生,所以该回合对应的轨迹τ\tau的概率就会很小;如果有一个回合θ\theta一直没死,因为这种情况很可能发生,所以该回合对应的轨迹τ\tau的概率就会很大。我们可以根据θ\theta算出某一条轨迹τ\tau出现的概率,接下来计算τ\tau的总奖励。总奖励使用τ\tau出现的概率进行加权,对所有的τ\tau进行求和就是期望值。给定一个参数,我们可以计算期望值为:

Rθ=τR(τ)pθ(τ)=Eτpθ(τ)[R(τ)]\overline{\mathrm{R}}_{\theta}=\sum_{\tau} \mathrm{R}(\tau) \mathrm{p}_{\theta}(\tau)=\mathrm{E}_{\tau \sim \mathrm{p}_{\theta}(\tau)}[\mathrm{R}(\tau)]

我们要最大化期望奖励,可以使用**梯度上升(gradient ascent)**来最大化期望奖励。我们先计算梯度:

Rˉθ=τR(τ)pθ(τ)=τR(τ)pθ(τ)logpθ(τ)\nabla \bar{R}_{\theta}=\sum_{\tau} \mathrm{R}(\tau) \nabla \mathrm{p}_{\theta}(\tau)=\sum_{\tau} \mathrm{R}(\tau) \mathrm{p}_{\theta}(\tau) \nabla \log \mathrm{p}_{\theta}(\tau)

如下式所示,我们对τ\tau进行求和,把R(τ)R({\tau})logpθ(τ)\log p_{\theta}({\tau})这两项使用pθ(τ)p_{\theta}({\tau})进行加权,既然使用pθ(τ)p_{\theta}({\tau})进行加权,它们就可以被写成期望的形式。

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

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

Eτpθ(τ)[R(τ)logpθ(τ)]1Nn=1NR(τn)logpθ(τn)=1Nn=1Nt=1TnR(τn)logpθ(atnstn)\begin{aligned} \mathbb{E}_{\tau \sim p_{\theta}(\tau)}\left[R(\tau) \nabla \log p_{\theta}(\tau)\right] & \approx \frac{1}{N} \sum_{n=1}^{N} R\left(\tau^{n}\right) \nabla \log p_{\theta}\left(\tau^{n}\right) \\ &=\frac{1}{N} \sum_{n=1}^{N} \sum_{t=1}^{T_{n}} R\left(\tau^{n}\right) \nabla \log p_{\theta}\left(a_{t}^{n} \mid s_{t}^{n}\right) \end{aligned}

上式中logpθ(τ)\nabla \log p_{\theta}(\tau)的具体过程可以写为:

logpθ(τ)=(logp(s1)+t=1Tlogpθ(atst)+t=1Tlogp(st+1st,at))=logp(s1)+t=1Tlogpθ(atst)+t=1Tlogp(st+1st,at)=t=1Tlogpθ(atst)=t=1Tlogpθ(atst)\begin{aligned} \nabla \log p_{\theta}(\tau) &=\nabla\left(\log p\left(s_{1}\right)+\sum_{t=1}^{T} \log p_{\theta}\left(a_{t} \mid s_{t}\right)+\sum_{t=1}^{T} \log p\left(s_{t+1} \mid s_{t}, a_{t}\right)\right) \\ &=\nabla \log p\left(s_{1}\right)+\nabla \sum_{t=1}^{T} \log p_{\theta}\left(a_{t} \mid s_{t}\right)+\nabla \sum_{t=1}^{T} \log p\left(s_{t+1} \mid s_{t}, a_{t}\right) \\ &=\nabla \sum_{t=1}^{T} \log p_{\theta}\left(a_{t} \mid s_{t}\right) \\ &=\sum_{t=1}^{T} \nabla \log p_{\theta}\left(a_{t} \mid s_{t}\right) \end{aligned}

注意,p(s1)p(s_{1})p(st+1st,at)p(s_{t+1}|s_{t}, a_{t})来自环境,pθ(atst)p_{\theta}(a_{t}|s_{t})来自智能体。p(s1)p(s_{1})p(st+1st,at)p(s_{t+1}|s_{t}, a_{t})由环境决定,与θ\theta无关,因此logp(s1)=0\nabla \log p\left(s_{1}\right) = 0以及t=1Tlogp(st+1st,at)=0\nabla \sum_{t=1}^{T} \log p\left(s_{t+1} \mid s_{t}, a_{t}\right) = 0

Rˉθ=τR(τ)pθ(τ)=τR(τ)pθ(τ)pθ(τ)pθ(τ)=τR(τ)pθ(τ)logpθ(τ)=Eτpθ(τ)[R(τ)logpθ(τ)]1Nn=1NR(τn)logpθ(τn)=1Nn=1Nt=1TnR(τn)logpθ(atnstn)\begin{aligned} \nabla \bar{R}_{\theta} &=\sum_{\tau} R(\tau) \nabla p_{\theta}(\tau) \\ &=\sum_{\tau} R(\tau) p_{\theta}(\tau) \frac{\nabla p_{\theta}(\tau)}{p_{\theta}(\tau)} \\ &=\sum_{\tau} R(\tau) p_{\theta}(\tau) \nabla \log p_{\theta}(\tau) \\ &=\mathbb{E}_{\tau \sim p_{\theta}(\tau)}\left[R(\tau) \nabla \log p_{\theta}(\tau)\right] \\ & \approx \frac{1}{N} \sum_{n=1}^{N} R\left(\tau^{n}\right) \nabla \log p_{\theta}\left(\tau^{n}\right) \\ &=\frac{1}{N} \sum_{n=1}^{N} \sum_{t=1}^{T_{n}} R\left(\tau^{n}\right) \nabla \log p_{\theta}\left(a_{t}^{n} \mid s_{t}^{n}\right) \end{aligned}

我们可以直观的理解上式,也就是在采样到的数据中,采样到在某一个状态sts_t要执行某一个动作ata_t(st,at)(s_{t}, a_{t})是在整条轨迹τ\tau的某一个状态和动作的对。假设我们要在sts_t执行ata_t,最后发现τ\tau是的奖励正的,就要增加在sts_t执行ata_t的概率。反之,则相反。那这怎么实现呢?我们用梯度上升来更新参数,原来有一个参数θ\theta,把θ\theta加上梯度Rˉθ\nabla \bar{R}_{\theta},当然要有一个学习率η\eta,即

θθ+ηRˉθ\theta \leftarrow \theta+\eta \nabla \bar{R}_{\theta}

总结一下就是,我们通过采样,把采样大的数据代入梯度求导。也就是把每一个ssaa的对拿出来,计算再某个状态下采取某个动作的对数概率logpθ(atnstn)\log p_{\theta}(a_{t}^{n}|s_{t}^{n})。对这个概率求梯度,在梯度前面乘一个权重,权重就是这场游戏的奖励。计算出梯度后,就可以根据上面那个式子更新策略参数θ\theta。流程如下图所示:

3

实现技巧

添加baseline

如果给定状态ss采取动作aa,整场游戏得到正的奖励,就要增加(s,a)(s, a)的概率。如果给定状态s执行动作aa,整场游戏得到负的奖励,就要减小(s,a)(s, a)的概率。但是在实际的场景中,有时候R(τ)R(\tau)总是正的,如果按照上面的策略梯度计算公式,那么不管什么动作,训练都是提高该动作的发生的频率,显然是不合理的。因此,我们一般会对奖励做归一化。但是,有些时候部分动作不会被采样到,如下图中的a。那么他的概率就不会提高,反而会下降。因此我们希望不同动作的奖励并不总是正的,希望他们有正有负。

4

5

为了实现有正有负,我们可以让奖励值减去b。这样便可以得到有正有负的权重。

Rθ1 Nn=1Nt=1Tn[(t=tTnrtnb)logPθ(atnstn)]\overline{\mathrm{R}}_{\theta} \approx \frac{1}{\mathrm{~N}} \sum_{\mathrm{n}=1}^{\mathrm{N}} \sum_{\mathrm{t}=1}^{\mathrm{T}_{\mathrm{n}}}\left[\left(\sum_{\mathrm{t}^{\prime}=\mathrm{t}}^{\mathrm{T}_{\mathrm{n}}} \mathrm{r}_{\mathrm{t}^{\prime}}^{\mathrm{n}}-{b}\right) \nabla \log \mathrm{P}_{\theta}\left(\mathrm{a}_{\mathrm{t}}^{\mathrm{n}} \mid \mathrm{s}_{\mathrm{t}}^{\mathrm{n}}\right)\right]

分配合适的权重

在前面的讲述中,对不同的状态-动作对概率梯度都用全局奖励值,都是用全局的奖励值作为它的权重进行更新。显然是不合理的。因为一个回合中,有些动作是好的,有些动作是坏的,但是最终的奖励不大,难道我们就放弃前面这个好动作的经验吗?

因此我们希望可以给每一个不同的动作前面都乘上不同的权重。每一个动作的不同权重反映了每一个动作到底是好的还是不好的。当前的状态执行的动作并不会对之前的状态产生影响。

所以我们计算某个状态-动作对的奖励的时候,不把整场游戏得到的奖励全部加起来,而是只计算从这个动作执行以后得到的奖励。只有从这个动作之后得到的奖励才能代表这个动作是否是坏。

此外,我们在计算奖励时,考虑tt时刻的动作对未来的影响大小,引入一个折扣因子$ \gamma$。因此,带有BaseLine的策略梯度公式就可以进一步表示为:

Rθ1 Nn=1Nt=1Tn[(t=tTnγttrtnb)logPθ(atnstn)]\overline{\mathrm{R}}_{\theta} \approx \frac{1}{\mathrm{~N}} \sum_{\mathrm{n}=1}^{\mathrm{N}} \sum_{\mathrm{t}=1}^{\mathrm{T}_{\mathrm{n}}}\left[\left(\sum_{\mathrm{t}^{\prime}=\mathrm{t}}^{\mathrm{T}_{\mathrm{n}}} {\gamma }^{\mathrm{t}^{\prime}-\mathrm{t}} \mathrm{r}_{\mathrm{t}^{\prime}}^{\mathrm{n}}-{b}\right) \nabla \log \mathrm{P}_{\theta}\left(\mathrm{a}_{\mathrm{t}}^{\mathrm{n}} \mid \mathrm{s}_{\mathrm{t}}^{\mathrm{n}}\right)\right]

实际上就是这么实现的。bb 可以是依赖状态(state-dependent)的,事实上 bb 通常是一个网络估计出来的,它是一个网络的输出。我们把 RbR-b 这一项称为优势函数(advantage function), 用 Aθ(st,at)A^{\theta}(s_t,a_t) 来代表优势函数。优势函数取决于 ssaa,我们就是要计算在某个状态 ss 采取某个动作 aa 的时候,优势函数的值。在计算优势函数值时,我们要计算 t=tTnrtn\sum_{t^{\prime}=t}^{T_{n}} r_{t^{\prime}}^{n},需要有一个模型与环境交互,才能知道接下来得到的奖励。优势函数 Aθ(st,at)A^{\theta}\left(s_{t}, a_{t}\right) 的上标是 θ\thetaθ\theta 代表用模型 θ\theta 与环境交互。从时刻 tt 开始到游戏结束为止,所有 rr 的加和减去 bb,这就是优势函数。优势函数的意义是,假设我们在某一个状态sts_t 执行某一个动作 ata_t,相较于其他可能的动作,ata_t有多好。优势函数在意的不是绝对的好,而是相对的好,即相对优势(relative advantage)。因为在优势函数中,我们会减去一个基线 bb,所以这个动作是相对的好,不是绝对的好。 Aθ(st,at)A^{\theta}\left(s_{t}, a_{t}\right) 通常可以由一个网络估计出来,这个网络称为评论员(critic)。

REINFORCE:蒙特卡洛策略梯度

蒙特卡洛方法可以理解为算法完成一个回合之后,再利用这个回合的数据去学习,做一次更新。因为我们已经获得了整个回合的数据,所以也能够获得每一个步骤的奖励,我们可以很方便地计算每个步骤的未来总奖励,即回报 GtG_tGtG_t 是未来总奖励,代表从这个步骤开始,我们能获得的奖励之和。G1G_1代表我们从第一步开始,往后能够获得的总奖励。G2G_2 代表从第二步开始,往后能够获得的总奖励。

相比蒙特卡洛方法一个回合更新一次,时序差分方法是每个步骤更新一次,即每走一步,更新一次,时序差分方法的更新频率更高。时序差分方法使用Q函数来近似地表示未来总奖励 GtG_t

6

介绍一下策略梯度中最简单的也是最经典的一个算法REINFORCE。REINFORCE 用的是回合更新的方式,它在代码上的处理上是先获取每个步骤的奖励,然后计算每个步骤的未来总奖励 GtG_t,将每个 GtG_t 代入:

Rˉθ1Nn=1Nt=1TnGtnlogπθ(atnstn)\nabla \bar{R}_{\theta} \approx \frac{1}{N} \sum_{n=1}^{N} \sum_{t=1}^{T_{n}} G_{t}^{n} \nabla \log \pi_{\theta}\left(a_{t}^{n} \mid s_{t}^{n}\right)

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

Gt=k=t+1Tγkt1rk=rt+1+γGt+1(4.8)\begin{aligned} G_{t} &=\sum_{k=t+1}^{T} \gamma^{k-t-1} r_{k} \\ &=r_{t+1}+\gamma G_{t+1} \end{aligned} \tag{4.8}

7

参考链接:

策略梯度