策略梯度(Policy Gradient)

对于DQN来说使用一个网络直接逼近了值函数，最后取得了非常不错的效果, 但是对于一些连续性控制或者动作空间特别大的环境来说，很难全部计算所有的值函数来得到最好的策略，那么直接计算策略的方法就别提出来了。

1 策略梯度理论

在Value Based的方法中，我们迭代计算的是值函数，然后根据值函数对策略进行改进；而在Policy Based方法中，我们直接对策略 ({pi _ heta }left( {a|s} ight)) 进行迭代计算，直到累积回报的期望最大，此时的参数所对应的策略为最优策略。

下图来自周博磊老师的课件(^{[2]})，左边就是基于策略的方法，可以看出每到一个地方(state)就会得到一个方向(action)。右边是基于值得方法，当到一个地方时，需要计算一下周围哪个地方的值函数更大，就会往那走。

下面用 ( au) 来表示一个轨迹：( au = {s_0},{a_0},{s_1},{a_1} ldots {s_T}). 对于给定策略，智能体和环境进行一次轨迹为 ( au) 的交互，收到的总回报为：

[Gleft( au ight) = sumlimits_{t = 0}^{T - 1} {{gamma ^t}{r_{t + 1}}} ag{1-1} ]

由于策略和状态转移都有一定的个随机性，所以每次的轨迹也是随机的，我们希望基于策略的方法能够学习到一个最佳策略 (pi _ heta^{*} left( {a|s} ight)) 来最大化这个总回报的期望：

[egin{aligned} Jleft( heta ight) &= {mathbb{E}_{ au sim{p_ heta }left( au ight)}}left[ {Gleft( au ight)} ight]\ &= int {{p_ heta }left( au ight)} Gleft( au ight)d au end{aligned} ag{1-2} ]

对这个目标函数 (Jleft( heta ight)) 求关于参数 ( heta) 的偏导为：

[egin{aligned} abla Jleft( heta ight) &=frac{partial}{partial heta} int p_{ heta}( au) G( au) mathrm{d} au \ &=intleft(frac{partial}{partial heta} p_{ heta}( au) ight) G( au) mathrm{d} au \ &=int p_{ heta}( au)left(frac{1}{p_{ heta}( au)} frac{partial}{partial heta} p_{ heta}( au) ight) G( au) mathrm{d} au \ &=int p_{ heta}( au)left(frac{partial}{partial heta} log p_{ heta}( au) ight) G( au) mathrm{d} au \ &=mathbb{E}_{ au sim p_{ heta}( au)}left[ abla log p_{ heta}( au) G( au) ight] end{aligned} ag{1-3} ]

进一步求解 ( abla log p_{ heta}( au)) 可得：

[egin{aligned} abla & log p_{ heta}( au)=frac{partial}{partial heta} log left(pleft(s_{0} ight) prod_{t=0}^{T-1} pi_{ heta}left(a_{t} | s_{t} ight) pleft(s_{t+1} | s_{t}, a_{t} ight) ight) \ &=frac{partial}{partial heta}left(log pleft(s_{0} ight)+sum_{t=0}^{T-1} log pi_{ heta}left(a_{t} | s_{t} ight)+sum_{t=0}^{T-1} log pleft(s_{t+1} | s_{t}, a_{t} ight) ight) \ &=sum_{t=0}^{T-1} abla log pi_{ heta}left(a_{t} | s_{t} ight) end{aligned} ag{1-4} ]

可以看出 ( abla log p_{ heta}( au)) 只和策略函数 ({pi _ heta }left( {a|s} ight)) 相关，和状态转移概率 (pleft(s_{t+1} | s_{t}, a_{t} ight)) 无关。把式 (1-4) 带入 (1-3) 可得到：

[egin{aligned} abla {J}( heta) &=mathbb{E}_{ au sim p_{ heta}( au)}left[left(sum_{t=0}^{T-1} abla log pi_{ heta}left(a_{t} | s_{t} ight) ight) G( au) ight] \ &=mathbb{E}_{ au sim p_{ heta}( au)}left[left(sum_{t=0}^{T-1} abla log pi_{ heta}left(a_{t} | s_{t} ight) ight)left( sumlimits_{t = 0}^{T - 1} {{gamma ^t}{r_{t + 1}}} ight) ight] \ &=mathbb{E}_{ au sim p_{ heta}( au)}left[sum_{t=0}^{T-1}left( abla log pi_{ heta}left(a_{t} | s_{t} ight) gamma^{t} Gleft( au_{t: T} ight) ight) ight] end{aligned} ag{1-5} ]

这里定义 (Gleft( au_{t: T} ight)) 为把时刻 (t) 当成起始时刻收到的总回报：

[Gleft( au_{t: T} ight)=sum_{t^{prime}=t}^{T-1} gamma^{t^{prime}-t} r_{t^{prime}+1} ag{1-6} ]

公式 (1-5) 从第二步得到第三步也就是李宏毅课中(^{[3]})讲的Tip2，即时刻 (t) 之前的回报和时刻 (t) 之后的动作无关。这个在直觉上很好理解，今天老板看到你工作努力想给你奖赏，老板不会给你昨天的工资加倍，只会给你今天的工资或者未来的工资加倍。证明如下：

公式(1-5)证明

2 REINFORCE 算法

公式 (1-5) 中的 ( abla {J}( heta)) 是用期望表示的，期望可以通过采样的方法来近似。可以根据当前的策略 (pi _ heta) 通过游走采集多条轨迹 ({ au ^{left( { m{1}} ight)}},{ au ^{left( 2 ight)}}, ldots { au ^{left( N ight)}}). 其中一条轨迹 ${ au ^{left( n ight)}} = s_0^{left( n ight)},a_0^{left( n ight)},s_1^{left( n ight)},a_1^{left( n ight)}, ldots $ 所以 ( abla {J}( heta)) 可以写成：

[ abla {J}( heta) approx frac{1}{N} sum_{n=1}^{N}left(sum_{t=0}^{T-1} abla log pi_{ heta}left(a_{t}^{(n)} | s_{t}^{(n)} ight) gamma^{t} G^{(n)}left( au_{t: T} ight) ight) ag{2-1} ]

有了策略梯度的计算公式就可以更新梯度了：

[hat heta = heta + alpha abla Jleft( heta ight) ag{2-2} ]

邱锡鹏老师书上的具体的算法如下：

REINFORCE算法

可以看出其实是每采集一条轨迹，计算每个时刻的梯度就开始更新参数了

3 带基准线的 REINFORCE 算法

假如在状态 (s_t) 下有三个动作 (a,b,c)，其概率之和为1。如果执行这个动作后得到正的总回报 (Gleft( au ight))，则需要增大这个动作被选中的概率，如果得到负的总回报则减小其概率。

在理想情况下，三个动作都被采样到了，可以看出他们的总回报 (Gleft( au ight)) 全都是正的值。然而这三个动作的总概率为1，所以被选中的概率不能全都增大，肯定是有的增大有的减小。所以只能哪个动作得到的总回报更多，就让它的概率大一点。

然而在实际中，不可能采样到所有的动作，假如动作 (a) 没被采到，动作 (b,c) 得到的回报都是正的值。这样在下一个回合选中动作 (b,c) 的概率都会上升，而选中动作 (a) 的概率会下降。但这并不代表动作 (a) 一定不好，只是没有采样到。

Sampling the actions

解决办法：减去一个固定值 (b(s_t))，让各个动作对应的奖励有正有负。一个常用的选择是令 (b(s_t)) 为这个状态的值函数 ({V^{{pi _ heta }}}left( {{s_t}} ight)).

邱锡鹏老师的书上有证明(^{[1]})，虽然减去了一个和 (s_t) 相关的固定值，但是并没有影响 ( abla {J}( heta))，也就是说参数 ( heta) 更新的规则是不变的.

需要注意的两点是：

其实这个值函数 ({V^{{pi _ heta }}}left( {{s_t}} ight)) 是不知道的，可以用监督学习的办法来做，用学习得到的函数 ({V_phi }left( {{s_t}} ight)) 来近似表示 ({V^{{pi _ heta }}}left( {{s_t}} ight)) . 另外 (Loss function) 定义为：

[Lleft( phi ight) = {left( {{V^{{pi _ heta }}}left( {{s_t}} ight) - {V_phi }left( {{s_t}} ight)} ight)^2} ag{3-1} ]
问题又来了，上面 (Loss) 的定义需要用到值函数 ({V^{{pi _ heta }}}left( {{s_t}} ight))，但是我们又不知道值函数。先来看一下值函数的定义：

[V^{pi_{ heta}}left(s_{t} ight)=mathbb{E}left[Gleft( au_{t : T} ight) ight] ag{3-2} ]
实际上所采取的办法是用蒙特卡罗方法进行估计(用经验平均代替期望)，在算法执行的时候好像更简便，直接用一次采样代表期望了。

有了上面两点，就可以对学习的函数 ({V_phi }left( {{s_t}} ight)) 采用梯度下降法更新，参数 (phi) 的梯度为：

[frac{partial Lleft(phi | s_{t}, pi_{ heta} ight)}{partial phi}=-left(Gleft( au_{t: T} ight)-V_{phi}left(s_{t} ight) ight) frac{partial V_{phi}left(s_{t} ight)}{partial phi} ag{3-3} ]

有了这个基准线 ({V_phi }left( {{s_t}} ight)) 就可以把策略函数的梯度公式 (2-1) 改写为:

[ abla J( heta ) approx frac{1}{N}sumlimits_{n = 1}^N {sumlimits_{t = 0}^{T - 1} {left( {{gamma ^t}{G^{(n)}}left( {{ au _{t:T}}} ight) - {V_phi }left( {{s_t}} ight)} ight) abla } log {pi _ heta }left( {a_t^{(n)}|s_t^{(n)}} ight)} ag{3-4} ]

在上面的第二点中关于这个 (mathbb{E}left[Gleft( au_{t : T} ight) ight]) 的定义其实还有点疑问，邱锡鹏老师这个做法和李宏毅的做法不太一样，李宏毅是定义 ({Q^{{pi _ heta }}}left( {{s_t},{a_t}} ight) = mathbb{E}left[Gleft( au_{t : T} ight) ight]). 其实李宏毅课程中这么定义也是有道理的，因为这个 (Gleft( au_{t: T} ight)) 其实是总回报，他是来衡量在状态 (s_t) 执行动作 (a_t) 后得到的总奖励，然后来判定这个动作 (a_t) 好不好。所以说这个动作是执行过了，才能得到 (G). 这个定义在后面Actor-Critic还要用到，个人更偏向于李宏毅老师的定义。

(left{ egin{array}{l} {V^{{pi _ heta }}}left( {{s_t}} ight) = left[ {left. {Gleft( {{ au _{t:T}}} ight)} ight|{s_t}} ight]\ {Q^{{pi _ heta }}}left( {{s_t},{a_t}} ight) = left[ {left. {Gleft( {{ au _{t:T}}} ight)} ight|{s_t},{a_t}} ight] end{array} ight.)

下面来看一下具体的算法：

带基准线的REINFORCE算法