强化学习简介（五）：策略梯度Policy Gradient

DQN证明了深度学习在增强学习中的可行性。深度学习可以将复杂的概念隐含在网络之中。但是DQN并没有将所有的概念都隐含在网络之中，只是把Q值的计算放在了网络之中，比如${\displaystyle \epsilon -greedy}$动作选择策略。因为如何选择动作和如何通过Q值计算出目标值，都是DQN所面临的问题，而Q值的目的也是为了选择动作。我们可以将增加学习的问题简化为选择动作的问题。那么我们可否使用深度学习直接做出动作选择呢？显然，我们可以定义一个网络${\displaystyle {\pi }_{\theta }}$，其中输入为状态${\displaystyle s}$，输出为每个动作${\displaystyle a}$的概率。

因为这个网络与策略函数的定义一样，所以被称为策略网络。${\displaystyle {\pi }_{\theta }\left(a\mid s\right)}$，表示在${\displaystyle s}$状态下选择动作${\displaystyle a}$的概率。只要这个网络能够收敛，我们就可以直接得到最佳策略。这个网络的奖励函数也就是最终游戏的总奖励。

${\displaystyle J\left(\theta \right)=\sum _{s\in S}{d}^{\pi }\left(s\right)V^{\pi }\left(s\right)=\sum _{s\in S}{d}^{\pi }\left(s\right)\sum _{a\in A}{\pi }_{\theta }\left(a\mid s\right)Q^{\pi }(s,a)}$

${\displaystyle d^{\pi }\left(s\right)}$指状态${\displaystyle s}$在马尔科夫链上的稳定分布，${\displaystyle d^{\pi }\left(s\right)=\underset{t\to \infty }{lim}P(s_t=s\mid s_0,{\pi }_{\theta })}$。

但是这个表达式看上去是不可能计算的，因为状态的分布和Q值都是随着策略的更新而不断变化的。但是我们并不需要计算${\displaystyle J\left(\theta \right)}$，在梯度下降法中我们只需要计算梯度${\displaystyle {\nabla }_{\theta }J\left(\theta \right)}$即可

${\displaystyle {\nabla }_{\theta }{V}^{\pi }\left(s\right)}$
${\displaystyle ={\nabla }_{\theta }\left(\sum _{a\in A}{\pi }_{\theta }\left(a\mid s\right)Q^{\pi }(s,a)\right)}$
根据导数乘法规则
${\displaystyle =\sum _{a\in A}({\nabla }_{\theta }{\pi }_{\theta }{Q}^{\pi }(s,a)+{\pi }_{\theta }\left(a\mid s\right){\nabla }_{\theta }{Q}^{\pi }(s,a))}$
展开${\displaystyle Q^{\pi }(s,a)}$为各各种可能的下一状态奖励之和
${\displaystyle =\sum _{a\in A}({\nabla }_{\theta }{\pi }_{\theta }{Q}^{\pi }(s,a)+{\pi }_{\theta }\left(a\mid s\right){\nabla }_{\theta }\sum _{s’,r}P(s’,r\mid s,a)(r+V^{\pi }(s’)))}$
而其中状态转移函数${\displaystyle P(s’,r\mid s,a)}$、奖励${\displaystyle r}$由环境决定，与${\displaystyle {\nabla }_{\theta }}$无关，所以
${\displaystyle =\sum _{a\in A}({\nabla }_{\theta }{\pi }_{\theta }{Q}^{\pi }(s,a)+{\pi }_{\theta }\left(a\mid s\right)\sum _{s’,r}P(s’,r\mid s,a){\nabla }_{\theta }{V}^{\pi }(s’))}$
${\displaystyle =\sum _{a\in A}({\nabla }_{\theta }{\pi }_{\theta }{Q}^{\pi }(s,a)+{\pi }_{\theta }\left(a\mid s\right)\sum _{s’}P(s’\mid s,a){\nabla }_{\theta }{V}^{\pi }(s’))}$

现在我们有了一个形式非常好的递归表达式：
${\displaystyle {\nabla }_{\theta }{V}^{\pi }\left(s\right)=\sum _{a\in A}({\nabla }_{\theta }{\pi }_{\theta }{Q}^{\pi }(s,a)+{\pi }_{\theta }\left(a\mid s\right)\sum _{s’}P(s’\mid s,a){\nabla }_{\theta }{V}^{\pi }(s’))}$

设 ${\displaystyle {\rho }^{\pi }(s\to x,k)}$ 表示在策略${\displaystyle {\pi }^{\theta }}$下，${\displaystyle k}$步以后状态${\displaystyle s}$转移到状态${\displaystyle x}$的概率。有：

• ${\displaystyle {\rho }^{\pi }(s\to s,k=0)=1}$
• ${\displaystyle {\rho }^{\pi }(s\to s’,k=1)=\sum _a{\pi }_{\theta }\left(a\mid s\right)P(s’\mid s,a)}$
• ${\displaystyle {\rho }^{\pi }(s\to x,k+1)=\sum _{s’}{\rho }^{\pi }(s\to s’,k){\rho }^{\pi }(s’\to x,1)}$

为了简化计算，令 ${\displaystyle \varphi \left(s\right)=\sum _{a\in A}{\nabla }_{\theta }{\pi }_{\theta }\left(a\mid s\right)Q^{\pi }(s,a)}$

${\displaystyle {\nabla }_{\theta }{V}^{\pi }\left(s\right)}$
${\displaystyle =\varphi \left(s\right)+\sum _{a\in A}{\pi }_{\theta }\left(a\mid s\right)\sum _{s’}P(s’\mid s,a){\nabla }_{\theta }{V}^{\pi }(s’)}$
${\displaystyle =\varphi \left(s\right)+\sum _{s’}\sum _{a\in A}{\pi }_{\theta }\left(a\mid s\right)P(s’\mid s,a){\nabla }_{\theta }{V}^{\pi }(s’)}$
${\displaystyle =\varphi \left(s\right)+\sum _{s’}{\rho }^{\pi }(s\to s’,1){\nabla }_{\theta }{V}^{\pi }(s’)}$
${\displaystyle =\varphi \left(s\right)+\sum _{s’}{\rho }^{\pi }(s\to s’,1)(\varphi (s’)+\sum _{s’’}{\rho }^{\pi }(s’\to s’’,1){\nabla }_{\theta }{V}^{\pi }(s’’))}$
${\displaystyle =\varphi \left(s\right)+\sum _{s’}{\rho }^{\pi }(s\to s’,1)\varphi (s’)+\sum _{s’’}{\rho }^{\pi }(s\to s’’,2){\nabla }_{\theta }{V}^{\pi }(s’’)}$
${\displaystyle =\varphi \left(s\right)+\sum _{s’}{\rho }^{\pi }(s\to s’,1)\varphi (s’)+\sum _{s’’}{\rho }^{\pi }(s\to s’’,2)\varphi (s’’)+\sum _{s’’’}{\rho }^{\pi }(s\to s’’’,3){\nabla }_{\theta }{V}^{\pi }(s’’’)}$
${\displaystyle =\dots }$
${\displaystyle =\sum _{x\in S}\sum _{k=0}^{\infty }{\rho }^{\pi }(s\to x,k)\varphi \left(x\right)}$

令 ${\displaystyle \eta \left(s\right)=\sum _{k=0}^{\infty }{\rho }^{\pi }(s_0\to s,k)}$

${\displaystyle {\nabla }_{\theta }J\left(\theta \right)={\nabla }_{\theta }{V}^{\pi }\left(s_0\right)}$
${\displaystyle =\sum _s\sum _{k=0}^{\infty }{\rho }^{\pi }(s_0\to s,k)\varphi \left(s\right)}$
${\displaystyle =\sum _s\eta \left(s\right)\varphi \left(s\right)}$
${\displaystyle =\left(\sum _s\eta \left(s\right)\right)\sum _s\left(\frac{\eta \left(s\right)}{\sum _s\eta \left(s\right)}\right)\varphi \left(s\right)}$
因 ${\displaystyle \sum _s\eta \left(s\right)}$ 属于常数，对于求梯度而言常数可以忽略。
${\displaystyle \propto \sum _s\left(\frac{\eta \left(s\right)}{\sum _s\eta \left(s\right)}\right)\varphi \left(s\right)}$
因 ${\displaystyle \eta \frac{s}{\sum _s\eta \left(s\right)}}$表示${\displaystyle s}$的稳定分布
${\displaystyle =\sum _s{d}^{\pi }\left(s\right)\sum _a{\nabla }_{\theta }{\pi }_{\theta }\left(a\mid s\right)Q^{\pi }(s,a)}$
${\displaystyle =\sum _s{d}^{\pi }\left(s\right)\sum _a{\pi }_{\theta }\left(a\mid s\right)Q^{\pi }(s,a)\frac{{\nabla }_{\theta }{\pi }_{\theta }\left(a\mid s\right)}{{\pi }_{\theta }\left(a\mid s\right)}}$
因 ${\displaystyle \left(\ln x\right)’=\frac{1}{x}}$
${\displaystyle =Er{r}_{\pi }\left[Q^{\pi }(s,a){\nabla }_{\theta }{\ln \pi }_{\theta }\left(a\mid s\right)\right]}$

所以得出策略梯度最重要的定理：

${\displaystyle {\nabla }_{\theta }J\left(\theta \right)=Er{r}_{\pi }\left[Q^{\pi }(s,a){\nabla }_{\theta }{\ln \pi }_{\theta }\left(a\mid s\right)\right]}$

其中的${\displaystyle Q^{\pi }(s,a)}$也就是状态s的累计收益，可以在一次完整的动作轨迹中累计计算得出。

算法描述

该算法被称为 REINFORCE

• 随机初始化${\displaystyle \theta }$
• 生成一个完整的策略${\displaystyle {\pi }_{\theta }}$的轨迹: ${\displaystyle S1,A1,R2,S2,A2,\dots ,ST}$。
• For t=1, 2, … , T-1:
  • ${\displaystyle v_t=\sum _{i=0}^{\infty }{\gamma }^i{R}_{t+i+1}}$
  • ${\displaystyle \theta \leftarrow \theta +\alpha v_t{\ln \pi }_{\theta }\left(A_t\mid S_t\right)}$

参考：
Lilian Weng:Policy Gradient Algorithms