PPO Algorithm › Trust Region Methods

Trust Region Policy Optimization (TRPO), PPO's predecessor, formalizes this using KL divergence as a constraint. The KL divergence measures how different two probability distributions are, which makes it a natural choice for measuring policy similarity. Policies that assign similar probabilities to actions have low KL divergence, while policies that behave very differently have high KL divergence. This makes KL divergence a precise, mathematically grounded way to define "how much the policy has changed."

The TRPO objective addresses the policy update problem by maximizing expected advantage while explicitly constraining how much the policy can change. It maximizes the expected advantage weighted by the importance sampling ratio, which allows us to use data from the old policy to evaluate the new policy, while constraining the KL divergence between old and new policies:

$$\begin{aligned} \max_\theta \quad & \mathbb{E}_{s, a \sim \pi_{\theta_{\text{old}}}}\left[\frac{\pi_\theta(a|s)}{\pi_{\theta_{\text{old}}}(a|s)} A^{\pi_{\theta_{\text{old}}}}(s, a)\right] \\ \text{subject to} \quad & \mathbb{E}_s\left[D_{\text{KL}}\left(\pi_{\theta_{\text{old}}}(\cdot|s) \| \pi_\theta(\cdot|s)\right)\right] \leq \delta \end{aligned}$$

To understand how this constrained optimization problem balances improvement against stability, examine each component:

• $\theta$: parameters of the new policy being optimized
• $\theta_{\text{old}}$: parameters of the old policy from which data was collected
• $\mathbb{E}_{s, a \sim \pi_{\theta_{\text{old}}}}$: expectation over states and actions sampled from trajectories collected using the old policy
• $s$: a state sampled from the state distribution under the old policy
• $a$: an action sampled from the old policy in state $s$
• $\pi_\theta(a|s)$: probability of action $a$ in state $s$ under the new policy
• $\pi_{\theta_{\text{old}}}(a|s)$: probability of action $a$ in state $s$ under the old policy
• $\frac{\pi_\theta(a|s)}{\pi_{\theta_{\text{old}}}(a|s)}$: the importance sampling ratio, which reweights data from the old policy to evaluate the new policy
• $A^{\pi_{\theta_{\text{old}}}}(s, a)$: advantage function computed under the old policy, measuring how much better action $a$ is than average in state $s$
• $\mathbb{E}_s$: expectation over states from the state distribution under the old policy
• $D_{\text{KL}}(\pi_{\theta_{\text{old}}} \| \pi_\theta)$: Kullback-Leibler divergence measuring how much the new policy distribution differs from the old policy distribution
• $\delta$: maximum allowed KL divergence, the trust region radius

This constraint ensures the new policy $\pi_\theta$ does not diverge too far from the old policy $\pi_{\theta_{\text{old}}}$ in terms of the probability distributions over actions. The ratio $\frac{\pi_\theta(a|s)}{\pi_{\theta_{\text{old}}}(a|s)}$ is called the importance sampling ratio and allows us to evaluate the new policy using data collected from the old policy. This ratio acts as a correction factor: if the new policy is twice as likely to take an action as the old policy, we weight that action's contribution twice as heavily to account for the fact that it would occur more frequently under the new policy.

TRPO guarantees monotonic improvement under certain conditions, meaning the policy never gets worse than the previous version. This guarantee provides the stability that vanilla policy gradients lack. However, the mathematical machinery required to enforce this guarantee comes with significant computational costs: computing Fisher information matrices and solving linear systems.

Solving the constrained optimization problem requires computing second-order derivatives, specifically the Fisher information matrix, and performing conjugate gradient optimization to solve a system of linear equations. This makes TRPO computationally expensive and difficult to implement correctly. The Fisher information matrix has size $n \times n$ where $n$ is the number of policy parameters, so even storing it is impractical for large neural networks. Computing the matrix-vector product required by conjugate gradient solvers requires special tricks involving second-order automatic differentiation. Computing the Fisher information matrix across multiple workers in distributed settings adds significant overhead.

PPO achieves similar stability guarantees with a first-order method by replacing the hard constraint with a penalty built directly into the objective function. Instead of solving a constrained optimization problem, PPO modifies the objective itself to discourage excessive policy changes. This transformation from constraint to penalty makes PPO dramatically simpler to implement while preserving the needed benefits of trust region methods. The resulting algorithm fits cleanly into any standard deep learning training loop, with no exotic optimization machinery required.