# TRPO

> [Trust Region Policy Optimization](https://arxiv.org/pdf/1502.05477.pdf)

我们描述了一个优化策略的迭代过程，保证了单调的改进。 通过对理论上合理的过程进行几次近似，我们开发了一种称为信任区域策略优化（TRPO）的实用算法。 该算法与自然策略梯度方法类似，对于优化大型非线性策略（如神经网络）是有效的。 我们的实验证明了它在各种任务中的强大性能：学习模拟机器人游泳，跳跃和步行步态; 并使用屏幕图像作为输入玩Atari游戏。 尽管它的近似值偏离了理论，但TRPO倾向于提供单调的改进，通过微调超参数。

## 方法

### 预备

定义期望折扣回报

$$\begin{array}{l}{\eta(\pi)=\mathbb{E}*{s 0, a*{0}, \ldots}\left\[\sum\_{t=0}^{\infty} \gamma^{t} r\left(s\_{t}\right)\right], \text { where }} \ {s\_{0} \sim \rho\_{0}\left(s\_{0}\right), a\_{t} \sim \pi\left(a\_{t} | s\_{t}\right), s\_{t+1} \sim P\left(s\_{t+1} | s\_{t}, a\_{t}\right)}\end{array}$$

定义价值函数、动作价值函数、动作优势价值函数

$$
\begin{array}{l}{Q\_{\pi}\left(s\_{t}, a\_{t}\right)=\mathbb{E}*{s*{t+1}, a\_{t+1}, \ldots}\left\[\sum\_{l=0}^{\infty} \gamma^{l} r\left(s\_{t+l}\right)\right]} \ {V\_{\pi}\left(s\_{t}\right)=\mathbb{E}*{a*{t}, s\_{t+1}, \ldots}\left\[\sum\_{l=0}^{\infty} \gamma^{l} r\left(s\_{t+l}\right)\right]} \ {A\_{\pi}(s, a)=Q\_{\pi}(s, a)-V\_{\pi}(s), \text { where }} \ {a\_{t} \sim \pi\left(a\_{t} | s\_{t}\right), s\_{t+1} \sim P\left(s\_{t+1} | s\_{t}, a\_{t}\right) \text { for } t \geq 0}\end{array}
$$

定义策略 $$\tilde{\pi}$$ 相对于策略 $$\pi$$ 的期望优势

$$\eta(\tilde{\pi})=\eta(\pi)+\mathbb{E}*{s*{0}, a\_{0}, \cdots \sim \tilde{\pi}}\left\[\sum\_{t=0}^{\infty} \gamma^{t} A\_{\pi}\left(s\_{t}, a\_{t}\right)\right]$$

即动作根据$$\tilde{\pi}$$采样，策略评估还是使用 $$\pi$$

令 $$\rho\_{\pi}(s)=P\left(s\_{0}=s\right)+\gamma P\left(s\_{1}=s\right)+\gamma^{2} P\left(s\_{2}=s\right)+\ldots$$ ，上式可写为

$$
\begin{aligned} \eta(\tilde{\pi}) &=\eta(\pi)+\sum\_{t=0} \sum\_{s} P\left(s\_{t}=s | \tilde{\pi}\right) \sum\_{a} \tilde{\pi}(a | s) \gamma^{t} A\_{\pi}(s, a) \ &=\eta(\pi)+\sum\_{s} \sum\_{t=0}^{\infty} \gamma^{t} P\left(s\_{t}=s | \tilde{\pi}\right) \sum\_{a} \tilde{\pi}(a | s) A\_{\pi}(s, a) \ &=\eta(\pi)+\sum\_{s} \rho\_{\tilde{\pi}}(s) \sum\_{a} \tilde{\pi}(a | s) A\_{\pi}(s, a) \end{aligned}
$$

这个式子表明只要能保证 $$\sum\_{a} \tilde{\pi}(a | s) A\_{\pi}(s, a) \geq 0$$ ，策略的期望回报就能增大。考虑策略迭代 $$\tilde{\pi}(s)=\arg \max *{a} A*{\pi}(s, a)$$ ，只要一个 $$A\_\pi$$ 大于0，策略就会被提升，否则收敛。但是在近似的情况下，由于误差的存在，不可避免的有 $$\sum\_{a} \tilde{\pi}(a | s) A\_{\pi}(s, a)<0$$ 出现。为了简化问题我们提出了下面的近似公式：

$$
L\_{\pi}(\tilde{\pi})=\eta(\pi)+\sum\_{s} \rho\_{\pi}(s) \sum\_{a} \tilde{\pi}(a | s) A\_{\pi}(s, a)
$$

注意这里使用的是 $$\rho\_{\pi}(s)$$ 而不是 $$\rho\_{\tilde{\pi}}(s)$$ ，即使用旧策略采样的状态频率。

因为 $$L\_{\pi}$$ 与 $$\eta$$ 一阶匹配，则有梯度

$$
\begin{aligned} L\_{\pi\_{\theta\_{0}}}\left(\pi\_{\theta\_{0}}\right) &=\eta\left(\pi\_{\theta\_{0}}\right) \ \nabla\_{\theta} L\_{\pi\_{\theta\_{0}}}\left.\left(\pi\_{\theta}\right)\right|*{\theta=\theta*{0}} &=\nabla\_{\theta} \eta\left.\left(\pi\_{\theta}\right)\right|*{\theta=\theta*{0}} \end{aligned}
$$

上式给出了一个增强策略的梯度方向，然而却没有指出合适的步长，为了解决这个问题我们采用新的思路：

令 $$\pi^{\prime}=\arg \max *{\pi^{\prime}} L*{\pi\_{\mathrm{old}}}\left(\pi^{\prime}\right)$$ ，令新策略为 $$\pi\_{\text { new }}(a | s)=(1-\alpha) \pi\_{\text { old }}(a | s)+\alpha \pi^{\prime}(a | s)$$

根据 Kakade & Langford (2002) 等人的相关工作有下界关系：

$$\eta\left(\pi\_{\text { new }}\right) \geq L\_{\pi\_{\text { old }}}\left(\pi\_{\text { new }}\right)-\frac{2 \epsilon \gamma}{(1-\gamma)^{2}} \alpha^{2} \ where\ \epsilon=\max *{s}\left|\mathbb{E}*{a \sim \pi^{\prime}(a | s)}\left\[A\_{\pi}(s, a)\right]\right|$$

我们只要让下界单调递增，则可实现策略的提升

### 一般随机策略的单调改进保证

我们用total variation divergence作为 $$\alpha$$ 的度量 ：

$$D\_{\mathrm{TV}}^{\max }(\pi, \tilde{\pi})=\max *{s} D*{T V}(\pi(\cdot | s) | \tilde{\pi}(\cdot | s))$$ ，有定理（证明见原文附录）

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

注意到其与KL散度的关系 $$D\_{T V}(p | q)^{2} \leq D\_{\mathrm{KL}}(p | q)$$ ，定理可写为

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

于是有如下算法，可以保证策略的单调递增

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

证明：令 $$M\_{i}(\pi)=L\_{\pi\_{i}}(\pi)-C D\_{\mathrm{KL}}^{\max }\left(\pi\_{i}, \pi\right)$$ ，结合上式有

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

我们提出了算法1的近似算法Trust region policy optimization，其使用KL散度作为约束而不是惩罚项，以支持健壮的大步更新。

### 参数化策略的优化

我们把算法1的问题从

$$\underset{\theta}{\operatorname{maximize}}\left\[L\_{\theta\_{\text { old }}}(\theta)-C D\_{\mathrm{KL}}^{\max }\left(\theta\_{\text { old }}, \theta\right)\right]$$

转换为带约束的最大化问题

$$\begin{array}{l}{\text { maximize } L\_{\theta\_{\text { old }}}(\theta)} \ {\text { subject to } D\_{\mathrm{KL}}^{\max }\left(\theta\_{\text { old }}, \theta\right) \leq \delta}\end{array}$$

同时为了方便解决约束问题，我们用平均KL散度替换最大KL散度

$$\overline{D}*{\mathrm{KL}}^{\rho}\left(\theta*{1}, \theta\_{2}\right) :=\mathbb{E}*{s \sim \rho}\left\[D*{\mathrm{KL}}\left(\pi\_{\theta\_{1}}(\cdot | s) | \pi\_{\theta\_{2}}(\cdot | s)\right]\right.$$

于是得到

$$\begin{array}{l}{\text { maximize } L\_{\theta\_{\text { old }}}(\theta)} \ {\text { subject to } \overline{D}*{\mathrm{KL}}^{\rho \theta*{\text { old }}}\left(\theta\_{\text { old }}, \theta\right) \leq \delta}\end{array}$$

### 基于采样的目标和约束估计

本节旨在用蒙特卡洛模拟近似上面的优化问题，展开 $$L\_{\theta \text { old }}(\theta)$$

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

首先用 $$\frac{1}{1-\gamma} \mathbb{E}*{s \sim \rho*{\theta\_{\text { old }}}}\[\ldots]$$ 替换 $$\sum\_{S} \rho\_{\theta\_{\text { old }}}(s)\[\ldots]$$ ，然后用用 $$Q\_{\theta\_{\text { old }}}$$ 替换 $$A\_{\theta\_{\text { old }}}$$

最后用重要性采样处理动作求和

$$\sum\_{a} \pi\_{\theta}(a | s\_{n}) A\_{\theta\_{\text { old }}}\left(s\_{n}, a\right)=\mathbb{E}*{a \sim q}\left\[\frac{\pi*{\theta}(a | s\_{n})}{q(a | s\_{n})} A\_{\theta\_{\text { old }}}\left(s\_{n}, a\right)\right]$$

得到等价优化目标

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

剩下的就是用样本均值代替期望值，用经验估计代替Q值。以下部分描述了两种不同的方案来执行这种估计。

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

### 实际算法

通常可以分为三步

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

原文附录C给出了具体的优化算法

总结前面的内容

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

### 与前面工作的联系

使用L的线性近似和KL散度的二阶近似，自然梯度更新可以视为TRPO的特例

$$
\begin{array}{l}{\text { maximize }\left\[\nabla\_{\theta} L\_{\theta\_{\text { old }}}\left.(\theta)\right|*{\theta=\theta*{\text { old }}} \cdot\left(\theta-\theta\_{\text { old }}\right)\right]} \ {\text { subject to } \frac{1}{2}\left(\theta\_{\text { old }}-\theta\right)^{T} A\left(\theta\_{\text { old }}\right)\left(\theta\_{\text { old }}-\theta\right) \leq \delta} \ {\text { where } A\left(\theta\_{\text { old }}\right)*{i j}=} \ {\frac{\partial}{\partial \theta*{i}} \frac{\partial}{\partial \theta\_{j}} \mathbb{E}*{s \sim \rho*{\pi}}\left.\left\[D\_{\mathrm{KL}}(\pi(\cdot | s, \theta\_{\text { old }}) | \pi(\cdot | s, \theta))\right]\right|*{\theta=\theta*{\text { old }}}}\end{array}
$$

更新式: $$\theta\_{\text { new }}=\theta\_{\text { old }}+\frac{1}{\lambda} A\left(\theta\_{\text { old }}\right)^{-1} \nabla\_{\theta} L\left.(\theta)\right|*{\theta=\theta*{\text { old }}}$$

## 实验

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