← Advanced Policy Gradient Methods

Trust Region Policy Optimization (TRPO)

Overview

Trust Region Policy Optimization (TRPO) addresses the central weakness of vanilla policy gradients: a gradient points toward local improvement, but an ordinary parameter-space step gives no principled guarantee that the represented policy distribution changes only a small amount.

TRPO keeps the local policy-improvement objective, but constrains the update using KL divergence so that the new policy remains inside a trusted neighborhood of the old one.

The Constrained Optimization Problem

Let \(\theta_{\mathrm{old}}\) denote the parameters that generated the current batch, and let \(\theta\) denote a candidate new policy. TRPO optimizes the importance-sampled surrogate objective while constraining the average KL divergence:

\[ \max_\theta \quad L_{\theta_{\mathrm{old}}}^{\mathrm{IS}}(\theta) \qquad \text{subject to} \qquad \bar D_{\mathrm{KL}} \left( \pi_{\theta_{\mathrm{old}}} \,\middle\|\, \pi_\theta \right) \le \delta. \]

Define the parameter displacement

\[ \Delta\theta = \theta-\theta_{\mathrm{old}}. \]

TRPO then replaces the original nonlinear constrained problem with a local approximation around \(\theta_{\mathrm{old}}\).

Local Approximation

Around the current policy, approximate the objective to first order:

\[ L(\theta_{\mathrm{old}}+\Delta\theta) \approx L(\theta_{\mathrm{old}}) + g^\top \Delta\theta, \]

where

\[ g = \nabla_\theta L_{\theta_{\mathrm{old}}}^{\mathrm{IS}}(\theta) \bigg|_{\theta=\theta_{\mathrm{old}}}. \]

The constant \(L(\theta_{\mathrm{old}})\) does not affect which update maximizes the local objective, so we keep only

\[ g^\top\Delta\theta. \]

This term is the first-order predicted improvement in the surrogate objective.

Second-Order KL Constraint

The KL divergence is locally quadratic:

\[ \bar D_{\mathrm{KL}} \left( \pi_{\theta_{\mathrm{old}}} \,\middle\|\, \pi_{\theta_{\mathrm{old}}+\Delta\theta} \right) \approx \frac{1}{2} \Delta\theta^\top F \Delta\theta, \]

where \(F\) is the Fisher information matrix evaluated at the old policy.

Therefore, the local TRPO problem becomes

\[ \boxed{ \max_{\Delta\theta} \quad g^\top\Delta\theta \qquad \text{subject to} \qquad \frac{1}{2} \Delta\theta^\top F \Delta\theta \le \delta }. \]

Why the Solution Points Along the Natural Gradient

The ordinary gradient \(g\) tells us which direction improves the surrogate fastest per unit of Euclidean parameter movement.

TRPO instead asks:

Which parameter change improves the surrogate fastest while changing the policy distribution by only a small amount?

The constrained solution has direction

\[ \Delta\theta \propto F^{-1}g. \]

This is the natural-gradient direction.

Multiplying by \(F^{-1}\) reshapes the raw gradient according to the local geometry of probability distributions:

Solving for the Step Size

Let

\[ v = F^{-1}g. \]

Write the update as

\[ \Delta\theta = \alpha v. \]

Enforcing the quadratic KL boundary gives

\[ \frac{1}{2} \alpha^2 v^\top F v = \delta. \]

Since \(v=F^{-1}g\),

\[ v^\top F v = g^\top F^{-1}g. \]

Therefore,

\[ \alpha = \sqrt{ \frac{ 2\delta }{ g^\top F^{-1}g } }. \]

The local TRPO step is consequently

\[ \boxed{ \Delta\theta_{\mathrm{TRPO}} = \sqrt{ \frac{ 2\delta }{ g^\top F^{-1}g } } F^{-1}g }. \]

Why We Do Not Form \(F^{-1}\) Explicitly

In a neural network, \(F\) can contain millions of rows and columns. Constructing it explicitly is expensive; inverting it directly is worse.

TRPO therefore does not compute \(F^{-1}\). Instead, it solves the linear system

\[ Fv = g \]

approximately using conjugate gradient.

The crucial computational trick is that conjugate gradient only needs products of the form

\[ Fv, \]

not the full matrix \(F\). These Fisher-vector products can be computed efficiently through automatic differentiation using the Hessian-vector product of the KL divergence.

Conjugate Gradient

Conjugate gradient is an iterative method for approximately solving

\[ Fv=g \]

when \(F\) is symmetric positive semidefinite. This is exactly the structure provided by the Fisher information matrix.

It efficiently produces the direction \(v\approx F^{-1}g\) without explicitly computing the inverse.

Why the Natural Gradient Is Different from the Raw Gradient

The raw gradient \(g\) is generally not the direction that gives the best improvement per unit of policy change. It only answers the Euclidean question:

\[ \text{Which direction increases the objective fastest per unit of } \|\Delta\theta\|_2? \]

The natural gradient answers the distributional question:

\[ \text{Which direction improves the objective fastest per unit of local KL change?} \]

Since \(F\) measures how sensitive the policy distribution is to each parameter direction, the transformation

\[ F^{-1}g \]

rescales the raw gradient according to the geometry of policy space.

Line Search

The derivation above uses local first- and second-order approximations. Those approximations are only reliable near \(\theta_{\mathrm{old}}\).

TRPO therefore commonly performs a backtracking line search along the candidate natural-gradient direction. Starting from the proposed step, it repeatedly shrinks the update until the actual policy satisfies the KL constraint and achieves sufficient surrogate improvement.

\[ \theta_{\mathrm{new}} = \theta_{\mathrm{old}} + \beta^j \Delta\theta_{\mathrm{TRPO}}, \qquad 0<\beta<1. \]

This converts the local approximation into a practical algorithm with an explicit check on the realized policy change.

Putting It Together

TRPO can be understood as the following sequence:

  1. collect trajectories using \(\pi_{\theta_{\mathrm{old}}}\);
  2. estimate advantages \(\hat A_t\);
  3. compute the surrogate gradient \(g\);
  4. compute Fisher-vector products from the KL divergence;
  5. use conjugate gradient to approximately solve \(Fv=g\);
  6. scale the direction so the predicted KL change is at most \(\delta\);
  7. perform a backtracking line search and accept a step satisfying the trust region.

The result is a policy update that follows the local improvement direction while explicitly respecting the geometry of the policy distribution.

Connection to PPO

TRPO solves a constrained optimization problem directly. PPO keeps the same underlying idea but replaces the hard trust-region machinery with a simpler first-order objective that discourages the policy ratio from moving too far.

In that sense, PPO can be viewed as a practical approximation to the trust-region principle developed here. Continue to Proximal Policy Optimization for the penalty and clipping formulations.

Next: Proximal Policy Optimization

Continue to Proximal Policy Optimization to see how the trust-region idea is turned into the KL-penalty and clipped-surrogate objectives.