Computational Cost of TRPO
What you'll learn: You'll understand why TRPO is computationally expensive and where the bottlenecks lie in its implementation.
Why TRPO is Expensive
Trust Region Policy Optimization (TRPO) is powerful but comes with significant computational overhead compared to simpler policy gradient methods like REINFORCE or basic Actor-Critic. The complexity stems from two main operations you've learned: the conjugate gradient method and computing Fisher-vector products.
Breaking Down the Costs
Conjugate Gradient Iterations
The conjugate gradient (CG) method solves the equation Fx = g (where F is the Fisher information matrix and g is the policy gradient) without explicitly computing or inverting F. Each CG iteration requires:
- A Fisher-vector product computation: O(n) where n is the number of policy parameters
- Typically needs 10-20 iterations to converge
Fisher-Vector Products
Computing Fv (Fisher matrix times a vector) requires:
- Computing KL divergence between old and new policies
- Taking second-order derivatives (Hessian-vector products)
- Two backward passes through the network per CG iteration
The Multiplication Effect
Since you need ~15 CG iterations, and each requires expensive second-order computations, TRPO is roughly 10-30x slower than simple policy gradient methods per update.
The Trade-Off
Think of TRPO like using a high-precision GPS system versus a simple compass. The GPS (TRPO) gives you much more reliable directions (stable updates), but requires more computational power. The compass (REINFORCE) is fast but less accurate.
Key Takeaway: TRPO's computational cost scales with conjugate gradient iterations (typically 10-20) multiplied by the cost of Fisher-vector products (requiring two backward passes each), making it significantly slower than first-order methods but offering much better stability.