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:
- KL constraint satisfied: The new policy doesn't diverge too much from the old one
- Performance improved: The surrogate objective actually increases
The Algorithm in Plain English
- Start with your maximum allowed step size
- Apply that step to get a candidate new policy
- Check: Does it satisfy KL ≤ δ (your trust region bound)?
- Check: Does the surrogate objective improve?
- If both yes: accept this step. If no: shrink the step size and try again
- 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.