ICML 2015

Trust Region Policy Optimization

John Schulman, Sergey Levine, Philipp Moritz, Michael Jordan, Pieter Abbeel • University of California, Berkeley

TL;DR

TRPO introduces an iterative method for optimizing reinforcement learning policies with guaranteed monotonic improvement. By enforcing a mathematical constraint on policy updates using Kullback-Leibler (KL) divergence, TRPO prevents catastrophic policy degradation during training, enabling stable learning for complex continuous control and discrete tasks.

Reinforcement Learning Policy Gradient Trust Region Conjugate Gradient

Why This Matters

In deep reinforcement learning, training a policy is notoriously unstable. Standard policy gradient methods (like REINFORCE) update parameters using first-order gradient steps. If the step size is even slightly too large, the policy can shift into a regime where it performs terribly, leading to a catastrophic drop in performance from which the agent can rarely recover.

Conversely, setting the step size too small makes learning painfully slow and sample-inefficient. TRPO solves this fundamental trade-off by mathematically answering the question: How large of a step can we safely take to guarantee that the policy always improves?

The Big Idea

TRPO bridges the gap between theoretical policy iteration guarantees and practical deep learning. The authors prove that optimizing a local surrogate objective $L_{\pi}(\tilde{\pi})$ subject to a hard constraint on the average KL divergence between the old and new policy ($\bar{D}_{KL}(\theta_{old}, \theta) \le \delta$) guarantees monotonic improvement. Instead of using a fixed step size in parameter space, TRPO dynamically scales its updates based on the information-theoretic distance between the policy distributions themselves.

How It Works

1. The Monotonic Improvement Bound

The authors build on conservative policy iteration to derive a lower bound on the expected return $\eta(\pi_{new})$ of a new policy:

$$\eta(\pi_{new}) \ge L_{\pi_{old}}(\pi_{new}) - \frac{4\gamma\epsilon}{(1-\gamma)^2} \alpha^2$$

where $\alpha = D_{TV}^{max}(\pi_{old}, \pi_{new})$ is the maximum total variation divergence, $\gamma$ is the discount factor, and $\epsilon$ is the maximum advantage. By replacing the total variation divergence with the more computationally tractable KL divergence, we get a practical surrogate optimization objective.

2. The Trust Region Formulation

Using the theoretical penalty coefficient $C = \frac{4\gamma\epsilon}{(1-\gamma)^2}$ results in step sizes that are far too small in practice. TRPO replaces this penalty with a hard constraint, forming the trust region optimization problem:

$$\max_{\theta} \mathbb{E}_{s \sim \rho_{\theta_{old}}, a \sim q} \left[ \frac{\pi_\theta(a|s)}{q(a|s)} Q_{\theta_{old}}(s,a) \right]$$ $$\text{subject to } \mathbb{E}_{s \sim \rho_{\theta_{old}}} \left[ D_{KL}(\pi_{\theta_{old}}(\cdot|s) \parallel \pi_\theta(\cdot|s)) \right] \le \delta$$

3. Efficient Optimization via Conjugate Gradient

Solving this directly for a neural network with thousands of parameters is highly demanding. TRPO approximates the objective linearly and the constraint quadratically:

$$g^T (\theta - \theta_{old}) \quad \text{subject to} \quad \frac{1}{2}(\theta - \theta_{old})^T H (\theta - \theta_{old}) \le \delta$$

where $g$ is the policy gradient and $H$ is the Fisher Information Matrix (FIM). Instead of computing and inverting the massive matrix $H$, TRPO uses the Conjugate Gradient (CG) algorithm to solve $Hs = g$ using only matrix-vector products $Hx$, reducing the computational complexity dramatically.

Interactive Playground

Explore the mechanics of TRPO through live simulations and interactive visualizations.

1. Trust Region & Policy Collapse

Drag the step-size slider to see how standard policy gradient (which ignores curvature) can overshoot and cause catastrophic policy collapse, while TRPO's trust region constraint ($\delta$) ensures safety.

Step Size ($\beta$) 1.2

True Performance $\eta(\theta)$ Surrogate $L(\theta)$ Trust Region ($\delta$)

2. Single-Path vs. Vine Sampling

TRPO describes two ways to estimate the policy objective: Single-Path (standard trajectory rollouts) and Vine (branching rollouts from a subset of states). Toggle below to see how they explore state-action space.

Single-Path generates continuous trajectories using the current policy. It is highly practical and works model-free without state resets.

3. Natural Gradient & FIM Warping

Standard gradient descent moves orthogonal to objective contours. Natural Gradient (TRPO) warps the direction using the Fisher Information Matrix (FIM) to respect the probability distribution's true geometry.

Showing: Standard Gradient

Empirical Results

TRPO was evaluated across challenging continuous control tasks (MuJoCo) and discrete environments (Atari). Unlike previous methods, TRPO consistently learned high-quality locomotion gaits from scratch without complex reward shaping or hand-designed policy architectures.

Locomotion Task Performance (Average Return)

Swimmer TRPO (Single Path): 364 params

Hopper TRPO (Vine): 4,806 params

Walker TRPO (Vine): 8,206 params

Limitations & Open Questions

Computational Complexity: Computing Hessian-vector products via Conjugate Gradient is far more expensive than simple first-order gradient steps. This paved the way for successors like PPO (Proximal Policy Optimization) which approximate the trust region with a clipped objective.
Sample Efficiency: While TRPO is highly stable, it still requires millions of environment steps to learn complex locomotion gaits from scratch.
Shared Parameters: TRPO does not easily support architectures where policy and value function networks share parameters, as the trust region constraint is only defined over the policy's action distribution.

Glossary

Kullback-Leibler (KL) Divergence

A mathematical measure of how one probability distribution diverges from a second, expected probability distribution. In TRPO, it is used to constrain how much the updated policy can differ from the old policy.

Fisher Information Matrix (FIM)

A matrix that measures the amount of information that an observable random variable carries about an unknown parameter. In policy optimization, it defines the local curvature of the policy's parameter space.

Conjugate Gradient (CG) Method

An algorithm for the numerical solution of particular systems of linear equations, used in TRPO to solve the quadratic trust-region constraint without explicitly storing the dense Fisher Information Matrix.

BibTeX Citation

@inproceedings{schulman2015trust,
  title={Trust region policy optimization},
  author={Schulman, John and Levine, Sergey and Moritz, Philipp and Jordan, Michael and Abbeel, Pieter},
  booktitle={International conference on machine learning},
  pages={1889--1897},
  year={2015},
  organization={PMLR}
}