Trust Region Policy Optimization (TRPO)

WHY does TRPO exist?

Vanilla policy gradient (REINFORCE / A2C) updates $\theta \leftarrow \theta + \alpha \nabla_\theta J$ . The problem: the gradient is only accurate locally. A single large step can push the policy into a region where the collected data (samples from the old policy) no longer describes the environment well. Result: a bad update collapses performance, and because RL data depends on the policy, you may never recover.

TRPO answers: how large a step can I take and still guarantee improvement?

WHAT are we actually optimizing?

We want to maximize expected discounted return $J(\pi) = \mathbb{E}_{\tau\sim\pi}\!\left[\sum_t \gamma^t r_t\right]$ .

The exact performance-difference identity (first principles)

The key lemma (Kakade & Langford):

J(\pi') - J(\pi) = \mathbb{E}_{s\sim d^{\pi'},\, a\sim \pi'}\big[A^{\pi}(s,a)\big]

where $A^\pi(s,a)=Q^\pi(s,a)-V^\pi(s,a)$ is the advantage under the old policy, and $d^{\pi'}$ is the discounted state-visitation distribution of the new policy $\pi'$ .

Why this identity is beautiful: it says the improvement of a new policy equals how much extra advantage it collects, measured against the old policy's advantage function. But it's impractical: the states come from $d^{\pi'}$ , which we can't sample until we already have $\pi'$ .

The surrogate: freeze the state distribution

Approximate $d^{\pi'}\approx d^{\pi}$ (valid when $\pi'\approx\pi$ ). Define the surrogate objective:

L_\pi(\pi') = J(\pi) + \mathbb{E}_{s\sim d^\pi,\, a\sim \pi}\!\left[\frac{\pi'(a|s)}{\pi(a|s)}\,A^\pi(s,a)\right]

HOW do we bound the approximation error? (The trust region)

$L_\pi$ matches $J$ to first order at $\pi$ , but drifts as $\pi'$ moves away. TRPO's central theorem bounds the drift by the KL divergence:

J(\pi') \;\ge\; L_\pi(\pi') - C\,\max_s D_{\mathrm{KL}}\big(\pi(\cdot|s)\,\|\,\pi'(\cdot|s)\big), \qquad C = \frac{4\epsilon\gamma}{(1-\gamma)^2}

with $\epsilon = \max_{s,a}|A^\pi(s,a)|$ .

The theoretical penalty coefficient $C$ is huge, forcing tiny steps. TRPO instead turns the penalty into a hard constraint (a "trust region") with a tunable size $\delta$ :

Formula The TRPO optimization problem

\max_{\theta}\;\; \mathbb{E}_{s,a\sim\pi_{\theta_{\text{old}}}}\!\left[\frac{\pi_\theta(a|s)}{\pi_{\theta_{\text{old}}}(a|s)}\,A^{\pi_{\theta_{\text{old}}}}(s,a)\right]

\text{subject to}\quad \bar D_{\mathrm{KL}}(\theta_{\text{old}},\theta)\;\le\;\delta

where $\bar D_{\mathrm{KL}}=\mathbb{E}_{s\sim d^\pi}\!\big[D_{\mathrm{KL}}(\pi_{\theta_{\text{old}}}(\cdot|s)\|\pi_\theta(\cdot|s))\big]$ (mean KL, easier than max KL).

Figure — Trust Region Policy Optimization (TRPO)

HOW is it solved? (Deriving the natural-gradient step)

We can't solve the constrained problem exactly for a deep net. TRPO approximates locally:

Linearize the objective around $\theta_{\text{old}}$ : $L(\theta)\approx g^\top(\theta-\theta_{\text{old}})$ , where $g=\nabla_\theta L$ is the policy gradient.
Quadratically approximate the KL constraint: $\bar D_{\mathrm{KL}}\approx \tfrac12(\theta-\theta_{\text{old}})^\top F (\theta-\theta_{\text{old}})$ , where $F$ is the Fisher Information Matrix (the Hessian of KL, which is $0$ to first order — that's why we need the quadratic term).

The problem becomes:

\max_{s}\; g^\top s \quad\text{s.t.}\quad \tfrac12 s^\top F s \le \delta,\qquad s=\theta-\theta_{\text{old}}.

Solve with a Lagrangian $g^\top s - \lambda(\tfrac12 s^\top F s-\delta)$ . Setting derivative to zero: $g-\lambda F s = 0 \Rightarrow s = \tfrac1\lambda F^{-1}g$ .

Plug into the constraint $\tfrac12 s^\top F s=\delta$ to solve for $\lambda$ :

Why is this smart?

We never form $F^{-1}$ (huge). We compute $F^{-1}g$ via conjugate gradient, needing only Fisher-vector products $Fv$ (cheap via a second autodiff).
Because approximations may violate the true constraint, TRPO does a backtracking line search: shrink the step by $\beta^j$ until the true KL $\le\delta$ and the surrogate actually improved.

Worked Examples

Worked example Example 1 — 2D toy: computing the step

Suppose $g=\begin{bmatrix}2\\0\end{bmatrix}$ , $F=\begin{bmatrix}1&0\\0&4\end{bmatrix}$ , $\delta=0.02$ . Step 1: $F^{-1}g=\begin{bmatrix}2\\0\end{bmatrix}$ . Why? Diagonal inverse: divide by $1$ and $4$ . Step 2: $g^\top F^{-1}g = 2\cdot2=4$ . Why? Dot product with the natural gradient. Step 3: scale $=\sqrt{2\cdot0.02/4}=\sqrt{0.01}=0.1$ . Why? Exactly hits the KL boundary. Step 4: $s=0.1\cdot\begin{bmatrix}2\\0\end{bmatrix}=\begin{bmatrix}0.2\\0\end{bmatrix}$ . Check: $\tfrac12 s^\top F s=\tfrac12(0.2^2\cdot1)=0.02=\delta.$ ✓

Common Mistakes (Steel-manned)

Recall Feynman: explain to a 12-year-old

Imagine you're adjusting a recipe you already cooked. You tasted the food (collected data) and know which changes make it better. But if you change too many ingredients at once, your old taste-notes no longer apply — you might ruin it. TRPO says: change the recipe in the best direction, but only a little bit each time — small enough that your notes still make sense. The "how much is too much" is measured by how different the new recipe is from the old one, not by how many numbers you changed.

Active Recall

What performance-difference identity does TRPO build on?

J(\pi')-J(\pi)=\mathbb{E}_{s\sim d^{\pi'},a\sim\pi'}[A^\pi(s,a)]

— new-minus-old return equals extra advantage collected.

Why is that identity impractical to use directly?

The states are drawn from

d^{\pi'}

(the new policy's visitation), which we can't sample before we have

\pi'

What approximation gives the surrogate objective?

Replace

d^{\pi'}

with

d^{\pi}

(valid when

\pi'\approx\pi

), then importance-sample actions.

Write the TRPO surrogate objective.

\mathbb{E}_{s,a\sim\pi_{old}}\big[\frac{\pi_\theta(a|s)}{\pi_{old}(a|s)}A^{\pi_{old}}(s,a)\big]

What is the TRPO constraint?

Mean KL divergence

\bar D_{KL}(\theta_{old},\theta)\le\delta

— a hard trust region in policy-distribution space.

Why constrain KL instead of

\|\Delta\theta\|

Equal parameter steps cause unequal distribution changes; KL measures distance in distribution space, which is what actually matters for validity of the surrogate.

What matrix approximates the KL constraint quadratically?

The Fisher Information Matrix

F

(Hessian of KL at

\theta_{old}

Give the closed-form TRPO step.

s=\sqrt{\frac{2\delta}{g^\top F^{-1}g}}\,F^{-1}g

, i.e. natural gradient scaled to the trust boundary.

How is

F^{-1}g

computed without inverting

F

Conjugate gradient using Fisher-vector products

Fv

Why the backtracking line search after the CG step?

The linear/quadratic approximations may violate the true KL constraint or fail to improve the surrogate; line search shrinks the step until both hold.

What does

F^{-1}g

(the natural gradient) represent geometrically?

The steepest-ascent direction measured in KL geometry rather than Euclidean parameter geometry.

What guarantee does the theory provide?

Monotonic (non-decreasing) improvement of true

J

when optimizing the lower bound

L-C\cdot D_{KL}

Connections

Policy Gradient Methods — TRPO fixes their instability under large steps.
Natural Gradient Descent — the $F^{-1}g$ direction is the natural gradient.
Fisher Information Matrix — curvature of the KL, defines the trust-region geometry.
KL Divergence — the distance measure defining the trust region.
Proximal Policy Optimization (PPO) — cheaper successor: clips the ratio instead of a hard KL constraint.
Conjugate Gradient Method — solves $Fx=g$ without forming $F$ .
Advantage Estimation (GAE) — how $A^\pi$ is estimated in practice.
Importance Sampling — reweights old samples to score the new policy.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, RL me problem ye hai ki agar aap policy ko ek hi step me bahut zyada change kar do, toh jo purana data collect kiya tha wo naye policy ke liye galat ho jaata hai — aur RL me galat policy toh galat data banati hai, phir cheezein aur bigadti jaati hain. Isliye TRPO kehta hai: improvement ki direction me jao, par utna hi jao jitna "trust" kar sakte ho.

"Kitna trust karein" — yahi TRPO ka mast idea hai. Hum step ko $\theta$ (parameters) me nahi, balki policy distribution me measure karte hain, using KL divergence. Constraint ye hai: naya aur purana policy ka mean KL $\le \delta$ hona chahiye. Yani ek chhota sa "speed limit" distribution-space me. Objective hum optimize karte hain wo hai surrogate — jisme importance ratio $\frac{\pi_{new}}{\pi_{old}}$ ko advantage $A$ se multiply karte hain. Agar action achha hai ( $A>0$ ), objective uski probability badhata hai; bura hai toh ghatata hai.

Solve kaise karte? Objective ko linear approx karo (gradient $g$ ), constraint ko quadratic approx karo (Fisher matrix $F$ ). Lagrangian solve karne pe step milta hai: $s=\sqrt{2\delta/(g^\top F^{-1}g)}\,F^{-1}g$ . Ye $F^{-1}g$ hi natural gradient hai — matlab steepest direction, par KL geometry me. Practically hum $F$ invert nahi karte (bahut bada hota hai), balki conjugate gradient se $F^{-1}g$ nikaalte hain, aur end me ek line search karke confirm karte hain ki actual KL constraint aur improvement dono theek hain.

Bottom line: TRPO ka guarantee hai ki har step me true return kam nahi hoga (monotonic improvement) — stable, safe learning. Baad me PPO isi idea ko simple bana deta hai (hard KL constraint ki jagah ratio clipping), par samajh TRPO se aati hai.

Trust Region Policy Optimization (TRPO)

WHY does TRPO exist?

WHAT are we actually optimizing?

The exact performance-difference identity (first principles)

The surrogate: freeze the state distribution

HOW do we bound the approximation error? (The trust region)

HOW is it solved? (Deriving the natural-gradient step)

Worked Examples

Common Mistakes (Steel-manned)

Active Recall

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Deep & Advanced RL

Connections