Trust Region Policy Optimization

Trust Region Policy Optimization (TRPO)

Trust Region Policy Optimization (TRPO) is a mathematically rigorous algorithm in Reinforcement Learning (RL), belonging to the family of Policy Gradient Methods. First proposed by John Schulman et al. in 2015, TRPO solves the step-size selection problem in policy gradients. In standard gradient methods, a step that is too large in parameter space can lead to a catastrophic drop in policy performance. TRPO addresses this by restricting updates to a “trust region” in the space of action distributions rather than the parameter space.

Key Features

• Monotonic Improvement Guarantee: TRPO provides a theoretical guarantee that each policy update will not decrease the expected return of the policy, ensuring stable optimization.
• Trust Region Constraint: Rather than checking step size in parameter space, TRPO constrains the update using the average Kullback-Leibler Divergence (KL divergence) between the old policy ${\pi }_{{\theta }_{\text{old}}}$ and the new policy ${\pi }_{\theta }$ to be within a bound $\delta$: ${\bar{D}}_{\text{KL}}({\theta }_{\text{old}}\parallel \theta )\le \delta$
• Surrogate Objective Maximization: The policy is updated by maximizing a surrogate advantage objective, which uses importance sampling to estimate the new policy’s performance using trajectories collected by the old policy: $\mathcal{L}({\theta }_{\text{old}},\theta )={\mathbb{E}}_{s\sim {\rho }_{{\theta }_{\text{old}}},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]$
• Second-Order Optimization: TRPO computes the search direction using second-order approximation (Fisher Information Matrix), making it highly sample-efficient but computationally intensive.
• On-Policy Learning: TRPO is an on-policy method, requiring new trajectories to be sampled after every policy update.

Practical Implementation

To handle the high computational complexity of calculating the Fisher Information Matrix (FIM) and its inverse, TRPO utilizes:

1. Conjugate Gradient Method: An iterative solver used to compute the search direction (natural gradient step) efficiently without constructing or inverting the FIM explicitly.
2. Backtracking Line Search: A procedure to scale the search direction step size to satisfy the non-linear KL-divergence constraint and ensure a performance improvement.

Related Topics

• Natural Policy Gradient (NPG): The theoretical baseline for TRPO, which uses the Fisher Information Matrix for steepest descent in the policy distribution space.
• Proximal Policy Optimization (PPO): A popular, simpler successor to TRPO that approximates the trust-region constraint using a clipped surrogate objective, making it first-order and easier to scale.
• Policy Gradient Methods: The broader class of reinforcement learning algorithms that directly parameterize and optimize policies.