Policy Gradient Methods, DPG 和 D

作者: Junr_0926 | 来源:发表于2019-02-23 16:09 被阅读0次

1. 介绍

首先了解一下策略梯度法，之后再对DPG和DDPG两篇论文进行学习。

2. 梯度策略法

梯度策略法 ( Policy Gradient Methods ) 英文好的同学移步这里看原文。

增强学习的基础那一套这里就不说了，策略梯度允许我们直接通过参数对策略建模，并且通过reward来直接对策略进行更新，以最大化 $J$ ，也就是累积reward。

那么重点就是如果计算策略梯度(Policy Gradient)。

2.1 Finite-difference Methods

有限差分法。
算法如下：

FInite Difference

对策略参数 $\theta_i$ ，产生一个扰动 $\Delta \theta_i$ ，之后根据扰动后的策略参数得到一个estimates $\Delta \hat{J}_i \approx J(\theta_h + \Delta \theta_i) - J_{ref}$ 。这里的 $J_{ref}$ 是reference value，它有不同的选择。
那么policy gradient estimate $g_{FD}$ 就可以通过回归问题求解

Screen Shot 2019-02-22 at 10.33.18 PM.png

这里推导思路是：将estimate的策略梯度，也就是 $\Delta \hat{J}$ 作为回归中的 $y$ ，将 $J(\theta_h + \Delta \theta_i) - J_{ref}$ 进行泰勒一阶展开，这里选择 $J_{ref} = J(\theta_h)$ ，发现它等于真实梯度乘 $\Delta \theta$ 。那么问题就类似于线性回归，也就得到了上面的公式。

这个方法感觉简单，限制很少（捂脸），但是扰动的选择会是个问题。由于我对这个方法了解非常少，就不多说啦。

缺点：

扰动可能做不到
很难探索
对于随机系统，非常慢

2.2 Likelihood Ratio Methods 和 REINFORCE

这种方法是非常非常重要的。
公式如下：

REINFORCE

求期望可以通过采样来近似，重要的是 $\bigtriangledown_\theta log p_\theta(\tau)$ 的计算不需要分布的相关知识：

score function
这里就省去了转换函数的计算，也就不需要模型来对转换函数进行建模来。

然而如果我们使用的是确定性策略： $u = \pi (x)$ ，那么就需要计算：

Screen Shot 2019-02-22 at 11.28.38 PM.png

为了减少gradient estimator的variance，通常会加一个baseline。

算法如下：

REINFORCE

2.3 Natural Policy Gradients

我们在计算梯度的时候，通常是期望参数在梯度的方向，移动一小段距离。但是这个距离的度量，我们通常是在欧式空间下的。

然后，度量两个分布之间的相似性，有多种方式：KL divergence, Hellinger distance等。大多数的距离可以通过二阶泰勒展开进行近似：
例如：

Screen Shot 2019-02-22 at 11.49.52 PM.png

$F_\theta$ 是Fisher信息矩阵。

为了尽可能使得参数更新接近梯度，并且移动的距离满足一定的条件，可以优化下面问题：
$argmax_{\Delta \theta} \Delta \theta^T \bigtriangledown_\theta J$ , $s.t. \Delta \theta^T F_\theta \bigtriangledown \theta = \epsilon$
solution为：
$\Delta \theta \propto F_\theta^{-1} \bigtriangledown_\theta J$

我们可以这样解释natural gradient：选择参数的更新量，是的策略的分布的变化为一个定值。

Reference
https://www.ias.informatik.tu-darmstadt.de/uploads/Research/MPI2007/MPI2007peters.pdf
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.70.4294&rep=rep1&type=pdf
http://home.deib.polimi.it/restelli/MyWebSite/pdf/rl7.pdf

3. DPG 算法

论文链接

3.1 Policy gradient theorem

https://lilianweng.github.io/lil-log/2018/04/08/policy-gradient-algorithms.html

首先我们先给出policy gradient theorem。从前面我们已经知道了， $\bigtriangledown_\theta J$ 的计算取决于两个部分：一个是动作的选择，因为动作取决于 $\pi_\theta$ ，也就是策略（policy）；一个是状态转移函数： $p(x_{k+1}|x_k,u_k)$ ，因为它也间接地取决于策略。但是通常情况下，环境是未知的，所以我们无法求解。

但是policy gradient theorem告诉我们，梯度求解不需要知道环境信息：

Screen Shot 2019-02-23 at 9.37.07 AM.png

可以看到，求导只是对于 $\pi_\theta$ 。

3.2 证明

首先是reward函数的定义：

Screen Shot 2019-02-23 at 9.52.38 AM.png

$d^\pi(s) = lim_{t\rightarrow \infty} P(s_t=s|s_0, \pi_0)$

给出价值状态函数 $V$ 的导数：

Screen Shot 2019-02-23 at 9.58.07 AM.png

第一行通过展开价值函数
第二行通过乘积的求导法则
第三行是 $Q$ 的展开
第四行，reward不是 $\theta$ 的函数
第五行，将reward求和

所以我们得到了下面公式：

Screen Shot 2019-02-23 at 10.01.15 AM.png

红色部分显示了这是一种递归的形式。

用 $\phi(s)$ 表示求和的第一个部分，然后对第二部分进行展开。

Screen Shot 2019-02-23 at 10.38.59 AM.png

带入到reward function：

Screen Shot 2019-02-23 at 10.42.06 AM.png

这里 $\sum_s \eta (s)$ 是 1 ？表示任意状态开始，经历任意步数，到达任意状态？？

这里证明就结束了，进一步可以表示为：

Screen Shot 2019-02-23 at 10.48.03 AM.png

总结一下，Policy gradient theorem就说了一件事：策略梯度和状态分布无关。

3.3 DPG

回到我们的DPG算法，论文在背景介绍里提到了一些随机策略梯度的算法

Stochastic Actor-Critic Algorithms: 用一个critic函数来拟合 $Q^w(s,a) \approx Q^\pi(s,a)$ 。
Off-policy Actor-Critic: 通过 $\rho^\beta(s)$ 来修改 $V^\pi$ ，通常是使用behavior policy $\beta$ 来产生轨迹，也就是 $(s,a)$ ，使用critic来计算价值换上 $V^\pi(s)$ 。由于两个策略的不同，需要importance sample ratio。公式如下：

Screen Shot 2019-02-23 at 1.11.54 PM.png

3.4 确定性策略的梯度

Gradients of Deterministic Policies。
这里的策略不同于随机策略 $\pi$ ，采用的是确定性策略： $\mu^{k+1}(s) = argmax_a Q^{\mu^k}(s,a)$ 。在连续的动作，状态空间下，我们期望策略能够沿着 $Q$ 值的梯度运动，达到最大化的目的。也就是希望参数的变化量，正比于 $\triangledown_\theta Q^{\mu^k}(s,\mu_\theta(s))$ 。对于不同的状态，取平均即可，公式如下：

Screen Shot 2019-02-23 at 1.20.20 PM.png

用动作代替公式中的 $\mu_\theta(s)$ ，根据链式求导，得到下面公式：

Screen Shot 2019-02-23 at 1.21.56 PM.png

显然，它是策略对策略参数的导数，和Q对动作的导数的组合。通常来讲， $\triangledown_\theta \mu_\theta$ 是一个Jacobian矩阵，它的第 $d$ 列表示的是，第 $d$ 维的动作空间，对策略参数 $\theta$ 的导数。然而，策略的改变会导致期望里状态分布的改变，因此，我们无法认为，这个更新会改善策略。

3.5 Deterministic Policy Gradient Theorem

作者这里主要是证明了像随机策略梯度一样，确定性策略梯度也同样不需要计算状态分布的梯度。也就是下面公式：

Screen Shot 2019-02-23 at 1.37.16 PM.png

证明作者放在了附录里面，这里给出地址
http://proceedings.mlr.press/v32/silver14-supp.pdf

作者还证明了，在随机策略的方差趋近于零的时候，随机策略趋近于确定性策略，并且随机策略的梯度，趋近于确定性策略的梯度。

3.6 确定性策略梯度算法

在拥有了确定性策略梯度定理之后，作者给出了一些确定性actor-critic的算法。

On-policy Deterministic Actor-Critic：更新公式如下：

Screen Shot 2019-02-23 at 1.52.08 PM.png

可以看出来， $Q$ 值的更新采用的是Sarsa，所以它是on-policy。

Off-policy Deterministic Actor-Critic：更新公式如下：

Screen Shot 2019-02-23 at 1.57.48 PM.png

可以看出它和on-policy的区别在于 $Q$ 的更新，它采用的是Q-learning的方式。

3.7 Compatible Function Approximation

通常来说，使用一个近似值 $Q^w$ 不一定会使得前面的确定性策略梯度近似于真实梯度。但是我们可以找到一组compatible function approximation，使得 $\triangledown_a Q^\mu(s,a)$ 可以被 $\triangledown_a Q^w(s,a)$ 代替。

定理如下：

Screen Shot 2019-02-23 at 2.34.05 PM.png

对于任意的确定性策略，总存在compatible function approximator： $Q^w(s,a) = (a - \mu_\theta(s))^T \triangledown_\theta \mu_\theta(s)^T w + V^v(s)$ ，其中 $V^v(s)$ 可以是任何独立于动作 $a$ 的可微分函数。通常将第一项解释为advantage function，第二项解释为价值函数。

4. DDPG

论文地址

DDPG我理解其实就是 DPG + DQN

4.1 Why DDPG

DQN可以用于处理类似于图片，视频的非常高维度的输入，或者说obervation space，但是无法处理连续的输出，也就是动作空间。

DPG可以用于连续的动作空间，深度学习可以处理高维度的观察空间，两者结合起来就得到了DDPG。

同时采用了DQN的一些做法：1. replay buffer， 2. target Q network。

4.2 DDPG

首先回顾一下DPG，它有个actor函数： $\mu(s|\theta^\mu)$ ，给定策略下的状态，直接返回一个确定性的动作，它还有一个critic： $Q(s,a)$ ，可以通过Q-learning或者sarsa来进行学习。

Actor的更新公式如下：

Screen Shot 2019-02-23 at 3.29.52 PM.png

如果使用神经网络来作为estimator，就得到了Deep DPG（DDPG）。我们知道，神经网络使用梯度下降，也就要求样本是独立，同分布的。但是，显然增强学习中通过agent探索的方式得到的sample，关联性很强。

类似于DQN，作者使用replay buffer来克服这个问题。也就是用一个经验池，里面存放了一堆 $(s_t,a_t,r_t,s_{t+1})$ ，之后再从这个池子里面采样作为样本输入神经网络训练。

由于在Q-learning中，被更新的Q同时被用于了计算目标Q值，所以会导致不稳定。因此类似DQN，作者使用了target网络， $Q'(s,a|\theta^{Q'}), \mu'(s|\theta^{Q'})$ 。使用target网络来计算目标值。
更新目标网络参数时，采用： $\theta' \leftarrow \tau\theta + (1 - \tau) \theta'$ 。

为了引入exploration，作者使用了exploration policy $\mu'(s_t) = \mu(s_t|\theta_t^\mu) + N$ 。

最终，算法如下：

DDPG