# IMPALA

> [IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures](https://arxiv.org/pdf/1802.01561.pdf)

在这项工作中，我们的目标是使用单个强化学习代理来解决大量任务。 一个关键的挑战是处理增加的数据量和延长的培训时间。 我们开发了一种新的分布式代理IMPALA（Importance Weighted Actor-Learner Architectures），它不仅可以在单机训练中更有效地使用资源，而且可以扩展到数千台机器而不会牺牲数据效率或资源利用率。 通过将解耦的行为学习与一种称为V-trace的校正方法相结合，我们实现了稳定的高吞吐学习。 我们展示了IMPALA在DMLab-30和Atari-57中的多任务强化学习的有效性。 我们的结果表明，IMPALA能够在数据较少的情况下取得比以前的代理更好的性能，并且由于其多任务处理方式，在任务之间表现出了正向的迁移。

## 方法

### IMPALA

![](https://2281160879-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LaNHyhKoX7GdL4Ytevq%2F-LaNII8X8nnM6zkOZPLK%2F-LaNIJQCI-XYUa2P0U1b%2Fimage%20\(57\).png?generation=1553038396527077\&alt=media)

如图1，在每个轨迹的开始，actor将自己的本地策略 $$μ$$ 更新为最新的Leaner的策略 $$π$$ ，并在其环境中运行在n步之l后，actor通过队列将状态、动作和回报 $${x\_{1}, a\_{1}, r\_{1}, \dots, x\_{n}, a\_{n}, r\_{n}}$$ 连同相应的策略分布 $$\mu\left(a\_{t} | x\_{t}\right)$$ 和初始LSTM状态一起发送给leaner。然后，leaner利用样本轨迹更新策略 $$π$$ 。这种简单的架构使得leaner能够使用GPU加速，并且actor能够轻松地分布在许多机器上。然而，在更新时，leaner的策略 $$π$$ 可能比actor的策略 $$μ$$ 提前更新几个版本，因此actor和leaner之间存在一种policy-lag。V-trace校正了这种lag，从而在保持数据效率的同时实现极高的数据吞吐量。使用actor-learner 架构，提供像分布式A3C这样的容错能力，但是由于actor并且没有发送参数/梯度，因此通信开销较低。

### V-trace

在解耦的分布式actor-critic架构中，off-policy学习很重要，因为actor生成动作与leaner估计梯度之间存在滞后。 为此，我们为学习者引入了一种新颖的off-policy actor-critic算法，称为V-trace。

off-policy RL算法的目标是使用某个策略 $$μ$$ 生成的轨迹，称为行为策略，来学习另一个策略 $$π$$ (可能不同于 $$μ$$ )的值函数 $$v\_π$$ ，称为目标策略。

#### V-trace target

考虑行为策略 $$μ$$ 生成的轨迹 $$\left(x\_{t}, a\_{t}, r\_{t}\right)\_{t=s}^{t=s+n}$$ ，n-steps V-trace的价值函数为

$$v\_{s} \stackrel{\mathrm{def}}{=} \quad V\left(x\_{s}\right)+\sum\_{t=s}^{s+n-1} \gamma^{t-s}\left(\prod\_{i=s}^{t-1} c\_{i}\right) \delta\_{t} V$$

上式中 $$\delta\_{t} V \stackrel{\mathrm{def}}{=} \rho\_{t}\left(r\_{t}+\gamma V\left(x\_{t+1}\right)-V\left(x\_{t}\right)\right)$$ 是时间差分。 $$\rho\_{t} \stackrel{\mathrm{def}}{=} \min \left(\overline{\rho}, \frac{\pi\left(a\_{t} | x\_{t}\right)}{\mu\left(a\_{t} | x\_{t}\right)}\right)$$ 和 $$c\_{i} \stackrel{\mathrm{def}}{=} \min \left(\overline{c}, \frac{\pi\left(a\_{i} | x\_{i}\right)}{\mu\left(a\_{i} | x\_{i}\right)}\right)$$ 是截断的重要性采样权重，其中 $$\prod\_{i=s}^{t-1} c\_{i}=1 for (t = s)$$ ，且假设 $$\overline{\rho} \geq \overline{c}$$ 。

注意：对于on-policy的情况，我们假定 $$\overline{c} \geq 1$$ ， $$c\_{i}=1 \text { and } \rho\_{t}=1$$ ，上式可被写为：

$$\begin{aligned} v\_{s} &=V\left(x\_{s}\right)+\sum\_{t=s}^{s+n-1} \gamma^{t-s}\left(r\_{t}+\gamma V\left(x\_{t+1}\right)-V\left(x\_{t}\right)\right) \ &=\sum\_{t=s}^{s+n-1} \gamma^{t-s} r\_{t}+\gamma^{n} V\left(x\_{s+n}\right) \end{aligned}$$

所以在on-policy的时候，V-trace退化为on-policy n-steps Bellman update，这个性质允许V-trace同时用于off-policy和on-policy。

注意：截断的重要性采样权重 $$c\_{i} \text { and } \rho\_{t}$$ 的作用是不同的， $$\rho\_{t}$$ 出现在时间差分 $$\delta\_{t} V$$ 中，定义了更新的fixed point。在表格法（强化学习）中，更新的fixed point（即当 $$V\left(x\_{s}\right)=v\_{s}\ for\ all\ state$$ ），特征为 $$\delta\_{t} V$$的期望等于0（在策略 $$μ$$ 下），是一些策略 $$\pi\_{\overline{\rho}}$$ （定义如下）的值函数 $$V^{\pi} \overline{\rho}$$

$$\pi\_{\overline{\rho}}(a | x) \stackrel{\mathrm{def}}{=} \frac{\min (\overline{\rho} \mu(a | x), \pi(a | x))}{\sum\_{b \in A} \min (\overline{\rho} \mu(b | x), \pi(b | x))}$$

这意味着，当 $$\overline{\rho}<\infty$$ 时，策略 $$\pi\_{\overline{\rho}}$$ 介于目标策略 $$\pi$$ 和行为策略$$μ$$之间。而 $$\overline{\rho}=\infty$$ 时候，该策略等于目标策略$$\pi$$。

$$c\_{i}$$ 类似于"trace cutting"系数， $$c\_{s} \ldots c\_{t-1}$$ 的乘积度量着时间差分$$\delta\_{t} V$$在时间 $$t$$ 出现的频率，影响着 $$t=s$$ 的值函数更新。目标策略$$\pi$$和行为策略$$\pi$$相差越大，这个乘积的方差越大，这里通过截断来限制方差。

总的来说： $$\overline{\rho}$$ 影响收敛到的价值函数的性质， $$\overline{c}$$ 影响收敛到这个函数的速度。

![](https://2281160879-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LaNHyhKoX7GdL4Ytevq%2F-LaNII8X8nnM6zkOZPLK%2F-LaNIJQP8TTIJ_Pakdtn%2Fimage%20\(97\).png?generation=1553038399048116\&alt=media)

#### Actor-Critic algorithm

**策略梯度(Policy Gradient)**

在on-policy的情况下，价值函数关于策略 $$μ$$ 的参数的梯度为

$$\nabla V^{\mu}\left(x\_{0}\right)=\mathbb{E}*{\mu}\left\[\sum*{s \geq 0} \gamma^{s} \nabla \log \mu\left(a\_{s} | x\_{s}\right) Q^{\mu}\left(x\_{s}, a\_{s}\right)\right]$$

其中： $$Q^{\mu}\left(x\_{s}, a\_{s}\right) \stackrel{\mathrm{def}}{=} \mathbb{E}*{\mu}\left\[\sum*{t \geq s} \gamma^{t-s} r\_{t} | x\_{s}, a\_{s}\right]$$

现在考虑off-policy的情况，我们可以重要性权重来更新策略参数：

$$\mathbb{E}*{a*{s} \sim \mu(\cdot | x\_{s})}\left\[\frac{\pi\_{\overline{\rho}}\left(a\_{s} | x\_{s}\right)}{\mu\left(a\_{s} | x\_{s}\right)} \nabla \log \pi\_{\overline{\rho}}\left(a\_{s} | x\_{s}\right) q\_{s} | x\_{s}\right] \ \ (4)$$

其中： $$q\_{s} \stackrel{\mathrm{def}}{=} r\_{s}+\gamma v\_{s+1}$$ *，*&#x6700;后为了减少方差，我们减去了一个强化学习中的基数 $$V\left(x\_{s}\right)$$

最后注意(4)估计 $$\pi\_{\overline{\rho}}$$ 的策略梯度，这是使用截断级别 $$\overline{\rho}$$ 的V-trace算法评估的策略。

**扩展到Actor-Critic**

critic梯度

$$\left(v\_{s}-V\_{\theta}\left(x\_{s}\right)\right) \nabla\_{\theta} V\_{\theta}\left(x\_{s}\right)$$

actor梯度

$$\rho\_{s} \nabla\_{\omega} \log \pi\_{\omega}\left(a\_{s} | x\_{s}\right)\left(r\_{s}+\gamma v\_{s+1}-V\_{\theta}\left(x\_{s}\right)\right)$$

为了防止过早收敛，我们可能增加*一个*熵

$$-\nabla\_{\omega} \sum \pi\_{\omega}(a | x\_{s}) \log \pi\_{\omega}(a | x\_{s})$$

## 实验

### 训练性能

![](https://2281160879-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LaNHyhKoX7GdL4Ytevq%2F-LaNII8X8nnM6zkOZPLK%2F-LaNIJQTRw08JTqTUczw%2Fimage%20\(34\).png?generation=1553038396651402\&alt=media)

### 游戏测试

![](https://2281160879-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LaNHyhKoX7GdL4Ytevq%2F-LaNII8X8nnM6zkOZPLK%2F-LaNIJQV6JUcHOeUgdqK%2Fimage%20\(110\).png?generation=1553038396881461\&alt=media)