Abracadabra

策略梯度方法


译者注:

本篇文章翻译自 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)

策略梯度算法

今年来强化学习领域内提出了大量的策略梯度算法,我不可能罗列出所有的算法。因此在这里我仅仅列举出一些我恰巧了解的算法。

REINFORCE

REINFORCE(蒙特卡洛策略梯度)依靠使用蒙特卡洛方法从采样出的轨迹样本得到的估计的累积回报来更新策略的参数$\theta $。REINFORCE算法能够起效的原因是因为采样的梯度的期望值是真实梯度的无偏估计:
$$
\begin{aligned}
\nabla_\theta J(\theta)
&= \mathbb{E}_\pi [Q^\pi(s, a) \nabla_\theta \ln \pi_\theta(a \vert s)] & \\
&= \mathbb{E}_\pi [G_t \nabla_{\theta} \ln \pi_\theta(A_t \vert S_t)] & \scriptstyle{\text{; 因为 } Q^\pi(S_t, A_t) = \mathbb{E}_\pi[G_t \vert S_t, A_t]}
\end{aligned}
$$
因此我们能够从真实的采样轨迹中计算$G_t$并且使用它来去更新我们的策略梯度。它依赖于一条完整的轨迹,这也是为什么被叫做蒙特卡洛方法的原因。

整个算法流程十分直接:

  1. 随机初始化策略参数$\theta $
  2. 使用当前策略$\pi_{\theta} $产生一条完整的轨迹:$S_{1}, A_{1}, R_{2}, S_{2}, A_{2}, \dots, S_{T}$
  3. 对于每个时间步$\mathrm{t}=1,2, \ldots, \mathrm{T}$:
    1. 估计累积回报$G_t$
    2. 更新参数:$\theta \leftarrow \theta+\alpha \gamma^{t} G_{t} \nabla_{\theta} \ln \pi_{\theta}\left(A_{t} | S_{t}\right)$

一个被广泛应用的REINFORCE算法的变种是从$G_t$中减去一个基准值用来在保证偏差不变的情况下减小估计梯度时产生的方差(我们总是希望尽可能这样做)。举个例子,一个被广泛使用的基准值是状态-值,如果我们应用状态-值作为基准,那么我们实际在估计梯度进行梯度上升来更新参数的过程中使用的是优势值:$A(s, a)=Q(s, a)-V(s)$。这篇博客不仅仅很好地解释了为什么采用基准值会减小方差,而且还详细讲解了策略梯度的一些基础知识。

演员-评论家算法(Actor-Critic)

策略梯度算法主要包括策略模型以及值函数两个部分。在学习策略的基础上额外学习值函数是有很大意义的,因为值函数可以辅助策略更新,例如在平凡策略梯度算法中利用值函数来进行方差缩减,而这也是演员-评论家算法在做的事情。

演员-评论家模型由两个模型组成,可以选择是否共享参数:

  • 评论家更新值函数的参数$w$并且根据算法的不同值函数可以为动作-值$Q_{w}(a | s)$或者状态-值$V_{w}(s)$
  • 演员根据评论家建议的方向更新策略$\pi_{\theta}(a | s)$参数$\theta $

下面让我们看看一个简单的动作-值演员-评论家算法:

  1. 随机初始化$s, w, \theta$;从初始策略中采样$a \sim \pi_{\theta}(a | s)$
  2. 对于每个时间步$t=1 \ldots T :$
    1. 采样回报$r_{t} \sim R(s, a)$以及下一个状态$s^{\prime} \sim P\left(s^{\prime} | s, a\right)$
    2. 采样下一个动作$a^{\prime} \sim \pi_{\theta}\left(a^{\prime} | s^{\prime}\right)$
    3. 更新策略参数:$\theta \leftarrow \theta+\alpha_{\theta} Q_{w}(s, a) \nabla_{\theta} \ln \pi_{\theta}(a | s)$
    4. 对于当前时间步的动作-值计算校正值(TD误差):$\delta_{t}=r_{t}+\gamma Q_{w}\left(s^{\prime}, a^{\prime}\right)-Q_{w}(s, a)$并且使用它来更新动作-值函数的参数:$w \leftarrow w+\alpha_{w} \delta_{t} \nabla_{w} Q_{w}(s, a)$
    5. 更新当前动作$a \leftarrow a^{\prime}$以及状态$s \leftarrow s^{\prime}$

$\alpha_w$和$\alpha_{\theta}$是两个预先定义的分别用来更新策略以及值函数的学习率。

离线策略梯度(Off-Policy Policy Gradient)

REINFORCE算法以及上述简单版本的演员-评论家算法都是在线(on-policy)的:训练样本是通过目标策略(target policy)——我们想要去优化的策略——收集的。然而离线方法拥有以下额外的优势:

  1. 离线方法不需要完整的轨迹样本并且可以复用任何历史轨迹的样本(“经验回放”)从而具有更好的样本有效性。
  2. 训练样本根据行为策略(behavior policy)而不是目标策略收集而来,给算法带来更好的探索性

现在让我们来看看离线策略梯度是如何计算的。用来收集训练样本的行为策略是一个已知的策略(类似一个预先定义好的超参数),我们把它记作$\beta(a | s)$。那么目标函数(这里我们采用的是平均值形式的目标函数,其他形式的目标函数可以导出相同的结果)为由此行为策略导出的平稳状态分布下的回报的加和:

$$
J(\theta)=\sum_{s \in \mathcal{S}} d^{\beta}(s) \sum_{a \in \mathcal{A}} Q^{\pi}(s, a) \pi_{\theta}(a | s)=\mathbb{E}_{s \sim d^{\beta}}\left[\sum_{a \in \mathcal{A}} Q^{\pi}(s, a) \pi_{\theta}(a | s)\right],
$$
其中$d^{\beta}(s)$为行为策略$\beta$导出的平稳分布,$d^{\beta}(s)=\lim _{t \rightarrow \infty} P\left(S_{t}=s | S_{0}, \beta\right)$。$Q^{\pi}$为根据目标策略$\pi$(不是行为策略!)估计的动作-值函数。

给定根据行为策略采样得到的动作$a \sim \beta(a | s)$产生的训练样本,我们可以将策略梯度改写为如下形式:
$$
\begin{aligned}
\nabla_{\theta} J(\theta) &= \nabla_{\theta} \mathbb{E}_{s \sim d^{\beta}} \Big[ \sum_{a \in \mathcal{A}} Q^{\pi}(s, a) \pi_{\theta}(a \vert s) \Big] & \\
&= \mathbb{E}_{s \sim d^{\beta}} \Big[ \sum_{a \in \mathcal{A}} \big( Q^{\pi}(s, a) \nabla_{\theta} \pi_{\theta}(a \vert s) + \color{red}{\pi_{\theta}(a \vert s) \nabla_{\theta} Q^{\pi}(s, a)} \big) \Big] & \scriptstyle{\text{; 微分乘法法则.}}\\
&\stackrel{(i)}{\approx} \mathbb{E}_{s \sim d^{\beta}} \Big[ \sum_{a \in \mathcal{A}} Q^{\pi}(s, a) \nabla_{\theta} \pi_{\theta}(a \vert s) \Big] & \scriptstyle{\text{; 忽略红色部分: } \color{red}{\pi_{\theta}(a \vert s) \nabla_{\theta} Q^{\pi}(s, a)}}. \\
&= \mathbb{E}_{s \sim d^{\beta}} \Big[ \sum_{a \in \mathcal{A}} \beta (a \vert s) \frac{\pi_{\theta}(a \vert s)}{\beta (a \vert s)} Q^{\pi}(s, a) \frac{\nabla_{\theta} \pi_{\theta}(a \vert s)}{\pi_{\theta}(a \vert s)} \Big] & \\
&= \mathbb{E}_\beta \Big[\frac{\color{blue}{\pi_{\theta}(a \vert s)}}{\color{blue}{\beta (a \vert s)}} Q^{\pi}(s, a) \nabla_{\theta} \ln \pi_{\theta}(a \vert s) \Big], & \scriptstyle{\text{; 蓝色部分成为重要性权重.}}
\end{aligned}
$$
其中$\frac{\pi_{\theta}(a | s)}{\beta(a | s)}$为重要性权重(importance weight)。由于$Q^{\pi}$是目标策略的函数因而也就是策略参数$\theta$的参数,因而根据微分乘法法则我们需要计算梯度$\nabla_{\theta} Q^{\pi}(s, a)$。然而在现实问题中计算$\nabla_{\theta} Q^{\pi}(s, a)$是一件超级困难的事情。幸运的是如果我们直接忽略掉$Q$的梯度而去使用一个近似的策略梯度的话,依旧能够保证采用梯度上升算法能够使得策略性能提升并且最终收敛到一个真实的局部最优解。上述结论的具体证明过程请参阅这篇论文(Degris, White & Sutton, 2012)。

总而言之,当我们想在离线环境下应用策略梯度时,只需通过加权求和的方式对其进行简单的修改,权重为目标策略与行为策略的比值。

A3C

[论文|代码]

异步优势演员-评论家方法(Asynchronous Advantage Actor-Critic)(Mnih et al., 2016),简写为A3C时一种经典的策略梯度方法,尤其注重并行训练。

在A3C中,评论家学习值函数,同时有多个演员并行训练并且不时与全局参数同步。因而,A3C旨在用于并行训练。

让我们用状态-值函数进行举例。状态值的损失函数是最小化均方误差 $J_{v}(w)=\left(G_{t}-V_{w}(s)\right)^{2}$,因而采用梯度下降方法可以找到最优参数$w$。状态-值函数用来在策略梯度更新中作为基准值。

下面是算法大纲:

  1. 定义全局参数 $\theta$ 和 $w$ 以及特定线程参数 $\theta^{\prime}$ 和 $w^{\prime}$。
  2. 初始化时间步 $t=1$。
  3. 当 $T<=T_{\mathrm{max}}$:

    1. 重置梯度:$\mathrm{d} \theta=0$ 并且 $\mathrm{d} \mathrm{w}=0$。

    2. 将特定于线程的参数与全局参数同步:$\theta^{\prime}=\theta$ 以及 $w^{\prime}=w$。

    3. 令 $t_{\text {start }}=t$ 并且随机采样一个初始状态 $s_t$。

    4. 当 ($s_{t} !=$ 终止状态)并且 $t-t_{\text {start}}<=t_{\text {max}}$:

      1. 根据当前线程的策略选择当前执行的动作 $a_{t} \sim \pi_{\theta^{\prime}}\left(a_{t} | s_{t}\right)$,执行动作后接收回报$r_t$然后转移到下一个状态$s_{t+1}$。
      2. 更新 $t$ 以及 $T$:$t=t+1$ 并且 $T=T+1$。
    5. 初始化保存累积回报估计值的变量:$r=\left\{\begin{array}{ll}{0} & {\text { 如果 } s_{t} \text { 是终止状态}} \\ {V_{w^{\prime}}\left(s_{t}\right)} & {\text { 否则}}\end{array}\right.$

    6. 对于 $i=t-1, \dots, t_{\text {start}}$:

      1. $r \leftarrow \gamma r+r_{i}$;这里 $r$ 是 $G_i$ 的蒙特卡洛估计。

      2. 累积关于参数 $\theta^{\prime}$ 的梯度:$d \theta \leftarrow d \theta+\nabla_{\theta^{\prime}} \log \pi_{\theta^{\prime}}\left(a_{i} | s_{i}\right)\left(r-V_{w^{\prime}}\left(s_{i}\right)\right)$;

        累积关于参数 $w^{\prime}$ 的梯度:$d w \leftarrow d w+2\left(r-V_{w^{\prime}}\left(s_{i}\right)\right) \nabla_{w^{\prime}}\left(r-V_{w^{\prime}}\left(s_{i}\right)\right)$。

    7. 分别使用 $d\theta$ 以及 $dw$异步更新 $\theta$ 以及 $w$。

A3C支持多智能体(译者注:这里的多智能体与多智能体强化学习中的多智能体不是一个概念)并行训练。梯度累积步骤(6.2)可以认为是基于小批量样本的随机梯度下降在并行环境下的变形:$w$ 或者 $\theta$ 的值在每个训练线程得出的更新方向上独立地校正一点点。

A2C

[论文|代码]

A2C是A3C的同步、确定版本;这也是为什么要把A3C的第一个”A“(”异步“)去掉。在A3C中,每个演员独立地与(保存)全局参数(的服务器)进行交互,因此有时不同线程中的演员将使用不同版本的策略,因此累积更新的方向将不是最优的。为了解决上述执行策略不一致问题,A2C中引入协调器,在更新全局参数之前等待所有并行的演员完成其工作,那么在下一次迭代中并行的演员将均执行同一策略。同步的梯度更新使得训练过程更加耦合因而有可能使得算法具有更快得收敛速度。

A2C已被证明在能够实现与A3C相同或更好的性能得同时,更有效地利用GPU,并且能够适应更大的批量大小。

图2. A3C与A2C架构对比。

确定性策略梯度(DPG)

[论文|代码]

在上述方法中,策略函数 $\pi( . | s)$ 总是被建模为给定当前状态下在动作空间 $\mathcal{A}$ 上的概率分布,因而策略是随机的。相反,确定性策略梯度(Deterministic Policy Gradient)将环境建模为一个确定性决策:$a=\mu(s)$。这可能看上去很奇怪——你如何计算一个只能输出单个动作的策略函数的梯度呢?让我们一步步往下看。

回忆一些符号以便进行下面的讨论:

  • $\rho_{0}(s)$:初始状态分布
  • $\rho^{\mu}\left(s \rightarrow s^{\prime}, k\right)$:从状态 $s$ 开始,遵循策略 $\mu$ 的情况下经过 $k$ 个时间步后到达状态 $s^{\prime}$ 的访问概率密度
  • $\rho^{\mu}\left(s^{\prime}\right)$:折扣状态分布,定义为 $\rho^{\mu}\left(s^{\prime}\right)=\int_{\mathcal{S}} \sum_{k=1}^{\infty} \gamma^{k-1} \rho_{0}(s) \rho^{\mu}\left(s \rightarrow s^{\prime}, k\right) d s$

(平均值形式的)目标函数定义如下:
$$
J(\theta)=\int_{\mathcal{S}} \rho^{\mu}(s) Q\left(s, \mu_{\theta}(s)\right) ds
$$
确定性策略梯度定理:现在该计算梯度了!根据链式法则,我们首先计算 $Q$ 相对于动作 $a$ 的梯度然后计算确定性策略函数 $\mu$ 相对于其参数 $\theta$ 的参数:
$$
\begin{aligned}
\nabla_{\theta} J(\theta) &=\int_{\mathcal{S}} \rho^{\mu}(s) \nabla_{a} Q^{\mu}(s, a) \nabla_{\theta} \mu_{\theta}\left.(s)\right|_{a=\mu_{\theta}(s)} d s \\ &=\mathbb{E}_{s \sim \rho^{\mu}}\left[\nabla_{a} Q^{\mu}(s, a) \nabla_{\theta} \mu_{\theta}\left.(s)\right|_{a=\mu_{\theta}(s)}\right]
\end{aligned}
$$
我们可以将确定性策略看成是随即策略的一个特例,前者的在整个动作空间的概率分布只在一个动作上是非零值。实际上在DPG论文中作者表明,如果随机策略 $\pi_{\mu_{\theta}, \sigma}$ 被确定性策略 $\mu_{\theta}$ 以及一个方差变量 $\sigma$ 重参数化,则当 $\sigma = 0$ 时随机策略最终将等价于确定策略。与确定性策略相比,我们可以认为随机策略需要更多样本,因为它整合了整个状态和动作空间的数据。

确定性梯度定理可以整合到通用的策略梯度算法框架中。

让我们考虑一个在线演员-评论家算法的例子来表明这个过程。在在线演员-评论家算法的每次迭代过程中,两个时间步的动作通过确定策略来选择 $a=\mu_{\theta}(s)$,然后 SARSA 算法通过上面计算得到的新形式的梯度来更新策略参数:
$$
\begin{aligned}
\delta_t &= R_t + \gamma Q_w(s_{t+1}, a_{t+1}) - Q_w(s_t, a_t) & \scriptstyle{\text{; SARSA算法中的 TD 误差}}\\
w_{t+1} &= w_t + \alpha_w \delta_t \nabla_w Q_w(s_t, a_t) & \\
\theta_{t+1} &= \theta_t + \alpha_\theta \color{red}{\nabla_a Q_w(s_t, a_t) \nabla_\theta \mu_\theta(s) \rvert_{a=\mu_\theta(s)}} & \scriptstyle{\text{; 确定性策略梯度定理}}
\end{aligned}
$$
然而,除非环境本身具有足够多的噪声,否则由于策略的确定性很难保证在训练的过程中有进行足够多的探索。我们可以在确定策略中添加噪音(讽刺的是,这使得它将不具有确定性!)或者通过遵循不同的随机行为策略来收集样本来离线地学习目标确定策略。

比方说,在离线方法中,训练轨迹样本是通过一个随机行为策略 $\beta(a | s)$ 产生的因而状态分布服从对应的折扣状态密度 $\rho^{\beta}$:
$$
\begin{aligned}
J_\beta(\theta) &= \int_\mathcal{S} \rho^\beta Q^\mu(s, \mu_\theta(s)) ds \\
\nabla_\theta J_\beta(\theta) &= \mathbb{E}_{s \sim \rho^\beta} [\nabla_a Q^\mu(s, a) \nabla_\theta \mu_\theta(s) \rvert_{a=\mu_\theta(s)} ]
\end{aligned}
$$
注意由于策略是确定性的,我们只需要通过 $Q^{\mu}\left(s, \mu_{\theta}(s)\right)$ 而不是 $\sum_{a} \pi(a | s) Q^{\pi}(s, a)$ 来估计给定状态 $s$ 的累积回报(译者注:这也是为什么上述第二个等式期望的下标只有状态的期望)。就像我们在之前提到的,在采用随机目标策略的离线方法中,会引入重要性采样来校正行为策略与目标策略之间的不匹配现象。然而,由于确定性策略梯度中移除了在动作空间中的积分项,我们就可以避免使用重要性采样。

深度确定性策略梯度 (DDPG)

[论文|代码]

DDPGLillicrap, et al., 2015)是深度确定性策略梯度(Deep Deterministic Policy Gradient)的缩写,是一个结合了DPG以及DQN的无模型离线演员-评论家算法。回忆一下,DQN(深度Q网络)通过经验回访以及冻结目标网络的方式来稳定Q函数的训练过程。原始的DQN算法只能在离散的动作空间上使用,DDPG算法在学习一个确定性策略的同时通过演员-评论家框架将其扩展到连续的动作空间中。

为了获得更好的探索度,DDPG通过添加噪声 $\mathcal{N}$ 的方式构建了一个探索策略 $\mu^{\prime}$:
$$
\mu^{\prime}(s)=\mu_{\theta}(s)+\mathcal{N}
$$
另外,DDPG对演员以及评论家的目标网络的参数实行的是软更新(”保守策略迭代“),其中 $\tau \ll 1$:$\theta^{\prime} \leftarrow \tau \theta+(1-\tau) \theta^{\prime}$。采用这种方式,目标网络的值被限制为缓慢变化,不同于在DQN的设计中目标网络在一段时间内直接被冻结。

论文中关于机器人领域特别有用的一个细节是如何正则化低维特征的不同物理单位。例如,我们设计一个模型旨在学习以机器人的位置和速度为输入的策略;这些物理统计数据本质上是不同的,甚至相同类型的统计数据在多个机器人中也可能会有很大差异。论文通过应用批正则化通过对一个小批量中的样本的每个维度进行正则化来解决上述问题。

图3. DDPG算法。图片来源:[Lillicrap, et al., 2015](https://arxiv.org/pdf/1509.02971.pdf)

D4PG

[论文|代码(在谷歌中搜索”github d4pg“可以找到一些非官方开源实现)]

分布地分布式DDPG(Distributed Distributional DDPGD4PG)在DDPG算法上进行了一系列的改进使得其可以分布式地运行。

(1)分布式评论家:分布式评论家不再只估计Q值的期望值,而是去估计期望Q值的分布,即将期望Q值作为一个随机变量来进行估计——该变量服从一个由 $w$ 参数化的分布 $Z_w$ 因而 $Q_{w}(s, a)=\mathbb{E} Z_{w}(x, a)$。学习该分布的参数所对应的损失函数是去最小化两个分布之间的某种距离度量——分布式TD误差:$L(w)=\mathbb{E}\left[d\left(\mathcal{T}_{\mu_{\theta}}, Z_{w^{\prime}}(s, a), Z_{w}(s, a)\right]\right.$,其中 $T_{\mu_{\theta}}$ 表示贝尔曼算子。

相应的,确定性策略梯度更新转变为以下形式:
$$
\begin{aligned}
\nabla_\theta J(\theta)
&\approx \mathbb{E}_{\rho^\mu} [\nabla_a Q_w(s, a) \nabla_\theta \mu_\theta(s) \rvert_{a=\mu_\theta(s)}] & \scriptstyle{\text{; DPG中的梯度更新}} \\
&= \mathbb{E}_{\rho^\mu} [\mathbb{E}[\nabla_a Q_w(s, a)] \nabla_\theta \mu_\theta(s) \rvert_{a=\mu_\theta(s)}] & \scriptstyle{\text{; Q值分布的期望}}
\end{aligned}
$$
(2)N步累积回报:当计算TD误差时,D4PG计算的是N步的TD目标值而不仅仅只有一步,这样就可以考虑未来更多步骤的回报。因而新的TD目标值变为:
$$
r\left(s_{0}, a_{0}\right)+\mathbb{E}\left[\sum_{n=1}^{N-1} r\left(s_{n}, a_{n}\right)+\gamma^{N} Q\left(s_{N}, \mu_{\theta}\left(s_{N}\right)\right) | s_{0}, a_{0}\right]
$$
(3)多个分布式并行演员:D4PG使用$K$个独立的演员并行收集训练样本并存储到同一个回访缓冲中。

(4)优先经验回放Prioritized Experience ReplayPER):最后一个改进是使用一个非均匀的概率 $p_i$ 从一个大小为 $R$ 的回放缓冲中进行采样。在这种采样方式下,一个样本 $i$ 将以概率 $\left(R p_{i}\right)^{-1}$ 被采样到因而重要性权重为 $\left(R p_{i}\right)^{-1}$。

图4. D4PG算法。图片来源:[Barth-Maron, et al. 2018。注意在原始论文中变量符号的选择与本文有些微的区别;例如,我使用$\mu(.)$而不是$\pi(.)$来表示一个确定性策略](https://openreview.net/forum?id=SyZipzbCb)。

MADDPG

[论文|代码]

多智能体DDPG(Multi-agent DDPGMADDPGLowe et al., 2017)将DDPG扩展到多智能体环境中,其中包含多个智能体在仅依靠局部信息的情况下协作完成任务。从单个智能体的角度来看,环境是非平稳的,因为其他智能体的策略在很快地更新并且一直是未知的。MADDPG是一个经过重新设计的演员评论家算法,专门用于处理这种不断变化的环境以及智能体之间的互动。

这个问题可以被建模为多智能体版本的MDP,也被称为马尔科夫游戏。其中,共有 $N$ 个智能体,公共的状态空间为 $\mathcal{S}$。每个智能体拥有自己的动作空间 $\mathcal{A}_{1}, \dots, \mathcal{A}_{N}$ 以及观察空间 $\mathcal{O}_{1}, \dots, \mathcal{O}_{N}$。状态转移函数包括所有的状态、动作以及观察空间$\mathcal{T} : \mathcal{S} \times \mathcal{A}_{1} \times \ldots \mathcal{A}_{N} \mapsto \mathcal{S}$。每个智能体自己的随机策略仅仅用到属于自己的观察以及动作:$\pi_{\theta_{i}} : \mathcal{O}_{i} \times \mathcal{A}_{i} \mapsto[0,1]$,一个给定其自身观察下关于动作的概率分布;或者一个确定性策略:$\mu_{\theta_{i}} : \mathcal{O}_{i} \mapsto \mathcal{A}_{i}$。

令 $\vec{o}=o_{1}, \ldots, o_{N}, \vec{\mu}=\mu_{1}, \ldots, \mu_{N}$ 并且策略是由 $\vec{\theta}=\theta_{1}, \dots, \theta_{N}$ 参数化的。

MADDPG中的评论家为第 $i$ 个智能体(每个智能体)学习一个中心化的动作-值函数 $Q_{i}^{\vec{\mu}}\left(\vec{o}, a_{1}, \ldots, a_{N}\right)$,其中 $a_{1} \in \mathcal{A}_{1}, \ldots, a_{N} \in \mathcal{A}_{N}$ 是所有智能体的动作。每一个 $Q_{i}^{\vec{\mu}},\;i=1, \dots, N$ 都是独立学习的,因而每个智能体可以拥有任意形式的回报函数,包括竞争环境中相互冲突的回报函数。同时,每个智能体各自的演员,也是独立探索以及独立更新策略参数 $\theta_{i}$。

演员更新:
$$
\nabla_{\theta_{i}} J\left(\theta_{i}\right)=\mathbb{E}_{\vec{o}, a \sim D}\left[\nabla_{a_{i}} Q_{i}^{\vec{\mu}}\left(\vec{o}, a_{1}, \ldots, a_{N}\right) \nabla_{\theta_{i}} \mu_{\theta_{i}}\left.\left(o_{i}\right)\right|_{a_{i}=\mu_{\theta_{i}}\left(o_{i}\right)}\right]
$$
其中 $\mathcal{D}$ 表示经验回放缓冲,包含大量轨迹样本 $\left(\vec{o}, a_{1}, \ldots, a_{N}, r_{1}, \ldots, r_{N}, \vec{o}^{\prime}\right)$ —— 给定当前联合观察 $\vec{o}$,每个智能体分别执行动作 $a_{1}, \dots, a_{N}$ 后获取各自的回报 $r_{1}, \dots, r_{N}$,并转移到下一个联合观察 $\vec{o}^{\prime}$。

评论家更新:
$$
\begin{aligned}
\mathcal{L}(\theta_i) &= \mathbb{E}_{\vec{o}, a_1, \dots, a_N, r_1, \dots, r_N, \vec{o}’}[ (Q^{\vec{\mu}}_i(\vec{o}, a_1, \dots, a_N) - y)^2 ] & \\
\text{其中 } y &= r_i + \gamma Q^{\vec{\mu}’}_i (\vec{o}’, a’_1, \dots, a’_N) \rvert_{a’_j = \mu’_{\theta_j}} & \scriptstyle{\text{; TD目标值!}}
\end{aligned}
$$
其中 $\vec{\mu}^{\prime}$ 是延迟软更新参数的目标策略。

如果在评论家更新的过程中策略 $\vec{\mu}$ 是未知的,我们可以让每个智能体学习并更新自己对其他智能体策略的近似。当使用近似的策略时,尽管推断出的策略可能不够精确但是MADDPG仍然能够有效地学习。

为了缓解环境中竞争或协作关系的智能体之间由于相互作用所带来的高方差,MADDPG提出了另外一个技术——策略集成:

  1. 为单个智能体训练 $K$ 个策略;
  2. 随机选取一个策略用以轨迹采样;
  3. 使用 $K$ 个策略的集成梯度来进行参数更新。

总之,MADDPG在DDPG之上添加了三个额外部分,使其适应多智能体环境:

  • 中心化评论家+去中心化演员;
  • 智能体能够使用估计的其他智能体的策略来进行学习;
  • 策略集成能够很好的减小方差。

图5. MADDPG的算法框架. 图片来源:[Lowe et al., 2017](https://arxiv.org/pdf/1706.02275.pdf)

TRPO

[论文|代码]

为了提升训练的稳定性,我们应该避免更新一步就使得策略发生剧烈变化的参数更新。置信区间策略优化(Trust region policy optimization,TRPOSchulman, et al., 2015)通过在每次迭代时对策略更新的幅度强制施加KL散度约束来实现上述理念。

对于离线情况,目标函数衡量的是在遵循一个不同的行为策略 $\beta(a | s)$ 进行采样的同时在状态访问分布以及动作空间上所有的优势:
$$
\begin{aligned}
J(\theta)
&= \sum_{s \in \mathcal{S}} \rho^{\pi_{\theta_\text{old}}} \sum_{a \in \mathcal{A}} \big( \pi_\theta(a \vert s) \hat{A}_{\theta_\text{old}}(s, a) \big) & \\
&= \sum_{s \in \mathcal{S}} \rho^{\pi_{\theta_\text{old}}} \sum_{a \in \mathcal{A}} \big( \beta(a \vert s) \frac{\pi_\theta(a \vert s)}{\beta(a \vert s)} \hat{A}_{\theta_\text{old}}(s, a) \big) & \scriptstyle{\text{; 重要性采样}} \\
&= \mathbb{E}_{s \sim \rho^{\pi_{\theta_\text{old}}}, a \sim \beta} \big[ \frac{\pi_\theta(a \vert s)}{\beta(a \vert s)} \hat{A}_{\theta_\text{old}}(s, a) \big] &
\end{aligned}
$$
其中 $\theta_{\mathrm{old}}$ 是更新之前的策略参数因而对于我们来说是已知的;$\rho^{\pi_{\mathrm{old}}}$ 和之前的定义相同;$\beta(a | s)$是用来采样轨迹数据的行为策略。注意这里我们使用的是一个估计的优势 $\hat{A}(\cdot)$ 而不是真实的优势 $A(\cdot)$,因为真实的回报往往是未知的。

对于在线情况,行为策略是 $\pi_{\theta_{\text {old}}}(a | s) :$
$$
J(\theta) = \mathbb{E}_{s \sim \rho^{\pi_{\theta_\text{old}}}, a \sim \pi_{\theta_\text{old}}} \big[ \frac{\pi_\theta(a \vert s)}{\pi_{\theta_\text{old}}(a \vert s)} \hat{A}_{\theta_\text{old}}(s, a) \big]
$$
TRPO算法旨在满足置信区间约束下最大化目标函数 $J(\theta)$。该约束强制旧策略与新策略之间的KL散度小于某个参数 $\delta$:
$$
\mathbb{E}_{s \sim \rho^{\pi_{\theta_\text{old}}}} [D_\text{KL}(\pi_{\theta_\text{old}}(.\vert s) | \pi_\theta(.\vert s)] \leq \delta
$$
通过这种方式,当满足这种硬约束时,旧策略和新策略不会差距太大。虽然如此,TRPO可以保证策略一直在往好的方向迭代(很厉害,对吧?)。如果大家感兴趣的话,可以去看看论文中的证明:)

PPO

[论文|代码]

鉴于TRPO相对复杂但是我们仍然想要去实现一个类似的约束,近端策略优化(proximal policy optimization ,PPO)在实现相似性能的同时通过使用一个截断的替代目标函数来简化TRPO。

首先,让我们将旧策略和新策略之间的概率比值表示为:
$$
r(\theta)=\frac{\pi_{\theta}(a | s)}{\pi_{\theta_{\text {old}}}(a | s)}
$$
接着,TRPO的目标函数(在线)变为:
$$
J^{\mathrm{TRPO}}(\theta)=\mathbb{E}\left[r(\theta) \hat{A}_{\theta_{\mathrm{old}}}(s, a)\right]
$$
如果在最大化 $J^{\mathrm{TRPO}}(\theta)$ 时不对 $\theta_{\mathrm{old}}$ 和 $\theta$ 之间的距离加以限制的话,将会因为过大的参数更新幅度以及过大的策略比值而使得更新过程不稳定。PPO通过强行使得 $r(\theta)$ 保持在 $1$ 附近的邻域中,即 $[1-\varepsilon, 1+\varepsilon]$,来施加这一约束。其中 $\varepsilon$ 为超参数。
$$
J^{\mathrm{CLIP}}(\theta)=\mathbb{E}\left[\min \left(r(\theta) \hat{A}_{\theta_{\mathrm{dd}}}(s, a), \operatorname{clip}(r(\theta), 1-\epsilon, 1+\epsilon) \hat{A}_{\theta_{\mathrm{dd}}}(s, a)\right)\right]
$$
函数 $\operatorname{clip}(r(\theta), 1-\epsilon, 1+\epsilon)$ 将策略比值约束在 $[1-\varepsilon, 1+\varepsilon]$ 范围内。PPO的目标函数是去取原始值与截断版本的之间的较小值因此我们违背了TRPO最开始的一个理念,即尽可能最大化策略的更新幅度从而得到更好的回报。

当将PPO算法应用在策略(演员)和值函数(评论家)共享参数的网络结构上时,除了截断回报之外,目标函数上还加上了关于值估计的误差项(红色部分)以及一个熵正则项(蓝色部分)用以鼓励探索。
$$
J^\text{CLIP’} (\theta) = \mathbb{E} [ J^\text{CLIP} (\theta) - \color{red}{c_1 (V_\theta(s) - V_\text{target})^2} + \color{blue}{c_2 H(s, \pi_\theta(.))} ]
$$
其中 $c_1$ 和 $c_2$ 为两个常数超参数。

PPO已经在一系列基准任务上进行了测试并证明可以以更加简单的方式得到可喜的结果。

ACER

[论文|代码]

ACER,带有经验回放的演员-评论家(Actor-Critic with Experience ReplayWang, et al., 2017)算法的缩写,是一个带有经验回放的离线演员-评论家算法,它极大地提升了采样有效性并且较低了训练数据间的关联性。A3C基于ACER构建,只不过它是在线方法;ACER是A3C的离线版本。使A3C成为离线方法的主要障碍是如何保证离线估计器的稳定性。ACER提出了三种改进来去克服这个障碍:

  • 使用 Retrace Q值估计
  • 使用偏差校正截断重要性权重
  • 使用更加高效的TRPO算法

Retrace Q值估计

Retrace 是一种离线的基于累积回报的Q值估计算法。它在任意的目标-策略网络对 $(\pi, \beta)$ 下都有一个比较好的收敛性保证并且拥有很好的数据有效性。

回忆一下TD学习是如何进行预测的:

  1. 计算TD误差:$\delta_{t}=R_{t}+\gamma \mathbb{E}_{a \sim \pi} Q\left(S_{t+1}, a\right)-Q\left(S_{t}, A_{t}\right)$;其中 $r_{t}+\gamma \mathbb{E}_{a \sim \pi} Q\left(s_{t+1}, a\right)$ 被称为”TD目标“。使用期望值 $\mathbb{E}_{a \sim \pi}$ 是因为如果我们遵循当前策略 $\pi$ 的话对于未来时间步我们能做的最好的估计就是累积回报可能是多少。
  2. 通过校正误差往目标移动来更新Q值:$Q\left(S_{t}, A_{t}\right) \leftarrow Q\left(S_{t}, A_{t}\right)+\alpha \delta_{t}$。换句话说,Q的增量更新幅度与TD误差成正比:$\Delta Q\left(S_{t}, A_{t}\right)=\alpha \delta_{t}$。

当进行离线采样时,我们需要在Q值更新过程中应用重要性采样:
$$
\Delta Q^{\mathrm{imp}}\left(S_{t}, A_{t}\right)=\gamma^{t} \prod_{1 \leq \tau \leq t} \frac{\pi\left(A_{\tau} | S_{\tau}\right)}{\beta\left(A_{\tau} | S_{\tau}\right)} \delta_{t}
$$
当我们想象一下重要性权重的连乘会带来多大的方差时就会感觉到这个连乘项有多么可怕了。Retrace Q值估计方法通过截断重要性权重使其不超过某个常数 $c$ 的方式对 $\Delta Q$ 进行修改:
$$
\Delta Q^{\mathrm{ret}}\left(S_{t}, A_{t}\right)=\gamma^{t} \prod_{1 \leq \tau \leq t} \min \left(c, \frac{\pi\left(A_{\tau} | S_{\tau}\right)}{\beta\left(A_{\tau} | S_{\tau}\right)}\right) \delta_{t}
$$
ACER使用 $Q^{\mathrm{ret}}$ 作为TD目标通过最小化 $L2$ 误差项来训练评论家:$\left(Q^{\mathrm{ret}}(s, a)-Q(s, a)\right)^{2}$。

重要性权重截断

为了减少估计策略梯度 $\hat{g}$ 时产生的高方差,ACER使用一个常数 $c$ 加上一个校正项来截断重要性权重。$\hat{g}_{t}^{\text { acer }}$ 代表 $t$ 时刻的ACER策略梯度。
$$
\begin{aligned}
\hat{g}_t^\text{acer}
= & \omega_t \big( Q^\text{ret}(S_t, A_t) - V_{\theta_v}(S_t) \big) \nabla_\theta \ln \pi_\theta(A_t \vert S_t)
& \scriptstyle{\text{; 令 }\omega_t=\frac{\pi(A_t \vert S_t)}{\beta(A_t \vert S_t)}} \\
= & \color{blue}{\min(c, \omega_t) \big( Q^\text{ret}(S_t, A_t) - V_w(S_t) \big) \nabla_\theta \ln \pi_\theta(A_t \vert S_t)} \\
& + \color{red}{\mathbb{E}_{a \sim \pi} \big[ \max(0, \frac{\omega_t(a) - c}{\omega_t(a)}) \big( Q_w(S_t, a) - V_w(S_t) \big) \nabla_\theta \ln \pi_\theta(a \vert S_t) \big]}
& \scriptstyle{\text{; 令 }\omega_t (a) =\frac{\pi(a \vert S_t)}{\beta(a \vert S_t)}}
\end{aligned}
$$
其中 $Q_{w}( .)$ 以及 $V_{w}( .)$ 由 $w$ 参数化的评论家预测的动作-值以及状态-值。第一项(蓝色部分)包含了截断重要性权重。截断操作促进方差缩减,减去状态-值 $V_{w}( .)$ 作为基准进一步加强了方差缩减的效果。第二项(红色部分)进行了校正使得上述方差估计为无偏估计。

高效TRPO

此外,ACER采用TRPO的思想,但通过一个小的调整使其具有更高的计算效率:ACER不再去计算当前策略与更新一步之后的新策略之间的KL散度,而是去维护一个历史策略的运行平均(running average)值并且强制新策略不会偏离这个平均策略太远。

ACER论文信息量很大,包含很多公式。但是在事先了解了TD学习,Q学习,重要性采样和TRPO之后,你会发现这篇论文会稍微变得容易理解一些:)

ACKTR

[论文|代码]

Kronecker因子化置信区间的演员-评论家算法(Actor-Critic using Kronecker-factored Trust Region,ACKTRYuhuai Wu, et al., 2017)使用Kronecker因子化曲率估计(K-FAC)同时进行演员以及评论家的梯度更新。K-FAC对自然梯度的计算进行了改进,这与我们的标准梯度有很大不同。这里有一个对于自然梯度很好很直观的解释。

如果要用一句话总结的话:

“我们首先考虑所有参数组合,这些参数组合导致新网络与旧网络保持恒定的KL差异。该常数值可以视为步长或学习速率。在所有这些可能的组合中,我们选择最小化损失函数的组合。“

我在这里列出了ACTKR主要是为了这篇文章的完整性,但我不会深入到细节部分,因为它涉及很多关于自然梯度和优化方法的理论知识。如果有兴趣,请在阅读ACKTR论文之前查看这些文章/帖子:

以下是K-FAC论文的高度概括(译者注:以下为论文原文,因此不做翻译):

“This approximation is built in two stages. In the first, the rows and columns of the Fisher are divided into groups, each of which corresponds to all the weights in a given layer, and this gives rise to a block-partitioning of the matrix. These blocks are then approximated as Kronecker products between much smaller matrices, which we show is equivalent to making certain approximating assumptions regarding the statistics of the network’s gradients.

In the second stage, this matrix is further approximated as having an inverse which is either block-diagonal or block-tridiagonal. We justify this approximation through a careful examination of the relationships between inverse covariances, tree-structured graphical models, and linear regression. Notably, this justification doesn’t apply to the Fisher itself, and our experiments confirm that while the inverse Fisher does indeed possess this structure (approximately), the Fisher itself does not.”

SAC

[论文|代码]

软演员-评论家算法(Soft Actor-Critic,SACHaarnoja et al. 2018)将策略的熵度量纳入回报函数中用以鼓励探索:我们希望学习到一种尽可能随机行动的策略,同时仍然能够在任务中完成目标。它是一个遵循最大熵强化学习框架的离线演员-评论家模型。一个先例工作是软Q学习

SAC算法中的三个关键部分如下:

  • 包含分离策略网络以及值函数网络的演员-评论家架构;
  • 离线形式使其能够复用历史收集的数据从而实现高采样有效性;
  • 熵最大化以使得训练稳定并鼓励探索。

策略的训练目标是同时最大化期望累积回报以及策略的熵度量:
$$
J(\theta)=\sum_{t=1}^{T} \mathbb{E}_{\left(s_{t}, a_{t}\right) \sim \rho_{\pi_{\theta}}}\left[r\left(s_{t}, a_{t}\right)+\alpha \mathcal{H}\left(\pi_{\theta}\left( . | s_{t}\right)\right)\right]
$$

其中 $\mathcal{H}( .)$ 表示熵度量,$\alpha$ 被称为热度(temperature)参数用以控制熵正则项的重要度。熵最大化使得策略再训练过程中可以(1)进行更多的探索更多和(2)捕获近似最优策略的多种模式(例如,如果存在似乎同样好的多种选项,则策略应该为每个选项分配以相同的概率被选中)。

准确地说,SAC旨在学习三个函数:

  • 由 $\theta$ 参数化的策略 $\pi_{\theta}$。
  • 由 $w$ 参数化的软Q值函数 $Q_w$。
  • 由 $\psi$ 参数化的软状态-值函数 $V_{\psi}$ ;理论上来说我们可以通过 $Q$ 以及 $\pi$ 来推导出 $V$,但是在实际情况下,显式对状态-值函数建模可以使得训练过程更加稳定。

软Q值以及软状态值分别定义如下:
$$
\begin{aligned}
Q(s_t, a_t) &= r(s_t, a_t) + \gamma \mathbb{E}_{s_{t+1} \sim \rho_{\pi}(s)} [V(s_{t+1})] & \text{; 根据贝尔曼方程}\\
\text{where }V(s_t) &= \mathbb{E}_{a_t \sim \pi} [Q(s_t, a_t) - \alpha \log \pi(a_t \vert s_t)] & \text{; 软状态值函数}
\end{aligned}
$$

$$
\text{Thus, } Q(s_t, a_t) = r(s_t, a_t) + \gamma \mathbb{E}_{(s_{t+1}, a_{t+1}) \sim \rho_{\pi}} [Q(s_{t+1}, a_{t+1}) - \alpha \log \pi(a_{t+1} \vert s_{t+1})]
$$

$\rho_{\pi}(s)$ 和 $\rho_{\pi}(s, a)$ 分别表示由策略 $\pi(a\vert s)$ 导出的状态分布的状态以及状态-动作边际分布;DPG算法部分有类似的定义。

软状态值函数通过最小化均方误差来训练:
$$
\begin{aligned}
J_V(\psi) &= \mathbb{E}_{s_t \sim \mathcal{D}} [\frac{1}{2} \big(V_\psi(s_t) - \mathbb{E}[Q_w(s_t, a_t) - \log \pi_\theta(a_t \vert s_t)] \big)^2] \\
\text{其中梯度为: }\nabla_\psi J_V(\psi) &= \nabla_\psi V_\psi(s_t)\big( V_\psi(s_t) - Q_w(s_t, a_t) + \log \pi_\theta (a_t \vert s_t) \big)
\end{aligned}
$$
其中 $\mathcal{D}$ 代表经验回放缓冲。

软Q值函数通过最小化软贝尔曼残差来训练:
$$
\begin{aligned}
J_Q(w) &= \mathbb{E}_{(s_t, a_t) \sim \mathcal{D}} [\frac{1}{2}\big( Q_w(s_t, a_t) - (r(s_t, a_t) + \gamma \mathbb{E}_{s_{t+1} \sim \rho_\pi(s)}[V_{\bar{\psi}}(s_{t+1})]) \big)^2] \\
\text{其中梯度为: } \nabla_w J_Q(w) &= \nabla_w Q_w(s_t, a_t) \big( Q_w(s_t, a_t) - r(s_t, a_t) - \gamma V_{\bar{\psi}}(s_{t+1})\big)
\end{aligned}
$$
其中 $\bar{\psi}$ 代表目标值函数,它是个指数移动平均值(exponential moving average)或者只是采用一种“硬”方式进行周期更新。就像DQN中目标Q网络中的参数一样,为了使得训练过程更加稳定。

SAC通过最小化如下KL散度来去更新策略:
$$
\begin{aligned}
\pi_\text{new}
&= \arg\min_{\pi’ \in \Pi} D_\text{KL} \Big( \pi’(.\vert s_t) | \frac{\exp(Q^{\pi_\text{old}}(s_t, .))}{Z^{\pi_\text{old}}(s_t)} \Big) \[6pt]
&= \arg\min_{\pi’ \in \Pi} D_\text{KL} \big( \pi’(.\vert s_t) | \exp(Q^{\pi_\text{old}}(s_t, .) - \log Z^{\pi_\text{old}}(s_t)) \big) \[6pt]
\text{目标函数: } J_\pi(\theta) &= \nabla_\theta D_\text{KL} \big( \pi_\theta(. \vert s_t) | \exp(Q_w(s_t, .) - \log Z_w(s_t)) \big) \[6pt]
&= \mathbb{E}_{a_t\sim\pi} \Big[ - \log \big( \frac{\exp(Q_w(s_t, a_t) - \log Z_w(s_t))}{\pi_\theta(a_t \vert s_t)} \big) \Big] \[6pt]
&= \mathbb{E}_{a_t\sim\pi} [ \log \pi_\theta(a_t \vert s_t) - Q_w(s_t, a_t) + \log Z_w(s_t) ]
\end{aligned}
$$
其中 $\prod$ 是潜在策略的集合,我们可以将这些策略建模为容易处理的形式;例如,$\prod$ 可以是高斯混合分布族,虽然建模时复杂度较高但是具有很强的表达能力并且易于处理。$Z^{\pi_\text{old}}(s_t)$ 是用于正则化分布的配分函数。它一般是很难处理的但所幸对于梯度值没有影响。最小化 $J_{\pi}(\theta)$ 的方式依赖于 $\prod$ 的选择。

一旦我们为软动作-值,软状态值和策略网络定义了目标函数和梯度,软演员-评论家算法就很简单了:

图6. 软演员-评论家算法. 图片来源:[原始论文](https://arxiv.org/abs/1801.01290)

带有自动热度调整的软演员-评论家算法

[论文|代码]

SAC算法对于热度参数十分敏感。不幸的是,调整热度参数是一件很困难的事情。因为在随着策略由于训练变得更优的过程中或者在不同任务中进行训练时熵都会出现不可预测的变化。在SAC算法针对上述问题的改进可以建模为如下带约束的优化问题:在最大化期望累积回报的同时,策略应满足最小熵约束:
$$
\max _{\pi_{0}, \ldots, \pi_{T}} \mathbb{E}\left[\sum_{t=0}^{T} r\left(s_{t}, a_{t}\right)\right] \text { s.t. } \forall t, \mathcal{H}\left(\pi_{t}\right) \geq \mathcal{H}_{0}
$$
其中 $\mathcal{H}_{0}$ 表示预定义的最小策略熵阈值。

其中期望收益 $\mathbb{E}\left[\sum_{t=0}^{T} r\left(s_{t}, a_{t}\right)\right]$ 可以分解为每一时间步回报的和。因为在时刻 $t$ 的策略 $\pi_t$ 不会影响到之前时刻的策略 $\pi_{t-1}$,我们可以从后往前逐步最大化收益——这其实就是动态规划了。
$$
\underbrace{\max_{\pi_0} \Big( \mathbb{E}[r(s_0, a_0)]+ \underbrace{\max_{\pi_1} \Big(\mathbb{E}[…] + \underbrace{\max_{\pi_T} \mathbb{E}[r(s_T, a_T)]}_\text{第一步最大化} \Big)}_\text{第二步但也是最后一步最大化} \Big)}_\text{最后一步最大化}
$$
其中 $\gamma=1$。

我们从最后一个时间步 $T$ 开始最大化:
$$
\mathbb{E}_{\left(s_{T}, a_{T}\right) \sim \rho_{\pi}}\left[r\left(s_{T}, a_{T}\right)\right] \text { s.t. } \mathcal{H}\left(\pi_{T}\right)-\mathcal{H}_{0} \geq 0
$$
首先,我们定义以下一些函数:
$$
\begin{aligned}
h(\pi_T) &= \mathcal{H}(\pi_T) - \mathcal{H}_0 = \mathbb{E}_{(s_T, a_T) \sim \rho_{\pi}} [-\log \pi_T(a_T\vert s_T)] - \mathcal{H}_0\\
f(\pi_T) &= \begin{cases}
\mathbb{E}_{(s_T, a_T) \sim \rho_{\pi}} [ r(s_T, a_T) ], & \text{if }h(\pi_T) \geq 0 \\
-\infty, & \text{otherwise}
\end{cases}
\end{aligned}
$$
因而优化问题就转变为如下形式:
$$
f\left(\pi_{T}\right) \text { s.t. } h\left(\pi_{T}\right) \geq 0
$$
为了解决带有不等式约束的最大化优化问题,我们可以构建一个带有拉格朗日乘子(也被称为“对偶变量”) $\alpha_{T}$ 的拉格朗日表达式
$$
L\left(\pi_{T}, \alpha_{T}\right)=f\left(\pi_{T}\right)+\alpha_{T} h\left(\pi_{T}\right)
$$
考虑如下情况,在给定策略 $\pi_{T}$ 的情况下,我们尝试去找到最小化 $L\left(\pi_{T}, \alpha_{T}\right)$ 的 $\alpha_{T}$ 值,

  • 如果约束被满足,即 $h\left(\pi_{T}\right) \geq 0$ ,那么因为我们无法通过 $\alpha_T$ 控制 $f\left(\pi_{T}\right)$ 的值因此最好将其设置为0(译者注:这里我有些无法理解,如果要最小化,那么当 $h\left(\pi_{T}\right) \geq 0$ 时 $\alpha_T$ 为负数应该会使得目标函数更小?)。因而,$L\left(\pi_{T}, 0\right)=f\left(\pi_{T}\right)$。
  • 如果约束被违背了,即 $h\left(\pi_{T}\right)<0$,我们可以通过令 $\alpha_{T} \rightarrow \infty$ 来使得 $L\left(\pi_{T}, \alpha_{T}\right) \rightarrow-\infty$。因而 $L\left(\pi_{T}, \infty\right)=-\infty=f\left(\pi_{T}\right)$。

无论哪种情况,我们都可以得到如下等式:
$$
f\left(\pi_{T}\right)=\min _{\alpha_{T} \geq 0} L\left(\pi_{T}, \alpha_{T}\right)
$$
同时,我们想要去最大化$ f\left(\pi_{T}\right)$:
$$
\max _{\pi_{T}} f\left(\pi_{T}\right)=\min _{\alpha_{T} \geq 0} \max _{\pi_{T}} L\left(\pi_{T}, \alpha_{T}\right)
$$
因此,为了最大化 $f\left(\pi_{T}\right)$,其对应的对偶问题罗列如下。注意为了保证 $\max _{\pi_{T}} f\left(\pi_{T}\right)$ 是一个良定的操作(即 $f\left(\pi_{T}\right)$ 不为 $-\infty$),约束必须要被满足。
$$
\begin{aligned}
\max_{\pi_T} \mathbb{E}[ r(s_T, a_T) ]
&= \max_{\pi_T} f(\pi_T) \\
&= \min_{\alpha_T \geq 0} \max_{\pi_T} L(\pi_T, \alpha_T) \\
&= \min_{\alpha_T \geq 0} \max_{\pi_T} f(\pi_T) + \alpha_T h(\pi_T) \\
&= \min_{\alpha_T \geq 0} \max_{\pi_T} \mathbb{E}_{(s_T, a_T) \sim \rho_{\pi}} [ r(s_T, a_T) ] + \alpha_T ( \mathbb{E}_{(s_T, a_T) \sim \rho_{\pi}} [-\log \pi_T(a_T\vert s_T)] - \mathcal{H}_0) \\
&= \min_{\alpha_T \geq 0} \max_{\pi_T} \mathbb{E}_{(s_T, a_T) \sim \rho_{\pi}} [ r(s_T, a_T) - \alpha_T \log \pi_T(a_T\vert s_T)] - \alpha_T \mathcal{H}_0 \\
&= \min_{\alpha_T \geq 0} \max_{\pi_T} \mathbb{E}_{(s_T, a_T) \sim \rho_{\pi}} [ r(s_T, a_T) + \alpha_T \mathcal{H}(\pi_T) - \alpha_T \mathcal{H}_0 ]
\end{aligned}
$$
我们可以迭代地计算最优的 $\pi_T$ 以及 $\alpha_T$。首先给定目前的 $\alpha_{T}$,通过最大化 $L\left(\pi_{T}^{\star}, \alpha_{T}\right)$ 来得到最优的策略 $\pi_{T}^{\star}$。然后将 $\pi_{T}^{\star}$ 代入去最小化 $L\left(\pi_{T}^{\star}, \alpha_{T}\right)$ 来计算 $\alpha_{T}^{\star}$。想象一下我们用一个神经网络来表示策略,用另一个网络来表示热度参数,这个迭代过程就与训练演员-评论家算法时更新两者的网络参数比较类似了。
$$
\begin{aligned}
\pi^{\star}_T
&= \arg\max_{\pi_T} \mathbb{E}_{(s_T, a_T) \sim \rho_{\pi}} [ r(s_T, a_T) + \alpha_T \mathcal{H}(\pi_T) - \alpha_T \mathcal{H}_0 ] \\
\color{blue}{\alpha^{\star}_T}
&\color{blue}{=} \color{blue}{\arg\min_{\alpha_T \geq 0} \mathbb{E}_{(s_T, a_T) \sim \rho_{\pi^{\star}}} [\alpha_T \mathcal{H}(\pi^{\star}_T) - \alpha_T \mathcal{H}_0 ]}
\end{aligned}
$$

$$
\text{因而, }\max_{\pi_T} \mathbb{E} [ r(s_T, a_T) ]
= \mathbb{E}_{(s_T, a_T) \sim \rho_{\pi^{\star}}} [ r(s_T, a_T) + \alpha^{\star}_T \mathcal{H}(\pi^{\star}_T) - \alpha^{\star}_T \mathcal{H}_0 ]
$$

现在,让我们回到软Q值函数:
$$
\begin{aligned}
Q_{T-1}(s_{T-1}, a_{T-1})
&= r(s_{T-1}, a_{T-1}) + \mathbb{E} [Q(s_T, a_T) - \alpha_T \log \pi(a_T \vert s_T)] \\
&= r(s_{T-1}, a_{T-1}) + \mathbb{E} [r(s_T, a_T)] + \alpha_T \mathcal{H}(\pi_T) \\
Q_{T-1}^{\star}(s_{T-1}, a_{T-1})
&= r(s_{T-1}, a_{T-1}) + \max_{\pi_T} \mathbb{E} [r(s_T, a_T)] + \alpha_T^{\star} \mathcal{H}(\pi^{\star}_T) & \text{; 代入最优策略 }\pi_T^{\star}
\end{aligned}
$$
因此,当我们进一步退回到 $T-1$ 时间步时,期望收益如下:
$$
\begin{aligned}
&\max_{\pi_{T-1}}\Big(\mathbb{E}[r(s_{T-1}, a_{T-1})] + \max_{\pi_T} \mathbb{E}[r(s_T, a_T] \Big) \\
&= \max_{\pi_{T-1}} \Big( Q^{\star}_{T-1}(s_{T-1}, a_{T-1}) - \alpha^{\star}_T \mathcal{H}(\pi^{\star}_T) \Big) & \text{; 需 } \mathcal{H}(\pi_{T-1}) - \mathcal{H}_0 \geq 0 \\
&= \min_{\alpha_{T-1} \geq 0} \max_{\pi_{T-1}} \Big( Q^{\star}_{T-1}(s_{T-1}, a_{T-1}) - \alpha^{\star}_T \mathcal{H}(\pi^{\star}_T) + \alpha_{T-1} \big( \mathcal{H}(\pi_{T-1}) - \mathcal{H}_0 \big) \Big) & \text{; 对偶问题} \\
&= \min_{\alpha_{T-1} \geq 0} \max_{\pi_{T-1}} \Big( Q^{\star}_{T-1}(s_{T-1}, a_{T-1}) + \alpha_{T-1} \mathcal{H}(\pi_{T-1}) - \alpha_{T-1}\mathcal{H}_0 \Big) - \alpha^{\star}_T \mathcal{H}(\pi^{\star}_T)
\end{aligned}
$$
与之前类似,我们有:
$$
\begin{aligned}
\pi^{\star}_{T-1} &= \arg\max_{\pi_{T-1}} \mathbb{E}_{(s_{T-1}, a_{T-1}) \sim \rho_\pi} [Q^{\star}_{T-1}(s_{T-1}, a_{T-1}) + \alpha_{T-1} \mathcal{H}(\pi_{T-1}) - \alpha_{T-1} \mathcal{H}_0 ] \\
\color{green}{\alpha^{\star}_{T-1}} &\color{green}{=} \color{green}{\arg\min_{\alpha_{T-1} \geq 0} \mathbb{E}_{(s_{T-1}, a_{T-1}) \sim \rho_{\pi^{\star}}} [ \alpha_{T-1} \mathcal{H}(\pi^{\star}_{T-1}) - \alpha_{T-1}\mathcal{H}_0 ]}
\end{aligned}
$$
绿色部分更新 $\alpha_{T-1}^{\star}$ 的公式与上面蓝色部分更新 $\alpha_{T}^{\star}$ 的公式具有相同的形式。通过不断重复上述过程,我们可以通过最小化相同的目标函数(译者注:这里的目标函数中的策略不是最优的)来学习每个时间步的最优热度参数:
$$
J(\alpha)=\mathbb{E}_{a_{t} \sim \pi_{t}}\left[-\alpha \log \pi_{t}\left(a_{t} | \pi_{t}\right)-\alpha \mathcal{H}_{0}\right]
$$
除了根据最小化 $J(\alpha)$ 来显式地学习 $\alpha$ 之外本部分算法与SAC算法没有任何区别(见图7)。

图7. 带有自动热度调整的软演员-评论家算法. 图片来源:[原始论文](https://arxiv.org/abs/1812.05905)

TD3

[论文|代码]

众所周知Q学习一直存在对值函数过估计的问题。过估计会随着训练过程不断传播最终会对策略学习造成负面影响。这个问题促使双Q学习以及双DQN的提出:通过使用两个值网络将动作选择和Q值更新进行解耦。

双延迟深度确定性策略梯度方法(Twin Delayed Deep Deterministic,TD3; Fujimoto et al., 2018)在DDPG算法的基础上应用了很多新的改进从而防止值函数的过估计现象:

(1)截断双Q学习:在双Q学习中,动作选择以及Q值估计是通过两个独立的网络完成的。在DDPG中,给定两个确定性演员 $\left(\mu_{\theta_{1}}, \mu_{\theta_{2}}\right)$ 以及两个对应的评论家 $\left(Q_{w_{1}}, Q_{w_{2}}\right)$,双Q学习的贝尔曼目标如下:
$$
\begin{aligned}
y_1 &= r + \gamma Q_{w_2}(s’, \mu_{\theta_1}(s’))\\
y_2 &= r + \gamma Q_{w_1}(s’, \mu_{\theta_2}(s’))
\end{aligned}
$$
然而,由于策略变化过于缓慢,使得两个演员网络会过于相似从而很难做出完全独立的决策。截断双Q学习使用两者中的最小估计,从而倾向于使用难以通过训练传播的欠估计偏差:
$$
\begin{aligned}
y_1 &= r + \gamma \min_{i=1,2}Q_{w_i}(s’, \mu_{\theta_1}(s’))\\
y_2 &= r + \gamma \min_{i=1,2} Q_{w_i}(s’, \mu_{\theta_2}(s’))
\end{aligned}
$$
(2)延迟更新目标和策略网络:在演员-评论家模型中,策略与值函数的更新深度耦合:当策略较差时值函数的估计将会由于过估计问题发散;相反如果值函数估计不准确又会使得策略变差。

为了减小训练过程中的方差,TD3以一个相对于Q值函数更低的更新频率来更新策略。策略网络的参数将会保持不变直至值函数误差经过多轮迭代后足够小。这个想法类似于定期更新的目标网络如何在DQN中作为稳定的目标存在。

(3)目标策略平滑:考虑到确定性策略会过拟合到值函数的峰值上,TD3在值函数上引入了平滑正则化策略。在所选动作中添加少量经过截断的随机噪声,并对小批量数据进行平均。
$$
\begin{aligned}
y &= r + \gamma Q_w (s’, \mu_{\theta}(s’) + \epsilon) & \\
\epsilon &\sim \text{clip}(\mathcal{N}(0, \sigma), -c, +c) & \scriptstyle{\text{ ; 截断的随机噪声}}
\end{aligned}
$$
这种做法模仿了SARSA参数更新的思想,并强制相似的动作应具有相似的动作-值。

下面是最终的算法框架:

图8. TD3算法. 图片来源:[原始论文](https://arxiv.org/abs/1802.09477)

总结

研究完上面的所有算法后,我列出了一些似乎在它们中很常见的基础构件或原则:

  • 尽量减少方差并保持偏差不变以稳定训练过程。
  • 离线方法可以带来更高的探索度以及更高的数据有效性。
  • 经验回放(训练数据从一个回放缓存中采样)。
  • 目标网络要么周期更新要么比正在学习的网络更慢地更新。
  • 批标准化。
  • 带有熵正则的回报函数
  • 演员和评论家可以共享网络的低层参数然后两个输出头分别为策略和值函数。
  • 可以学习一个确定性的策略而不是一个随即策略。
  • 在策略更新上施加距离约束。
  • 新的优化方法(例如K-FAC)。
  • 最大化策略的熵度量从而鼓励探索。
  • 避免对值函数过估计。
  • 等等

如果你在这篇文章中发现了一些错误或描述不当的地方,不要犹豫,马上通过邮件[lilian dot wengweng at gmail dot com]联系我,我很乐意及时改正!

下篇文章再见:D

参考文献

[1] jeremykun.com Markov Chain Monte Carlo Without all the Bullshit

[2] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction; 2nd Edition. 2017.

[3] John Schulman, et al. “High-dimensional continuous control using generalized advantage estimation.” ICLR 2016.

[4] Thomas Degris, Martha White, and Richard S. Sutton. “Off-policy actor-critic.” ICML 2012.

[5] timvieira.github.io Importance sampling

[6] Mnih, Volodymyr, et al. “Asynchronous methods for deep reinforcement learning.” ICML. 2016.

[7] David Silver, et al. “Deterministic policy gradient algorithms.” ICML. 2014.

[8] Timothy P. Lillicrap, et al. “Continuous control with deep reinforcement learning.” arXiv preprint arXiv:1509.02971 (2015).

[9] Ryan Lowe, et al. “Multi-agent actor-critic for mixed cooperative-competitive environments.”NIPS. 2017.

[10] John Schulman, et al. “Trust region policy optimization.” ICML. 2015.

[11] Ziyu Wang, et al. “Sample efficient actor-critic with experience replay.” ICLR 2017.

[12] Rémi Munos, Tom Stepleton, Anna Harutyunyan, and Marc Bellemare. “Safe and efficient off-policy reinforcement learning” NIPS. 2016.

[13] Yuhuai Wu, et al. “Scalable trust-region method for deep reinforcement learning using Kronecker-factored approximation.” NIPS. 2017.

[14] kvfrans.com A intuitive explanation of natural gradient descent

[15] Sham Kakade. “A Natural Policy Gradient.”. NIPS. 2002.

[16] “Going Deeper Into Reinforcement Learning: Fundamentals of Policy Gradients.” - Seita’s Place, Mar 2017.

[17] “Notes on the Generalized Advantage Estimation Paper.” - Seita’s Place, Apr, 2017.

[18] Gabriel Barth-Maron, et al. “Distributed Distributional Deterministic Policy Gradients.” ICLR 2018 poster.

[19] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. “Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor.” arXiv preprint arXiv:1801.01290 (2018).

[20] Scott Fujimoto, Herke van Hoof, and Dave Meger. “Addressing Function Approximation Error in Actor-Critic Methods.” arXiv preprint arXiv:1802.09477 (2018).

[21] Tuomas Haarnoja, et al. “Soft Actor-Critic Algorithms and Applications.” arXiv preprint arXiv:1812.05905 (2018).

[22] David Knowles. “Lagrangian Duality for Dummies” Nov 13, 2010.