Abracadabra

Do it yourself


  • Home

  • Categories

  • About

  • Archives

  • Tags

  • Sitemap

  • 公益404

  • Search
close
Abracadabra

策略梯度方法

Posted on 2019-04-14 | | Visitors

译者注:

本篇文章翻译自 Dr. Weng 的 博客。

翻译行为已得到原作者授权,转载请注明原作者。


摘要:在本文中,我们将深入探讨策略梯度算法的工作原理以及近年来提出的一些新的策略梯度算法:平凡策略梯度、演员评论家算法、离线策略演员评论家算法、A3C、A2C、DPG、DDPG、D4PG、MADDPG、TRPO、PPO、ACER、ACKTR、SAC以及TD3算法。

什么是策略梯度

策略梯度算法是一类解决强化学习问题的方法。如果你对于强化学习领域还不熟悉,请首先阅读这篇博客来对强化学习的问题定义以及核心概念进行初步了解。

符号

下面是一个符号列表,可以帮助您更轻松地理解本文中的公式。

符号含义
$s \in \mathcal{S}$状态。
$a \in \mathcal{A}$动作。
$r \in \mathcal{R}$回报。
$S_{t}, A_{t}, R_{t}$一个轨迹中第$t$个时间步对应的状态、动作以及回报。我可能会偶尔使用$s_{t}, a_{t}, r_{t}$来代替。
$\gamma$折扣因子;用于惩罚未来回报中的不确定性;$0<\gamma \leq 1$。
$G_{t}$累积回报;或者说累积折扣回报;$G_{t}=\sum_{k=0}^{\infty} \gamma^{k} R_{t+k+1}$。
$P\left(s^{\prime}, r\vert s, a\right)$在当前状态$s$下采取动作$a$后转移到下一个状态$s^{\prime}$并得到回报$r$的概率。
$\pi(a\vert s)$随机策略(智能体行为逻辑);$\pi_{\theta}( .)$代表由$\theta$参数化的策略。
$\mu(s)$确定性策略;虽然也可以把确定性策略记为$\pi(s)$,但是采用一个不同的字母可以让我们更容易分辨一个策略到底是确定性的还是随机的。$\pi$或者$\mu$都是强化学习算法要学习的目标。
$V(s)$状态-值函数衡量状态$s$的期望累积回报;$V_{w}( .)$代表由$w$参数化的状态-值函数。
$V^{\pi}(s)$当智能体遵循策略$\pi$时状态$s$的期望累积回报;$V^{\pi}(s)=\mathbb{E}_{a \sim \pi}\left[G_{t}\vert S_{t}=s\right]$。
$Q(s, a)$动作-值函数,与状态-值函数类似,但是它衡量在状态$s$下采取动作$a$后的期望累积回报;$Q_{w}( .)$代表由$w$参数化的动作-值函数。
$Q^{\pi}(s, a)$与$V^{\pi}(s)$类似,当智能体遵循策略$\pi$时,在状态$s$下采取动作$a$后的期望累积回报;$Q^{\pi}(s, a)=\mathbb{E}_{a \sim \pi}\left[G_{t}\vert S_{t}=s,A_{t}=a\right]$。
$A(s, a)$优势函数,$A(s, a)=Q(s, a)-V(s)$;可以认为优势函数是加强版本的动作-值函数,但是由于它采用状态-值函数作为基准使得它具有更小的方差。

策略梯度

强化学习的目标是为智能体找到一个最优的行为策略从而获取最大的回报。策略梯度方法主要特点在于直接对策略进行建模并优化。策略通常被建模为由$\theta$参数化的函数$\pi_{\theta}(a | s)$。回报(目标)函数的值受到该策略的直接影响,因而可以采用很多算法来对$\theta$进行优化来最大化回报(目标)函数。

回报(目标)函数定义如下:
$$
J(\theta)=\sum_{s \in \mathcal{S}} d^{\pi}(s) V^{\pi}(s)=\sum_{s \in \mathcal{S}} d^{\pi}(s) \sum_{a \in \mathcal{A}} \pi_{\theta}(a | s) Q^{\pi}(s, a)
$$
其中$d^{\pi}(s)$代表由$\pi_{\theta}$引出的马尔科夫链的平稳分布($\pi$下的在线策略状态分布)。


译者注:上述目标函数是在连续环境(没有固定的终止状态)下的目标函数(被称为平均值),在连续环境下还有一种性质更好的目标函数,叫做平均回报:
$$
\begin{aligned} J(\theta) \doteq r(\pi) & \doteq \lim _{h \rightarrow \infty} \frac{1}{h} \sum_{t=1}^{h} \mathbb{E}\left[R_{t} | S_{0}, A_{0 : t-1} \sim \pi\right] \\ &=\lim _{t \rightarrow \infty} \mathbb{E}\left[R_{t} | S_{0}, A_{0 : t-1} \sim \pi\right] \\ &=\sum_{s} \mu(s) \sum_{a} \pi_{\theta}(a | s) \sum_{s^{\prime}, r} p\left(s^{\prime}, r | s, a\right) r \end{aligned}
$$
在这种定义下,(差分)累积回报定义为回报与平均回报的差值的累加值:
$$
G_{t} \doteq R_{t+1}-r(\pi)+R_{t+2}-r(\pi)+R_{t+3}-r(\pi)+\cdots
$$
对应的还有差分状态-值函数以及差分-动作值函数:
$$
\begin{array}{l}
{V_{\pi}(s)=\sum_{a} \pi_{\theta}(a | s) \sum_{r, s^{\prime}} p\left(s^{\prime}, r | s, a\right)\left[r-r(\pi)+V_{\pi}\left(s^{\prime}\right)\right]} \\ {Q_{\pi}(s, a)=\sum_{r, s^{\prime}} p\left(s^{\prime}, r | s, a\right)\left[r-r(\pi)+\sum_{a^{\prime}} \pi_{\theta}\left(a^{\prime} | s^{\prime}\right) Q_{\pi}\left(s^{\prime}, a^{\prime}\right)\right]}\end{array}
$$
之所以说上述目标函数性质更好,是因为平均值目标函数其实只是它的另外一种形式,下面我们就来证明一下(Sutton&Barto,2017; Sec 10.4):
$$
\begin{aligned}
J(\theta)=&\sum_{s \in \mathcal{S}} d^{\pi}(s) V^{\pi}(s) \\
=& \sum_{s} d_{\pi}(s) \sum_{a} \pi_{\theta}(a | s) \sum_{s^{\prime}} \sum_{r} p\left(s^{\prime}, r | s, a\right)\left[r+\gamma V_{\pi}\left(s^{\prime}\right)\right] \\
=&\;r(\pi) + \sum_{s} d_{\pi}(s) \sum_{a} \pi_{\theta}(a | s) \sum_{s^{\prime}} \sum_{r} p\left(s^{\prime}, r | s, a\right)\gamma V_{\pi}\left(s^{\prime}\right) \\
=&\;r(\pi) + \gamma \sum_{s^{\prime}} V_{\pi}\left(s^{\prime}\right) \sum_{s} d_{\pi}(s) \sum_{a} \pi_{\theta}(a | s) p\left(s^{\prime} | s, a\right) \\
=&\;r(\pi) + \gamma\sum_{s^{\prime}}V_{\pi}(s^{\prime})d_{\pi}(s^{\prime}) \\
=&\;r(\pi) + \gamma J(\theta) \\
=&\;r(\pi) + \gamma r(\pi) + \gamma^{2}J(\theta) \\
=&\;r(\pi) + \gamma r(\pi) + \gamma^{2}r(\pi) + \gamma^{3}J(\theta) + \cdots \\
=&\;\frac{1}{1-\gamma}r(\pi)
\end{aligned}
$$
因而在下面进行策略梯度定理证明时,我们仅考虑平均回报形式的目标函数。

另一方面,在周期环境下的目标函数(不包含折扣因子)如下:
$$
J(\theta)=V^{\pi}(s_{0})
$$
之所以不在连续环境下也使用上述目标函数,是因为在连续环境下上述目标函数的值为无穷大,优化一个无穷大值是没有意义的。


为了简化符号,当策略作为其他函数的上标或者下标出现时$\pi_{\theta}$中的参数$\theta$将省略,例如:$d^{\pi}$以及$Q^{\pi}$的完整形式为$d^{\pi_{\theta}}$以及$Q^{\pi_{\theta}}$。想象一下你一直在马尔科夫链构成的状态序列中游荡,随着时间不断向前推进,你经过某个状态的概率将保持不变——这个概率就是$\pi_{\theta}$下的平稳概率。$d^{\pi}(s)=\lim _{t \rightarrow \infty} P\left(s_{t}=s | s_{0}, \pi_{\theta}\right)$就表示你从状态$s_0$开始,在策略$\pi_{\theta}$下经过$t$个时间步后到达状态$s$的概率。实际上,PageRank正是利用了马尔科夫链的平稳分布。你可以阅读这篇文章以获取更多细节。

我们可以很自然的预见到基于策略的方法能够很好地处理连续空间中的强化学习问题。因为在连续空间中存在无限多的动作及(或)状态因而基于值函数的算法由于需要去估计所有的动作及(或)状态的值导致其所需的算力变得无法接受。例如,在一般的策略迭代过程中,策略提升步骤$\arg \max _{a \in \mathcal{A}} Q^{\pi}(s, a)$需要去遍历整个动作空间,因而会遭受维度诅咒。

使用梯度上升方法,我们可以将参数$\theta$往梯度$\nabla_{\theta} J(\theta)$给出的方向进行改变从而去找到最优的$\theta$使得其对应的策略$\pi_{\theta}$能够给智能体带来最大的期望累积回报。

策略梯度定理

计算梯度$\nabla_{\theta} J(\theta)$可不是一件简单的事情。因为梯度值不仅依赖于动作的选择(由$\pi_{\theta}$直接决定),还依赖于由选择的动作而产生的状态的平稳分布(由$\pi_{\theta}$间接决定)。鉴于环境通常是未知的,很难去估计策略的更新对于状态分布造成的影响。

哇哦!这时候出现了策略梯度定理来拯救世界了!该定理对梯度的形式进行了变形使其不依赖于状态分布$d^{\pi}( .)$的导数,从而在很大程度上简化了梯度$\nabla_{\theta} J(\theta)$的计算:
$$
\begin{aligned}
\nabla_{\theta} J(\theta) &=\nabla_{\theta} \sum_{s \in \mathcal{S}} d^{\pi}(s) \sum_{a \in \mathcal{A}} Q^{\pi}(s, a) \pi_{\theta}(a | s) \\
&\propto \sum_{s \in \mathcal{S}} d^{\pi}(s) \sum_{a \in \mathcal{A}} Q^{\pi}(s, a) \nabla_{\theta} \pi_{\theta}(a \vert s) \end{aligned}
$$


译者注:这里策略梯度定理的形式不够完全,只考虑了目标函数为连续环境下的平均值形式,上述定理还同时适用于连续环境下的平均回报形式目标函数以及周期环境下的目标函数,即:
$$
\begin{aligned}
\nabla_{\theta} J(\theta) &\stackrel{\text{def}}{=} \nabla_{\theta} \sum_{s \in \mathcal{S}} d^{\pi}(s) \sum_{a \in \mathcal{A}} Q^{\pi}(s, a) \pi_{\theta}(a | s) & \scriptstyle{\text{连续环境下的平均值形式目标函数}} \\
&\stackrel{\text{def}}{=} \nabla_{\theta} \sum_{s\in\mathcal{S}} \mu(s) \sum_{a\in\mathcal{A}} \pi_{\theta}(a | s) \sum_{s^{\prime}\in\mathcal{S}, r} p\left(s^{\prime}, r | s, a\right) r & \scriptstyle{\text{连续环境下的平均回报形式目标函数}}\\
&\stackrel{\text{def}}{=} \nabla_{\theta} V^{\pi}(s_{0}) & \scriptstyle{\text{周期环境下的目标函数}}\\
& \propto \sum_{s \in \mathcal{S}} d^{\pi}(s) \sum_{a \in \mathcal{A}} Q^{\pi}(s, a) \nabla_{\theta} \pi_{\theta}(a | s) & \scriptstyle{}
\end{aligned}
$$


策略梯度定理的证明

现在我们要深入上述定理的证明(Sutton&Barto,2017; Sec 13.1(译者注:这里应该更改为Sec 13.2))从而理解为什么该定理的正确的,因而这部分会包含很多的数学公式。

我们首先从计算状态-值函数的梯度开始:
$$
\begin{aligned}
& \nabla_\theta V^\pi(s) \\
=& \nabla_\theta \Big(\sum_{a \in \mathcal{A}} \pi_\theta(a \vert s)Q^\pi(s, a) \Big) & \\
=& \sum_{a \in \mathcal{A}} \Big( \nabla_\theta \pi_\theta(a \vert s)Q^\pi(s, a) + \pi_\theta(a \vert s) \color{red}{\nabla_\theta Q^\pi(s, a)} \Big) & \scriptstyle{\text{; 微分乘法法则}} \\
=& \sum_{a \in \mathcal{A}} \Big( \nabla_\theta \pi_\theta(a \vert s)Q^\pi(s, a) + \pi_\theta(a \vert s) \color{red}{\nabla_\theta \sum_{s’, r} P(s’,r \vert s,a)(r + V^\pi(s’))} \Big) & \scriptstyle{\text{; 扩展} Q^\pi} \\
=& \sum_{a \in \mathcal{A}} \Big( \nabla_\theta \pi_\theta(a \vert s)Q^\pi(s, a) + \pi_\theta(a \vert s) \color{red}{\sum_{s’, r} P(s’,r \vert s,a) \nabla_\theta V^\pi(s’)} \Big) & \scriptstyle{; P(s’,r \vert s,a) \text{或者} r \text{不是}\theta \text{的函数}}\\
=& \sum_{a \in \mathcal{A}} \Big( \nabla_\theta \pi_\theta(a \vert s)Q^\pi(s, a) + \pi_\theta(a \vert s) \color{red}{\sum_{s’} P(s’ \vert s,a) \nabla_\theta V^\pi(s’)} \Big) & \scriptstyle{\text{; 因为 } P(s’ \vert s, a) = \sum_r P(s’, r \vert s, a)}
\end{aligned}
$$

现在我们有:
$$
{\color{red}{\nabla_\theta V^\pi(s)}}
= \sum_{a \in \mathcal{A}} \Big( \nabla_\theta \pi_\theta(a \vert s)Q^\pi(s, a) + \pi_\theta(a \vert s) \sum_{s’} P(s’ \vert s,a) \color{red}{\nabla_\theta V^\pi(s’)} \Big)
$$
上述等式拥有很好的递归特性(红色部分)因而未来状态的状态-值函数$V^{\pi}\left(s^{\prime}\right)$可以根据上式来递归地展开。让我们考虑一个下面这样的状态访问序列并将从状态$s$开始在策略$\pi_{\theta}$下经过$k$个时间步到达状态$x$的概率记为$\rho^{\pi}(s \rightarrow x, k)$:
$$
s \xrightarrow[]{a \sim \pi_\theta(.\vert s)} s’ \xrightarrow[]{a \sim \pi_\theta(.\vert s’)} s’’ \xrightarrow[]{a \sim \pi_\theta(.\vert s’’)} \dots
$$

对于不同的$k$值,$\rho^{\pi}(s \rightarrow x, k) $值包含以下几种情况:

  • 当$k=0$时:$\rho^{\pi}(s \rightarrow s, k=0)=1$。
  • 当$k=1$时,我们遍历在状态$s$下所有可能的动作$a$然后将所有从元组$(s,a)$转移到目标状态的概率累加:$\rho^{\pi}\left(s \rightarrow s^{\prime}, k=1\right)=\sum_{a} \pi_{\theta}(a | s) P\left(s^{\prime} | s, a\right)$。
  • 设想以下我们的目标是从状态$s$开始依照策略$\pi_{\theta} $经过$k+1$个时间步最终达到目标状态$x$。为了实现这个目标,我们可以先从状态$s$开始经过$k$个时间步后达到某个中间状态$s^{\prime} $(任何一个状态$s\in\mathcal{S}$均可成为中间状态)然后经过最后一个时间步到达目标状态$x$。这样的话,我们就可以递归地计算访问概率:$\rho^{\pi}(s \rightarrow x, k+1)=\sum_{s^{\prime}} \rho^{\pi}\left(s \rightarrow s^{\prime}, k\right) \rho^{\pi}\left(s^{\prime} \rightarrow x, 1\right)$。

有了以上的相关基础,我们就可以递归地展开$\nabla_\theta V^\pi(s)$!首先为了简化符号我们进行以下符号上的替换:$\phi(s)=\sum_{a \in \mathcal{A}} \nabla_{\theta} \pi_{\theta}(a | s) Q^{\pi}(s, a)$。如果我们不停地展开$\nabla_{\theta} V^{\pi}(\cdot)$,那么可以发现通过这个展开过程我们可以从状态$s$开始经过任意时间步后到达任意的状态,并且将上述过程中的访问概率累加起来就可以得到$\nabla_\theta V^\pi(s)$!
$$
\begin{aligned}
& \color{red}{\nabla_\theta V^\pi(s)} \\
=& \phi(s) + \sum_a \pi_\theta(a \vert s) \sum_{s’} P(s’ \vert s,a) \color{red}{\nabla_\theta V^\pi(s’)} \\
=& \phi(s) + \sum_{s’} \sum_a \pi_\theta(a \vert s) P(s’ \vert s,a) \color{red}{\nabla_\theta V^\pi(s’)} \\
=& \phi(s) + \sum_{s’} \rho^\pi(s \to s’, 1) \color{red}{\nabla_\theta V^\pi(s’)} \\
=& \phi(s) + \sum_{s’} \rho^\pi(s \to s’, 1) \color{red}{[ \phi(s’) + \sum_{s’’} \rho^\pi(s’ \to s’’, 1) \nabla_\theta V^\pi(s’’)]} \\
=& \phi(s) + \sum_{s’} \rho^\pi(s \to s’, 1) \phi(s’) + \sum_{s’’} \rho^\pi(s \to s’’, 2){\color{red}{\nabla_\theta V^\pi(s’’)}} \scriptstyle{\text{ ; 考虑将 }s’\text{ 作为 }s \to s’’}\text{的中间状态}\\
=& \phi(s) + \sum_{s’} \rho^\pi(s \to s’, 1) \phi(s’) + \sum_{s’’} \rho^\pi(s \to s’’, 2)\phi(s’’) + \sum_{s’’’} \rho^\pi(s \to s’’’, 3)\color{red}{\nabla_\theta V^\pi(s’’’)} \\
=& \dots \scriptstyle{\text{; 递归展开 }\nabla_\theta V^\pi(.)} \\
=& \sum_{x\in\mathcal{S}}\sum_{k=0}^\infty \rho^\pi(s \to x, k) \phi(x)
\end{aligned}上述
$$

上述变形使得我们无需计算Q-值函数的梯度$\nabla_\theta Q^\pi(s, a)$。将其带入目标函数$J(\theta)$中,可得:
$$
\begin{aligned}
\nabla_\theta J(\theta)
&= \nabla_\theta V^\pi(s_0) & \scriptstyle{\text{; 从一个随机状态 } s_0 \text{开始}} \\
&= \sum_{s}\color{blue}{\sum_{k=0}^\infty \rho^\pi(s_0 \to s, k)} \phi(s) &\scriptstyle{\text{; 令 }\color{blue}{\eta(s) = \sum_{k=0}^\infty \rho^\pi(s_0 \to s, k)}} \\
&= \sum_{s}\eta(s) \phi(s) & \\
&= \Big( {\sum_s \eta(s)} \Big)\sum_{s}\frac{\eta(s)}{\sum_s \eta(s)} \phi(s) & \scriptstyle{\text{; 正则化 } \eta(s), s\in\mathcal{S} \text{ 使其成为一个概率分布}}\\
&\propto \sum_s \frac{\eta(s)}{\sum_s \eta(s)} \phi(s) & \scriptstyle{\sum_s \eta(s)\text{ 是一个常数}} \\
&= \sum_s d^\pi(s) \sum_a \nabla_\theta \pi_\theta(a \vert s)Q^\pi(s, a) & \scriptstyle{d^\pi(s) = \frac{\eta(s)}{\sum_s \eta(s)}\text{ 即为平稳分布}}
\end{aligned}
$$


译者注:上述证明过程仅仅涉及周期环境,连续环境下的证明如下:
$$
\begin{aligned}
& \nabla_\theta V^\pi(s) \\
=& \nabla_\theta \Big(\sum_{a \in \mathcal{A}} \pi_\theta(a \vert s)Q^\pi(s, a) \Big) & \\
=& \phi(s) + \sum_{a \in \mathcal{A}} \Big( \pi_\theta(a \vert s) {\color{red}{\nabla_\theta Q^\pi(s, a)}} \Big) & \scriptstyle{\text{; 微分乘法法则}} \\
=& \phi(s) + \sum_{a \in \mathcal{A}} \Big( \pi_\theta(a \vert s) {\color{red}{\nabla_\theta \sum_{s’, r} P(s’,r \vert s,a)(r - r(\pi) + V^\pi(s’))}}\Big) & \scriptstyle{\text{; 扩展} Q^\pi} \\
=& \phi(s) + \sum_{a \in \mathcal{A}} \Big( \pi_\theta(a \vert s){\color{red}{\bigg[{\color{blue}{-\nabla_{\theta}r(\pi)}}+\sum_{s’, r} P(s’,r \vert s,a) \nabla_\theta V^\pi(s’)} \bigg]}\Big) & \scriptstyle{; P(s’,r \vert s,a) \text{或者} r \text{不是}\theta \text{的函数}}\\
=& \phi(s) + \sum_{a \in \mathcal{A}} \Big( \pi_\theta(a \vert s) {\color{red}{\bigg[{\color{blue}{-\nabla_{\theta}r(\pi)}}+\sum_{s’} P(s’ \vert s,a) \nabla_\theta V^\pi(s’)} \bigg]}\Big) & \scriptstyle{\text{; 因为 } P(s’ \vert s, a) = \sum_r P(s’, r \vert s, a)} \\
=& {\color{blue}{-\nabla_{\theta}r(\pi)}} + \phi(s) + \sum_{a \in \mathcal{A}} \Big( \pi_\theta(a \vert s) {\color{red}{\sum_{s’} P(s’ \vert s,a) \nabla_\theta V^\pi(s’)}}\Big)
\end{aligned}
$$

经过移项可得:
$$
\color{blue} {\nabla_{\theta}r(\pi)} =\phi(s) + \sum_{a}\left[\pi_{\theta}(a | s) \color{red} {\sum_{s^{\prime}} p\left(s^{\prime} | s, a\right) \nabla_{\theta} V^{\pi}\left(s^{\prime}\right)} \right]-\nabla_{\theta} V^{\pi}(s)
$$
那么平均回报形式的目标函数的梯度有:
$$
\begin{aligned}
\nabla_{\theta}J(\theta) =&\;\nabla_{\theta} r(\pi) \\
=& \sum_{s} d^{\pi}(s)\left(\phi(s) + \sum_{a}\left[\pi_{\theta}(a | s) \sum_{s^{\prime}} p\left(s^{\prime} | s, a\right) \nabla_{\theta} V^{\pi}\left(s^{\prime}\right)\right]-\nabla_{\theta} V^{\pi}(s)\right) \\
=& \sum_{s} d^{\pi}(s) \phi(s) +\sum_{s} d^{\pi}(s) \sum_{a} \pi_{\theta}(a | s) \sum_{s^{\prime}} p\left(s^{\prime} | s, a\right) \nabla_{\theta} V^{\pi}\left(s^{\prime}\right)-\sum_{s} d^{\pi}(s) \nabla_{\theta} V^{\pi}(s) \\
=& \sum_{s} d^{\pi}(s) \phi(s) + \sum_{s^{\prime}} \underbrace{\sum_{s} d^{\pi}(s) \sum_{a} \pi_{\theta}(a|s) p\left(s^{\prime}|s,a\right)}_{d^{\pi}\left(s^{\prime}\right)} \nabla_{\theta} V^{\pi}\left(s^{\prime}\right)-\sum_{s} d^{\pi}(s) \nabla_{\theta} V^{\pi}(s) \\
=& \sum_{s} d^{\pi}(s) \phi(s) + \sum_{s^{\prime}} d^{\pi}(s^{\prime}) \nabla_{\theta} V^{\pi}\left(s^{\prime}\right)-\sum_{s} d^{\pi}(s) \nabla_{\theta} V^{\pi}(s) \\
=& \sum_{s} d^{\pi}(s) \phi(s) \\
=& \sum_s d^\pi(s) \sum_a Q^\pi(s, a)\nabla_\theta\pi_\theta(a \vert s) \\
\propto& \sum_s d^\pi(s) \sum_a Q^\pi(s, a)\nabla_\theta \pi_\theta(a \vert s)
\end{aligned}
$$
其中第二个等式成立是因为$\nabla_{\theta}r(\pi)$不依赖$s$且$\sum_{s}d^{\pi}(s)=1$。

另外,平均值形式的目标函数的梯度有:
$$
\begin{aligned}
\nabla_{\theta}J(\theta) =&\;\nabla_{\theta}\sum_{s \in \mathcal{S}} d^{\pi}(s) V^{\pi}(s) \\
=&\;\nabla_{\theta} \sum_{s \in \mathcal{S}} d^{\pi}(s) \sum_{a \in \mathcal{A}} Q^{\pi}(s, a) \pi_{\theta}(a | s)\\
=&\;\frac{1}{1-\gamma}\nabla_{\theta} r(\pi) \\
=&\;\frac{1}{1-\gamma}\left(\sum_s d^\pi(s) \sum_a Q^\pi(s, a)\nabla_\theta\pi_\theta(a \vert s)\right) \\
\propto& \sum_s d^\pi(s) \sum_a Q^\pi(s, a)\nabla_\theta \pi_\theta(a \vert s)
\end{aligned}
$$


梯度还可以改写为如下形式:
$$
\begin{aligned}
\nabla_\theta J(\theta)
&\propto \sum_{s \in \mathcal{S}} d^\pi(s) \sum_{a \in \mathcal{A}} Q^\pi(s, a) \nabla_\theta \pi_\theta(a \vert s) &\\
&= \sum_{s \in \mathcal{S}} d^\pi(s) \sum_{a \in \mathcal{A}} \pi_\theta(a \vert s) Q^\pi(s, a) \frac{\nabla_\theta \pi_\theta(a \vert s)}{\pi_\theta(a \vert s)} &\\
&= \mathbb{E}_\pi [Q^\pi(s, a) \nabla_\theta \ln \pi_\theta(a \vert s)] & \scriptstyle{\text{; 因为 } (\ln x)’ = 1/x}
\end{aligned}
$$
$\mathbb{E}_{\pi}$代表$\mathbb{E}_{s \sim d_{\pi}, a \sim \pi_{\theta}}$,下标表示遵循策略$\pi_{\theta}$(在线策略)时状态以及动作的分布。

上述策略梯度定理是许多策略梯度算法的理论基础。平凡策略梯度算法由于直接使用采样得到的回报所以其估计的梯度不存在偏差(bias)但是有较大的方差(variance)(见下式)。因此后续的算法被相继提出用以在保持偏差有界的情况下减小方差。
$$
\nabla_{\theta} J(\theta)=\mathbb{E}_{\pi}\left[Q^{\pi}(s, a) \nabla_{\theta} \ln \pi_{\theta}(a | s)\right]
$$
这里有一个从GAE(泛化优势估计,genaral advantage estimate)论文 (Schulman et al., 2016)中引用的很好的策略梯度算法一般形式的归纳,并且这篇博客深入探讨了GAE的几大组成部分,值得一读。

图1. 策略梯度方法的一般形式。图片来源:[Schulman et al., 2016](https://arxiv.org/abs/1506.02438)

Read more »
Abracadabra

Guided Policy Search(GPS)

Posted on 2019-04-06 | | Visitors

一篇因为各种突发状况断断续续写了将近两周的文章 = =


这篇博客将介绍GPS方法,GPS方法是由强化学习大牛Sergey Levine(在最近的ICLR 2019发表了13篇论文)于2013年提出的,目前被作为基础算法广泛应用于各种强化学习任务中。其出发点在于纯粹的策略梯度方法在更新参数时不会用到环境模型因而属于一种无模型强化学习算法,所谓成也萧何败也萧何,虽然这使得策略梯度方法通用性很好,但是由于没有利用到任何环境的内在属性,使得其训练只能完全依靠试错,效率较低。

基于模型的路径优化算法(例如前面博客里提到的iLQR)方法,能够充分利用环境模型,从而在利用较少训练样本的情况下即可使得算法收敛到局部最优解。但是路径优化算法是一个开环方法,在随机环境下效果较差,虽然能够通过使用MPC方法(基本思想是每次只执行路径优化算法输出的第一个时间步的动作)来增加算法的稳定性,但是执行时耗时较长无法适用于实时任务。但是策略梯度方法是一个闭环方法,因而其对于随即环境的适应能力以及执行耗时上都能达到很好的效果。因而一个直观的想法是,能不能将两者结合起来,用路径优化算法的输出结果来指导策略梯度方法的训练过程,从而提升策略梯度方法的效率呢?GPS方法正是基于这种思想提出的。

本文主要对早期GPS的三篇论文进行了总结(还包括了一些其他论文的相关结论),具体请参阅文末的参考文献。文章的结构如下:第一部分将会对最原始的GPS方法进行介绍,第二部分将会介绍一个改进版本。注意,这两种版本的GPS算法都必须事先已知环境模型。第三部分将介绍一个在未知环境模型(需要在算法训练的过程中对环境模型进行局部估计)的情况下也能够使用的GPS算法。以上三种GPS算法均属于基于模型的强化学习算法(以后我将专门写一篇文章来介绍基于模型的强化学习算法)。为了方便起见,我将最原始的GPS算法记为GPS-V1(ICML2013)[^2],改进版记为GPS-V2(ICML2014)[^3],最后一个版本记为GPS-V3(NIPS2014)[^4]。

GPS-V1

原始版本的GPS算法基本思想是首先使用路径优化算法产生一些训练数据并加入训练集中用以指导后续策略梯度方法的训练。但是策略梯度方法是在线策略算法,只能使用当前策略采样得到的数据来估计梯度从而更新参数。为了能够使用其他策略采样的数据,这里必须要使用一种技术:重要性采样。在这里我首先跑一下题来介绍一下重要性采样。

重要性采样

对于一个函数$f$以及一个概率分布$P$,我们想要计算如下统计量:
$$
\mathbf{E}_{P(X)}[f(X)]=\int_{x}P(x)f(x)dx.
$$
我们知道,一般估计一个期望值的方法是从变量从属的概率分布中进行采样,然后计算均值。但是实际上概率分布$P$可能非常复杂,我们没有办法从其中进行采样。重要性采样方法通过从另外一个较为简单的分布$Q$中采样出的样本对以上期望值进行估计:
$$
\begin{align}
\mathbf{E}_{P(X)}[f(X)]&=\mathbf{E}_{Q(X)}\left[\frac{P(X)}{Q(X)}f(X)\right] \\
&\approx \frac{1}{m}\sum_{i=1}^m \frac{P(x^{(i)})}{Q(x^{(i)})}f(x^{(i)})\;\;\text{with}\;\;x^{(i)}\sim Q.
\end{align}
$$

基于重要性采样的策略梯度方法

让我们回到正题,利用这种方法就可以在估计当前正在学习的策略的梯度时采用其他策略采样出的样本:
$$
\mathbf{E}[J(\theta)]\approx\sum_{t=1}^T \frac{1}{Z_t(\theta)}\sum_{i=1}^m \frac{\pi_{\theta}(\tau_{i,1:t)}}{q(\tau_{i,1:t})}r(x_t^i,u^i_t),
$$
其中$Z_t(\theta)=\sum_{i=1}^m\frac{\pi_{\theta}(\tau_{i,1:t)}}{q(\tau_{i,1:t})}$。从理论上来说$Z_t(\theta)=m$才是期望的无偏估计,这里为了减小训练时的方差采用了这个特殊值。但是我们是在其他策略采样出的样本分布的基础上进行新策略的搜索,一旦新策略的样本分布与采样样本分布相距较远时,无法保证估计梯度的准确性。前面有工作是通过计算重要性权重的方差来判断新策略的准确性的[^6],但是对于很长的路径,重要性权重在大部分地方都为0,方差也很小,但是并不能说明什么问题。V1版本的GPS算法通过在优化目标上额外加入重要性权重的对数值的方式,来“软最大化”重要性权重值,毕竟重要性权重越大,代表新策略分布与采样分布更为接近(但其实在采样分布概率较小的地方新策略分配一个较大的概率也会使得这个值比较大,所以感觉这种方法还是有很大缺陷的):
$$
\Phi(\theta)=\sum_{t=1}^{T}\left[\frac{1}{Z_{t}(\theta)} \sum_{i=1}^{m} \frac{\pi_{\theta}\left(\zeta_{i, 1 : t}\right)}{q\left(\zeta_{i, 1 : t}\right)} r\left(\mathbf{x}_{t}^{i}, \mathbf{u}_{t}^{i}\right)+w_{r} \log Z_{t}(\theta)\right].
$$

指导样本的生成

GPS系列算法希望使用路径优化算法生成的指导样本来引导策略梯度算法往高回报的区域搜索(而非暴力试错)。在之前的文章中我们讲过iLQR算法,但是只展开讲了确定性情况下的相关知识。而策略梯度算法的应用场景大部分都是非确定性场景,即使是确定性场景,也会因为噪声的存在使其实际上同样是非确定性的。因而,下面我们主要关注非确定性场景下的指导样本生成。

在非确定性条件下,指导样本将服从某个概率分布,我们希望这个概率分布满足以下两个性质:

  1. 各区域的概率密度不要过大(否则会使得重要性权重较小,使得指导样本对于梯度的贡献很小)
  2. 该分布要尽可能覆盖高回报区域

GPS-V1的作者发现,如果指导样本的分布$q$是分布$\rho(\zeta) \propto \exp (r(\zeta))$的I-投影,即最小化如下KL散度:
$$
D_{\mathrm{KL}}(q | \rho)=E_{q}[-r(\zeta)]-\mathcal{H}(q),
$$
得到的分布$q$即可满足以上两个性质。具体来说,上式右边第一部分保证了性质2,右边第二部分保证了性质1。那么剩余的问题是分布$q$的具体形式是什么呢?GPS-V1假设分布$q$是一个高斯分布,这是一个很自然的也是最容易想到的假设。而且如果我们希望能够用只能解决非随机环境的路径优化算法例如iLQR来解决随即环境下的规划问题的话,只能假设$q$为高斯分布。

为了能够直接使用类似iLQR算法的路径优化算法,我们这里再引入另外一个概念或者一个框架,叫做线性可解马尔科夫决策过程(LMDP)[^5]。该框架的核心思想在于,摒弃动作(action)的概念。智能体在不断优化其策略的过程中,会通过动作来改变其自身的状态转移概率(即在一个状态下转移到下一个状态的概率,策略在不断优化,那么每个状态下采取的动作也会变化,因而状态转移概率也会发生变化)。那么为何不放弃这一间接的做法,将策略直接定义为状态转移概率呢?即:

$$
p\left(x^{\prime} | x, u\right)=u\left(x^{\prime} | x\right)
$$
这就是LMDP的核心思想(这部分牵涉的知识较广,我同样会之后单独写一篇文章来详细介绍)。在LMDP的框架下,其回报函数变成如下形式:
$$
\tilde{r}\left(\mathbf{x}_{t}, \mathbf{u}_{t}\right)=r\left(\mathbf{x}_{t}, \mathbf{u}_{t}\right)-D_{\mathrm{KL}}\left(\pi_{\mathcal{G}}\left(\cdot | \mathbf{x}_{t}\right) | p\left(\cdot | \mathbf{x}_{t}\right)\right),
$$
其中$\pi_{\mathcal{G}}$代表学习到的策略(即学习到的状态转移概率),$p$代表智能体在没有任何算法控制的情况下的状态转移概率。当$p$表示一个均匀分布时,上式可转化为:
$$
E_{\pi_{\mathcal{G}}}[\tilde{r}(\zeta)]=E_{\pi_{\mathcal{G}}}[r(\zeta)]+\mathcal{H}\left(\pi_{\mathcal{G}}\right).
$$
因而求解一个LMDP得到的指导样本的概率分布是满足前面提到的两个性质的。另外,可以证明,当状态转移是线性以及回报函数是二次函数的情况下,最优策略可以直接通过iLQR算法求解并且求解出的最优策略服从以下高斯分布:
$$
\pi_{\mathcal{G}}\left(\mathbf{u}_{t} | \mathbf{x}_{t}\right)=\mathcal{G}\left(\mathbf{u}_{t} ; g\left(\mathbf{x}_{t}\right),-Q_{\mathbf{u u} t}^{-1}\right).
$$
$g(\mathbf{x}_t)$代表确定环境下运用iLQR算法得出的最优策略,$Q_{\mathbf{u u} t}^{-1}$代表确定环境下运行iLQR算法中的参数,具体参见iLQR算法。值得注意的是,由于LMDP并没有动作这一概念,之所以可以得出以上结论,是采用LMDP估计MDP得出的结论,具体细节我会单独写一篇文章细讲。这里得出的结论是什么意思呢?其实就是说在运行iLQR算法时,将前向循环中计算最优动作的过程转化为从以上高斯分布中采样,然后将优化目标从仅仅最小化(或最大化)损失函数(或回报函数)转变为同时最大化最优策略的熵即可即可。这样导出的指导样本就满足我们的要求。

还有一个问题是$\pi_{\mathcal{G}}$只有在状态转移是线性的情况下才是一个高斯分布,在状态转移是非线性的情况下,$\pi_{\mathcal{G}}$是指导样本分布的一个局部的高斯估计。由于GPS算法需要通过指导样本来将策略搜索的方向引导向高回报区域(这个高回报区域就是采样出指导样本的高斯分布的均值区域),但是这个分布只在指导样本附近是准确的,离得比较远就会出现较大误差,但是策略搜索的区域是任意的,就会出现梯度估计不准确的现象。以上问题其实已经缓解了,前面提到的改进版的梯度公式中的正则项保证了策略搜索的区域会靠近指导样本的区域:
$$
\Phi(\theta)=\sum_{t=1}^{T}\left[\frac{1}{Z_{t}(\theta)} \sum_{i=1}^{m} \frac{\pi_{\theta}\left(\zeta_{i, 1 : t}\right)}{q\left(\zeta_{i, 1 : t}\right)} r\left(\mathbf{x}_{t}^{i}, \mathbf{u}_{t}^{i}\right)+w_{r} \log Z_{t}(\theta)\right].
$$

适应性指导样本分布

我们的策略是用某个特定的函数来进行估计的,而函数的表示能力是有限的(即使是神经网络,不同网络层数以及神经元个数都会对网络的表示能力产生影响。而所谓的通用函数估计器是在神经元个数无限的情况下才成立),那么强行让学习策略的分布与知道样本的分布尽可能一致可能会导致一些问题。考虑下面这种情况:指导样本是在了解模型的情况下进行决策的,而策略梯度算法是在不知道模型的情况下进行决策的。因而前者除了观察到的状态外还利用了环境模型的信息,在相似的观察下可能会进行差异较大的决策。换句话讲,策略函数要尝试去拟合一些相似输入产生不同输出的数据点,这就会使得算法训练起来十分困难。

目前的算法流程是在算法初始化时就使用iLQR算法产生大量的指导样本,之后就不再产生新的指导样本了。为了解决以上问题,在策略不断更新的过程中,重新根据以下这个新的回报函数来运行iLQR算法产生新的指导样本:
$$
\overline{r}\left(\mathbf{x}_{t}, \mathbf{u}_{t}\right)=r\left(\mathbf{x}_{t}, \mathbf{u}_{t}\right)+\log \pi_{\theta}\left(\mathbf{u}_{t} | \mathbf{x}_{t}\right).
$$
通过以上回报函数产生的指导样本会尝试产生策略函数能够产生的样本分布。

算法框架

GPS-V1的整体流程如下图所示:

GPS-V1

这里有几点细节需要说明。

  1. 算法第6行选取训练样本,其实主要包括以下两种样本。第一种,全部的指导样本;第二种,重要性权重较大的新样本,权重较大代表与指导样本更为相似。
  2. 第7行进行参数更新时,是从上一步最优的参数作为初始点进行更新的。但是有时算法会陷入到局部最优解中,使得在该局部最优解下指导样本的重要性权重较小,那么指导样本就对梯度的估计无法产生影响,这样就会使得算法进一步往更差的方向更新。为了防止以上问题,这一步的参数更新从两个不同的初始点开始:第一个初始点就是上一步更新的结果;而第二个则是求得一个使得当前采集到的回报较高的样本重要性权重最大的参数当作初始化参数。
  3. 关于第11-17行,具体解释以下为什么要采取这些操作。当新搜索到的策略比原先的策略要好时,适当减小约束项的权重,这样可以增大下一步的策略搜索范围,换句话说就是可以步子迈得大一些;反之,如果新搜索到的策略比上一步的要差,那么可能目前处于一个局部最优解较多的区域内,或者搜索区域过大使得梯度估计得不准确,这时候应该适当缩小搜索范围,在更接近指导样本的区域内搜索。再者,如果这样还是不能搜索到更好的策略,那么可能就是采样出的训练样本不好,这时候可以尝试重新采样。

以上就是GPS-V1算法的全部内容。其实在理解GPS-V1算法之后,后面两个版本就很简单了,因此我下面的内容相对也会少很多。

GPS-V2

作者在GPS-V1算法里发现了一个问题,其实V1算法也尝试去解决这个问题但是效果不好,这个问题就是1.4节中所描述的问题。基于模型的路径优化算法产生的指导样本,不基于模型的策略梯度方法有时候并不能拟合出来,就像在上一节中讲到的那样,策略梯度算法观察不到一些通过模型才能反应出来的因素。这样会使得对于复杂问题学习出来的样本分布并不能与指导样本分布符合的很好。GPS-V2从另外一个角度解决了上述问题,即完全抛弃了策略梯度步骤,直接让策略通过对指导样本进行监督学习得出,并且在路径优化算法更新时考虑到与当前策略的距离并且尝试使得这个距离尽可能小。通过这样一种迭代更新的流程来使得两者最终匹配。

上述思想其实GPS-V1部分的1.4节已经考虑到了,但是是通过改变回报函数的方式达到的。GPS-V2通过一种更直接的方式来建模,并抛弃了策略梯度部分,通过更加鲁棒的监督学习来学习策略,使得算法更新更为稳定。具体来说,GPS-V2求解以下优化问题:
$$
\begin{align} \min _{\theta, q(\tau)} & D_{\mathbf{KL}}(q(\tau) | \rho(\tau)) \\ \text { s.t. } & q\left(\mathbf{x}_{1}\right)=p\left(\mathbf{x}_{1}\right) \nonumber \\ & q\left(\mathbf{x}_{t+1} | \mathbf{x}_{t}, \mathbf{u}_{t}\right)=p\left(\mathbf{x}_{t+1} | \mathbf{x}_{t}, \mathbf{u}_{t}\right) \nonumber \\ & D_{\mathrm{KL}}\left(q\left(\mathbf{x}_{t}\right) \pi_{\theta}\left(\mathbf{u}_{t} | \mathbf{x}_{t}\right) | q\left(\mathbf{x}_{t}, \mathbf{u}_{t}\right)\right)=0. \nonumber \end{align}
$$
其中第一个和第二个约束在路径优化算法运行的过程中已经默认保证了,实际我们只需要考虑第三个约束。注意优化目标就是GPS-V1中提到的I-projection,只不过这里没有展开。我们采用拉格朗日乘子法(或者扩展拉格朗日乘子法)将上述问题转化为一个无约束优化问题:
$$
\begin{align} \mathcal{L}(\theta, q, \lambda)=& D_{\mathrm{KL}}(q(\tau) | \rho(\tau))+\nonumber\\ & \sum_{t=1}^{T} \lambda_{t} D_{\mathrm{KL}}\left(q\left(\mathbf{x}_{t}\right) \pi_{\theta}\left(\mathbf{u}_{t} | \mathbf{x}_{t}\right) | q\left(\mathbf{x}_{t}, \mathbf{u}_{t}\right)\right). \end{align}
$$
而对于上述优化问题,我们可以采用对偶梯度下降法(DGD,或者交替方向乘子法,ADMM)分别更新三部分的参数。而对偶变量通过以下公式更新:
$$
\lambda_{t} \leftarrow \lambda_{t}+\eta D_{\mathrm{KL}}\left(q\left(\mathbf{x}_{t}\right) \pi_{\theta}\left(\mathbf{u}_{t} | \mathbf{x}_{t}\right) | q\left(\mathbf{x}_{t}, \mathbf{u}_{t}\right)\right).
$$
可以看出更新$q$其实就是在采用路径优化算法,更新$\theta$时就是在做监督学习。最后给出算法流程:

GPS-V2

GPS-V3

其实我觉得最实用的还是V3版本的GPS算法,因为对于大部分现实问题,环境模型对与算法设计者来说都是未知的。但是前两个版本的GPS算法都假设环境模型是已知的(这样才能运行路径优化算法)。GPS-V3算法尝试解决事先未知环境模型场景下的相关问题,其实其基本思想也很直接,未知模型那我就估计模型,只不过全局模型肯定是很难估计准确的,而且要采用类似iLQR这种路径优化算法要对模型进行线性近似,因而更加不可能采用全局模型了。GPS-V3通过估计局部模型来缓解上述问题,但是采用局部模型又会引入类似GPS-V1这样的问题,在搜索区域距离当前样本过远时,算法误差就会较大,因而GPS-V3在GPS-V2的基础上再加了一个约束来解决这个问题。

具体来说,GPS-V1是解决如下优化问题来产生指导样本的:
$$
p(\tau)=\arg \min _{p(\tau) \in \mathcal{N}(\tau)} E_{p}[\ell(\tau)]-\mathcal{H}(p(\tau)) \text { s.t. } p\left(\mathbf{x}_{t+1} | \mathbf{x}_{t}, \mathbf{u}_{t}\right)=\mathcal{N}\left(\mathbf{x}_{t+1} ; f_{\mathbf{x} t} \mathbf{x}_{t}+f_{\mathbf{u} t} \mathbf{u}_{t}, \mathbf{F}_{t}\right).
$$
然后我们先转回到最原始iLQR算法的优化目标,不过因为这个时候我们是用估计的局部模型来运行该算法的,我们加上如下KL散度的约束来使得搜索范围不会离当前样本太远:
$$
\min _{p(\tau) \in \mathcal{N}(\tau)} E_{p}[\ell(\tau)] \text { s.t. } D_{\mathrm{KL}}(p(\tau) | \hat{p}(\tau)) \leq \epsilon.
$$
接下来同样采用拉格朗日乘子法(或者扩展拉格朗日乘子法)将其转变为无约束问题:
$$
\mathcal{L}_{\text { traj }}(p(\tau), \eta)=E_{p}[\ell(\tau)]+\eta\left[D_{\mathrm{KL}}(p(\tau) | \hat{p}(\tau))-\epsilon\right].
$$
将上式中的KL散度展开:
$$
\mathcal{L}_{\mathrm{traj}}(p(\tau), \eta)=\left[\sum_{t} E_{p\left(\mathbf{x}_{t}, \mathbf{u}_{t}\right)}\left[\ell\left(\mathbf{x}_{t}, \mathbf{u}_{t}\right)-\eta \log \hat{p}\left(\mathbf{u}_{t} | \mathbf{x}_{t}\right)\right]\right]-\eta \mathcal{H}(p(\tau))-\eta \epsilon.
$$
和GPS-V1的优化问题对比,我们可以发现一个优秀的巧合,我们只需要对上式两边除以$\eta$,并将回报函数转变一下:$\tilde{\ell}\left(\mathbf{x}_{t}, \mathbf{u}_{t}\right)=\frac{1}{\eta} \ell\left(\mathbf{x}_{t}, \mathbf{u}_{t}\right)-\log \hat{p}\left(\mathbf{u}_{t} | \mathbf{x}_{t}\right)$,就可以直接采用GPS-V1一样的方法产生指导样本。再将GPS-V2算法引入进来:
$$
\begin{align} \mathcal{L}(\theta, q, \lambda)=& \mathcal{L}_{\mathrm{traj}}(p(\tau), \eta) +\nonumber\\ & \sum_{t=1}^{T} \lambda_{t} D_{\mathrm{KL}}\left(q\left(\mathbf{x}_{t}\right) \pi_{\theta}\left(\mathbf{u}_{t} | \mathbf{x}_{t}\right) | q\left(\mathbf{x}_{t}, \mathbf{u}_{t}\right)\right). \end{align}
$$
对于上式同样采用GPS-V2一样的DGD方法(或者ADMM算法)求解即可。具体流程如下:

GPS-V3

这里需要再提一点,关于估计局部模型采用的方法。由于局部模型是一个高斯分布,我们其实只要去估计其均值即可(方差设定为$Q_{\mathbf{u u} t}^{-1}$)。而均值又是个线性函数,其实只要估计两个梯度即可:
$$
p\left(\mathbf{x}_{t+1} | \mathbf{x}_{t}, \mathbf{u}_{t}\right)=\mathcal{N}\left(\mathbf{A}_{t} \mathbf{x}_{t}+\mathbf{B}_{t} \mathbf{u}_{t}+\mathbf{c}, \mathbf{N}_{t}\right) \quad \mathbf{A}_{t} \approx \frac{d f}{d \mathbf{x}_{t}} \quad \mathbf{B}_{t} \approx \frac{d f}{d \mathbf{u}_{t}}
$$
因而可以用简单的线性回归方法。当然,对于较复杂的问题,一般会采用贝叶斯线性回归,选用高斯过程、深度网络或者高斯混合模型作为贝叶斯先验(这部分有机会我也会展开讲一讲)。

总结

最后,我引用[^1]文中的一段文字来总结GPS算法的核心思想:

Since each trajectory-centric teacher only needs to solve the task from a single initial state, it is faced with a much easier problem. The final policy is trained with supervised learning, which allows us to use a nonlinear, high-dimensional representation for this final policy, such as a multilayer neural network, in order to learn complex behaviors with good generalization. A key component in guided policy search is adaptation between the trajectories produced by the teacher and the final policy. This adaptation ensures that, at convergence, the teacher does not take actions that the final policy cannot reproduce. This is realized by an alternating optimization procedure, which iteratively optimizes the policy to match each teacher, while the teachers adapt to gradually match the behavior of the final policy.

参考文献

[^1]: Zhang, Marvin, et al. “Learning deep neural network policies with continuous memory states.” 2016 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2016.

[^2]: Levine, Sergey, and Vladlen Koltun. “Guided policy search.” International Conference on Machine Learning. 2013.

[^3]: Levine, Sergey, and Vladlen Koltun. “Learning complex neural network policies with trajectory optimization.” International Conference on Machine Learning. 2014.

[^4]: Levine, Sergey, and Pieter Abbeel. “Learning neural network policies with guided policy search under unknown dynamics.” Advances in Neural Information Processing Systems. 2014.

[^5]: Dvijotham, Krishnamurthy, and Emanuel Todorov. “Inverse optimal control with linearly-solvable MDPs.” Proceedings of the 27th International Conference on Machine Learning (ICML-10). 2010.

[^6]: Jie, Tang, and Pieter Abbeel. “On a connection between importance sampling and the likelihood ratio policy gradient.” Advances in Neural Information Processing Systems. 2010.

Abracadabra

How to make an optimal decision in the case of knowing the environment model(CS294 lecture notes) ?

Posted on 2019-03-25 | | Visitors

首先我们假设环境是确定性的,即在某个状态执行某个动作之后,转移到的下一个状态是确定的,不存在任何随机性。而在这种情况下,我们想做的是在环境给了我们一个初始状态的条件下,根据我们需要完成的任务以及环境模型,直接得出从初始状态到任务完成状态中间最优的动作序列。因为环境是确定的,而我们又已知环境模型,因而以上想法是自然且可行的。下图展示了我们想做的事情:

目标任务

现在我们将以上问题抽象成一个正式的优化问题:

优化目标

其中$f$就代表环境模型。但是一旦环境不再是确定的,即正在某个状态执行某个动作之后,转移到的下一个状态是从一个状态分布中随机采样的。对于这种情况,上述的优化问题就会转变为最大化如下形式的期望值:

期望优化目标

但是在随机环境下,解决与确定环境的类似的如上优化问题并不能得到与确定环境一样的最优解。原因在于我们只接受环境反馈回来的初始状态,接着便凭借着我们掌握的环境模型在脑海中进行规划。这种方法在确定环境下没有任何问题,但在随机环境下,智能体实际会转移到的状态可能并不符合我们的预期,因为它是从一个条件状态分布中随机采样的。而一旦从某一个状态开始与我们的预期产生偏差,那么后续的所有状态都会产生偏差,而我们设想的最优动作序列便不是最优了。从优化函数的角度来看,我们优化的只是一个期望值,而不是某一次随机采样的值。

我们把上述解决问题的方法叫做开环方法,与之对应的叫做闭环方法。那么这个“环”具体是指什么呢?具体示意图如下:

环

开环方法是只在最开始时接收环境反馈的初始状态,然后开始规划从开始到任务完成的过程中所经历的所有状态对应的最优动作,并不需要一个基于状态产生动作的策略;反之,闭环方法在每一个时间步都会接收环境反馈的状态,然后利用一个根据状态输出动作的策略来产生一个动作。我们可以看出,对于一个随机环境,闭环方法显然比开环方法更具优势,因为其可以根据所处的状态随时调整自己的动作。

但接下来我们还是首先假定一个确定性的环境,因而采用开环方法来解决上述问题。下面将介绍三种优化方法:随机优化方法、蒙特卡洛树搜索法以及轨迹优化方法。

随机优化方法

对于随机优化方法来讲,上述优化问题可以简化为如下等价优化问题:

随机优化目标

随机优化方法完全不关系优化目标的特殊结构等信息,而是把任何优化问题都当作上图右半边这样的一般优化问题。

随即发射方法

最简单的随机优化方法就是随机瞎猜,即随机选择一个动作序列,然后评估其累积的代价。如上过程不断进行,最后选择一个累积代价最小的动作序列作为上述优化问题的最优解,因而这类方法也叫做“随机发射方法”:

随机发射方法

CMA算法

但是这种方法在相对高维的情况下效率会很低,因为搜索空间太大但是目标区域比较小。回顾一下上述方法,我们可以在采样分布上做些文章。假设第一次从一个均匀分布采样一些动作序列之后,得到的累积代价分别为如下情况:

随机采样

那么下一次我们可以不再继续从一个均匀分布中采样了,我们可以聚焦于累积代价较小(累积回报较大)的区域,然后估计那个区域的分布,在这里我们假设分布是一个高斯分布:

估计分布

接下来的采样我们就从这个新的分布中进行采样:

新的采样结果

然后在下一次采样之前,我们再次聚焦于性能更好的区域然后估计其分布:

再次估计分布

就这样不断迭代,直到满足停止条件。以上方法就是Cross-Entropy Method(CEM)算法,其伪代码如下:

CEM算法

该方法还有个进阶版的算法叫做CMA-ES算法,后者可以看作是CMA算法带动量的版本。CMA算法会直接舍弃之前采样的数据点,但是CMA-ES算法会保留部分之前采样的数据点的相关信息,用来指导后续的采样。可以类比一下梯度下降法以及带动量的梯度下降法。

总结

随机优化方法具有以下优点:

  • 并行化后效率极高
  • 实现起来十分简单

但是也存在如下不可避免地缺点:

  • 极易受到维度灾难的影响
  • 只适用于开环情形

随即优化方法虽然可以同时适用于连续变量以及离散变量的情况,但不是专门为离散情况设计的。下面我们将介绍一种专门为离散动作空间设计的强大的优化方法(严格来讲叫做启发式搜索算法):蒙特卡洛树搜索MCTS方法。

蒙特卡洛树搜索算法

MCTS方法本质是一个搜索算法:

搜索算法

假设我们想要训练一个智能体能够自动去玩上面这个游戏(击沉敌方潜水艇将会获得分数,但是潜水艇自身的氧气储存量是逐渐减少的,需要不时地去浮出水面补充氧气。被敌方潜水艇撞上会损失生命值,游戏目标就是获得尽可能多的分数)。一个简单的暴力搜索算法可能会包含上图右边的过程,假设一段最优动作序列仅仅包含十个时间步,每个状态下仅仅包含两个可能动作,那么最后一个时间步就包含1024个可能性。但对于大多数问题来说,十个时间步远远不足以完成目标,因而暴力搜索算法是不可行的。

那么蒙特卡洛算法是如何在不穷举所有可能性直到到达终点的情况下对一个动作序列进行评估的呢?考虑潜水艇游戏,在潜水艇做出攻击指令后,由于炮弹的运行需要时间,因而几个时间步之后敌方潜水艇才会被击沉从而受到奖励,在潜水艇做出攻击指令那个时间步是没有任何奖励的,因而智能体可能认为这个动作并不是一个优秀的动作。对于以上情况,其实我们只需要在做出攻击指令后,如果要评估这个动作的优劣,“等待”几个时间步 即可。蒙特卡洛树搜索算法正是采用这种思想,同样用上图右边的过程举例,当动作执行到第三层时,如何评估这四个动作序列的性能好坏呢?算法进行了某种“等待”,即从第三层开始,不再把树进行完全的扩展了,而是采用一个随机策略随机执行动作直到游戏结束或者到达某个设定的时间步。这就类似于在潜水艇游戏中,潜水艇在发出炮弹后,随机执行一些动作,直到炮弹击中敌方潜水艇。

评估过程

而蒙特卡洛算法正是通过这种评估方法来避免暴力搜索,具体来说,蒙特卡洛树搜索算法会根据评估结果的好坏以及访问次数来决定下一步应该搜索哪一条路径:

搜索策略

可能以上描述有点难以理解,那么下面我们过一遍蒙特卡洛树搜索方法的搜索过程。我们首先给出算法的执行步骤:

蒙特卡洛树搜索算法框架

首先我们处于一个初始状态:

初始状态

然后我们进行算法第一步,根据一个“树策略”找到一个叶子节点,注意这里找到一个叶节点的意思是找到一个*新的叶节点。树策略的具体形式如下:

树策略

根据以上策略,由于初始状态没有被完全扩展,因而随机选择一个动作,并执行第二步使用默认策略来评估执行这个动作的好坏,这里默认策略使用的是随机采样策略:

随机选择

假设评估结果如下:

评估结果

这里Q代表环境定义的回报,N代表访问这个状态的次数。这里值得注意的是,N记录的并不是某个具体的状态的访问次数,而是执行某个动作的次数,执行这个动作后在随机环境下可能转移到很多个不同的状态,但在树中均显示为一个节点。评估完之后,我们需要更新根节点到这个新加入的叶节点之间所有节点的Q值以及N值。由于这里两者之间并没有其他的节点,因而跳过这一步。然后以上过程开始循环,我们再将状态跳回到初始状态,遵循树策略,找到下一个新的叶节点。由于初始状态还是没有扩展完毕,因此这一次执行下一个未被执行过的状态:

第二轮随机选择

再采用默认策略对其进行评估,假设我们得到了以下结果:

初始状态

由于根节点与新的叶节点之间的路径并没有其他节点,因而更新步骤略过。再次重复以上过程,将状态跳回到初始状态,执行树策略找到一个新的叶节点。首先根据树策略,初始状态已经被完全扩展开了(即所有可能的动作均已经执行过),这个时候我们根据树策略中的公式计算每一条路径的一个分数。从分数计算公式可以看出,这个分数是同时考虑动作的回报以及动作的执行次数,更加倾向于执行被执行次数少的回报高的动作。在这里,由于两个动作被执行次数均为1,因而我们选择回报更高的第二个动作执行,然后再根据树策略(在没有找到新的叶节点之前,循环执行树策略),第二层的状态没有被完全扩展,因而随机选择一个动作执行:

再次找到新的叶节点

依据默认策略进行评估:

采用默认策略评估

注意,到了这一步,根节点到新的叶节点之间的路径存在其他节点了,我们就要用最新的叶节点的评估值以及访问次数加到这些中间节点的评估值以及访问次数上:

更新中间节点

再次重复上述过程,将状态跳回到初始状态,调用树策略,这时候根据分数计算公式,在假设一些超参数的情况下,我们假定这个时候更加侧重于执行被执行次数更小的动作并评估:

侧重被访问次数更少的动作

然后再更新再跳回……

循环

循环

循环

循环

如果想详细了解蒙特卡洛树搜索算法的扩展以及应用,可以参考下面这篇综述:

综述

这里讲一个比较有意思的案例:

利用蒙特卡洛树搜索算法进行模仿学习

其思想其实是将DAgger算法与MCTS算法进行结合。由于DAgger算法需要人工的不断参与进行新数据的标注,以上案例将专家标注的过程用MCTS算法进行替代,学习一个MCTS的策略估计器:

DAgger

DAgger with MCTS

那么为什么不直接使用MCTS算法呢?其实是基于以下两点考虑的:

  • 实时性要求较高的任务中MCTS太慢了
  • 采用类似神经网络的策略估计器具有更好的泛化性

路径优化算法

让我们再次回顾以下优化问题:

优化目标

直接丢弃掉以上优化问题中的特殊结构显然不是十分恰当的,接下来让我们回到一般解决以上优化问题的思路。我们一看到以上问题,就会首先想到能不能利用类似梯度下降的方法呢?为了与最优控制中路径优化算法的一般符号记法一致,我们将以上问题重写为以下形式:

路径优化问题的优化目标

我们可以将约束部分放进优化函数中从而将以上问题转变为一个无约束问题:

无约束形式

对于以上问题,只要我们知晓以下四项,即可根据链式法则得出其最优解:

需要知道的梯度

LQR算法

确定性环境

为了解决以上优化问题,我们接下来将介绍一种路径优化算法LQR,此算法假设环境模型是线性的,并且代价函数是二次的:

LQR优化目标

为了解决这种特殊形式的以上优化问题,我们采用动态规划的思想,先找出最优的最后一个时间步的动作。之所以这样做,是因为我们可以发现,以上连加项中只有最后一项是与最后一个时间步的动作相关的。如果我们首先解决第一个时间步的最优动作,那么连加项的所有项都与第一个时间步的动作相关。接下来,我们把最后一项中连续的函数求值简写为$x_{T}$,注意这个值是未知的。进行了以上的准备工作后,求解最后一个时间步的最优动作对应的优化目标如下,我们把其记为$Q(x_T,u_T)$:

Q值函数

然后我们将线性项系数以及二次项系数展开:

系数展开

然后,为了得出最优动作,我们令这个优化目标关于最后一个时间步动作的梯度等于0:

最小化Q值函数

求解以上线性方程,可以得出最后一个时间步的最优动作为:

最后一个时间步的最优动作

将其进行简单的转化,我们可以看出,最后一个时间步的最优动作是最后一个时间步状态(现在还是未知项)的线性函数(以上关系适用于所有时间步):

最后一个时间步的动作是状态的线性函数

其中:

系数的具体形式

由于最后一步的最优动作完全可以用最后一步的状态表示,我们可以得出最后一个时间步的最优的Q值,这里我们将其记为V:

最后一个时间步的最优Q值

这里的Q值以及V值其实是和强化学习中的定义是一致的。接下来,我们将上式展开:

V值展开

将上式合并同类项可得:

合并同类项

其中:

系数具体形式

因而我们可以得到另一个关系,最后一个时间步的V值(最优Q值)是最后一个时间步状态的二次函数(以上关系适用于所有时间步)。进行到这里,我们已经解出最后一个时间步的最优动作了。接下来,我们要在此基础上解出倒数第二个时间步的最优动作。首先我们注意到,倒数第二个时间步的Q值函数可以记为:

倒数第二个时间步的Q值函数

将环境模型引入可将V值展开:

环境模型

展开后的V值

我们将展开后的V值代入倒数第二时间步的Q值函数中:

带入展开后V值的倒数第二个时间步的Q值函数

其中:

系数具体形式

同样,为了求出倒数第二个时间步的最优动作,我们令相关梯度为零:

最小化Q值函数

解得倒数第二个时间步的最优动作为:

倒数第二个时间步的最优动作

其中:

系数具体形式

让我们不断地重复以上过程,直到第一个时间步。值得注意的是,由于每一时间步的最优动作与那个时间步的状态有关,但是状态是未知的。

循环以上过程

当整个过程回溯到初始时间步时,情况发生了变化,初始状态我们是已知的!因而,我们就可以算法初始时间步的最优动作。利用环境模型,我们就可以得知第二个时间步的状态,如此循环下去,我们就可以得知所有时间步的最优动作:

前向循环

以上就是整个LQR算法的执行过程。

非确定性环境 (未完成)

对于非确定性环境,假设我们的环境模型如下:

随机环境模型

那么LQR算法依旧是完全可行的。

iLQR算法

LQR算法由于假设环境模型以及代价函数是线性以及二次的,表达能力有限,对于更加复杂的任务显然不能很好的估计。因而,解决这个问题的iLQR算法应运而生。其基本思想很简单,既然线性以及二次函数不足以估计全局的真实函数,那么估计局部的总是足够的。因而我们可以对环境模型以及代价函数分别做一阶以及二阶的泰勒展开!:

泰勒展开

那么我们的问题其实又转变回了原始的LQR设定:

原始设定

其中:

参数具体形式

iLQR算法的具体框架如下:

iLQR算法

该算法之所以采用迭代的形式,是因为其需要不断地用真实样本来去”矫正“其对于环境模型以及代价函数的估计。更严格来讲,该算法之所以能够达到很好的效果,是因为它和牛顿方法的本质是一样的(通过泰勒展示来估计一个复杂的非线性函数的局部特性):

牛顿方法

而如果我们对环境模型估计时也进行二阶泰勒展开:

参数具体形式

那么我们的算法就变为微分动态规划算法(DDP)。但是在实际情况中,代价函数的形式一般比较简单,因而进行二阶泰勒展开代价不大。但是环境模型一般是十分复杂的,一阶展开还好,一旦进行二阶展开其复杂性将会大大增加。事实表明一阶展开其实是足够的。

但是以上算法还存在一个问题,考虑以下估计误差:

局部估计误差

对于这种情况,其实我们只要简单的在原始iLQR算法中加一个line search过程即可:

Line Search

最后我们看一个iLQR算法在实际情况应用的实例:

实例

为了保证iLQR更加稳定,这个工作采用了如下形式的改进:

改进

即在每一步都进行一个完整的规划,但是考虑到iLQR的估计误差随着时间会产生累积,因而每次只执行规划的第一步。

Abracadabra

TD-VAE [ICLR 2019]

Posted on 2019-03-20 | | Visitors

简介

【笔记版】

今天要讲的是ICLR2019中DeepMind的一个工作,TD-VAE,一个序列生成模型。通过引入强化学习中时序差分以及变分自动编码器,来实现从当前时间步到未来时间步的预测。这里值得注意的是,TD-VAE并不是一个固定时间步的序列生成模型(当然如果训练时喂的训练数据是一个时间间隔固定的序列数据,那么训练出的模型就是固定时间步的序列生成模型),即其生成的数据时间间隔不是一个固定的时间步,而是随机的。如果想生成数据的时间间隔可控,那么可以在前向模型的建模中显式地将时间步作为变量即可。

这篇论文的作者认为,一个序列生成模型需要具备以下三点属性:

  • 这个模型应该学习一个数据的抽象状态表示并且在状态空间中进行预测,而不是在观察空间进行预测。
  • 这个模型应该学习一个置信状态,这个状态需要包含目前为止智能体对于周围环境的所有感知信息。置信状态相当于状态表示的隐变量。
  • 这个模型应该表现出时序抽象,既能够直接预测多个时间步之后的状态,也能够只通过两个独立的时间点进行训练而不需要中间所有时间点的信息。

优化目标

TD-VAE的目标便是优化以下对数条件似然:
$$
\log p(x_t|x_{<t})
$$
这里假设$x_t$可以通过该时间步以及上一个时间步的状态表示$z_t$和$z_{t-1}$推断得出,类似于VAE中损失函数的推导过程,这里同样引入ELBO,具体推导过程如下图:

推导过程

推导过程

推导过程

推导过程

最后的损失函数包含以下几个部分:

损失函数1

然后我们把两个连续时间步的状态表示换为两个任意时刻的状态表示:

损失函数2

这实质上是如下VAE的损失函数:

VAE

其中$t2>t1$。整个损失函数可以直观地解释为以下四个部分组成:

直观解释1

直观解释2

训练时的计算图如下所示:

计算图

最后在三个不同任务上的实验结果:

直观解释1

直观解释1

直观解释1

Abracadabra

Survey of Sim2Real: Part I

Posted on 2019-03-20 | | Visitors

最近survey了一下sim2real领域最近的相关工作,先整理个第一版(共有七篇论文)的总结。

整篇总结分为以下四个部分:

  • 问题的定义以及工作的出发点
  • 方法的分类
  • 具体算法
  • 一个实例

问题的定义以及工作的出发点

sim2real的全称是simulation to reality,是强化学习的一个分支,同时也属于transfer learning的一种。主要解决的问题是机器人领域中,直接让机器人或者机械臂在现实环境中与环境进行交互、采样时,会出现以下两个比较严重的问题:

  • 采样效率太低(在用强化学习算法解决机器人相关问题时,所需要的样本量一般会达到上千万,在现实环境中采集如此数量级的样本要耗费几个月的时间)
  • 安全问题 (由于强化学习需要通过智能体在环境中进行大范围的随机采样来进行试错,因而在某些时刻其做出的行为可能会损伤机器人自身,例如手臂转动角度过大或者避障任务中由于碰撞造成的不可逆损伤等等;也可能会损害周围的环境甚至生物)

但是如果我们在模拟器中进行强化学习算法的训练,以上两个问题均可迎刃而解。但是,这里同样会存在一个问题,由于模拟器对于物理环境的建模都是存在误差的,因而在模拟环境中学习到的最优策略是否可以直接在现实环境中应用呢?答案往往是否定的,我们把这个问题称为 “reality gap”。而sim2real的工作就是去尝试解决这个问题。

这里值得注意的一点是,虽然这个方向叫做sim2real,其实其中的所有的算法都可以直接应用在sim2sim,real2real等的任务中。

方法的分类

sim2real中的典型工作大致可以分为以下五类:

  • Domain Adaption 主要是通过学习一个模拟环境以及现实环境共同的状态到隐变量空间的映射,在模拟环境中,使用映射后的状态空间进行算法的训练;因而在迁移到现实环境中时,同样将状态映射到隐含空间后,就可以直接应用在模拟环境训练好的模型了。
  • Progressive Network 利用一类特殊的Progressive Neural Network来进行sim2real。其主要思想类似于cumulative learning,从简单任务逐步过渡到复杂任务(这里可以认为模拟器中的任务总是要比现实任务简单的)。
  • Inverse Dynamic Model 通过在现实环境中学习一个逆转移概率矩阵来直接在现实环境中应用模拟环境中训练好的模型。
  • Domain Randomization 对模拟环境中的视觉信息或者物理参数进行随机化,例如对于避障任务,智能体在一个墙壁颜色、地板颜色等等或者摩擦力、大气压强会随机变化的模拟环境中进行学习。

具体算法

这一部分将对以下六篇论文进行详细的说明:

  • Towards Adapting Deep Visuomotor Representations from Simulated to Real Environments[arXiv 2015] Eric Tzeng, Coline Devin, Judy Hoffman, Chelsea Finn, Xingchao Peng, Sergey Levine, Kate Saenko, Trevor Darrell
  • Learning Invariant Feature Spaces to Transfer Skills with Reinforcement Learning [arXiv 2017] Abhishek Gupta, Coline Devin, YuXuan Liu, Pieter Abbeel, Sergey Levine
  • Sim-to-Real Robot Learning from Pixels with Progressive Nets [arXiv 2016] Andrei A. Rusu Deepmind.
  • Transfer from Simulation to Real World through Learning Deep Inverse Dynamics Model[arXiv 2016] Paul Christiano, Zain Shah, Igor Mordatch, Jonas Schneider, Trevor Blackwell, Joshua Tobin, Pieter Abbeel, and Wojciech Zaremba
  • Sim-to-Real Transfer of Robotic Control with Dynamics Randomization [ICRA 2018] Xue Bin Peng, Marcin Andrychowicz, Wojciech Zaremba, and Pieter Abbeel
  • Domain Randomization for Transferring Deep Neural Networks from Simulation to the Real World [IROS 2017] Josh Tobin, Rachel Fong, Alex Ray, Jonas Schneider, Wojciech Zaremba, Pieter Abbeel

Towards Adapting Deep Visuomotor Representations from Simulated to Real Environments

该论文属于 Domain Adaption 类别。

虚拟环境以及现实环境收集到的图像对比

如上图,本文的基本思想是,无论是在模拟环境还是在现实环境智能体收集的图像中,对于任务比较重要的便是一些可控制物体或者目标的位置。因而希望学到的隐含表示能够保留这部分物体的位置信息。

以上是针对图像局部信息的约束。而对于整体图像来说,本文希望模拟环境以及现实环境在这个公共的隐含表示空间中的隐含表示无法被一个二分类器所分辨出来。另外,对于一对图片,例如上图,本文希望这一对图片的隐含表示的欧氏距离能够尽可能接近。

根据以上三个约束,可以得到以下三个损失函数:

Pose Estimation Loss:

Pose Estimation Loss

Domain Confusion Loss:

Domain Confusion Loss

其中

q function

Contrastive Loss:

Contrastive Loss

其中:

D

而求解整个问题的最终优化目标即以上三个损失函数的加权求和:

Objective Function

给出一个更加容易理解的框架图:

Architecture

但是这种方法存在一个问题,在计算contrastive loss时需要使用一对在模拟环境以及现实环境中能对应上的图片。这种对应关系如果需要人工完成工作量很大而且如何去分辨两张图是否是对应关系也没有一个绝对的标准。因而本文提出了一种无监督方法来自动从数据集中找出这种对应关系,具体来说分为以下五个步骤:

  1. 只使用虚拟环境中收集的图片(进行位置标记)并只是用pose estimation loss训练一个表示学习网络。
  2. 使用上一步训练好的表示学习网络抽取数据集中所有图片(包括仿真环境以及真实环境)的第一个卷积特征图。
  3. 对以上特征图采用5x5的最大池化。
  4. 为每一个仿真-现实图片对计算相似度,即计算其拉直后的特征图的内积。
  5. 每一张真实环境中的图片对应的虚拟环境的图片为相似度最高的那一张。

Learning Invariant Feature Spaces to Transfer Skills with Reinforcement Learning

这篇论文同样属于 Domain Adaption 领域,即学习一个虚拟环境以及真实环境的状态(state)的公共的隐含表示空间。其整个学习过程分为两步,第一步进行表示学习,第二步采用学习到的表示在现实环境中进行强化学习。

首先本文对需要解决的问题有如下假设:

Assume that the reward functions share some structural similarity, in that the state distribution of an optimal policy in the source domain will resemble the state distribution of an optimal policy in the target domain when projected into some common feature space.

即当仿真环境以及真实环境的状态同时映射到一个公共的隐含表示空间中,这两个环境所需要解决的问题的回报函数具有一定的相似性。举个例子,我们在仿真环境中构建一个拥有两个关节的机械臂希望它能够将一个冰球推到指定位置,回报函数设计为冰球与目标位置的距离的负值;然后在现实环境中,我们拥有一个有三个关节的机械臂去完成同样的任务。在这个例子中,虽然从智能体获得的图像表示完全不同(一个两关节一个三关节),但是回报函数其实是一样的,与关节数目没有关系。当然这是一个比较极端的例子,回报函数可以不完全一样。

所以本文的目标是学习两个映射函数,能够将两个环境中的状态映射到一个共同的隐含表示空间,这与上一篇论文只有一个公共的映射函数不同:

Common Feature Space

而要能通过这个目标来求出两个映射函数,还需要做出以下假设:

  • 仿真环境以及真实环境的智能体需要学会完成同一个任务
  • 动作空间一致,状态空间的维度一致

第一个假设必须存在是由于需要从这个共同的任务中去学习这两个映射函数。这两个假设其实不算很强烈的假设,对于第一个假设来说,这个共同任务可以是一些比较简单的任务,使得训练成本较小;另外对于第二个假设,如果仿真环境以及现实环境中使用的是同一款机器人或者机械臂,动作空间一致以及状态空间的维度一致是一个非常自然的假设。

表示学习

要进行如上公式所示的表示学习,我们首先需要对两个环境中的状态(学会的共同任务中的状态)进行对齐(与上一篇论文里的对齐意义是一样的),这里存在两种方法进行对齐:

  • Time-bases Alignment
  • Dynamic Time Wrapping

第一种方法非常简单,对于两个环境中的智能体都学会解决的共同任务,如果智能体在仿真环境以及现实环境中动作执行的时钟是大致相同的,那么只要让两个环境中的智能体同时开始执行这个共同的任务,其分别产生的状态序列一定是对齐的;但是时钟相等的假设过于强烈了,因而第二种方法是一个可行性更高的方法。它是一个迭代的方法,它需要一个计算两个序列相似度的距离函数,根据这个距离函数来找出使得两个序列距离最近的对齐方式;对齐后,再根据新的对齐方式更新距离函数,如此不断迭代直至收敛或者到达停止条件。这个方法主要在于如何去选择这个距离函数,本文的做法是首先用time-bases alignment方法得到一个初始的对齐方式,再使用下面要讲到的表示学习的方法学习两个映射函数,将整个序列每一对对齐状态映射后隐含表示向量的欧氏距离的和作为dynamic time warpping方法中序列相似度的距离函数。

以上就是状态对齐步骤,下面就要进行正式的表示学习了。我们注意到,对于以上公式,其实有个非常简单的解,即这两个映射函数的是个输出永远为0的常数函数。这样一个解显然不是我们需要的,因为我们可以加上一个约束,即学习到的隐含表示能够尽可能多的保留原表示的信息,即学习到的隐含表示是一个auto encoder的隐向量。根据以上假设以及我们的优化目标,可以得到如下表示学习损失函数:

Common Feature Spaces Loss

Auto Encoder Losses

Objective Function

同样给出一个更容易理解的框架图:

Architecture

知识迁移

在进行了第一步的表示学习后,我们需要利用学习到的表示在现实环境中进行新任务的训练。但是注意,我们学习的表示是经过如下两个约束学到的,第一个约束可以认为是一个auto encoder的降维;第二个约束是能够与模拟环境最优策略产生的状态概率分布相同的一个隐含状态表示空间。因而我们不能单单只利用学习到隐含表示去在现实世界中训练,这样在模拟环境中训练好的策略没有办法对现实任务的训练造成任何影响,这个影响必须通过将现实任务的状态序列与模拟环境中最优策略产生的状态序列对齐后才能够实现。

本文通过对现实环境中智能体需要解决的任务的回报函数的基础上加上如下附加项来实现知识迁移:

Addition Reward Term

这里的上标$t$表明,在进行现实环境中智能体的训练时,模拟环境必须同步运行。

Sim-to-Real Robot Learning from Pixels with Progressive Nets

本方法属于 Progressive Network 类别方法,其使用的Progressive Nerual Network是迁移学习领域提出的一种网络结构,其具体形式如下图(左)所示:

Progressive Neural Network

左图中每一列(column)代表一个独立的任务,任务训练顺序从左到右。虽然任务训练顺序从简单到复杂从直觉上来看是比较合理的,但是PNN并不一定要满足这个规律, 其任务训练顺序可以是任意的。由于我们以第三列(第三个任务)为中心来考虑,因而有实线与虚线的差异。可以看到PNN的思想非常简单,在后面任务的每一层计算时,输入端并上之前任务前一层的输出即可。但是PNN扩展到强化学习中进行了如下三个改变:

  1. 现实环境中使用的神经网络要比模拟环境中要小。原因主要是由于原PNN论文发现,当列数越多时每一列网络的参数都很稀疏,完全可以进行网络压缩或者剪枝。
  2. 输出层不再接受前置任务的输入。由于模拟环境与现实环境在动作空间上可能存在差异,因而在输出层借鉴前面任务的知识反而容易产生误导。
  3. 为了让智能体在现实环境中训练所需的样本量更小,因而输出层的参数直接复制之前任务的参数用来初始化,用以提升算法训练初期的探索度。

值得注意的是,论文的结果还表明使用LSTM进行策略网络的建模要比使用MLP效果更好。其实还有很多其他工作也同样发现了这一点,主要还是因为大部分现实中的强化学习问题都是部分观察的,不满足马尔可夫性质。

Transfer from Simulation to Real World through Learning Deep Inverse Dynamics Model

本文属于 Inverse Dynamic Model 类别。其主要基于的假设是即使虚拟环境无法对现实世界进行完全准确的建模,但是其状态的变化还是合理的。例如,对于一个将物体推到指定目标位置的任务来说,一个机械臂将冰球往前推那么下一个状态就是冰球往推动方向前进一些,但是不会往相反的方向移动。基于这个假设,首先在虚拟环境训练好一个策略,其输入是前n个时间步的状态(这里同样考虑到部分观察的问题),将输出的动作输入到虚拟环境模型中,就会转移到虚拟环境中的下一个状态。将这个状态与现实环境中的前n个时间步的状态输入到真实环境中学习到的逆动态模型中,就会得出能够输出这下一个状态所需要采取的动作。具体见下图:

训练流程图

以上过程唯一需要详细说明的便是如何在现实环境中学习一个逆动态模型,其实非常简单:

Inverse Dynamic Model

但是这个模型的好坏取决于在现实环境中收集的样本的质量,即样本是否具有足够的多样性从而覆盖足够大的状态空间。一个简单但有效的做法是在探索时的动作上增加一定的噪声,但是加入噪声的频率等需要仔细考量否则就会使得收集到的数据质量下降,论文经过实际的实验得出以下两点经验:

  1. 不需要每个时间步都加入噪声。
  2. 当现实环境中智能体执行动作发生状态转移时转移到一个与虚拟环境差别很大的状态时,就应当即时停止这一轮的采样。

Sim-to-Real Transfer of Robotic Control with Dynamics Randomization

本文属于 Domain Randomization 类别。本文出发点在于深度强化学习算法具有以下特性:

DeepRL policies are prone to exploiting idiosyncrasies of the simulator to realize behaviours that are infeasible in the real world.

即强化学习算法在一个特定环境中进行学习时,会尝试去挖掘某些专属于这个环境的特性从而使得算法的泛化能力很差。为此,本文将强化学习的优化目标更改如下:

Dynamic Randomization Problem

这里的$\mu$代表决定环境的物理参数。如果智能体优化的是在大量不同物理参数确定的虚拟环境中累积回报的期望值的话,训练出的策略就会更加鲁棒。对于一个特定的环境,本文采用HER+RDPG算法进行最优策略的训练:

Dynamic Randomization RL Algorithm

54

其中的策略网络以及值函数网络采用如下方式进行建模:

Netowrk Archtectures

Domain Randomization for Transferring Deep Neural Networks from Simulation to the Real World

本文同样属于 Domain Randomization 类别,只不过不同于上一篇论文是随机化物理参数,本文是随机化环境的视觉表示。具体来说,本文是想学习一个定位器,通过输入一张图片来定位其中所有目标物体的三维坐标:

Domain Randomization

具体需要随机化的视觉信息包括:

  • 桌子上所有目标物体的位置以及纹理
  • 桌子、地板、背景以及机械臂的纹理
  • 摄像机的位置、朝向以及可视范围
  • 场景中光源的数量
  • 场景中光源的位置、朝向以及光谱特征
  • 加入到图像中噪声的类型以及数量

一个实例

在这一部分我将介绍一下OpenAI在sim2real领域做出的一个工作,其地位类似于多智能体强化学习领域的OpenAI Five。

Learning Dexterous In-Hand Manipulation

这个例子主要用到的技术包括以下几点:虚拟环境的随机化、大规模分布式采样以及精确的虚拟环境搭建。其所需要完成的任务是:使用一个具有20个自由度的机械手,将其手掌中的立方体从初始朝向利用手指翻转到目标朝向:

Task

为了建立一个足够精细(但是依旧存在无法建模的物理量)的虚拟环境,OpenAI以机械手为球心半径为80厘米的球面上均匀分布了16个精度为20微米的追踪器,能够定位机械手任意位置的微小位移。之所以采用如此高精度的追踪器是为了尽可能准确地对机械手的相关物理参数,例如手指关节处的阻尼等等,这样的物理参数有将近500个。我认为这个工作之所以能够直接将虚拟环境中学习到的最优策略直接应用到现实环境中,这个高精度的虚拟环境功不可没:

真实环境 vs 虚拟环境

整个系统的训练步骤大致可分为以下三个部分(最后是训练完毕的执行部分):

系统流程图

下面将详细对每一个部分进行说明。首先是第一个部分,包括模拟环境中数据的并行采样以及整个强化学习的参数更新框架:

分布式数据采集以及参数更新

分布式架构

上图中采用的分布式数据收集以及模型训练框架同样也是OpenAI Five所采用的。从左下方开始,多个并行采样的worker会将自己根据当前策略采集的样本发送给与自己相关联的Redis服务器上,模型更新模块中的Puller将会定期异步地从Redis服务器中拉取一个batch的数据并放到RAM中,之后Stager从RAM中拉取一个mini-batch放到GPU上,与其他采用MPI协议联系的GPU一起对参数进行更新。更新后的参数将每个Optimizer都保存一份。之后Optimizer沿着之前相反的路径将更新后的参数存储到Redis服务器上,workers将定期异步地从Redis服务器上拉取最新的策略参数进行采样。整个训练过程就是以上过程的迭代。下图表示了不同规模的并行对于最终算法性能的影响:

不同并行度对于最终算法性能的影响

第二部分,具体的强化算法选用的是PPO算法,其策略网络以及值函数网络建模如下:

强化学习算法架构

策略网络以及值函数网络结构

其中输入部分左边代表机械手的状态,右边代表物体的朝向,具体的维度如下所示:

状态空间

由于PPO算法的值函数网络只会在训练时使用到,因而采用完整信息对其进行训练。在训练时算法采用了如下三种随机注入方法:

  • Dynamic Randomization
  • Domain Randomization
  • Unmodeled Effects Randomization

具体见下面三张图:

Dynamic Randomization

Domain Randomization

Unmodeled Effects Randomization

最后一部分,由于机械手的任务不应该局限于转动方块,还应该包括操纵其他物体。而且由第二部分可知策略网络以及值函数网络的输入可知需要立方体的朝向以及位置信息,目前是通过16个高精度追踪器确定的。OpenAI为了提高整个系统的通用性,因而在方块的周围相隔一定高度120度角均匀放置了三个摄像头,尝试学习一个模型,输入是三张不同角度的图片,输出是立方体的位置以及朝向。这样就可以把立方体换为任意的物体。其具体的网络结构如下:

Object Pose Prediction

Pose Prediction Network Architecture

12…27
Ewan Li

Ewan Li

Ewan's IT Blog

131 posts
64 tags
RSS
Github Twitter
© 2019 Ewan Li
Powered by Hexo
Theme - NexT.Mist
本站访客数人次 本站总访问量次