Course contentsShow
← Machine Learning and Deep Learning
Lesson 2299 of 3,53850. Deep Reinforcement Learning: Advanced Policy MethodsFree lesson

Computational Cost of TRPO

Analyzing the computational complexity of conjugate gradient and Fisher-vector products in TRPO.

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:

  1. Computing KL divergence between old and new policies
  2. Taking second-order derivatives (Hessian-vector products)
  3. 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.