第20-21周论文阅读（2019年）

2019-05-28 本文已影响81人 d88e0445288d

上周去北京出差，没来得及更新，因此这次将两周的论文笔记合并，主要是 ICLR 2019 强化相关的paper。

Composing Complex Skills By Learning Transition Policies

这篇论文的落脚点比较有意思。我们知道一些复杂的技巧是需要简单技巧的组合来完成的，例如对于篮球来说，一个进球动作的完成，是需要诸如抢断、运球、投篮等技巧组合而成。但是这些技巧并不能简单的顺序拼接，例如运球到指定地点后准备进行投篮时，运球的终止动作是不能够直接转换到投篮的起始动作（比如说运球结束后是一个“三威胁”的姿势，但是投篮是一个身体直立微微后仰的姿势，中间需要平滑的过渡）。而本篇论文所做的事情就是将这些简单技巧结合起来，并且学习一个能够在技巧中间进行平滑过渡的技巧（策略）。上述过程可见下图。

策略转换

本篇文章假定完成整个复杂任务过程中的收到的回报时稀疏的并且二值化的，即在每个子策略（技巧）成功完成时才会收到回报，完成为 1 ，失败为 -1，否则在子策略执行过程中每个时间步收到的回报为 0。

文章整体框架一共分为三个部分：

元策略（选择此时该执行哪一个前置策略）
前置策略（即子策略，是事先学习好的）
转移策略（用以平滑转换两个子策略）

整体流程见下图：

总体框架

这里提几个细节问题。第一，前置策略只会使用与子任务相关的状态信息（state），但是元策略会使用到额外的与整体任务相关的状态信息。由于本文（本篇论文，下同）的主要工作聚焦在转移策略的学习，因而元策略使用简单的基于规则的策略。第二，某个前置策略均对应一个转移策略，这个转移策略能够处理所有的从其他前置策略的终止状态，转移到其对应的前置策略初始状态的情况。第三，前置策略对应的转移策略与前置策略的状态空间以及动作空间完全相同，并且会学到一个终止信号，表明转移策略执行完毕，可以开始执行对应的前置策略。

下面介绍如何训练转移策略。从上面的讨论我们知道，转移策略训练时所能接收到的回报是稀疏的且是二值化的。对于这种稀疏回报的情况，一般的做法是额外构建一个新的稠密的回报函数，本文也不例外。具体来说，该回报函数中包含一个邻近预测器，这个预测器会预估在执行转移策略时，当前状态距离该转移策略对应的前置策略的初始状态集合的距离，被定义为 $v=\delta^{s t e p}$ ，其中 step 表示当前状态距离前置策略的初始状态集合的最短时间步。前置策略的初始状态集合，是将前置策略随机运行若干遍，取其收集到的轨迹的前 10%-20% 的状态作为初始状态集合。

前置策略的训练数据通过如下方式收集：

前置策略训练框架

可以看到，这里会维护两个经验回放缓存，一个是成功缓存，一个是失败缓存。成功与失败通过后续执行前置策略成功与否来进行判断，因为转移策略的最终目标就是保证后续的前置策略能够被成功执行，而前置策略已经训练好了，所以只要转移策略能够将智能体引导到前置策略的初始状态集合，那么前置策略就一定可以成功执行，即前置策略成功与否对应着转移策略是否将智能体引导到对应的初始状态集合。一旦后续的前置策略成功执行，那么就将转移策略采样的整个轨迹放入成功缓存中，并对每个状态计算 $v$ 值；否则将整个轨迹放入失败缓存中。接着，根据这两个经验回放缓存，我们通过下面的损失函数训练邻近预测器：
$L_{P}\left(\omega, \mathcal{B}^{S}, \mathcal{B}^{F}\right)=\frac{1}{2} \mathbb{E}_{(s, v) \sim \mathcal{B}^{S}}\left[\left(P_{\omega}(s)-v\right)^{2}\right]+\frac{1}{2} \mathbb{E}_{s \sim \mathcal{B}^{F}}\left[P_{\omega}(s)^{2}\right]$
这样训练出来的邻近预测器，如果某个状态的输出值为 1 ，则该状态位于初始状态集合中；为 0 则代表该状态会导致后续的前置策略执行失败；在 0 和 1 之间则表明该状态是位于到初始状态集合的轨迹上的。有了邻近预测器，强化学习的优化目标（回报函数）为：
$R_{\text { trans }}(\phi)=\mathbb{E}_{\left(s_{0}, s_{1}, \ldots, s_{T}\right) \sim \pi_{\phi}}\left[\gamma^{T} P_{\omega}\left(s_{T}\right)+\sum_{t=0}^{T-1} \gamma^{t}\left(P_{\omega}\left(s_{t+1}\right)-P_{\omega}\left(s_{t}\right)\right)\right]$
本文采用 PPO 算法优化上述目标函数。设计这个回报函数的出发点有二。其一，我们希望转移策略的终止状态位于初始状态集合中；其二，我们希望转移策略产生的状态轨迹是逐步逼近初始状态集合的。

最后，算法的伪代码如下：

训练部分伪代码

采样部分伪代码

Learning to Navigate the Web

这是谷歌近期的一个工作，其目的是使用强化学习算法训练出一个智能体，该智能体能够识别人的指令在网页上完成指定的任务，例如订购机票等。本文提出了两个算法：1）当专家示例数据存在时，采用模仿学习的方式训练智能体；2）否则，训练一个生成模型来产生训练样本，从而训练智能体。

本文采用的是 DQN 算法，并且整个强化学习问题的回报是稀疏的，只有在最终任务完成时才会收到反馈。首先我们先对整个问题进行正式的定义。用户的指令 I = [ F = (K, V) ] 是一个键值对列表，例如机票订购任务，[起点：旧金山，终点：纽约，日期：2018年12月4日]。在每个时间步，状态由指令以及当前网页的 DOM 树表示，DOM 树中的每一个 DOM 元素由一个命名属性列表构成，例如 tag, value, name, text, id, class 等。回报函数设计为终止状态的 DOM 树是否与目标状态的 DOM 树一致。动作空间（组合动作空间）定义为下图所示的层次表示：

组合动作空间

因而 Q 值函数定义如下：
$Q(s, a)=Q\left(s, a_{D}\right)+Q\left(s, a_{C} | a_{D}\right)+Q\left(s, a_{T} | a_{D},\left[a_{C}==^{\prime \prime} \operatorname{type}^{\prime \prime}\right]\right)$
下面是第一个算法（有专家示例数据存在）的伪代码：

算法一伪代码

关于第一个算法有两点值得关注，第一个是该算法采用了课程学习的思想。由于一个网页的 DOM 元素非常多，因此动作空间很大，这会对强化学习算法的训练带来很大的困难。因此本文首先使用专家策略将一些 DOM 元素直接设置为目标状态，这样智能体需要完成的任务就会简单很多。第二，这里 Q 值网络的设计也是一个重点：

QWeb网络

可以看到整体的网络设计十分复杂，结合了自注意力机制、LSTM以及浅度编码等，由于我目前的研究方向不在 NLP，所以具体的网络设计就不再详细解释，感兴趣的可以去看原始论文。第一个算法的具体训练过程如下：

DQN训练过程

由于是稀疏问题，中间状态的回报函数也被重新设计：
$R_{\text {potential}}=\gamma\left(\text {Potential}\left(s_{t+1}, g\right)-\text {Potential}\left(s_{t}, g\right)\right)$
其中 Potential 的值代表当前状态与目标状态的 DOM 元素的匹配个数，并使用目标状态的总 DOM 元素个数进行归一化。

而对于第二个算法，我们是没有专家示例数据的，对于这种情况，本文的做法是采用一个随机策略生成目标状态，再训练一个指令生成器根据目标状态生成对应指令。下面我们简单介绍一下指令生成器的训练方式。

指令生成器同样采用 DQN 算法。对于这个新的强化学习问题，其状态定义为随机策略生成的目标状态G，以及从一个关键字列表中无放回采用出的一个关键字（例如订票任务中的起点、终点、日期），而动作空间则定义为从当前网页的 DOM 元素中选定一个，并从这个元素产生一个对应于关键字的内容（这里的产生可以是从该 DOM 元素对应的下拉列表中选择一行内容）。执行每个动作后，一旦产生的对应于这个状态对应的关键字的内容是正确的，收到 +1 的回报，否则收到 -1 的回报。指令生成器的对应的 Q 值网络（INET网络）定义如下：

INET网络

有了指令生成器，以及随机策略产生的动作序列，我们就可以将问题转变为拥有专家示例数据时的问题。算法二得伪代码如下：

算法二伪代码

Learning Self-Imitating Diverse Policies

本篇文章基于策略梯度算法，致力于解决稀疏回报问题。其核心思想在于，通过利用策略与其对应的状态-动作访问分布的等价性，将策略优化问题转化为最小化当前策略对应的访问分布，与经验回放缓存中高回报轨迹的访问分布之间的距离的问题（可以看作将自身收集的高回报轨迹作为专家数据进行模仿学习）。本文表明，将分布的距离定义为 JS 距离时，提出的算法等价于一个离线的、带有特殊形式的稠密回报的策略梯度算法。

我们可以将上述最小化问题定义如下：
$\min _{\pi} D\left(\rho_{\pi},\left\{\left(s_{i}, a_{i}\right)\right\}_{\mathcal{M}_{E}}\right)$
距离函数中的第一个参数代表当前策略对应的状态-动作分布，后者代表经验回放缓存中高回报轨迹对应的状态-动作分布。这里本文将距离函数定为 JS 散度，即：
$D_{J S}\left(\rho_{\pi}, \rho_{\pi_{E}}\right)=\max _{d(s, a), d_{E}(s, a)} \widetilde{\mathbb{E}}_{\rho_{\pi_{\theta}}}\left[\log \frac{d(s, a)}{d(s, a)+d_{E}(s, a)}\right]+\widetilde{\mathbb{E}}_{\rho_{\pi_{E}}}\left[\log \frac{d_{E}(s, a)}{d(s, a)+d_{E}(s, a)}\right]$
其中 $d(s,a)$ 以及 $d_{E}(s,a)$ 分别表示真实分布的经验估计。上述目标函数关于策略参数 $\theta$ 的梯度为：
$\begin{aligned} \nabla_{\theta} D_{J S}\left(\rho_{\pi}, \rho_{\pi_{E}}\right) & \approx \widetilde{\mathbb{E}}_{\rho_{\pi}(s, a)}\left[\nabla_{\theta} \log \pi_{\theta}(a | s) \widetilde{Q}^{\pi}(s, a)\right] \\ \text { where } \widetilde{Q}^{\pi}\left(s_{t}, a_{t}\right) &=\widetilde{\mathbb{E}}_{\rho_{\pi}(s, a)}\left[\sum_{t^{\prime}=t}^{\infty} \gamma^{t^{\prime}-t} \log \frac{d_{\pi}\left(s_{t^{\prime}}, a_{t^{\prime}}\right)}{d_{\pi}\left(s_{t^{\prime}}, a_{t^{\prime}}\right)+d_{\pi_{E}}\left(s_{t^{\prime}}, a_{t^{\prime}}\right)}\right] . \end{aligned}$
对于经验回放中高回报轨迹集合的构建，本文采用了一个十分简单的方式，就是从当前策略采样的轨迹中选择回报高于某个阈值的轨迹放入高回报轨迹集合中。该集合更新的方式也是优胜略汰。

由于 JS 散度的估计梯度的形式于标准的策略梯度的行驶类似，本文结合了两者：
$\nabla_{\theta} \eta\left(\pi_{\theta}\right)=(1-\nu) \mathbb{E}_{\rho_{\pi}(s, a)}\left[\nabla_{\theta} \log \pi_{\theta}(a | s) Q^{r}(s, a)\right]-\nu \nabla_{\theta} D_{J S}\left(\rho_{\pi}, \rho_{\pi_{E}}\right)$
令 $r^{\phi}(s, a)=d_{\pi}(s, a) /\left[d_{\pi}(s, a)+d_{\pi_{E}}(s, a)\right]$ 并将上式展开，我们有：
$\nabla_{\theta} \eta\left(\pi_{\theta}\right)=\mathbb{E}_{\rho_{\pi}(s, a)}\left[\nabla_{\theta} \log \pi_{\theta}(a | s)\left[(1-\nu) Q^{r}(s, a)+\nu Q^{r^{\phi}}(s, a)\right]\right]$
其中 $Q^{r^{\phi}}\left(s_{t}, a_{t}\right)=-\mathbb{E}_{p_{0}, p, \pi}\left[\sum_{t^{\prime}=t}^{\infty} \gamma^{t^{\prime}-t} \log r^{\phi}\left(s_{t^{\prime}}, a_{t^{\prime}}\right)\right]$ 。可以看出，采用本文的算法相当于设计了一个稠密的回报函数。

但是采用自身收集的高回报轨迹作为专家策略进行自模仿学习存在以下几个大的局限性：

高回报轨迹的质量依赖于学习中策略的探索度
只模仿自身容易陷入局部最优
环境中的随机性同样容易使得仅仅模仿收集到的高回报轨迹会陷入局部最优。

本文提出的解决方法是训练一系列通过自模仿进行学习的智能体，从而增大探索度。本文借鉴了 SVPG 的思想，其目标函数为：
$\max _{q} \mathbb{E}_{\theta \sim q}[\eta(\theta)]+\alpha H(q)$
参数更新方程为（SVGD）：
$\theta_{i} \leftarrow \theta_{i}+\epsilon \Delta \theta_{i}, \quad \Delta \theta_{i}=\frac{1}{n} \sum_{j=1}^{n}\left[\nabla_{\theta_{j}} \eta\left(\pi_{\theta_{j}}\right) k\left(\theta_{j}, \theta_{i}\right)+\alpha \nabla_{\theta_{j}} k\left(\theta_{j}, \theta_{i}\right)\right]$
该梯度第一项鼓励智能体挖掘高回报区域，第二项鼓励智能体学习不同的策略从而学习探索度更高的策略。SVPG 算法中核函数选为 $k\left(\theta_{j}, \theta_{i}\right)=\exp \left(-\left\|\theta_{j}-\theta_{i}\right\|_{2}^{2} / h\right)$ ，本文认为欧式距离不太合理，因而根据前面的基础提出了一个新的基于 JS 散度的核函数 $k\left(\theta_{j}, \theta_{i}\right)=\exp \left(-D_{J S}\left(\rho_{\pi_{\theta_{j}}}, \rho_{\pi_{\theta_{i}}}\right) / T\right)$ 。

最后，不采用集成策略的算法伪代码如下：

算法一

使用集成学习的算法伪代码如下：

算法二

Diversity is All You Need: Learning Diverse Skills without a Reward Function

本文提出了一个在稀疏回报环境下学习尽可能多样的的技巧（子策略）的强化学习方法 DIAYN。本文对于多样性通过如下方式定义：

不同的技巧（子策略）尽可能访问不同的状态，从而两两之间可以分辨。
使用状态而不是动作来定义多样性，因为不能影响到环境的动作甚至无法被观测，可以被观测的动作不一定代表了技巧的全部属性。
由于回报稀疏，我们希望学到的子策略尽可能拥有更高的探索度。

为了正式地定义技巧，我们引入一个随机变量 $Z \sim p(z)$ ，那么技巧就可以定义为与一个固定的 $Z$ 条件相关的策略。有了上述三个多样性的具体衡量指标，我们的优化目标为：
$\begin{aligned} \mathcal{F}(\theta) & \triangleq I(S ; Z)+\mathcal{H}[A | S]-I(A ; Z | S) \\ &=(\mathcal{H}[Z]-\mathcal{H}[Z | S])+\mathcal{H}[A | S]-(\mathcal{H}[A | S]-\mathcal{H}[A | S, Z]) \\ &=\mathcal{H}[Z]-\mathcal{H}[Z | S]+\mathcal{H}[A | S, Z] \end{aligned}$
可以看到，上述优化目标，第一项鼓励 $Z$ 的先验分布（类别分布，类别数预定义好）熵尽可能高，因而我们固定其先验分布为均匀分布；第二项建议应当很容易从当前状态推断出现在执行的技巧；第三项鼓励学到的技巧尽可能随机。我们采用变分的方法对上述目标函数进行估计：
$\begin{aligned} \mathcal{F}(\theta) &=\mathcal{H}[A | S, Z]-\mathcal{H}[Z | S]+\mathcal{H}[Z] \\ &=\mathcal{H}[A | S, Z]+\mathbb{E}_{z \sim p(z), s \sim \pi(z)}[\log p(z | s)]-\mathbb{E}_{z \sim p(z)}[\log p(z)] \\ & \geq \mathcal{H}[A | S, Z]+\mathbb{E}_{z \sim p(z), s \sim \pi(z)}\left[\log q_{\phi}(z | s)-\log p(z)\right] \triangleq \mathcal{G}(\theta, \phi) \end{aligned}$
有了上述理论支持，我们可以开始付诸实践了。本文采用 SAC 算法实现 DIAYN，学习一个基于当前状态以及隐含随机变量 $z$ 的策略（技巧）。由于 SAC 中本身便具有熵正则项，因而我们只需对其原始目标函数进行以下修改：
$r_{z}(s, a) \triangleq \log q_{\phi}(z | s)-\log p(z)$
所以这是一个完全无监督的强化学习，没有任何外部的回报。在训练过程中，每一个 episode 开始时都从 $p(z)$ 中进行采样，接下来便是正常的 SAC 算法训练流程。

下面将两个非常重要的扩展。第一个是可以采用学到的技巧来初始化特定任务。具体做法是，对于一个特定任务，我们首先将学习到的所有技巧（策略）在该任务上进行测试，选择一个回报最高的，再进行 finetune。第二个是层次强化学习，我们可以训练一个元控制器来选择此时间段内应该执行哪个技巧（策略）。

Discriminator-Actor-Critic: Addressing Sample Inefficiency and Reward Bias in Adversarial Imitation Learning

本文是对逆强化学习算法（对抗模仿学习算法） GAIL 做出的一点改进，提出了 DAC 算法，通过采用离线训练判别器以及无偏回报函数的方式来改进 GAIL 算法中存在的样本低效性等问题。

首先对于无偏回报函数，一般逆强化都是将最终状态的回报设置为 0，本文发现这样做会导致回报函数的设计出现偏差，因而对于最终状态的回报，采用了一个通过学习得到的非 0 的回报。具体来说，GAIL 通过下述目标函数来训练判别器以及策略：
$\max _{\pi} \max _{D} \mathbb{E}_{\pi}[\log (D(s, a))]+\mathbb{E}_{\pi_{E}}[\log (1-D(s, a))]-\lambda H(\pi)$
其回报函数设计为：
$r\left(s, a, s^{\prime}\right)=\log \left(D\left(s, a, s^{\prime}\right)-\log \left(1-D\left(s, a, s^{\prime}\right)\right)\right.$
可以看到在训练初期，由于判别器很容易分辨真假样本，该回报函数基本都是负值，从而鼓励智能体尽快结束任务，从而使得学到的策略陷入局部最优。DAC 算法的做法是为将最终状态的回报函数设计如下：
$R_{T}=r\left(s_{T}, a_{T}\right)+\sum_{t=T+1}^{\infty} \gamma^{t-T} r\left(s_{a}, \cdot\right)$
其中 $r(s_a, \cdot)$ 为学习的回报函数，另外，DAC 算法还学习了一个额外的指示器来判断当前状态是否为最终状态。

另外，为了解决 GIAL 算法只能在线学习判别器从而降低了采样效率的问题，DAC 对 GAIL 的目标函数进行了修改：
$\max _{D} \mathbb{E}_{\mathcal{R}}[\log (D(s, a))]+\mathbb{E}_{\pi_{E}}[\log (1-D(s, a))]-\lambda H(\pi)$
从而可以利用经验缓存里的离线数据进行训练（按理说要加上重要性采样，但是本文认为重要性权重很难估计，并且实验表明不加也没什么关系），最终将 DAC 与 TD3 这个离线方法进行结合，伪代码如下：

DAC

Hindsight Policy Gradient

本文将 Hindsight 方法扩展到策略梯度方法中，从而大大扩展了该类方法的使用范围。对于基于目标的策略，其采样的轨迹的联合概率通过下式计算：
$p(\boldsymbol{\tau} | g, \boldsymbol{\theta})=p\left(s_{1}\right) \prod_{t=1}^{T-1} p\left(a_{t} | s_{t}, g, \boldsymbol{\theta}\right) p\left(s_{t+1} | s_{t}, a_{t}\right)$
那么使用 $\theta$ 参数化的策略对应的期望收益（累积回报）为：
$\eta(\boldsymbol{\theta})=\mathbb{E}\left[\sum_{t=1}^{T} r\left(S_{t}, G\right) | \boldsymbol{\theta}\right]=\sum_{g} p(g) \sum_{\boldsymbol{\tau}} p(\boldsymbol{\tau} | g, \boldsymbol{\theta}) \sum_{t=1}^{T} r\left(s_{t}, g\right)$
那么对应的，我们可以将策略梯度定理扩展到基于目标的策略梯度定理：
$\nabla \eta(\boldsymbol{\theta})=\sum_{g} p(g) \sum_{\boldsymbol{\tau}} p(\boldsymbol{\tau} | g, \boldsymbol{\theta}) \sum_{t=1}^{T-1} \nabla \log p\left(a_{t} | s_{t}, g, \boldsymbol{\theta}\right) \sum_{t^{\prime}=t+1}^{T} r\left(s_{t^{\prime}}, g\right)$
并使用 baseline function 进行方差缩减：
$\nabla \eta(\boldsymbol{\theta})=\sum_{g} p(g) \sum_{\boldsymbol{\tau}} p(\boldsymbol{\tau} | g, \boldsymbol{\theta}) \sum_{t=1}^{T-1} \nabla \log p\left(a_{t} | s_{t}, g, \boldsymbol{\theta}\right)\left[\left[\sum_{t^{\prime}=t+1}^{T} r\left(s_{t^{\prime}}, g\right)\right]-b_{t}^{\theta}\left(s_{t}, g\right)\right]$
在 baseline function 为 state-value function 时，我们有：
$\nabla \eta(\boldsymbol{\theta})=\sum_{g} p(g) \sum_{\boldsymbol{\tau}} p(\boldsymbol{\tau} | g, \boldsymbol{\theta}) \sum_{t=1}^{T-1} \nabla \log p\left(a_{t} | s_{t}, g, \boldsymbol{\theta}\right) A_{t}^{\boldsymbol{\theta}}\left(s_{t}, a_{t}, g\right)$
再回到最原始的（不带 baseline的）策略梯度公式，根据重要性采样定理，对于任意一个目标 $g^{\prime}$ ，我们有：
$\nabla \eta(\boldsymbol{\theta})=\sum_{\boldsymbol{\tau}} p\left(\boldsymbol{\tau} | g^{\prime}, \boldsymbol{\theta}\right) \sum_{g} p(g) \sum_{t=1}^{T-1} \nabla \log p\left(a_{t} | s_{t}, g, \boldsymbol{\theta}\right) \sum_{t^{\prime}=t+1}^{T}\left[\prod_{k=1}^{T-1} \frac{p\left(a_{k} | s_{k}, g, \boldsymbol{\theta}\right)}{p\left(a_{k} | s_{k}, g^{\prime}, \boldsymbol{\theta}\right)}\right] r\left(s_{t^{\prime}}, g\right)$
同时，根据因果关系，我们知道某个时刻之后的任何行为均不会影响当前时间步的回报，因而我们可以将上式改写为：
$\nabla \eta(\boldsymbol{\theta})=\sum_{\boldsymbol{\tau}} p\left(\boldsymbol{\tau} | g^{\prime}, \boldsymbol{\theta}\right) \sum_{g} p(g) \sum_{t=1}^{T-1} \nabla \log p\left(a_{t} | s_{t}, g, \boldsymbol{\theta}\right) \sum_{t^{\prime}=t+1}^{T}\left[\prod_{k=1}^{t^{\prime}-1} \frac{p\left(a_{k} | s_{k}, g, \boldsymbol{\theta}\right)}{p\left(a_{k} | s_{k}, g^{\prime}, \boldsymbol{\theta}\right)}\right] r\left(s_{t^{\prime}}, g\right)$
最后我们同策略梯度定理一样引入优势函数，则最终的 Hindsight 策略梯度计算方法如下：
$\nabla \eta(\boldsymbol{\theta})=\sum_{\boldsymbol{\tau}} p\left(\boldsymbol{\tau} | g^{\prime}, \boldsymbol{\theta}\right) \sum_{g} p(g) \sum_{t=1}^{T-1} \nabla \log p\left(a_{t} | s_{t}, g, \boldsymbol{\theta}\right)\left[\prod_{k=1}^{t} \frac{p\left(a_{k} | s_{k}, g, \boldsymbol{\theta}\right)}{p\left(a_{k} | s_{k}, g^{\prime}, \boldsymbol{\theta}\right)}\right] A_{t}^{\boldsymbol{\theta}}\left(s_{t}, a_{t}, g\right)$
其中
$A_{t}^{\boldsymbol{\theta}}(s, a, g)=\mathbb{E}\left[r\left(S_{t+1}, g\right)+V_{t+1}^{\boldsymbol{\theta}}\left(S_{t+1}, g\right)-V_{t}^{\boldsymbol{\theta}}(s, g) | S_{t}=s, A_{t}=a\right]$
在具体实现过程中，对于最原始的基于目标的策略梯度（引入优势函数类似）的估计方式如下：
$\frac{1}{N} \sum_{i=1}^{N} \sum_{g} p(g) \sum_{t=1}^{T-1} \nabla \log p\left(A_{t}^{(i)} | S_{t}^{(i)}, G^{(i)}=g, \boldsymbol{\theta}\right) \sum_{t^{\prime}=t+1}^{T}\left[\prod_{k=1}^{t^{\prime}-1} \frac{p\left(A_{k}^{(i)} | S_{k}^{(i)}, G^{(i)}, G^{(i)}=g, \boldsymbol{\theta}\right)}{p\left(A_{k}^{(i)} | S_{k}^{(i)}, G^{(i)}, \boldsymbol{\theta}\right)}\right] r\left(S_{t^{\prime}}^{(i)}, g\right)$
最后为了解决训练不稳定问题，本文对重要性权重进行了归一化：
$\sum_{i=1}^{N} \sum_{g} p(g) \sum_{t=1}^{T-1} \nabla \log p\left(A_{t}^{(i)} | S_{t}^{(i)}, G^{(i)}=g, \boldsymbol{\theta}\right) \sum_{t^{\prime}=t+1}^{T} \frac{\left[\prod_{k=1}^{t^{\prime}-1} \frac{p\left(A_{k}^{(i)} | S_{k}^{(i)}, G^{(i)}, G^{(i)}=g, \boldsymbol{\theta}\right)}{p\left(A_{k}^{(i)} | S_{k}^{(i)}, G^{(i)}, \boldsymbol{\theta}\right)}\right] r\left(S_{t^{\prime}}^{(i)}, g\right)}{\sum_{j=1}^{N}\left[\prod_{k=1}^{t^{\prime}-1} \frac{p\left(A_{k}^{(j)} | S_{k}^{(j)}, G^{(j)}=g, \boldsymbol{\theta}\right)}{p\left(A_{k}^{(j)} | S_{k}^{(j)}, G^{(j)}, \boldsymbol{\theta}\right)}\right]}$
这里的重要性稀疏分母中的 $G^{(i)}$ 表示 batch 中所有 episode 中访问到的所有 state 的集合。

最后我们谈一下 HPG 方法的局限性，其主要的局限性在于，由于其需要对 batch 中所有的 episode 中访问到的 state 均作为 goal 进行求和 $\sum_g p(g)$ ，其计算负责度非常高。本文的解决方案是对 batch 中的所有的 state 的集合进行采样，从而减小计算复杂度，但这会导致梯度的计算存在偏差（从实验结果看这不是个大问题）。值得一提的是，使用上述带偏差的梯度估计时，实验表明引入优势函数反而使得训练不稳定，原因经过分析可能是因为优势函数的估计不准确所致。

CEM-RL : Combining evolutionary and gradient-based methods for policy searc

本文将 CEM 方法以及 DDPG 和 TD3 两个离线强化学习算法结合起来，具体流程如下以及伪代码如下所示：

框架图

伪代码

其中值得一提的有两点。其一，由于 CEM 算法需要估计下一轮采样分布的方差，而 DDPG 与 TD3 算法中用到神经网络作为函数估计器，因而参数量非常大，如果用下述正常的估计公式：
$\Sigma_{n e w}=\sum_{i=1}^{K_{e}} \lambda_{i}\left(z_{i}-\mu_{o l d}\right)\left(z_{i}-\mu_{o l d}\right)^{T}+\epsilon \mathcal{I}$
则计算复杂度会非常高，因而本文将此协方差矩阵简化为对角矩阵，对角元素通过如下方式计算：
$\boldsymbol{\Sigma}_{n e w}=\sum_{i=1}^{K_{e}} \lambda_{i}\left(z_{i}-\mu_{o l d}\right)^{2}+\epsilon \mathcal{I}$
其二，在进行策略评估时，会随机选取一般的个体进行一次强化学习更新，将更新后的个体与未更新的个体一起进行评估、排序，选择性能更好的前一半进行下一轮进化；并将所有个体采样得到的样本都放入经验缓存中。上述做法有两个好处：1）只对一般个体进行强化学习的更新，并与没有更新的个体一起排序，可以防止强化学习算法陷入局部最优；2）将所有个体采样的样本均放入经验缓存中，可以增加探索度。

Unsupervised Control Through Non-Parametric Discriminative Rewards

人类在学习玩一个游戏时可以很快的学会环境中那些方面时自己能够控制的并且如何去控制他们。因而本文将强化学习的目标建模为如何去掌握一个游戏的环境而不是最大化一个简单的标量回报函数。因为本文提出了一种强化学习算法 Discriminative Embedding Reward Networks(DISCERN) 只从状态-动作序列中进行学习，而不需要回报的反馈。最终算法训练完成时可以学习到一个指示任务完成度的回报函数，它只考虑当前状态与目标状态中策略可以控制的部分的相似度而不是整个观察空间的相似度。

注意，DISCERN 算法还可以完成那些不能够完美完成的目标任务，算法会尝试尽可能地使得智能体达到目标状态中的策略可控部分对应的状态。

本文致力于解决以下问题：在每个 episode 开始之前从某个分布中采样一个目标状态 $g$ ，智能体经过特定步数 $T$ 之后达到一个最终状态，并且只有在最后一步才会接收到一个环境的反馈，其余时间步均为 0。一般算法可能会将最后的回报函数定义为 1 或者 -1，或者进行人工设计。而 DISCERN 算法核心便是对最后的回报函数进行更加合理的定义。

本文目标是通过最大化目标状态以及最终状态之间的互信息来同时学习一个基于目标的策略以及一个指示目标完成度的回报函数（最后一个时间步的回报函数）：
$I\left(s_{g}, s_{T}\right)=H\left(s_{g}\right)+\mathbb{E}_{s_{g}, s_{T} \sim p\left(s_{g}, s_{T}\right)} \log p\left(s_{g} | s_{T}\right)$
我们可以对上式采用变分的方式进行估计：
$I\left(s_{g}, s_{T}\right) \geq H\left(s_{g}\right)+\mathbb{E}_{s_{g} \sim p_{g o a l}, s_{1}, \ldots s_{T} \sim \pi_{\theta}\left(\cdots | s_{g}\right)} \log q_{\phi}\left(s_{g} | s_{T}\right)$
由于右边第一项与参数无关，因而可以直接忽略，最终的优化目标为：
$O_{\mathrm{DISCERN}}=\mathbb{E}_{s_{g} \sim p_{\text {goal}, s_{1}, \ldots, s_{T} \sim \pi_{\theta}}\left(\cdots | s_{g}\right)} \log q_{\phi}\left(s_{g} | s_{T}\right)$

可以看出优化上述目标十分困难，因为目标状态是高维的，例如图片等。在这里本文通过将目标状态集合简化为有限集合（之前访问过的状态）来解决上述问题，即在实现时维护一个固定大小的目标集合（有关目标集合替换策略请见原论文），然后从中进行均匀采样（关于采样方式作者认为值得进一步研究）。

通过观察上述目标函数我们可以发现，这其实就是一个中间时间步回报为 0，最终时间步回报为 $\log q_{\phi}\left(s_{g} | s_{T}\right)$ 的强化学习目标函数。本文还发现将上述最后时间步的回报函数通过一个非线性函数映射到 $[0, 1]$ 范围内效果会更好。

我们将 $\log q_{\phi}\left(s_{g} | s_{T}\right)$ 建模为以下形式：
$\log \hat{q}\left(s_{g}=g | s_{T} ; d_{1}, \ldots d_{K}, \pi_{\theta}\right)=\log \frac{\exp \left(\beta \ell_{g}\right)}{\exp \left(\beta \ell_{g}\right)+\sum_{k=1}^{K} \exp \left(\beta \xi_{\phi}\left(h\left(s_{T}\right)\right)^{\top} \xi_{\phi}\left(h\left(d_{k}\right)\right)\right)}$
其中：
$\ell_{g}=\xi_{\phi}\left(h\left(s_{T}\right)\right)^{\top} \xi_{\phi}(h(g))$
$h$ 为策略网络的最后一层特征（避免学习第二个网络，减少参数数量从而防止过拟合）。这里的 $d_{1}, d_{2}, \ldots, d_{K}$ 代表负样本，通过类似于 NLP 中的 Negative Sampling 方法来对回报函数进行训练。我们使用 $\max \left(0, \ell_{g}\right)$ 作为最后一个时间步的回报函数，本文发现这个比直接使用 $\log \hat{q}\left(s_{g}=g | s_{T} ; d_{1}, \ldots d_{K}, \pi_{\theta}\right)$ 更好，因为它不受采样的负样本 $d_{1}, d_{2}, \ldots, d_{K}$ 的影响。最后本文使用 $\epsilon$ -greedy TD( $\lambda$ ) 算法来学习基于目标的策略。DISCERN 算法还结合了HER 算法，以一定的概率将某些轨迹最后一个时间步的回报由 $\max \left(0, \ell_{g}\right)$ 替换为 1 并将目标进行修改。

算法伪代码如下：

DISCERN算法

Motion Planning Networks

本文采用深度学习技术提出了一个新的机器人路径规划算法 MPNet ，最终实验结果能够在达到基准算法（RRT*等）性能的基础上大幅降低算法运行时间。

MPNet 算法一共包括两个网络，一个编码器网络以及一个规划网络。编码器网络通过学习将环境中的障碍物点云数据编码到隐空间中。规划网络则根据机器人当前时刻的状态、目标以及障碍物点云数据的隐含编码，来预测其下一步需要达到的位置。同时，考虑到神经网络目前还没有在理论上保证其性能的稳定性，因而本文提出了一个结合传统路径规划算法（RRT*）的混合路径规划算法。

MPNet 算法包含两个阶段：1）神经网络的离线训练阶段，以及 2）在线路径生成阶段。整体框架如下图所示：

MPNet算法框架

下面展开来讲算法细节：

离线训练

编码器

编码器采用 contrative autoencoders (CAE) ，其优点在于习得的隐含编码具有更好的鲁棒性以及泛化性能。其目标函数如下：
$L_{\mathrm{AE}}\left(\boldsymbol{\theta}^{e}, \boldsymbol{\theta}^{d}\right)=\frac{1}{N_{\mathrm{obs}}} \sum_{\boldsymbol{x} \in D_{\mathrm{obs}}}\|\boldsymbol{x}-\hat{\boldsymbol{x}}\|^{2}+\lambda \sum_{i j}\left(\theta_{i j}^{e}\right)^{2}$

规划网络

规划网络采用模仿学习的方式进行训练，采用的训练数据在本文中为 RRT* 算法产生的轨迹数据 $\tau^{*}=\left\{\boldsymbol{x}_{0}, \boldsymbol{x}_{1}, \cdots, \boldsymbol{x}_{T}\right\}$ ，目标函数如下：
$L_{\mathrm{Pnet}}(\boldsymbol{\theta})=\frac{1}{N_{p}} \sum_{j}^{\hat{N}} \sum_{i=0}^{T-1}\left\|\hat{\boldsymbol{x}}_{j, i+1}-\boldsymbol{x}_{j, i+1}\right\|^{2}$

在线规划

首先给出在线规划算法的伪代码：

在线路径规划算法伪代码

在线规划算法伪代码-续

下面对伪代码中的一些函数进行解释：

Enet：编码器网络
Pnet：带有 Dropout 的前向神经网络
steerTo：检查两个输入状态之间的连线是否均处于环境的无障碍区域中（采用 $\tau(\delta)=(1-\delta) x_{1}+\delta x_{2}$ 进行有限离散步的检查）
LazyStatesContraction：给定一个轨迹 $\left\{\boldsymbol{x}_{0}, \boldsymbol{x}_{1}, \cdots, \boldsymbol{x}_{T}\right\}$ ，算法连接可直接连接的不相邻结点，并去出中间结点
Replanner 包含以下两种方式：
- 神经网络重规划：首先使用规划网络规划一条粗糙路径，再不断重复调用规划网络重新规划路径中不可达（结点连线中包含障碍物）的子路径。
- 混合重规划：首先使用规划网络规划一条粗糙路径，再不断调用传统路径规划算法重新规划路径中不可达（结点连线中包含障碍物）的子路径

Neural Path Planning: Fixed Time, Near-Optimal Path Generation via Oracle Imitation

这篇文章同样是引入深度神经网络来提出了一个路径规划算法 OracleNet，其核心思想与上一篇论文类似（实际这两篇论文也是同一个团队的工作），也是采用模仿学习，这里模仿的是 A* 算法。但是这里不包含一个编码器网络，而是直接使用机器人观察到的状态，不使用障碍物的点云数据（因而本文提出的算法只适用于静态环境，但作者表明同样可采用 MPNet 的方式将 OracleNet 扩展到动态环境中，但是作者认为 MPNet 简单采用编码器的方式并没有学到一个高质量的嵌入表示，值得深入研究），并将前向神经网络改为一个四层的 LSTM 网络：

OracleNet网络结构

其在线规划流程的伪代码如下：

OracleNet在线路径规划

具体解释一下伪代码中的函数：

Repair：若当前规划出的路径点位于障碍物范围内，则在以当前路径点为圆心一定半径的圆周上随机选择新路径点，直到找到一个不位于障碍物范围内的路径点位置。接着使用这个新的路径点代替当前路径点，规划算法继续。
Rewire：类似 RRT* 算法中的 Rewire 算法。