Trust-Region Policy Optimisation

Policy gradient methods have a structural problem that kills training runs without warning: a single bad step can collapse a policy from expert-level behaviour into random flailing, and gradient ascent gives you no mechanism to detect or prevent this. In 2015, Schulman, Levine, Moritz, Jordan, and Abbeel published Trust Region Policy Optimisation (TRPO), a method that surrounds each update with a hard geometric constraint, turning an unbounded hill-climbing problem into a principled constrained optimisation.

The core instability vanilla policy gradients cannot fix

Standard REINFORCE and its variants maximise the expected return by computing:

∇J(θ) = E[∇ log π_θ(a|s) · A(s, a)]

where A(s, a) is the advantage estimate. The gradient points uphill in parameter space, but "uphill in parameter space" does not map cleanly onto "better policy". A large step in θ-space can move the policy distribution dramatically, invalidating the advantage estimates that were computed under the old policy. The result is an off-distribution update that often over-corrects, destabilising training.

The natural gradient partially addresses this by pre-multiplying by the inverse Fisher information matrix, which rescales the step into policy-distribution space rather than parameter space. TRPO formalises this intuition as an explicit constraint.

The trust-region objective

TRPO replaces the unconstrained gradient step with a constrained optimisation:

maximise over θ:   L(θ_old, θ) = E_s,a ~ π_old [ (π_θ(a|s) / π_old(a|s)) · A_old(s, a) ]

subject to:        E_s [ KL( π_old(·|s) || π_θ(·|s) ) ] ≤ δ

The quantity L is the "surrogate objective": it is a first-order approximation to the true objective improvement, valid as long as the new policy stays close to the old one. The KL constraint operationalises "close" in distribution space rather than parameter space, so the bound on policy degradation is meaningful regardless of the parameterisation.

The theoretical backbone is the Kakade-Langford policy improvement bound: the true expected return of a new policy can be bounded below as a function of the surrogate objective and the KL divergence. Keeping the KL within δ therefore provides a (noisy, approximate) monotonic improvement guarantee.

Solving the constrained problem efficiently

The naive approach, forming and inverting the full Fisher information matrix, costs O(n^2) in the number of parameters. For a neural network with millions of weights this is completely impractical. TRPO sidesteps this with two tricks.

Conjugate gradient. Instead of inverting the Fisher matrix F, TRPO solves the linear system F·x = g (where g is the policy gradient) iteratively using conjugate gradient, requiring only Hessian-vector products. A Hessian-vector product Fv can be computed with two backward passes and costs the same as a single gradient computation.

Backtracking line search. After computing the natural-gradient direction, TRPO shrinks the step size geometrically until both the KL constraint is satisfied and the surrogate objective actually improves (not just in theory but empirically, to catch numerical issues).

The resulting per-update cost is roughly 10 conjugate-gradient iterations plus a handful of line-search evaluations, each requiring a forward-backward pass. Expensive, but tractable.

What TRPO buys in practice

On MuJoCo locomotion tasks (Hopper, HalfCheetah, Ant) TRPO consistently converged where vanilla REINFORCE diverged, with little sensitivity to δ across an order of magnitude (δ ≈ 0.01 to 0.1). On Atari it matched or exceeded the A3C baseline of the time. Crucially, the learning curves are stable: you do not see the sudden collapses that require restarting runs from checkpoints.

TRPO also cleanly generalises advantage estimation. When paired with Generalised Advantage Estimation (GAE, Schulman et al. 2015), which blends TD(1) through TD(∞) advantage estimates via a λ parameter, TRPO achieves strong sample efficiency on high-dimensional continuous control.

When it falls down

Computational overhead. The conjugate-gradient solve plus line search makes each TRPO update roughly 10-20x more expensive than a plain Adam step on the same batch. For large models or tight compute budgets, Proximal Policy Optimisation (PPO) offers similar stability at a fraction of the cost by replacing the hard KL constraint with a clipped surrogate objective.

Second-order approximation is exact only locally. The KL constraint is computed as an expectation over visited states, but the Fisher matrix is approximated with samples. In low-data regimes or with high-variance advantage estimates the constraint can be violated by more than δ even when the algorithm nominally satisfies it.

Compatibility with recurrent policies. The standard formulation samples states independently. Recurrent policies (LSTMs, GRUs) have dependencies across time that break the i.i.d. state assumption; applying TRPO to RNN-based policies requires care in how the KL is computed and averaged.

Constrained multi-objective settings. When there are additional safety or auxiliary constraints beyond the trust-region KL (e.g., in safe RL), TRPO's single-constraint Lagrangian does not directly extend. Constrained Policy Optimisation (CPO) handles this, but at higher complexity.

Discrete low-dimensional tasks. For simple bandits or tabular MDPs, the constraint machinery adds overhead with no benefit. Plain policy gradient with a tuned learning rate performs identically and is far easier to debug.

Further reading

• Schulman, J., Levine, S., Moritz, P., Jordan, M., Abbeel, P. (2015). "Trust Region Policy Optimization." ICML 2015. https://arxiv.org/abs/1502.05477
• Schulman, J., Moritz, P., Levine, S., Jordan, M., Abbeel, P. (2015). "High-Dimensional Continuous Control Using Generalized Advantage Estimation." ICLR 2016. https://arxiv.org/abs/1506.02438
• Schulman, J., Wolski, F., Dhariwal, P., Radford, A., Klimov, O. (2017). "Proximal Policy Optimization Algorithms." https://arxiv.org/abs/1707.06347
• OpenAI Spinning Up - TRPO documentation and reference implementation. https://spinningup.openai.com/en/latest/algorithms/trpo.html