Conjugate Gradient Method
You'll learn how the conjugate gradient method enables TRPO to efficiently solve constrained optimization problems without computing expensive second-order derivatives.
The Problem TRPO Faces
In TRPO, we want to maximize our policy improvement while staying within a KL divergence constraint (the trust region). This creates a constrained optimization problem. The textbook solution involves computing the full Hessian matrix—a massive table of all second-order derivatives—which is computationally prohibitive for neural networks with millions of parameters.
What Conjugate Gradient Does
The conjugate gradient (CG) method is a clever iterative algorithm that solves systems of linear equations of the form Ax = b without ever constructing the full matrix A. Instead, it only needs the ability to compute matrix-vector products (Ax for any vector x).
Think of it like finding your way through a maze: instead of mapping every wall, you just need to know "if I go this direction, what happens?" You probe intelligently, and each probe gives you information that guides the next one.
Why It's Perfect for TRPO
In TRPO, we need to solve a system involving the Fisher information matrix (a special form of the Hessian for KL divergence). The conjugate gradient method only requires:
- Computing Hessian-vector products (much cheaper than the full Hessian)
- A handful of iterations to get a good approximate solution
This transforms an intractable computation into something feasible, enabling TRPO to scale to deep networks while maintaining theoretical guarantees about policy improvement.
Key Takeaway: The conjugate gradient method solves TRPO's constrained optimization by iteratively approximating the solution using only matrix-vector products, avoiding the prohibitive cost of computing and storing full second-order derivative matrices.