(RL – ICLR 2017)- ACER 算法

引言

Retrace(λ)

为了使用由其他策略得到的交互策略得到的样本对当前的模型进行训练. 但是由于样本来自不同的策略(也就说概率分布不同), 我们不能直接使用这些样本, 所以重要性采样就可以使用概率A来为概率分布B采样.

用于估计 off-policy 的轨迹价值. 具有三个方面的性质:

  • 低方差: 对总的回报的估计方差会比较低
  • 安全性: 对于off-policy的方法来说,如果行动策略和目标策略相差太大,那么它能确保在训练目标策略时仍可以安全使用行动策略采集的样本。
  • 高效性: 有时候收集样本的行动策略是很接近目标策略(on-policy)的,那它能确保对这种样本的高效利用。有些方法是有了安全性,但是缺失了这种情况下的样本利用的高效性。

符号定义

MDP 五元组$(\mathcal{X},\mathcal{A},\gamma,P,r)$. Q函数可以看作是一个把状态-行为对映射到空间$\mathbb{R}$的函数. 对策略$\pi$, 定义算子$P^\pi$:

$$(P^\pi{Q})(x,a){:=}\sum_{x'\in\mathcal{X}}\sum_{a'\in\mathcal{A}}P(x'|x,a)\pi$$

由于引入了策略算子, 所以关于策略的公式需要替换为带有算子的版本, 例如未来的预计衰减回报和:

$$Q^\pi{:=}\sum_{t\ge0}\gamma^t(P^\pi)^tr$$

策略$\pi$下的贝尔曼算子$T^\pi$定义为:

$$T^\pi{Q}{:=}{r+\gamma{P^\pi{Q}}}$$

其定点为$Q^\pi$, 也就说$T^\pi Q^\pi=Q^\pi=(I-\gamma{P}^\pi)^{-1}r$. 贝尔曼最优算子引入了一组策略中的最大值:

$$TQ{:=}{r+\gamma\max_\pi{P^\pi{Q}}}$$

其顶点为$Q^*$, 这个就是独一无二的最优值函数. 这个在 control setting 予以讨论.

Return-based Operators

$$T_\lambda^\pi{Q}{:=}(1-\lambda)\sum_{n\ge0}\lambda^n[(T^\pi)^nQ]=Q+(I-\lambda\gamma{P^\pi})^{-1}(T^\pi{Q-Q})$$

其中$T^\pi{Q-Q}$是在策略$\pi$下$Q$贝尔曼残差. 通过之前的介绍, $Q^\pi$也是$T_\lambda^\pi$:

  • 在$\lambda=0$的情况下, 贝尔曼算子$T_{\lambda=0}^\pi{Q}=T^\pi{Q}$
  • 在$\lambda=1$, 我们有策略评估(policy evaluation)算子$T_{\lambda=1}^\pi{Q}=Q^\pi$, 可以通过蒙特卡洛方法进行估计.

中间值$\lambda$可以用于权衡估计的偏差和采样方差.

我们也使用根据 行为策略(behavior policy $\mu$)采样得出的轨迹来评估目标策略(target policy)$\pi$. 当$\mu=\pi$的时候, 我们认为是on-polocy, 否则就是off-policy. 轨迹的形式为:

$$x_0=x,a_0=a,r_0,x_1,a_1,r_1,\cdots$$

其中$a_t\sim\mu(\cdot|x_t)$, $r_t=r(x_t,a_t)$, $x_{t+1}\sim{P(\cdot|x_t,a_t)}$. 记$\mathcal{F}_t$是最多到时间t的序列, $\mathbb{E}_\mu$是关于策略$\mu$h和MDP状态转移概率矩阵的矩阵的期望. 同时$||\cdot||$为上确界范数(supremum norm).

Off-Policy 算法

通用的算子, 用于计算一系列的 return-based off-policy 的表达式:

$$RQ(x,a){:=}{Q(x,a)+\mathbb{E}_\mu[\sum_{t\ge0}\gamma^t(\prod^t_{s=1}c_s)(r_t+\gamma{\mathbb{E}_\pi{Q(x_{t+1},\cdot)-Q(x_t,a_t)}})]}$$

其中:

  • $R$为 operator, 对 Q 作用
  • $\pi$ 是target policy 或者为 evaluation policy
  • $\mu$ 是 behavior policy 或者 action policy
  • $\mathbb{E}_\pi{Q(x,\cdot)}{:=}\sum_a{\pi(a|s)Q(s,a)}$, $E_\pi$表示的是在策略$\pi$的分布下求期望. 当$t=0$时, 有$(\Pi^t_{s=1}c_s)=1$.
  • $c_s$是非负系数, 被称为 trace of the operator. 这类似于效用迹(eligibility traces)

重要性采样(IS)

$c_s=\frac{\pi(a_s|x_s)}{\mu(a_s|x_s)}$用于修正当从 off-policy 学习 returns 的策略$\mu$和$\pi$的偏差. 注意 IS 估计会导致大的甚至正无穷的方差, 这个是由于策略的不同而在连乘的情况下导致的:$c_s=\frac{\pi(a_1|x_1)}{\mu(a_1|x_1)}\cdots\frac{\pi(a_t|x_t)}{\mu(a_t|x_t)}$

Off-policy $Q^\pi(\lambda)$和$Q^*(\lambda)$

$c_s=\lambda$, 这个方式来自论文, 带来了 off-policy 和 Q作为 baseline 的关联. 这个方式减小了 IS的方差, 但是这并不能保证对于任意的$\pi$和$\mu$都能收敛.

Tree-backup, TB(λ)

$c_s=\lambda\pi(a_s|x_s)$. 这里用上了target policy $\pi$ 。这下是安全了, 但是对于两种策略相近时(称为near on-policy)的样本利用效率下降了.因为它同样会将一些比较远的轨迹切掉. 而在near on-policy的情况下, 通常是不希望这样去做的.

Retrace(λ)

论文中引出$c_s=\lambda\min(1,\frac{\pi(a_s|x_s)}{\mu(a_s|x_s)})$. 不仅在 $\pi$ 和 $\mu$ 相差比较大时安全了,而且在它俩比较接近时也不会出现切掉较远轨迹的问题。由于最大值是1,所以也不会出现$\prod_{s=1}^{t}{c_s}$数值很大的情况。可谓是上面三个方法的优点的集大成者,而且还避开了它们的缺点。

总结:

论文中[3]的 3.1 和 3.2 节是评估和控制的收敛性分析(contraction properties).

在线更新算法(Online algorithms)

基于 every visit 的 MC 方法. 给定由$\mu_k:a_t~\mu_k(\cdot|x_t)$产生的第k个轨迹: $x_0,a_0,r_0,x_1,a_1,r_1,\cdots$. 对于每一个$(x,a)$, $s$是$(s,a)$首次出现的时间点, 更新:

$$Q_{k+1}(x,a)\gets{Q_k(x,a)+\alpha_k\sum_{t\ge{s}}\delta_t^{\pi_k}}\sum_{j=s}^t\gamma^{t-j}\left({\prod_{i=j+1}^t{c_i}}\right)\mathbb{I}\left\{x_j,a_j=x,a\right\}$$

其中$\delta_t^{\pi_k}{:=}{r_t+\gamma\mathbb{E}_{\pi_k}Q_k(x_{t+1},\cdot)-Q_k(x_{t},\cdot)},\alpha_k=\alpha_k(x_s,a_s)$. 若使用Retrace(λ), 那么$c_i=\lambda\min(1,\frac{\pi(a_i|x_i)}{\mu(a_i|x_i)})$

ACER

经验回放机制能够很好的破除深度Q学习(应该包括了 DNQ)的样本之间的关联性, 但是在深度Q学习由两个问题:

  1. 最优策略的确定性
  2. off-policy 贪心地选择行为在$\mathcal{A}$很大的时候, 开销大.

为了提高 AC 的数据利用率, ACER 使用了 Actor-Critic With Experience Reaply. 融入了 Retrace 算法, 并行的 RL agents. 同时论文[3]的成功却决于算法的出现:

  • truncated importance sampling with bias correction
  • stochastic dueling network architectures
  • efficient trust region policy optimization

主要的记号

和其他 AC 算法一样, ACER 使用了 advantage 的作为减小方差的手段:

$$\begin{aligned}
Q^\pi(x_t,a_t)&=\mathbb{E}_{x_{t+1}:\infty,a_{t+1}:\infty}[R_t|x_t,a_t]\\
V^\pi&=\mathbb{E}_{a_t}[A^\pi(s_t,a_t0)]=\mathbb{E}_{a_t}[Q^\pi(x_t,a_t)-V^\pi(x_t)]
\end{aligned}$$

使用参数$\theta$进行可微分的策略可以被来自[4]的公式更新(GAE):

$$g=\mathbb{E}_{x_0:\infty,a_0:\infty}\left[\sum_{t\ge0}A^\pi(x_t,a_t)\nabla_\theta\log\pi_\theta(a_t|x_t)\right]$$

在[4]中的命题1(Proposition 1), $A^\pi(x_t,a_t)$可以被普通的许多的函数:

ACER 的核心还是通过将$R_t$(这个是折扣后的, 类似于$G_t$)与当前的值函数估计来剑侠偏差并且保持受限的方差

使用 A3C 来平衡方差和偏差, 从一个轨迹来来计算梯度:

$$\hat{g}^\text{a3c}=\sum_{t\ge0}\left\{\left(\sum_{i=0}^{k-1}\gamma^i{r_{y+i}}\right)+\gamma^kV_{\theta_v}^\pi(x_{t+k})-V_{\theta_v}^\pi(x_t)\right\}\nabla_\theta\log\pi_\theta(a_t|x_t)$$

A3C 包括了 k 步的 returns 和值函数估计以权衡方差和偏差. 其中$V_{\theta_v}^\pi(x_t)$是用于降低策略梯度降低方差的 baseline.

离散行为的 ACER

参考了重要性采样, 假设有一段从经验记忆中(experience memory) 获取轨迹$\left\{x_0,a_0,r_0,\mu(\cdot|x_0),\cdots,x_k,a_k,r_k,\mu(\cdot|x_k)\right\}$, $\mu$和 Retrace 中定义的一样, 为行为策略, 故而产生回报. 那么经过重要性加权的策略梯度写作:

$$\begin{equation}
\hat{g}^\text{imp}=(\prod_{t=0}^k\rho_t)\sum_{t=0}^k(\sum_{i=0}^k{\gamma^ir_{t+i}})\nabla_\theta\log{\pi_\theta}(a_t|x_t)
\label{g_impl}
\end{equation}$$

重要性权重$\rho_t=\frac{\pi(a_t|x_t)}{\mu(a_t|x_t)}$, Retrace(λ)算法可用于估计$Q^\pi$. 这个估计是无偏的, 但是会因重要性权重的(未受限的取值范围)的乘积带来高方差, 但是, 在完整的轨迹上进行截断重要性采样, 偏差也高同时仍受限于方差.

[5]通过在$\eqref{g_impl}$的受限分布上使用 marginal value functions , 表示了梯度的估计(原文: attacked this problem by using marginal value functions over the

limiting distribution of the process to yield the following approximation of the gradient:)

$$\begin{equation}
g^\text{marg}=\mathbb{E}_{x_t\sim\beta,a_t\sim\mu}[\rho_t\nabla_\theta\log{\pi_\theta}(a_t|x_t)Q^\pi(x_t,a_t)]
\label{g_marg}
\end{equation}$$

这个来源与 PG 算法的定义有关:(强化学习)- 深入策略梯度 , 还记得那个$d^\mu$. 原始的策略梯度:

$$\begin{aligned}
\nabla_\theta{J(\theta)}&= \nabla_\theta \left[\sum_{s \in \mathcal{S}} d^\pi(s) V^\pi(s)\right] \\
&= \nabla_\theta \left[ \sum_{s \in \mathcal{S}} d^\pi(s) \sum_{a \in \mathcal{A}} \pi_\theta(a \vert s) Q_\pi(s, a) \right] \\
&=\sum_s d^\pi(s) \sum_a \left[ \nabla_\theta \pi_\theta(a \vert s)Q_\pi(s, a) +\pi(a|s)\nabla_\theta{Q_\pi(s,a)}\right] \\
\end{aligned}$$

注意, 如果是 on-policy, 是$d^\pi$, 但是行为策略不同的化, 就需要另设$d^\mu$. PG 的目标就是最大化(忽略了原始策略梯度中很难求的$\nabla_\theta{Q_\pi(s,a)}$):

$$\nabla_\theta{J(\theta)}\simeq{g(\theta)}=\sum_s d^\pi(s) \sum_a \left[ \nabla_\theta \pi_\theta(a \vert s)Q_\pi(s, a) \right]$$

然后通过 IS 大法(设$\beta{:=}{d^\mu}$):

$$\begin{aligned}
g(\theta)&=\sum_s \beta(s) \color{red}{\sum_a \left[ \nabla_\theta \pi_\theta(a \vert s)Q_\pi(s, a) \right]} &\\
&=\mathbb{E}_{s\sim\beta}\left[{\sum_a \nabla_\theta \pi_\theta(a \vert s)Q_\pi(s, a)}\right]&\scriptstyle{\text{假设}\color{red}{\sum_a \left[ \nabla_\theta \pi_\theta(a \vert s)Q_\pi(s, a) \right]}\color{black}{\text{的概率密度为}\beta(s)}}\\
&=\mathbb{E}_{s\sim\beta}\left[{\sum_a \mu(a|s)\frac{\pi(a|s)}{\mu(a|s)} \frac{\nabla_\theta \pi_\theta(a \vert s)}{\pi(a|s)}Q_\pi(s, a)}\right]&\\
&=\mathbb{E}_{s\sim\beta,a\sim\mu(\cdot|s)}\left[\rho(s,a)\nabla_\theta\log{\pi_\theta}(a_t|x_t)Q_\pi(s,a)\right]
\end{aligned}$$

其中, $\mathbb{E}_{x_t\sim\beta,a_t\sim\mu}[\cdot]$是关于受限分布$\beta(x)=\lim_{t\to\infty}P(x_t=x|x_0,\mu)$的期望, 将$\mathbb{E}_{x_t\sim\beta,a_t\sim\mu}$简化为$\mathbb{E}_{x_t,a_t}$用于简洁表示.

$\eqref{g_marg}$重要在于:

  • $\eqref{g_marg}$以来于$Q^\pi$而非$Q^\mu$这也导致了后来我们需要有办法估计$Q^\pi$
  • 不再需要对重要性权重求连乘, 转而使用 marginal 重要性权重$\rho_t$

多步状态-值函数估计(multi-step estimation of the state-action value function)

在$\eqref{g_marg}$中, 需要估计$Q^\pi$. 根据行为策略$\mu$产生的轨迹, $\lambda=1$的简化版本的 Retrace 的递归估计器(estimator):

$$Q^\text{ret}(x_t,a_t)=r_t+\gamma{\overline{{\rho}}_{t+1}[Q^\text{ret}(x_{t+1},a_{t+1})-Q(x_{t+1},a_{t+1})]+\gamma{V(x_{t+1})}}$$

其中, $\overline{\rho}_t$是为了防止$\rho_t$连乘出现的方差过大而做的截断: $\overline{\rho}_t=\min\left\{c,\rho_t\right\}$, $Q$是当前值函数$Q^\pi$的估计, $V(x)=\mathbb{E}_{a\sim\pi}Q(x,a)$, Retrace 由低方差而且在表格(tabular)的情况下对于目标策略的任何一个行为策略的值函数是可以收敛的(在[1]的证明中). 神经网络的表示也是一样, 除了输出向量$Q_{\theta_v}(x_t,a_t)$而非标量的$V_{\theta_v}(x_t)$, 且后者还可以继续写为为$Q_{\theta_v}$在$\pi_\theta$的期望.

为了估计策略梯度$g^\text{marg}$, ACER 使用了$Q^\text{ret}$来估计$Q^\pi$. Critic 部分估计$Q_{\theta_v}(x_t,a_t)$并输出均方误差同时更新值函数网络的参数$\theta_v$:

$$(Q^\text{ret}(x_t,a_t)-Q_{\theta_v}(x_t,a_t))\nabla_{\theta_v}Q_{\theta_v}(x_t,a_t)$$

因为 Retrace 是基于 return 的, 这个使 critic 学习地更快, 估计器$Q^\text{ret}$带来了:

  • 降低策略梯度的偏差
  • 由于降低了偏差, critic 学习地更快

importance weight truncation with bias correction

$\eqref{g_marg}$还是可能变得很大, 导致不稳定, 为了避免高方差, 提出了截断重要性权重和修正项:

$$
\begin{equation}
\begin{aligned}
g^\text{marg}&=\mathbb{E}_{x_t,a_t}[\rho_t\nabla_\theta\log{\pi_\theta}(a_t|x_t)Q^\pi(x_t,a_t)]\\
&=\mathbb{E}_{x_t}\left[{\mathbb{E}_{a_t}[\overline{\rho}_t\nabla_\theta\log{\pi_\theta}(a_t|x_t)Q^\pi(x_t,a_t)]+\mathbb{E}_{a\sim\pi}\left({ \left[ \frac{\rho_t(a)-c}{\rho_t(a)} \right]_+\nabla_\theta\log{\pi_\theta}(a|x_t)Q^\pi(x_t,a) } \right) }\right]
\end{aligned}
\end{equation}
\label{g_marg_clipped}
$$

其中, $\overline{\rho}_t=\min\left\{c,\rho_t\right\}$, 其中$\rho_t=\frac{\pi(a_t|x_t)}{\mu(a_t|x_t)}$. 公式的$\eqref{g_marg_clipped}$:

  • 第一项: 保证梯度的估计的方差有限
  • 第二项: 称为 correction term, 确保估计使无偏的. $[x]_+=x\quad{\text{if}\quad x>0}$. 也就是说, 当$\rho_t(a)>c$的时候, 这一项才有用, 也就是当选择很大的$c$值, 修正项只对在公式$\eqref{g_marg}$具有高方差中起作用, 同时 correction term 在第一项接接近于$c$的时候, $\left[ \frac{\rho_t(a)-c}{\rho_t(a)} \right]_+$接近于1

如果将 correction term 引入到以神经网络作为估计器的$Q_{\theta_v}(x_t,a_t)$, 那么估计的值函数写为:

$$\begin{equation}
\hat{g}^\text{marg}=\mathbb{E}_{x_t}\left[{\mathbb{E}_{a_t}[\overline{\rho}_t\nabla_\theta\log{\pi_\theta}(a_t|x_t)Q^\text{ret}(x_t,a_t)]+\mathbb{E}_{a\sim\pi}\left({ \left[ \frac{\rho_t(a)-c}{\rho_t(a)} \right]_+\nabla_\theta\log{\pi_\theta}(a|x_t)Q_{\theta_v}(x_t,a) } \right) }\right]
\label{g_marg_approx}
\end{equation}$$

公式$\eqref{g_marg_approx}$就是马尔可夫过程的平稳分布的期望, 但是可以在采样的轨迹$\left\{x_0,a_0,r_0,\mu(\cdot|x_0),\cdots,x_k,a_k,r_k,\mu(\cdot|x_k)\right\}$进行估计. 其中$\mu(\cdot|x_t)$是策略向量. 计算 off-policy 的 ACER 策略梯度:

$$\begin{equation}
\hat{g}_t^\text{acer}={\overline{\rho}_t\nabla_\theta\log{\pi_\theta}(a_t|x_t)[Q^\text{ret}(x_t,a_t)-V_{\theta_v}(x_t)]+\mathbb{E}_{a\sim\pi}\left({ \left[ \frac{\rho_t(a)-c}{\rho_t(a)} \right]_+\nabla_\theta\log{\pi_\theta}(a_t|x_t)[Q_{\theta_v}(x_t,a)-V_{\theta_v}(x_t)] } \right) }
\label{g_acer_approx}
\end{equation}
$$

注意, 我们还是需要 baseline. 当$c=\infty$, 那么公式$\eqref{g_acer_approx}$就变成使用 Retrace 的 off-policy 策略梯度; 如果$c=0$, 那么公式$\eqref{g_acer_approx}$就变成了依赖于对 Q估计的 AC 更新公式.

高效的 TRPO (efficient TRPO)

TRPO 是 PG 的一个优化算法, 具体见[7]. ACER 论文使用高效的 TRPO, 不需要计算开销大的 Fisher 向量点积. 新的 TROP 算法中, 提出了 average policy network, 它用于表示先前策略得平均并使用强制更新策略不使用这个平均.

论文把策略网络分为两部分:

  1. 分布函数 $f$
  2. 生成$f$的统计$\phi_\theta(x)$的神经网络. 也就是$\phi_\theta(\cdot|x)=f(\cdot|\phi_\theta(x))$.

记平均策略网络为$\phi_{\theta_a}$和 softly (可能是平缓更新)更新每一个策略的参数$\theta$的更新参数$\theta_a$: $\theta_a\gets{\alpha\theta_a+(1-\alpha)\theta}$.

按照公式$\eqref{g_acer_approx}$, 并引入$\phi$:

$$
\begin{equation}
\hat{g}_t^\text{acer}={\overline{\rho}_t\nabla_{\phi_\theta(x_t)}\log{f}(a_t|\phi_\theta(x))[Q^\text{ret}(x_t,a_t)-V_{\theta_v}(x_t)]+\mathbb{E}_{a\sim\pi}\left({ \left[ \frac{\rho_t(a)-c}{\rho_t(a)} \right]_+\nabla_{\phi_\theta(x_t)}\log{f}(a_t|\phi_\theta(x))[Q_{\theta_v}(x_t,a)-V_{\theta_v}(x_t)] } \right) }
\label{g_acer_phi}
\end{equation}
$$

新版本公式$\eqref{g_acer_phi}$的更新主要有两阶段:

  1. 解根据 KL 散度限制下的最优问题:

$$\begin{aligned}
\text{minimize}_z&\quad\frac{1}{2}||\hat{g}_t^\text{acer}-z||_2^2\\
\text{s.t.}&\quad\nabla_{\phi_\theta(x_t)}D_{KL}[f(\cdot|\phi_{\theta_a}(x_t))||f(\cdot|\phi_{\theta}(x_t))]^T\quad{z\le\delta}
\end{aligned}
$$
由于这是个线性约束, 问题转换为二次规划问题, 并应用 KKT 条件并转换为拉格朗日对偶问题: 详细的证明在[6]的275页. 令$k=\nabla_{\phi_\theta(x_t)}D_{KL}[f(\cdot|\phi_{\theta_a}(x_t))||f(\cdot|\phi_{\theta}(x_t))]$, 解为:$$z^*=\hat{g}_t^\text{acer}-\max\left\{0,\frac{k^T\hat{g}_t^\text{acer}-\delta}{||k||_2^2}\right\}k$$

如果约束满足, 那么关于$\phi_\theta(x_t)$的梯度不会改变; 否则, 更新的幅度成比例以$k$的梯度方向减小, 因为低学习率($\alpha$吗?)是激活当前策略还是平均策略网络的分水岭.

  1. 利用 BP 算法, $z^*$是以$\phi_\theta$为参数的更新后的权重. 根据链式法则, 跟新策略网络:

$$\frac{\partial{\phi_\theta}(x)}{\partial\theta}z^*$$
当然 trust region 是在分布$f$上的进行的操作, 所以在反向传播的时候需要在计算策略网络的之前停止传播. (例如tf.stop_gradient之类的操作)

伪代码

主控算法用于运行更新策略以及产生轨迹

算法2是离散部分的, 用于执行一些列的回放操作, 当使用 on-policy 的时候, ACER 的 baseline 是$Q$而不是 A3C 中的$V$, 仅此区别.

实验、连续空间、证明等内容见[3]

连续空间下的ACER

参考

  1. Munos, R., Stepleton, T., Harutyunyan, A., & Bellemare, M. (2016). Safe and efficient off-policy reinforcement learning. In Advances in Neural Information Processing Systems (pp. 1054-1062).
  2. RL Algorithm: Retrace
  3. Wang, Z., Bapst, V., Heess, N., Mnih, V., Munos, R., Kavukcuoglu, K., & de Freitas, N. (2016). Sample efficient actor-critic with experience replay. arXiv preprint arXiv:1611.01224.
  4. [J. Schulman, P. Moritz, S. Levine, M. I. Jordan, and P. Abbeel. High-dimensional continuous control usinggeneralized advantage estimation. arXiv:1506.02438, 2015b.]()
  5. T. Degris, M. White, and R. S. Sutton. Off-policy actor-critic. In ICML, pp. 457–464, 2012.
  6. 强化学习精要: 核心算法与 TensorFlow 实现. 冯超著, 2018, 电子工业出版社.
  7. J. Schulman, S. Levine, P. Abbeel, M. I. Jordan, and P. Moritz. Trust region policy optimization. In ICML, 2015a.

添加评论