Trust Region Policy Optimization

信赖域策略优化

John Schulman    Sergey Levine    Philipp Moritz    Michael I. Jordan    Pieter Abbeel

Abstract

摘要

We describe an iterative procedure for optimizing policies, with guaranteed monotonic improvement. By making several approximations to the theoretically-justified procedure, we develop a practical algorithm, called Trust Region Policy Optimization (TRPO). This algorithm is similar to natural policy gradient methods and is effective for optimizing large nonlinear policies such as neural networks. Our experiments demonstrate its robust performance on a wide variety of tasks: learning simulated robotic swimming, hopping, and walking gaits; and playing Atari games using images of the screen as input. Despite its approximations that deviate from the theory, TRPO tends to give monotonic improvement, with little tuning of hyperparameters.

我们描述一种有单调改进保证的策略迭代优化流程。对理论保证的流程做若干近似后，得到实用算法——信赖域策略优化（Trust Region Policy Optimization，TRPO）。该算法与自然策略梯度方法相近，能有效优化神经网络一类大型非线性策略。实验表明它在多种任务上表现稳健：学习仿真机器人的游泳、跳跃与行走步态，以及用屏幕图像作输入玩 Atari 游戏。尽管近似偏离了理论，TRPO 仍往往给出单调改进，且超参几乎不用细调。

1 Introduction

1 引言

Most algorithms for policy optimization can be classified into three broad categories: (1) policy iteration methods, which alternate between estimating the value function under the current policy and improving the policy (Bertsekas 2005); (2) policy gradient methods, which use an estimator of the gradient of the expected return (total reward) obtained from sample trajectories (Peters & Schaal 2008a) (and which, as we later discuss, have a close connection to policy iteration); and (3) derivative-free optimization methods, such as the cross-entropy method (CEM) and covariance matrix adaptation (CMA), which treat the return as a black box function to be optimized in terms of the policy parameters (Szita & Lörincz 2006).

策略优化算法大体可分三类：（1）策略迭代：在当前策略下估计价值函数与改进策略之间交替（Bertsekas 2005）；（2）策略梯度：用样本轨迹估计期望回报（总奖励）的梯度（Peters & Schaal 2008a）（后文也会谈到它与策略迭代的密切联系）；（3）无导数优化，如交叉熵方法（CEM）与协方差矩阵自适应（CMA），把回报当作策略参数上的黑箱函数来优化（Szita & Lörincz 2006）。

General derivative-free stochastic optimization methods such as CEM and CMA are preferred on many problems, because they achieve good results while being simple to understand and implement. For example, while Tetris is a classic benchmark problem for approximate dynamic programming (ADP) methods, stochastic optimization methods are difficult to beat on this task (Gabillon et al. 2013). For continuous control problems, methods like CMA have been successful at learning control policies for challenging tasks like locomotion when provided with hand-engineered policy classes with low-dimensional parameterizations (Wampler & Popović 2009). The inability of ADP and gradient-based methods to consistently beat gradient-free random search is unsatisfying, since gradient-based optimization algorithms enjoy much better sample complexity guarantees than gradient-free methods (Nemirovski 2005). Continuous gradient-based optimization has been very successful at learning function approximators for supervised learning tasks with huge numbers of parameters, and extending their success to reinforcement learning would allow for efficient training of complex and powerful policies.

在许多问题上，人们更偏爱 CEM、CMA 这类通用无导数随机优化：效果好，又简单易懂、好实现。例如，俄罗斯方块是近似动态规划（ADP）的经典基准，但随机优化方法在该任务上很难被打败（Gabillon et al. 2013）。连续控制里，若策略类由人工设计且参数维度低，CMA 等也能成功学会运动控制（Wampler & Popović 2009）。ADP 与基于梯度的方法无法稳定胜过无梯度随机搜索，这一点令人不满：因为有梯度的优化在样本复杂度保证上远好于无梯度方法（Nemirovski 2005）。连续梯度优化已在参数量巨大的监督学习函数逼近器上非常成功；若能把这一成功延到强化学习，就可高效训练复杂而强大的策略。

In this article, we first prove that minimizing a certain surrogate objective function guarantees policy improvement with non-trivial step sizes. Then we make a series of approximations to the theoretically-justified algorithm, yielding a practical algorithm, which we call trust region policy optimization (TRPO). We describe two variants of this algorithm: first, the single-path method, which can be applied in the model-free setting; second, the vine method, which requires the system to be restored to particular states, which is typically only possible in simulation. These algorithms are scalable and can optimize nonlinear policies with tens of thousands of parameters, which have previously posed a major challenge for model-free policy search (Deisenroth et al. 2013). In our experiments, we show that the same TRPO methods can learn complex policies for swimming, hopping, and walking, as well as playing Atari games directly from raw images.

本文先证明：最小化某一代理目标函数，可在非平凡步长下保证策略改进；再对理论算法做一系列近似，得到实用算法——信赖域策略优化（TRPO）。我们描述两种变体：一是可用于无模型设定的 single-path 方法；二是 vine 方法，要求系统能恢复到特定状态，通常只在仿真中可行。这些算法可扩展，能优化带数万参数的非线性策略——此前这对无模型策略搜索是重大挑战（Deisenroth et al. 2013）。实验中，同一套 TRPO 方法可学会游泳、跳跃、行走的复杂策略，也能直接从原始图像学会玩 Atari。

2 Preliminaries

2 预备知识

Consider an infinite-horizon discounted Markov decision process (MDP), defined by the tuple $(\mathcal{S},\mathcal{A},P,r,\rho_{0},\gamma)$, where $\mathcal{S}$ is a finite set of states, $\mathcal{A}$ is a finite set of actions, $P:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow\mathbb{R}$ is the transition probability distribution, $r:\mathcal{S}\rightarrow\mathbb{R}$ is the reward function, $\rho_{0}:\mathcal{S}\rightarrow\mathbb{R}$ is the distribution of the initial state $s_{0}$, and $\gamma\in(0,1)$ is the discount factor.

考虑无限时域折扣马尔可夫决策过程（MDP），由元组 $(\mathcal{S},\mathcal{A},P,r,\rho_{0},\gamma)$ 定义，其中 $\mathcal{S}$ 为有限状态集，$\mathcal{A}$ 为有限动作集，$P:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow\mathbb{R}$ 为转移概率分布，$r:\mathcal{S}\rightarrow\mathbb{R}$ 为奖励函数，$\rho_{0}:\mathcal{S}\rightarrow\mathbb{R}$ 为初始状态 $s_{0}$ 的分布，$\gamma\in(0,1)$ 为折扣因子。

Let $\pi$ denote a stochastic policy $\pi:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$, and let $\eta(\pi)$ denote its expected discounted reward:

令 $\pi$ 表示随机策略 $\pi:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$，令 $\eta(\pi)$ 表示其期望折扣奖励：

$$\displaystyle\eta(\pi)=\mathbb{E}_{s_{0},a_{0},\dots}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t})\right],\text{ where} \\ \displaystyle s_{0}\sim\rho_{0}(s_{0}),\ a_{t}\sim\pi(a_{t}|s_{t}),\ s_{t+1}\sim P(s_{t+1}|s_{t},a_{t}).$$

We will use the following standard definitions of the state-action value function $Q_{\pi}$, the value function $V_{\pi}$, and the advantage function $A_{\pi}$:

我们将使用状态—动作价值函数 $Q_{\pi}$、价值函数 $V_{\pi}$ 与优势函数 $A_{\pi}$ 的如下标准定义：

$$\displaystyle Q_{\pi}(s_{t},a_{t})=\mathbb{E}_{s_{t+1},a_{t+1},\dots}\left[\sum_{l=0}^{\infty}\gamma^{l}r(s_{t+l})\right], \\ \displaystyle V_{\pi}(s_{t})=\ \mathbb{E}_{a_{t},s_{t+1},\dots}\left[\sum_{l=0}^{\infty}\gamma^{l}r(s_{t+l})\right], \\ \displaystyle A_{\pi}(s,a)=\ Q_{\pi}(s,a)-V_{\pi}(s),\text{ where} \\ \displaystyle\quad a_{t}\sim\pi(a_{t}|s_{t}),s_{t+1}\sim P(s_{t+1}|s_{t},a_{t})\text{\ for $t\geq 0$}.$$

The following useful identity expresses the expected return of another policy $\tilde{\pi}$ in terms of the advantage over $\pi$, accumulated over timesteps (see Kakade & Langford 2002 or Appendix A for proof):

下面的有用恒等式把另一策略 $\tilde{\pi}$ 的期望回报写成相对 $\pi$ 的优势在各时间步上的累积（证明见 Kakade & Langford 2002 或附录 A）：

$$\displaystyle\eta(\tilde{\pi})=\eta(\pi)+\mathbb{E}_{s_{0},a_{0},\dots\sim\tilde{\pi}}\left[\sum_{t=0}^{\infty}\gamma^{t}A_{\pi}(s_{t},a_{t})\right] \tag{1}$$

where the notation $\mathbb{E}_{s_{0},a_{0},\dots\sim\tilde{\pi}}\left[\dots\right]$ indicates that actions are sampled $a_{t}\sim\tilde{\pi}(\cdot|s_{t})$. Let $\rho_{\pi}$ be the (unnormalized) discounted visitation frequencies

其中记号 $\mathbb{E}_{s_{0},a_{0},\dots\sim\tilde{\pi}}\left[\dots\right]$ 表示动作按 $a_{t}\sim\tilde{\pi}(\cdot|s_{t})$ 采样。令 $\rho_{\pi}$ 为（未归一化的）折扣访问频率

$$\displaystyle\rho_{\pi}(s)\!=\!P(s_{0}=s)\!+\!\gamma P(s_{1}=s)\!+\!\gamma^{2}P(s_{2}=s)\!+\!\dots,$$

where $s_{0}\sim\rho_{0}$ and the actions are chosen according to $\pi$. We can rewrite Equation 1 with a sum over states instead of timesteps:

其中 $s_{0}\sim\rho_{0}$，动作按 $\pi$ 选取。我们可把式 (1) 改写成对状态求和而非对时间步求和：

$$\displaystyle\eta(\tilde{\pi}) \\ \displaystyle=\eta(\pi)+\sum_{t=0}^{\infty}\sum_{s}P(s_{t}=s|\tilde{\pi})\sum_{a}\tilde{\pi}(a|s)\gamma^{t}A_{\pi}(s,a) \\ \displaystyle=\eta(\pi)+\sum_{s}\sum_{t=0}^{\infty}\gamma^{t}P(s_{t}=s|\tilde{\pi})\sum_{a}\tilde{\pi}(a|s)A_{\pi}(s,a) \\ \displaystyle=\eta(\pi)+\sum_{s}\rho_{\tilde{\pi}}(s)\sum_{a}\tilde{\pi}(a|s)A_{\pi}(s,a). \tag{2}$$

This equation implies that any policy update $\pi\rightarrow\tilde{\pi}$ that has a nonnegative expected advantage at every state $s$, i.e., $\sum_{a}\tilde{\pi}(a|s)A_{\pi}(s,a)\geq 0$, is guaranteed to increase the policy performance $\eta$, or leave it constant in the case that the expected advantage is zero everywhere. This implies the classic result that the update performed by exact policy iteration, which uses the deterministic policy $\tilde{\pi}(s)=\argmax_{a}A_{\pi}(s,a)$, improves the policy if there is at least one state-action pair with a positive advantage value and nonzero state visitation probability, otherwise the algorithm has converged to the optimal policy. However, in the approximate setting, it will typically be unavoidable, due to estimation and approximation error, that there will be some states $s$ for which the expected advantage is negative, that is, $\sum_{a}\tilde{\pi}(a|s)A_{\pi}(s,a)<0$. The complex dependency of $\rho_{\tilde{\pi}}(s)$ on $\tilde{\pi}$ makes Equation (2) difficult to optimize directly. Instead, we introduce the following local approximation to $\eta$:

该式意味着：任意在 每一个 状态 $s$ 上都有非负期望优势的策略更新 $\pi\rightarrow\tilde{\pi}$，即 $\sum_{a}\tilde{\pi}(a|s)A_{\pi}(s,a)\geq 0$，都能保证策略性能 $\eta$ 上升，或在处处期望优势为零时保持不变。由此得到经典结论：精确策略迭代所用的确定性策略 $\tilde{\pi}(s)=\argmax_{a}A_{\pi}(s,a)$，只要存在至少一个优势为正且状态访问概率非零的状态—动作对，就会改进策略；否则算法已收敛到最优策略。但在近似设定中，由于估计与逼近误差，通常不可避免地会有一些状态 $s$ 使期望优势为负，即 $\sum_{a}\tilde{\pi}(a|s)A_{\pi}(s,a)<0$。$\rho_{\tilde{\pi}}(s)$ 对 $\tilde{\pi}$ 的复杂依赖使式 (2) 难以直接优化。于是我们引入如下对 $\eta$ 的局部近似：

$$\displaystyle L_{\pi}(\tilde{\pi})=\eta(\pi)+\sum_{s}\rho_{\pi}(s)\sum_{a}\tilde{\pi}(a|s)A_{\pi}(s,a). \tag{3}$$

Note that $L_{\pi}$ uses the visitation frequency $\rho_{\pi}$ rather than $\rho_{\tilde{\pi}}$, ignoring changes in state visitation density due to changes in the policy. However, if we have a parameterized policy $\pi_{\theta}$, where $\pi_{\theta}(a|s)$ is a differentiable function of the parameter vector $\theta$, then $L_{\pi}$ matches $\eta$ to first order (see Kakade & Langford 2002). That is, for any parameter value $\theta_{0}$,

注意 $L_{\pi}$ 使用访问频率 $\rho_{\pi}$ 而非 $\rho_{\tilde{\pi}}$，忽略了策略改变引起的状态访问密度变化。不过，若有参数化策略 $\pi_{\theta}$，且 $\pi_{\theta}(a|s)$ 对参数向量 $\theta$ 可微，则 $L_{\pi}$ 与 $\eta$ 一阶吻合（见 Kakade & Langford 2002）。也即，对任意参数值 $\theta_{0}$，

$$\displaystyle L_{\pi_{\theta_{0}}}(\pi_{\theta_{0}}) \\ \displaystyle=\eta(\pi_{\theta_{0}}), \\ \displaystyle\nabla_{\theta}L_{\pi_{\theta_{0}}}(\pi_{\theta})\big\rvert_{\theta=\theta_{0}} \\ \displaystyle=\nabla_{\theta}\eta(\pi_{\theta})\big\rvert_{\theta=\theta_{0}}. \tag{4}$$

Equation 4 implies that a sufficiently small step $\pi_{\theta_{0}}\rightarrow\tilde{\pi}$ that improves $L_{\pi_{\theta_{\mathrm{old}}}}$ will also improve $\eta$, but does not give us any guidance on how big of a step to take.

式 (4) 意味着：充分小的、能改进 $L_{\pi_{\theta_{\mathrm{old}}}}$ 的一步 $\pi_{\theta_{0}}\rightarrow\tilde{\pi}$ 也会改进 $\eta$，但并未告诉我们步长可以取多大。

To address this issue, Kakade & Langford 2002 proposed a policy updating scheme called conservative policy iteration, for which they could provide explicit lower bounds on the improvement of $\eta$. To define the conservative policy iteration update, let $\pi_{\mathrm{old}}$ denote the current policy, and let $\pi^{\prime}=\argmax_{\pi^{\prime}}L_{\pi_{\mathrm{old}}}(\pi^{\prime})$. The new policy $\pi_{\mathrm{new}}$ was defined to be the following mixture:

为处理这一问题，Kakade & Langford 2002 提出名为保守策略迭代的更新方案，并能给出 $\eta$ 改进的显式下界。定义保守策略迭代更新：令 $\pi_{\mathrm{old}}$ 为当前策略，令 $\pi^{\prime}=\argmax_{\pi^{\prime}}L_{\pi_{\mathrm{old}}}(\pi^{\prime})$。新策略 $\pi_{\mathrm{new}}$ 定义为如下混合：

$$\displaystyle\pi_{\mathrm{new}}(a|s)=(1-\alpha)\pi_{\mathrm{old}}(a|s)+\alpha\pi^{\prime}(a|s). \tag{5}$$

Kakade and Langford derived the following lower bound:

Kakade 与 Langford 导出了如下下界：

$$\displaystyle\eta(\pi_{\mathrm{new}}) \\ \displaystyle\!\geq\!L_{\pi_{\mathrm{old}}}(\pi_{\mathrm{new}})-\frac{2\epsilon\gamma}{(1-\gamma)^{2}}\alpha^{2} \\ \displaystyle\text{ where }\epsilon=\max_{s}\left|\mathbb{E}_{a\sim\pi^{\prime}(a|s)}\left[A_{\pi}(s,a)\right]\right|. \tag{6}$$

(We have modified it to make it slightly weaker but simpler.) Note, however, that so far this bound only applies to mixture policies generated by Equation (5). This policy class is unwieldy and restrictive in practice, and it is desirable for a practical policy update scheme to be applicable to all general stochastic policy classes.

（我们稍作改写，使下界略弱但更简洁。）但注意，目前该界只适用于式 (5) 生成的混合策略。这类策略类在实践中笨拙且受限；实用的策略更新方案最好能适用于一般随机策略类。

3 Monotonic Improvement Guarantee for General Stochastic Policies

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

Equation 6, which applies to conservative policy iteration, implies that a policy update that improves the right-hand side is guaranteed to improve the true performance $\eta$. Our principal theoretical result is that the policy improvement bound in Equation 6 can be extended to general stochastic policies, rather than just mixture polices, by replacing $\alpha$ with a distance measure between $\pi$ and $\tilde{\pi}$, and changing the constant $\epsilon$ appropriately. Since mixture policies are rarely used in practice, this result is crucial for extending the improvement guarantee to practical problems. The particular distance measure we use is the total variation divergence, which is defined by $D_{TV}(p\ \|\ q)=\frac{1}{2}\sum_{i}|p_{i}-q_{i}|$ for discrete probability distributions $p,q$.[^1] Define $D^{\rm max}_{\rm TV}(\pi,\tilde{\pi})$ as

适用于保守策略迭代的式 (6) 意味着：改进右侧的策略更新保证能改进真实性能 $\eta$。我们的主要理论结果是：把 $\alpha$ 换成 $\pi$ 与 $\tilde{\pi}$ 之间的某种距离度量，并相应改写常数 $\epsilon$，即可把式 (6) 的策略改进界从混合策略推广到一般随机策略。由于实践中很少用混合策略，这一结果对把改进保证延到实际问题至关重要。我们采用的距离度量是全变差散度，对离散概率分布 $p,q$ 定义为 $D_{TV}(p\ \|\ q)=\frac{1}{2}\sum_{i}|p_{i}-q_{i}|$。定义 $D^{\rm max}_{\rm TV}(\pi,\tilde{\pi})$ 为

$$\displaystyle D^{\rm max}_{\rm TV}(\pi,\tilde{\pi})=\max_{s}D_{TV}(\pi(\cdot|s)\ \|\ \tilde{\pi}(\cdot|s)). \tag{7}$$

Theorem 1.

Let $\alpha=D^{\rm max}_{\rm TV}(\pi_{\mathrm{old}},\pi_{\mathrm{new}})$. Then the following bound holds:

定理 1。

令 $\alpha=D^{\rm max}_{\rm TV}(\pi_{\mathrm{old}},\pi_{\mathrm{new}})$。则下列界成立：

$$\displaystyle\eta(\pi_{\mathrm{new}})\geq L_{\pi_{\mathrm{old}}}(\pi_{\mathrm{new}})-\frac{4\epsilon\gamma}{(1-\gamma)^{2}}\alpha^{2} \\ \displaystyle\quad\text{ where }\epsilon=\max_{s,a}{\left|A_{\pi}(s,a)\right|} \tag{8}$$

We provide two proofs in the appendix. The first proof extends Kakade and Langford’s result using the fact that the random variables from two distributions with total variation divergence less than $\alpha$ can be coupled, so that they are equal with probability $1-\alpha$. The second proof uses perturbation theory.

附录给出两种证明。第一种利用全变差散度小于 $\alpha$ 的两分布随机变量可耦合、从而以概率 $1-\alpha$ 相等，来扩展 Kakade 与 Langford 的结果；第二种使用摄动理论。

Next, we note the following relationship between the total variation divergence and the KL divergence (Pollard 2000, Ch. 3): $D_{TV}(p\ \|\ q)^{2}\leq D_{\rm KL}(p\ \|\ q)$. Let ${D^{\rm max}_{\rm KL}}(\pi,\tilde{\pi})=\max_{s}D_{\rm KL}(\pi(\cdot|s)\ \|\ \tilde{\pi}(\cdot|s))$. The following bound then follows directly from 1:

接下来注意全变差散度与 KL 散度的关系（Pollard 2000，第 3 章）：$D_{TV}(p\ \|\ q)^{2}\leq D_{\rm KL}(p\ \|\ q)$。令 ${D^{\rm max}_{\rm KL}}(\pi,\tilde{\pi})=\max_{s}D_{\rm KL}(\pi(\cdot|s)\ \|\ \tilde{\pi}(\cdot|s))$。则由定理 1 直接得到如下界：

$$\displaystyle\eta(\tilde{\pi})\geq L_{\pi}(\tilde{\pi})-C{D^{\rm max}_{\rm KL}}(\pi,\tilde{\pi}), \\ \displaystyle\qquad\text{ where }C=\frac{4\epsilon\gamma}{(1-\gamma)^{2}}. \tag{9}$$

Algorithm 1 describes an approximate policy iteration scheme based on the policy improvement bound in Equation (9). Note that for now, we assume exact evaluation of the advantage values $A_{\pi}$.

算法 1 描述基于式 (9) 策略改进界的近似策略迭代方案。注意此刻我们假定优势值 $A_{\pi}$ 可精确求值。

Algorithm 1 Policy iteration algorithm guaranteeing non-decreasing expected return $\eta$

算法 1 保证期望回报 $\eta$ 非降的策略迭代算法

It follows from Equation 9 that Algorithm 1 is guaranteed to generate a monotonically improving sequence of policies $\eta(\pi_{0})\leq\eta(\pi_{1})\leq\eta(\pi_{2})\leq\dots$. To see this, let $M_{i}(\pi)=L_{\pi_{i}}(\pi)-C{D^{\rm max}_{\rm KL}}(\pi_{i},\pi)$. Then

由式 (9) 可知，算法 1 保证生成单调改进的策略序列 $\eta(\pi_{0})\leq\eta(\pi_{1})\leq\eta(\pi_{2})\leq\dots$。为此令 $M_{i}(\pi)=L_{\pi_{i}}(\pi)-C{D^{\rm max}_{\rm KL}}(\pi_{i},\pi)$。则

$$\displaystyle\eta(\pi_{i+1})\geq M_{i}(\pi_{i+1})\text{ by Equation~\eqref{eq:klminorizer}} \\ \displaystyle\eta(\pi_{i})=M_{i}(\pi_{i}),\text{ therefore,} \\ \displaystyle\eta(\pi_{i+1})-\eta(\pi_{i})\geq M_{i}(\pi_{i+1})-M(\pi_{i}). \tag{10}$$

Thus, by maximizing $M_{i}$ at each iteration, we guarantee that the true objective $\eta$ is non-decreasing. This algorithm is a type of minorization-maximization (MM) algorithm (Hunter & Lange 2004), which is a class of methods that also includes expectation maximization. In the terminology of MM algorithms, $M_{i}$ is the surrogate function that minorizes $\eta$ with equality at $\pi_{i}$. This algorithm is also reminiscent of proximal gradient methods and mirror descent.

因此，每步最大化 $M_{i}$ 即可保证真实目标 $\eta$ 非降。该算法属于一类称为最小化—最大化（MM）的算法（Hunter & Lange 2004），期望最大化也属此类。按 MM 术语，$M_{i}$ 是在 $\pi_{i}$ 处与 $\eta$ 相等、并 minorizes $\eta$ 的代理函数。该算法也令人想起近端梯度方法与镜像下降。

Trust region policy optimization, which we propose in the following section, is an approximation to Algorithm 1, which uses a constraint on the KL divergence rather than a penalty to robustly allow large updates.

下一节提出的 信赖域策略优化 是对算法 1 的近似：用 KL 散度约束代替惩罚项，从而稳健地允许较大更新。

4 Optimization of Parameterized Policies

4 参数化策略的优化

In the previous section, we considered the policy optimization problem independently of the parameterization of $\pi$ and under the assumption that the policy can be evaluated at all states. We now describe how to derive a practical algorithm from these theoretical foundations, under finite sample counts and arbitrary parameterizations.

上一节在与 $\pi$ 的参数化无关、并假定策略可在所有状态求值的前提下讨论策略优化。现在说明如何在有限样本与任意参数化下，从这些理论基础导出实用算法。

Since we consider parameterized policies $\pi_{\theta}(a|s)$ with parameter vector $\theta$, we will overload our previous notation to use functions of $\theta$ rather than $\pi$, e.g. $\eta(\theta)\vcentcolon=\eta(\pi_{\theta})$, $L_{\theta}(\tilde{\theta})\vcentcolon=L_{\pi_{\theta}}(\pi_{\tilde{\theta}})$, and $D_{\rm KL}(\theta\ \|\ \tilde{\theta})\vcentcolon=D_{\rm KL}(\pi_{\theta}\ \|\ \pi_{\tilde{\theta}})$. We will use $\theta_{\mathrm{old}}$ to denote the previous policy parameters that we want to improve upon.

由于考虑带参数向量 $\theta$ 的参数化策略 $\pi_{\theta}(a|s)$，我们将沿用先前记号，改写成 $\theta$ 的函数，例如 $\eta(\theta)\vcentcolon=\eta(\pi_{\theta})$，$L_{\theta}(\tilde{\theta})\vcentcolon=L_{\pi_{\theta}}(\pi_{\tilde{\theta}})$，以及 $D_{\rm KL}(\theta\ \|\ \tilde{\theta})\vcentcolon=D_{\rm KL}(\pi_{\theta}\ \|\ \pi_{\tilde{\theta}})$。用 $\theta_{\mathrm{old}}$ 表示我们希望改进的上一轮策略参数。

The preceding section showed that $\eta(\theta)\geq L_{\theta_{\mathrm{old}}}(\theta)-C{D^{\rm max}_{\rm KL}}(\theta_{\mathrm{old}},\theta)$, with equality at $\theta=\theta_{\mathrm{old}}$. Thus, by performing the following maximization, we are guaranteed to improve the true objective $\eta$:

上一节表明 $\eta(\theta)\geq L_{\theta_{\mathrm{old}}}(\theta)-C{D^{\rm max}_{\rm KL}}(\theta_{\mathrm{old}},\theta)$，且在 $\theta=\theta_{\mathrm{old}}$ 处等号成立。因此做如下最大化即可保证改进真实目标 $\eta$：

$$\displaystyle\operatorname*{maximize}_{\theta}\left[L_{\theta_{\mathrm{old}}}(\theta)-C{D^{\rm max}_{\rm KL}}(\theta_{\mathrm{old}},\theta)\right].$$

In practice, if we used the penalty coefficient $C$ recommended by the theory above, the step sizes would be very small. One way to take larger steps in a robust way is to use a constraint on the KL divergence between the new policy and the old policy, i.e., a trust region constraint:

实践中，若采用理论给出的惩罚系数 $C$，步长会非常小。一种稳健地迈出更大步的方式，是对新旧策略之间的 KL 散度施加约束，即信赖域约束：

$$\displaystyle\operatorname*{maximize}_{\theta}L_{\theta_{\mathrm{old}}}(\theta) \\ \displaystyle\text{\ \ subject to }{D^{\rm max}_{\rm KL}}(\theta_{\mathrm{old}},\theta)\leq\delta. \tag{11}$$

This problem imposes a constraint that the KL divergence is bounded at every point in the state space. While it is motivated by the theory, this problem is impractical to solve due to the large number of constraints. Instead, we can use a heuristic approximation which considers the average KL divergence:

该问题要求状态空间每一点上的 KL 散度都有界。虽有理论动机，但约束数量巨大，不切实际。可改用启发式近似，考虑平均 KL 散度：

$$\displaystyle{\overline{D}_{\rm KL}^{\rho}}(\theta_{1},\theta_{2})\vcentcolon=\mathbb{E}_{s\sim\rho}\left[D_{\rm KL}(\pi_{\theta_{1}}(\cdot|s)\ \|\ \pi_{\theta_{2}}(\cdot|s))\right].$$

We therefore propose solving the following optimization problem to generate a policy update:

因此我们提议解如下优化问题以产生策略更新：

$$\displaystyle\operatorname*{maximize}_{\theta}L_{\theta_{\mathrm{old}}}(\theta) \\ \displaystyle\text{\ \ subject to }{\overline{D}_{\rm KL}^{\rho_{\theta_{\mathrm{old}}}}}(\theta_{\mathrm{old}},\theta)\leq\delta. \tag{12}$$

Similar policy updates have been proposed in prior work (Bagnell & Schneider 2003; Peters & Schaal 2008b; Peters et al. 2010), and we compare our approach to prior methods in Section 7 and in the experiments in Section 8. Our experiments also show that this type of constrained update has similar empirical performance to the maximum KL divergence constraint in Equation (11).

类似的策略更新在先前工作中已有提出（Bagnell & Schneider 2003；Peters & Schaal 2008b；Peters et al. 2010），我们在第 7 节与第 8 节实验中与先前方法比较。实验也表明，这类带约束的更新与式 (11) 的最大 KL 散度约束经验表现相近。

5 Sample-Based Estimation of the Objective and Constraint

5 目标与约束的基于样本估计

The previous section proposed a constrained optimization problem on the policy parameters (Equation (12)), which optimizes an estimate of the expected total reward $\eta$ subject to a constraint on the change in the policy at each update. This section describes how the objective and constraint functions can be approximated using Monte Carlo simulation.

上一节提出策略参数上的约束优化问题（式 (12)）：在每次更新对策略变化施加约束的前提下，优化期望总奖励 $\eta$ 的估计。本节说明如何用蒙特卡洛仿真近似目标函数与约束函数。

We seek to solve the following optimization problem, obtained by expanding $L_{\theta_{\mathrm{old}}}$ in Equation (12):

我们要求解如下优化问题，由式 (12) 展开 $L_{\theta_{\mathrm{old}}}$ 得到：

$$\displaystyle\operatorname*{maximize}_{\theta}\sum_{s} \\ \displaystyle\rho_{\theta_{\mathrm{old}}}(s)\sum_{a}\pi_{\theta}(a|s)A_{\theta_{\mathrm{old}}}(s,a) \\ \displaystyle\text{\ \ subject to }{\overline{D}_{\rm KL}^{\rho_{\theta_{\mathrm{old}}}}}(\theta_{\mathrm{old}},\theta)\leq\delta. \tag{13}$$

We first replace $\sum_{s}\rho_{\theta_{\mathrm{old}}}(s)\left[\dots\right]$ in the objective by the expectation $\frac{1}{1-\gamma}\mathbb{E}_{s\sim\rho_{\theta_{\mathrm{old}}}}\left[\dots\right]$. Next, we replace the advantage values $A_{\theta_{\mathrm{old}}}$ by the $Q$-values $Q_{\theta_{\mathrm{old}}}$ in Equation (13), which only changes the objective by a constant. Last, we replace the sum over the actions by an importance sampling estimator. Using $q$ to denote the sampling distribution, the contribution of a single $s_{n}$ to the loss function is

首先把目标中的 $\sum_{s}\rho_{\theta_{\mathrm{old}}}(s)\left[\dots\right]$ 换成期望 $\frac{1}{1-\gamma}\mathbb{E}_{s\sim\rho_{\theta_{\mathrm{old}}}}\left[\dots\right]$。再把式 (13) 中的优势值 $A_{\theta_{\mathrm{old}}}$ 换成 $Q$ 值 $Q_{\theta_{\mathrm{old}}}$，这只使目标相差一个常数。最后把对动作的求和换成重要性采样估计。用 $q$ 表示采样分布，则单个 $s_{n}$ 对损失函数的贡献为

$$\displaystyle\sum_{a}\pi_{\theta}(a|s_{n})A_{\theta_{\mathrm{old}}}(s_{n},a)=\mathbb{E}_{a\sim q}\left[\frac{\pi_{\theta}(a|s_{n})}{q(a|s_{n})}A_{\theta_{\mathrm{old}}}(s_{n},a)\right].$$

Our optimization problem in Equation 13 is exactly equivalent to the following one, written in terms of expectations:

式 13 中的优化问题与下面用期望写成的问题完全等价：

$$\displaystyle\operatorname*{maximize}_{\theta}\mathbb{E}_{s\sim\rho_{\theta_{\mathrm{old}}},a\sim q}\left[\frac{\pi_{\theta}(a|s)}{q(a|s)}Q_{\theta_{\mathrm{old}}}(s,a)\right] \\ \displaystyle\text{\ \ subject to }\mathbb{E}_{s\sim\rho_{\theta_{\mathrm{old}}}}\left[D_{\rm KL}(\pi_{\theta_{\mathrm{old}}}(\cdot|s)\ \|\ \pi_{\theta}(\cdot|s))\right]\leq\delta. \tag{14}$$

All that remains is to replace the expectations by sample averages and replace the $Q$ value by an empirical estimate. The following sections describe two different schemes for performing this estimation.

剩下只需把期望换成样本平均，并把 $Q$ 值换成经验估计。以下两小节描述两种不同的估计方案。

The first sampling scheme, which we call single path, is the one that is typically used for policy gradient estimation (Bartlett & Baxter 2011), and is based on sampling individual trajectories. The second scheme, which we call vine, involves constructing a rollout set and then performing multiple actions from each state in the rollout set. This method has mostly been explored in the context of policy iteration methods (Lagoudakis & Parr 2003; Gabillon et al. 2013).

第一种采样方案称为 single path，是策略梯度估计中常用的做法（Bartlett & Baxter 2011），基于采样单条轨迹。第二种称为 vine，先构造 rollout 集合，再从该集合中每个状态执行多个动作。该方法多在策略迭代语境下被探索（Lagoudakis & Parr 2003；Gabillon et al. 2013）。

5.1 Single Path

In this estimation procedure, we collect a sequence of states by sampling $s_{0}\sim\rho_{0}$ and then simulating the policy $\pi_{\theta_{\mathrm{old}}}$ for some number of timesteps to generate a trajectory $s_{0},a_{0},s_{1},a_{1},\dots,s_{T-1},a_{T-1},s_{T}$. Hence, $q(a|s)=\pi_{\theta_{\mathrm{old}}}(a|s)$. $Q_{\theta_{\mathrm{old}}}(s,a)$ is computed at each state-action pair $(s_{t},a_{t})$ by taking the discounted sum of future rewards along the trajectory.

该估计流程中，我们采样 $s_{0}\sim\rho_{0}$，再按策略 $\pi_{\theta_{\mathrm{old}}}$ 仿真若干时间步，生成轨迹 $s_{0},a_{0},s_{1},a_{1},\dots,s_{T-1},a_{T-1},s_{T}$。于是 $q(a|s)=\pi_{\theta_{\mathrm{old}}}(a|s)$。每个状态—动作对 $(s_{t},a_{t})$ 上的 $Q_{\theta_{\mathrm{old}}}(s,a)$ 由轨迹上未来奖励的折扣和计算。

5.2 Vine

Figure 1: Left: illustration of single path procedure. Here, we generate a set of trajectories via simulation of the policy and incorporate all state-action pairs ($s_{n},a_{n}$) into the objective. Right: illustration of vine procedure. We generate a set of “trunk” trajectories, and then generate “branch” rollouts from a subset of the reached states. For each of these states $s_{n}$, we perform multiple actions ($a_{1}$ and $a_{2}$ here) and perform a rollout after each action, using common random numbers (CRN) to reduce the variance.

图 1：左：single path 流程示意。通过策略仿真生成一组轨迹，把全部状态—动作对 $(s_{n},a_{n})$ 纳入目标。右：vine 流程示意。先生成一组「主干」轨迹，再从到达状态的子集生成「分支」rollout。对其中每个状态 $s_{n}$，执行多个动作（此处为 $a_{1}$ 与 $a_{2}$），并在每个动作后做 rollout；使用公共随机数（CRN）以降方差。

In this estimation procedure, we first sample $s_{0}\sim\rho_{0}$ and simulate the policy $\pi_{\theta_{i}}$ to generate a number of trajectories. We then choose a subset of $N$ states along these trajectories, denoted $s_{1},s_{2},\dots,s_{N}$, which we call the “rollout set”. For each state $s_{n}$ in the rollout set, we sample $K$ actions according to $a_{n,k}\sim q(\cdot|s_{n})$. Any choice of $q(\cdot|s_{n})$ with a support that includes the support of $\pi_{\theta_{i}}(\cdot|s_{n})$ will produce a consistent estimator. In practice, we found that $q(\cdot|s_{n})=\pi_{\theta_{i}}(\cdot|s_{n})$ works well on continuous problems, such as robotic locomotion, while the uniform distribution works well on discrete tasks, such as the Atari games, where it can sometimes achieve better exploration.

该估计流程中，先采样 $s_{0}\sim\rho_{0}$ 并仿真策略 $\pi_{\theta_{i}}$ 生成若干轨迹。再沿这些轨迹选取 $N$ 个状态的子集，记为 $s_{1},s_{2},\dots,s_{N}$，称为「rollout 集合」。对集合中每个状态 $s_{n}$，按 $a_{n,k}\sim q(\cdot|s_{n})$ 采样 $K$ 个动作。只要 $q(\cdot|s_{n})$ 的支撑包含 $\pi_{\theta_{i}}(\cdot|s_{n})$ 的支撑，就能得到相合估计。实践中发现，连续问题（如机器人运动）上 $q(\cdot|s_{n})=\pi_{\theta_{i}}(\cdot|s_{n})$ 效果好；离散任务（如 Atari）上均匀分布效果好，有时还能带来更好的探索。

For each action $a_{n,k}$ sampled at each state $s_{n}$, we estimate $\hat{Q}_{\theta_{i}}(s_{n},a_{n,k})$ by performing a rollout (i.e., a short trajectory) starting with state $s_{n}$ and action $a_{n,k}$. We can greatly reduce the variance of the $Q$-value differences between rollouts by using the same random number sequence for the noise in each of the $K$ rollouts, i.e., common random numbers. See (Bertsekas 2005) for additional discussion on Monte Carlo estimation of $Q$-values and (Ng & Jordan 2000) for a discussion of common random numbers in reinforcement learning.

对每个状态 $s_{n}$ 上采样的每个动作 $a_{n,k}$，从状态 $s_{n}$、动作 $a_{n,k}$ 出发做一次 rollout（短轨迹），以估计 $\hat{Q}_{\theta_{i}}(s_{n},a_{n,k})$。若各次 $K$ 次 rollout 的噪声使用同一随机数序列，即 公共随机数，可大幅降低 rollout 之间 $Q$ 值差的方差。关于 $Q$ 值的蒙特卡洛估计另见 Bertsekas 2005；强化学习中公共随机数的讨论见 Ng & Jordan 2000。

In small, finite action spaces, we can generate a rollout for every possible action from a given state. The contribution to $L_{\theta_{\mathrm{old}}}$ from a single state $s_{n}$ is as follows:

在小的有限动作空间中，可从给定状态对每个可能动作各做一次 rollout。单个状态 $s_{n}$ 对 $L_{\theta_{\mathrm{old}}}$ 的贡献如下：

$$\displaystyle L_{n}(\theta)=\sum_{k=1}^{K}\pi_{\theta}(a_{k}|s_{n})\hat{Q}(s_{n},a_{k}), \tag{15}$$

where the action space is $\mathcal{A}=\left\{a_{1},a_{2},\dots,a_{K}\right\}$. In large or continuous state spaces, we can construct an estimator of the surrogate objective using importance sampling. The self-normalized estimator (Owen 2013, Chapter 9) of $L_{\theta_{\mathrm{old}}}$ obtained at a single state $s_{n}$ is

其中动作空间为 $\mathcal{A}=\left\{a_{1},a_{2},\dots,a_{K}\right\}$。在大或连续状态空间中，可用重要性采样构造代理目标的估计。在单个状态 $s_{n}$ 上得到的 $L_{\theta_{\mathrm{old}}}$ 自归一化估计（Owen 2013，第 9 章）为

$$\displaystyle L_{n}(\theta)=\frac{\sum_{k=1}^{K}\frac{\pi_{\theta}(a_{n,k}|s_{n})}{\pi_{\theta_{\mathrm{old}}}(a_{n,k}|s_{n})}\hat{Q}(s_{n},a_{n,k})}{\sum_{k=1}^{K}\frac{\pi_{\theta}(a_{n,k}|s_{n})}{\pi_{\theta_{\mathrm{old}}}(a_{n,k}|s_{n})}}, \tag{16}$$

assuming that we performed $K$ actions $a_{n,1},a_{n,2},\dots,a_{n,K}$ from state $s_{n}$. This self-normalized estimator removes the need to use a baseline for the $Q$-values (note that the gradient is unchanged by adding a constant to the $Q$-values). Averaging over $s_{n}\sim\rho(\pi)$, we obtain an estimator for $L_{\theta_{\mathrm{old}}}$, as well as its gradient.

假定我们从状态 $s_{n}$ 执行了 $K$ 个动作 $a_{n,1},a_{n,2},\dots,a_{n,K}$。该自归一化估计无需再为 $Q$ 值使用基线（注意给 $Q$ 值加常数不改变梯度）。对 $s_{n}\sim\rho(\pi)$ 取平均，即得到 $L_{\theta_{\mathrm{old}}}$ 及其梯度的估计。

The vine and single path methods are illustrated in Figure 1. We use the term vine, since the trajectories used for sampling can be likened to the stems of vines, which branch at various points (the rollout set) into several short offshoots (the rollout trajectories).

vine 与 single path 方法如图 1 所示。我们使用 vine 一词，因为采样所用轨迹可比作藤蔓主干，在若干点（rollout 集合）分出多条短枝（rollout 轨迹）。

The benefit of the vine method over the single path method that is our local estimate of the objective has much lower variance given the same number of $Q$-value samples in the surrogate objective. That is, the vine method gives much better estimates of the advantage values. The downside of the vine method is that we must perform far more calls to the simulator for each of these advantage estimates. Furthermore, the vine method requires us to generate multiple trajectories from each state in the rollout set, which limits this algorithm to settings where the system can be reset to an arbitrary state. In contrast, the single path algorithm requires no state resets and can be directly implemented on a physical system (Peters & Schaal 2008b).

vine 相对 single path 的好处是：在代理目标中给定同样数量的 $Q$ 值样本时，目标的局部估计方差低得多，即 vine 对优势值的估计好得多。代价是：每次优势估计要对仿真器调用远为多次；此外 vine 要求从 rollout 集合中每个状态生成多条轨迹，从而把算法限制在系统可重置到任意状态的设定。相比之下，single path 无需状态重置，可直接在物理系统上实现（Peters & Schaal 2008b）。

6 Practical Algorithm

6 实用算法

Here we present two practical policy optimization algorithm based on the ideas above, which use either the single path or vine sampling scheme from the preceding section. The algorithms repeatedly perform the following steps:

此处给出基于上述思想的两种实用策略优化算法，分别使用上一节的 single path 或 vine 采样方案。算法反复执行下列步骤：

1. Use the single path or vine procedures to collect a set of state-action pairs along with Monte Carlo estimates of their $Q$-values.
2. By averaging over samples, construct the estimated objective and constraint in Equation 14.
3. Approximately solve this constrained optimization problem to update the policy’s parameter vector $\theta$. We use the conjugate gradient algorithm followed by a line search, which is altogether only slightly more expensive than computing the gradient itself. See Appendix C for details.

1. 用 single path 或 vine 流程收集一组状态—动作对及其 $Q$ 值的蒙特卡洛估计。
2. 对样本取平均，构造式 14 中的估计目标与约束。
3. 近似求解该约束优化问题以更新策略参数向量 $\theta$。我们使用共轭梯度再接线搜索，整体代价仅略高于计算梯度本身。细节见附录 C。

With regard to (3), we construct the Fisher information matrix (FIM) by analytically computing the Hessian of the KL divergence, rather than using the covariance matrix of the gradients. That is, we estimate $A_{ij}$ as $\frac{1}{N}\sum_{n=1}^{N}\frac{\partial^{2}}{\partial\theta_{i}\partial\theta_{j}}D_{\rm KL}(\pi_{\theta_{\mathrm{old}}}(\cdot|s_{n})\ \|\ \pi_{\theta}(\cdot|s_{n}))$, rather than $\frac{1}{N}\sum_{n=1}^{N}\frac{\partial}{\partial\theta_{i}}\log\pi_{\theta}(a_{n}|s_{n})\frac{\partial}{\partial\theta_{j}}\log\pi_{\theta}(a_{n}|s_{n})$. The analytic estimator integrates over the action at each state $s_{n}$, and does not depend on the action $a_{n}$ that was sampled. As described in Appendix C, this analytic estimator has computational benefits in the large-scale setting, since it removes the need to store a dense Hessian or all policy gradients from a batch of trajectories. The rate of improvement in the policy is similar to the empirical FIM, as shown in the experiments.

关于第 (3) 步，我们通过解析计算 KL 散度的 Hessian 来构造 Fisher 信息矩阵（FIM），而不是用梯度的协方差矩阵。也即，把 $A_{ij}$ 估计为 $\frac{1}{N}\sum_{n=1}^{N}\frac{\partial^{2}}{\partial\theta_{i}\partial\theta_{j}}D_{\rm KL}(\pi_{\theta_{\mathrm{old}}}(\cdot|s_{n})\ \|\ \pi_{\theta}(\cdot|s_{n}))$，而非 $\frac{1}{N}\sum_{n=1}^{N}\frac{\partial}{\partial\theta_{i}}\log\pi_{\theta}(a_{n}|s_{n})\frac{\partial}{\partial\theta_{j}}\log\pi_{\theta}(a_{n}|s_{n})$。解析估计在每个状态 $s_{n}$ 上对动作积分，不依赖所采动作 $a_{n}$。如附录 C 所述，大规模设定下该解析估计有计算优势：无需存储稠密 Hessian，也无需存下一批轨迹的全部策略梯度。实验表明，策略改进速率与经验 FIM 相近。

Let us briefly summarize the relationship between the theory from Section 3 and the practical algorithm we have described:

简要总结第 3 节理论与上述实用算法之间的关系：

• • The theory justifies optimizing a surrogate objective with a penalty on KL divergence. However, the large penalty coefficient $C$ leads to prohibitively small steps, so we would like to decrease this coefficient. Empirically, it is hard to robustly choose the penalty coefficient, so we use a hard constraint instead of a penalty, with parameter $\delta$ (the bound on KL divergence).
• • The constraint on ${D^{\rm max}_{\rm KL}}(\theta_{\mathrm{old}},\theta)$ is hard for numerical optimization and estimation, so instead we constrain ${\overline{D}_{\rm KL}}(\theta_{\mathrm{old}},\theta)$.
• • Our theory ignores estimation error for the advantage function. Kakade & Langford 2002 consider this error in their derivation, and the same arguments would hold in the setting of this paper, but we omit them for simplicity.

• • 理论支持优化带 KL 散度惩罚的代理目标。但惩罚系数 $C$ 过大导致步长过小，我们希望减小该系数。经验上很难稳健地选惩罚系数，因此改用硬约束，参数为 $\delta$（KL 散度上界）。
• • 对 ${D^{\rm max}_{\rm KL}}(\theta_{\mathrm{old}},\theta)$ 的约束在数值优化与估计上都很难，因此改为约束 ${\overline{D}_{\rm KL}}(\theta_{\mathrm{old}},\theta)$。
• • 我们的理论忽略了优势函数的估计误差。Kakade & Langford 2002 在推导中考虑了该误差，同样论证适用于本文设定，但为简洁起见我们省略。

7 Connections with Prior Work

7 与先前工作的联系

As mentioned in Section 4, our derivation results in a policy update that is related to several prior methods, providing a unifying perspective on a number of policy update schemes. The natural policy gradient (Kakade 2002) can be obtained as a special case of the update in Equation (12) by using a linear approximation to $L$ and a quadratic approximation to the ${\overline{D}_{\rm KL}}$ constraint, resulting in the following problem:

如第 4 节所述，我们的推导得到的策略更新与若干先前方法相关，从而对多种策略更新方案给出统一视角。自然策略梯度（Kakade 2002）可视为式 (12) 更新的特例：对 $L$ 做线性近似、对 ${\overline{D}_{\rm KL}}$ 约束做二次近似，得到如下问题：

$$\displaystyle\operatorname*{maximize}_{\theta}\left[\nabla_{\theta}L_{\theta_{\mathrm{old}}}(\theta)\big\rvert_{\theta=\theta_{\mathrm{old}}}\cdot(\theta-\theta_{\mathrm{old}})\right] \\ \displaystyle\text{\ \ subject to }\frac{1}{2}(\theta_{\mathrm{old}}-\theta)^{T}A(\theta_{\mathrm{old}})(\theta_{\mathrm{old}}-\theta)\leq\delta, \\ \displaystyle\text{\ \ where }A(\theta_{\mathrm{old}})_{ij}= \\ \displaystyle\quad\frac{\partial}{\partial\theta_{i}}\frac{\partial}{\partial\theta_{j}}\mathbb{E}_{s\sim\rho_{\pi}}\left[D_{\rm KL}(\pi(\cdot|s,\theta_{\mathrm{old}})\ \|\ \pi(\cdot|s,\theta))\right]\big\rvert_{\theta=\theta_{\mathrm{old}}}. \tag{17}$$

The update is $\theta_{\mathrm{new}}=\theta_{\mathrm{old}}+\frac{1}{\lambda}A(\theta_{\mathrm{old}})^{-1}\nabla_{\theta}L(\theta)\big\rvert_{\theta=\theta_{\mathrm{old}}}$, where the stepsize $\frac{1}{\lambda}$ is typically treated as an algorithm parameter. This differs from our approach, which enforces the constraint at each update. Though this difference might seem subtle, our experiments demonstrate that it significantly improves the algorithm’s performance on larger problems.

更新为 $\theta_{\mathrm{new}}=\theta_{\mathrm{old}}+\frac{1}{\lambda}A(\theta_{\mathrm{old}})^{-1}\nabla_{\theta}L(\theta)\big\rvert_{\theta=\theta_{\mathrm{old}}}$，其中步长 $\frac{1}{\lambda}$ 通常当作算法参数。这与我们在每次更新都强制约束的做法不同。差异看似细微，但实验表明它在较大问题上显著提升算法表现。

We can also obtain the standard policy gradient update by using an $\ell_{2}$ constraint or penalty:

也可通过对 $\ell_{2}$ 约束或惩罚得到标准策略梯度更新：

$$\displaystyle\operatorname*{maximize}_{\theta}\left[\nabla_{\theta}L_{\theta_{\mathrm{old}}}(\theta)\big\rvert_{\theta=\theta_{\mathrm{old}}}\cdot(\theta-\theta_{\mathrm{old}})\right] \\ \displaystyle\text{\ \ subject to }\frac{1}{2}\|\theta-\theta_{\mathrm{old}}\|^{2}\leq\delta. \tag{18}$$

The policy iteration update can also be obtained by solving the unconstrained problem $\operatorname*{maximize}_{\pi}L_{\pi_{\mathrm{old}}}(\pi)$, using $L$ as defined in Equation 3.

策略迭代更新也可通过对无约束问题 $\operatorname*{maximize}_{\pi}L_{\pi_{\mathrm{old}}}(\pi)$ 求解得到，其中 $L$ 由式 3 定义。

Several other methods employ an update similar to Equation (12). Relative entropy policy search (REPS) (Peters et al. 2010) constrains the state-action marginals $p(s,a)$, while TRPO constrains the conditionals $p(a|s)$. Unlike REPS, our approach does not require a costly nonlinear optimization in the inner loop. Levine and Abbeel (Levine & Abbeel 2014) also use a KL divergence constraint, but its purpose is to encourage the policy not to stray from regions where the estimated dynamics model is valid, while we do not attempt to estimate the system dynamics explicitly. Pirotta et al. 2013 also build on and generalize Kakade and Langford’s results, and they derive different algorithms from the ones here.

另有若干方法采用类似式 (12) 的更新。相对熵策略搜索（REPS）（Peters et al. 2010）约束状态—动作边缘 $p(s,a)$，而 TRPO 约束条件分布 $p(a|s)$。与 REPS 不同，我们的方法不要求内层做代价高昂的非线性优化。Levine 与 Abbeel（Levine & Abbeel 2014）也使用 KL 散度约束，但其目的是鼓励策略不要离开估计动力学模型仍有效的区域，而我们并不试图显式估计系统动力学。Pirotta et al. 2013 也建立并推广了 Kakade 与 Langford 的结果，并导出与本文不同的算法。

8 Experiments

8 实验

We designed our experiments to investigate the following questions:

我们设计实验以考察下列问题：

1. What are the performance characteristics of the single path and vine sampling procedures?
2. TRPO is related to prior methods (e.g. natural policy gradient) but makes several changes, most notably by using a fixed KL divergence rather than a fixed penalty coefficient. How does this affect the performance of the algorithm?
3. Can TRPO be used to solve challenging large-scale problems? How does TRPO compare with other methods when applied to large-scale problems, with regard to final performance, computation time, and sample complexity?

1. single path 与 vine 采样流程的性能特征如何？
2. TRPO 与先前方法（如自然策略梯度）相关，但做了若干改动，最显著的是用固定 KL 散度约束代替固定惩罚系数。这如何影响算法表现？
3. TRPO 能否解决具有挑战性的大规模问题？在大规模问题上，TRPO 相对其他方法在最终性能、计算时间与样本复杂度上如何比较？

To answer (1) and (2), we compare the performance of the single path and vine variants of TRPO, several ablated variants, and a number of prior policy optimization algorithms. With regard to (3), we show that both the single path and vine algorithm can obtain high-quality locomotion controllers from scratch, which is considered to be a hard problem. We also show that these algorithms produce competitive results when learning policies for playing Atari games from images using convolutional neural networks with tens of thousands of parameters.

为回答 (1) 与 (2)，我们比较 TRPO 的 single path 与 vine 变体、若干消融变体，以及一批先前策略优化算法。关于 (3)，我们表明 single path 与 vine 都能从零得到高质量运动控制器——这被认为是难题；也表明在用带数万参数的卷积神经网络从图像学习 Atari 策略时，这些算法能给出有竞争力的结果。

Figure 2: 2D robot models used for locomotion experiments. From left to right: swimmer, hopper, walker. The hopper and walker present a particular challenge, due to underactuation and contact discontinuities.

图 2：运动实验所用的二维机器人模型。从左到右：swimmer、hopper、walker。hopper 与 walker 因欠驱动与接触不连续而特别具有挑战性。

8.1 Simulated Robotic Locomotion

8.1 仿真机器人运动

Figure 3: Neural networks used for the locomotion task (top) and for playing Atari games (bottom).

图 3：用于运动任务（上）与玩 Atari 游戏（下）的神经网络。

We conducted the robotic locomotion experiments using the MuJoCo simulator (Todorov et al. 2012). The three simulated robots are shown in Figure 2. The states of the robots are their generalized positions and velocities, and the controls are joint torques. Underactuation, high dimensionality, and non-smooth dynamics due to contacts make these tasks very challenging. The following models are included in our evaluation:

机器人运动实验在 MuJoCo 仿真器中进行（Todorov et al. 2012）。三台仿真机器人见图 2。状态为广义位置与速度，控制为关节力矩。欠驱动、高维以及接触带来的非光滑动力学使这些任务非常困难。评估包含下列模型：

1. Swimmer. $10$-dimensional state space, linear reward for forward progress and a quadratic penalty on joint effort to produce the reward $r(x,u)=v_{x}-10^{-5}\|u\|^{2}$. The swimmer can propel itself forward by making an undulating motion.
2. Hopper. $12$-dimensional state space, same reward as the swimmer, with a bonus of $+1$ for being in a non-terminal state. We ended the episodes when the hopper fell over, which was defined by thresholds on the torso height and angle.
3. Walker. $18$-dimensional state space. For the walker, we added a penalty for strong impacts of the feet against the ground to encourage a smooth walk rather than a hopping gait.

1. Swimmer。$10$ 维状态空间；前进进度的线性奖励与关节力矩的二次惩罚，奖励为 $r(x,u)=v_{x}-10^{-5}\|u\|^{2}$。游泳者可通过波动推进自身。
2. Hopper。$12$ 维状态空间；奖励与游泳者相同，非终止状态另有 $+1$ 奖励。当 hopper 摔倒（由躯干高度与角度阈值定义）时结束回合。
3. Walker。$18$ 维状态空间。对足部与地面的强冲击额外惩罚，以鼓励平滑行走而非跳跃步态。

We used $\delta=0.01$ for all experiments. See Table 2 in the Appendix for more details on the experimental setup and parameters used. We used neural networks to represent the policy, with the architecture shown in Figure 3, and further details provided in Appendix D. To establish a standard baseline, we also included the classic cart-pole balancing problem, based on the formulation from Barto et al. 1983, using a linear policy with six parameters that is easy to optimize with derivative-free black-box optimization methods.

全部实验取 $\delta=0.01$。实验设置与参数细节见附录表 2。策略用图 3 所示神经网络表示，更多细节见附录 D。为建立标准基线，我们还纳入经典倒立摆平衡问题（基于 Barto et al. 1983 的表述），使用仅六参数的线性策略，便于无导数黑箱优化方法优化。

The following algorithms were considered in the comparison: single path TRPO; vine TRPO; cross-entropy method (CEM), a gradient-free method (Szita & Lörincz 2006); covariance matrix adaption (CMA), another gradient-free method (Hansen & Ostermeier 1996); natural gradient, the classic natural policy gradient algorithm (Kakade 2002), which differs from single path by the use of a fixed penalty coefficient (Lagrange multiplier) instead of the KL divergence constraint; empirical FIM, identical to single path, except that the FIM is estimated using the covariance matrix of the gradients rather than the analytic estimate; max KL, which was only tractable on the cart-pole problem, and uses the maximum KL divergence in Equation (11), rather than the average divergence, allowing us to evaluate the quality of this approximation. The parameters used in the experiments are provided in Appendix E. For the natural gradient method, we swept through the possible values of the stepsize in factors of three, and took the best value according to the final performance.

比较中考虑下列算法：single path TRPO；vine TRPO；交叉熵方法（CEM），无梯度方法（Szita & Lörincz 2006）；协方差矩阵自适应（CMA），另一无梯度方法（Hansen & Ostermeier 1996）；自然梯度，经典自然策略梯度算法（Kakade 2002），与 single path 的差别在于使用固定惩罚系数（拉格朗日乘子）而非 KL 散度约束；经验 FIM，与 single path 相同，但 FIM 用梯度协方差矩阵估计而非解析估计；max KL，仅在倒立摆问题上可解，使用式 (11) 的最大 KL 散度而非平均散度，以便评估该近似的质量。实验参数见附录 E。对 自然梯度 方法，我们按三倍因子扫过可能步长，并按最终性能取最佳值。

Figure 4: Learning curves for locomotion tasks, averaged across five runs of each algorithm with random initializations. Note that for the hopper and walker, a score of $-1$ is achievable without any forward velocity, indicating a policy that simply learned balanced standing, but not walking.

图 4：运动任务学习曲线，每种算法五次随机初始化运行的平均。注意对 hopper 与 walker，分数 $-1$ 在无任何前进速度时即可达到，表示策略只学会了平衡站立而未学会行走。

Learning curves showing the total reward averaged across five runs of each algorithm are shown in Figure 4. Single path and vine TRPO solved all of the problems, yielding the best solutions. Natural gradient performed well on the two easier problems, but was unable to generate hopping and walking gaits that made forward progress. These results provide empirical evidence that constraining the KL divergence is a more robust way to choose step sizes and make fast, consistent progress, compared to using a fixed penalty. CEM and CMA are derivative-free algorithms, hence their sample complexity scales unfavorably with the number of parameters, and they performed poorly on the larger problems. The max KL method learned somewhat more slowly than our final method, due to the more restrictive form of the constraint, but overall the result suggests that the average KL divergence constraint has a similar effect as the theorecally justified maximum KL divergence. Videos of the policies learned by TRPO may be viewed on the project website: http://sites.google.com/site/trpopaper/.

图 4 给出每种算法五次运行平均的总奖励学习曲线。Single path 与 vine TRPO 解决了全部问题，并给出最佳解。自然梯度 在两个较易问题上表现良好，但无法生成有前进进度的跳跃与行走步态。这些结果经验表明：约束 KL 散度比使用固定惩罚更能稳健地选择步长并快速、一致地进步。CEM 与 CMA 是无导数算法，样本复杂度随参数量不利地增长，在较大问题上表现差。max KL 方法因约束形式更严而学得略慢，但总体结果表明平均 KL 散度约束与理论支持的最大 KL 散度作用相近。TRPO 学到的策略视频见项目网站：http://sites.google.com/site/trpopaper/。

Note that TRPO learned all of the gaits with general-purpose policies and simple reward functions, using minimal prior knowledge. This is in contrast with most prior methods for learning locomotion, which typically rely on hand-architected policy classes that explicitly encode notions of balance and stepping (Tedrake et al. 2004; Geng et al. 2006; Wampler & Popović 2009).

注意 TRPO 用通用策略与简单奖励函数、极少先验知识就学会了全部步态。这与多数先前运动学习方法形成对比——后者通常依赖显式编码平衡与迈步概念的手工策略类（Tedrake et al. 2004；Geng et al. 2006；Wampler & Popović 2009）。

	B. Rider	Breakout	Enduro	Pong	Qbert*	Seaquest	S. Invaders
Random	354	1.2	0	$-20.4$	157	110	179
Human (Mnih et al. 2013)	7456	31.0	368	$-3.0$	18900	28010	3690
Deep Q Learning (Mnih et al. 2013)	4092	168.0	470	20.0	1952	1705	581
UCC-I (Guo et al. 2014)	5702	380	741	21	20025	2995	692
TRPO - single path	1425.2	10.8	534.6	20.9	1973.5	1908.6	568.4
TRPO - vine	859.5	34.2	430.8	20.9	7732.5	788.4	450.2

Table 1: Performance comparison for vision-based RL algorithms on the Atari domain. Our algorithms (bottom rows) were run once on each task, with the same architecture and parameters. Performance varies substantially from run to run (with different random initializations of the policy), but we could not obtain error statistics due to time constraints.

	B. Rider	Breakout	Enduro	Pong	Qbert*	Seaquest	S. Invaders
Random	354	1.2	0	$-20.4$	157	110	179
Human (Mnih et al. 2013)	7456	31.0	368	$-3.0$	18900	28010	3690
Deep Q Learning (Mnih et al. 2013)	4092	168.0	470	20.0	1952	1705	581
UCC-I (Guo et al. 2014)	5702	380	741	21	20025	2995	692
TRPO - single path	1425.2	10.8	534.6	20.9	1973.5	1908.6	568.4
TRPO - vine	859.5	34.2	430.8	20.9	7732.5	788.4	450.2

表 1：Atari 域上基于视觉的 RL 算法性能比较。我们的算法（底两行）在每项任务上各跑一次，架构与参数相同。不同随机初始化下性能波动很大，但因时间限制未能获得误差统计。

8.2 Playing Games from Images

8.2 从图像玩游戏

To evaluate TRPO on a partially observed task with complex observations, we trained policies for playing Atari games, using raw images as input. The games require learning a variety of behaviors, such as dodging bullets and hitting balls with paddles. Aside from the high dimensionality, challenging elements of these games include delayed rewards (no immediate penalty is incurred when a life is lost in Breakout or Space Invaders); complex sequences of behavior (Q*bert requires a character to hop on $21$ different platforms); and non-stationary image statistics (Enduro involves a changing and flickering background).

为在具有复杂观测的部分可观测任务上评估 TRPO，我们以原始图像为输入训练玩 Atari 的策略。这些游戏需要学会多种行为，如躲避子弹、用挡板击球。除高维外，挑战还包括延迟奖励（Breakout 或 Space Invaders 丢命时无即时惩罚）、复杂行为序列（Q*bert 要求角色跳上 $21$ 个不同平台），以及非平稳图像统计（Enduro 背景变化且闪烁）。

We tested our algorithms on the same seven games reported on in (Mnih et al. 2013) and (Guo et al. 2014), which are made available through the Arcade Learning Environment (Bellemare et al. 2013) The images were preprocessed following the protocol in Mnih et al (Mnih et al. 2013), and the policy was represented by the convolutional neural network shown in Figure 3, with two convolutional layers with $16$ channels and stride $2$, followed by one fully-connected layer with $20$ units, yielding 33,500 parameters.

我们在 (Mnih et al. 2013) 与 (Guo et al. 2014) 所报的同一七款游戏上测试，游戏由 Arcade Learning Environment 提供（Bellemare et al. 2013）。图像预处理遵循 Mnih et al.（Mnih et al. 2013）的协议；策略由图 3 所示卷积神经网络表示：两个 $16$ 通道、步长 $2$ 的卷积层，再接一个 $20$ 单元全连接层，共 33,500 个参数。

The results of the vine and single path algorithms are summarized in Table 1, which also includes an expert human performance and two recent methods: deep $Q$-learning (Mnih et al. 2013), and a combination of Monte-Carlo Tree Search with supervised training (Guo et al. 2014), called UCC-I. The 500 iterations of our algorithm took about 30 hours (with slight variation between games) on a 16-core computer. While our method only outperformed the prior methods on some of the games, it consistently achieved reasonable scores. Unlike the prior methods, our approach was not designed specifically for this task. The ability to apply the same policy search method to methods as diverse as robotic locomotion and image-based game playing demonstrates the generality of TRPO.

vine 与 single path 算法的结果汇总于表 1，表中还包含专家人类表现以及两种近期方法：深度 $Q$ 学习（Mnih et al. 2013），以及蒙特卡洛树搜索与监督训练的结合（Guo et al. 2014），称为 UCC-I。算法运行 500 次迭代约需 30 小时（游戏间略有差异），在 16 核计算机上完成。我们的方法仅在部分游戏上超过先前方法，但始终达到合理分数。与先前方法不同，我们的方法并非专为该任务设计。能把同一策略搜索方法用于机器人运动与基于图像的游戏如此多样的问题，说明了 TRPO 的通用性。

9 Discussion

9 讨论

We proposed and analyzed trust region methods for optimizing stochastic control policies. We proved monotonic improvement for an algorithm that repeatedly optimizes a local approximation to the expected return of the policy with a KL divergence penalty, and we showed that an approximation to this method that incorporates a KL divergence constraint achieves good empirical results on a range of challenging policy learning tasks, outperforming prior methods. Our analysis also provides a perspective that unifies policy gradient and policy iteration methods, and shows them to be special limiting cases of an algorithm that optimizes a certain objective subject to a trust region constraint.

我们提出并分析了用于优化随机控制策略的信赖域方法。我们证明：反复优化带 KL 散度惩罚的策略期望回报局部近似的算法具有单调改进；并表明对该方法做带 KL 散度约束的近似，能在一系列有挑战性的策略学习任务上取得良好经验结果，超过先前方法。我们的分析也提供了统一策略梯度与策略迭代的视角，表明它们是在信赖域约束下优化某一目标的算法的特殊极限情形。

In the domain of robotic locomotion, we successfully learned controllers for swimming, walking and hopping in a physics simulator, using general purpose neural networks and minimally informative rewards. To our knowledge, no prior work has learned controllers from scratch for all of these tasks, using a generic policy search method and non-engineered, general-purpose policy representations. In the game-playing domain, we learned convolutional neural network policies that used raw images as inputs. This requires optimizing extremely high-dimensional policies, and only two prior methods report successful results on this task.

在机器人运动领域，我们在物理仿真器中用通用神经网络与信息量极少的奖励，成功学会了游泳、行走与跳跃的控制器。据我们所知，此前尚无工作用通用策略搜索方法与非工程化的通用策略表示，从零学会所有这些任务的控制器。在游戏领域，我们学会了以原始图像为输入的卷积神经网络策略。这要求优化极高维策略，此前仅有两种方法报告在该任务上成功。

Since the method we proposed is scalable and has strong theoretical foundations, we hope that it will serve as a jumping-off point for future work on training large, rich function approximators for a range of challenging problems. At the intersection of the two experimental domains we explored, there is the possibility of learning robotic control policies that use vision and raw sensory data as input, providing a unified scheme for training robotic controllers that perform both perception and control. The use of more sophisticated policies, including recurrent policies with hidden state, could further make it possible to roll state estimation and control into the same policy in the partially-observed setting. By combining our method with model learning, it would also be possible to substantially reduce its sample complexity, making it applicable to real-world settings where samples are expensive.

由于所提方法可扩展且有坚实理论基础，我们希望它能成为未来在一系列挑战性问题上训练大型、丰富函数逼近器的起点。在我们探索的两个实验域交汇处，有可能学习以视觉与原始感官数据为输入的机器人控制策略，从而给出同时完成感知与控制的统一训练方案。使用更复杂的策略（包括带隐状态的循环策略）可进一步使部分可观测设定下把状态估计与控制卷入同一策略成为可能。把我们的方法与模型学习结合，也可大幅降低样本复杂度，使其适用于样本昂贵的真实世界设定。

Acknowledgements

致谢

We thank Emo Todorov and Yuval Tassa for providing the MuJoCo simulator; Bruno Scherrer, Tom Erez, Greg Wayne, and the anonymous ICML reviewers for insightful comments, and Vitchyr Pong and Shane Gu for pointing our errors in a previous version of the manuscript. This research was funded in part by the Office of Naval Research through a Young Investigator Award and under grant number N00014-11-1-0688, DARPA through a Young Faculty Award, by the Army Research Office through the MAST program.

感谢 Emo Todorov 与 Yuval Tassa 提供 MuJoCo 仿真器；感谢 Bruno Scherrer、Tom Erez、Greg Wayne 以及匿名 ICML 审稿人的深刻评论；感谢 Vitchyr Pong 与 Shane Gu 指出手稿先前版本中的错误。本研究部分由海军研究办公室通过青年研究者奖及资助号 N00014-11-1-0688 资助，由 DARPA 通过青年教师奖资助，并由陆军研究办公室通过 MAST 项目资助。

References

参考文献

Bagnell & Schneider (2003) Bagnell, J. A. and Schneider, J. Covariant policy search. IJCAI, 2003.

Bartlett & Baxter (2011) Bartlett, P. L. and Baxter, J. Infinite-horizon policy-gradient estimation. arXiv preprint arXiv:1106.0665 , 2011.

Barto et al. (1983) Barto, A., Sutton, R., and Anderson, C. Neuronlike adaptive elements that can solve difficult learning control problems. IEEE Transactions on Systems, Man and Cybernetics , (5):834–846, 1983.

Bellemare et al. (2013) Bellemare, M. G., Naddaf, Y., Veness, J., and Bowling, M. The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research , 47:253–279, jun 2013.

Bertsekas (2005) Bertsekas, D. Dynamic programming and optimal control , volume 1. 2005.

Deisenroth et al. (2013) Deisenroth, M., Neumann, G., and Peters, J. A survey on policy search for robotics. Foundations and Trends in Robotics , 2(1-2):1–142, 2013.

Gabillon et al. (2013) Gabillon, Victor, Ghavamzadeh, Mohammad, and Scherrer, Bruno. Approximate dynamic programming finally performs well in the game of Tetris. In Advances in Neural Information Processing Systems , 2013.

Geng et al. (2006) Geng, T., Porr, B., and Wörgötter, F. Fast biped walking with a reflexive controller and realtime policy searching. In Advances in Neural Information Processing Systems (NIPS) , 2006.

Guo et al. (2014) Guo, X., Singh, S., Lee, H., Lewis, R. L., and Wang, X. Deep learning for real-time atari game play using offline Monte-Carlo tree search planning. In Advances in Neural Information Processing Systems , pp. 3338–3346, 2014.

Hansen & Ostermeier (1996) Hansen, Nikolaus and Ostermeier, Andreas. Adapting arbitrary normal mutation distributions in evolution strategies: The covariance matrix adaptation. In Evolutionary Computation, 1996., Proceedings of IEEE International Conference on , pp. 312–317. IEEE, 1996.