Policy Gradient Methods, DPG 和 DDPG

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：选择参数的更新量，是的策略的分布的变化为一个定值。

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
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 203,547评论 6赞 477
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,399评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 150,428评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,599评论 1赞 274
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,612评论 5赞 365
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,577评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,941评论 3赞 395
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,603评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,852评论 1赞 297
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,605评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,693评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,375评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,955评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,936评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,172评论 1赞 259
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 43,970评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,414评论 2赞 342

推荐阅读更多精彩内容