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

Line Search and Step Size Selection

Using backtracking line search to ensure the KL constraint is satisfied while improving performance.

Line Search and Step Size Selection

What You'll Learn

You'll learn how backtracking line search ensures your policy update satisfies the KL divergence constraint while still improving performance in TRPO.

The Core Problem

After computing an update direction using the conjugate gradient method and Fisher information matrix, you have a direction to move your policy—but how far should you actually step? Taking too large a step might violate your trust region (the KL constraint) and destabilize training. Too small a step wastes the opportunity to improve.

How Backtracking Line Search Works

Think of it like walking in fog with a safety rope. You know the direction you want to go (from conjugate gradient), and you have a maximum safe distance (the KL constraint). Backtracking line search starts optimistically—it tries the full step size first. If that violates the KL constraint or doesn't improve the surrogate objective, it "backtracks" by repeatedly shrinking the step size (typically by multiplying by 0.5 or similar) until both conditions are satisfied:

  1. KL constraint satisfied: The new policy doesn't diverge too much from the old one
  2. Performance improved: The surrogate objective actually increases

The Algorithm in Plain English

  1. Start with your maximum allowed step size
  2. Apply that step to get a candidate new policy
  3. Check: Does it satisfy KL ≤ δ (your trust region bound)?
  4. Check: Does the surrogate objective improve?
  5. If both yes: accept this step. If no: shrink the step size and try again
  6. Repeat until you find an acceptable step or hit a minimum threshold

This adaptive approach gives you the largest safe improvement rather than being overly conservative or recklessly aggressive.

Key Takeaway: Backtracking line search dynamically finds the largest step size that both respects the trust region (KL constraint) and improves policy performance, making TRPO updates both safe and effective.