Trust Region Policy Optimization (TRPO): Exercises

Definition The four objects you will use on every problem

Before any exercise, meet the players — each is just a list of numbers (a vector) or a table of numbers (a matrix) attached to the policy network's weights $θ$ .

$θ$ — the parameter vector: all the tunable weights of the policy network, stacked into one long column of numbers. Moving the policy = moving $θ$ .
$s = θ - θ_{old}$ — the step vector: the change we apply to the parameters in one update, i.e. "how far and in which direction we nudge every weight." A picture: an arrow starting at the old weights and pointing to the new weights. Everything TRPO computes is really "what should this arrow be?"
$g = \nabla_{θ} L$ — the policy gradient vector: for each weight, the number telling us how fast the surrogate objective $L$ rises if we increase that weight. It points in the steepest-uphill direction of $L$ (in raw parameter-space). See Policy Gradient Methods.
$F$ — the Fisher Information Matrix: a table of numbers that measures, for every pair of weights, how sensitively the policy distribution reacts when you move them. It is the local "map" from a parameter-step $s$ to the KL distance it causes. See Fisher Information Matrix.

So $g$ says "which way is uphill in weight-space," $F$ says "but moving those weights changes the policy by this much," and $s$ is the final arrow we actually take after $F$ corrects $g$ .

Level 1 — Recognition

Here we only name and match pieces. No computation yet.

Exercise 1.1 — Name every symbol

In the TRPO optimization problem

θ max E_{s, a \sim π_{θ_{old}}} [\frac{π _{θ} ( a ∣ s )}{π _{θ_{old}} ( a ∣ s )} A (s, a)] s.t. \overset{ˉ}{D}_{KL} (θ_{old}, θ) \leq δ,

identify in plain words what each of these is: the ratio $\frac{π _{θ}}{π _{θ_{old}}}$ , the quantity $A (s, a)$ , the symbol $\overset{ˉ}{D}_{KL}$ , and the number $δ$ .

Recall Solution

$\frac{π _{θ} ( a ∣ s )}{π _{θ_{old}} ( a ∣ s )}$ — the importance ratio. We collected data with the old policy but want to score the new one, so we re-weight each old sample by how much more (or less) likely the new policy makes that action. See Importance Sampling.
$A (s, a)$ — the advantage: how much better action $a$ is than the average action in state $s$ , under the old policy. Using the objects defined above, $A (s, a) = Q (s, a) - V (s)$ — the Q-value of taking $a$ minus the state's average value. Positive means "better than average, push it up."
$\overset{ˉ}{D}_{KL}$ — the mean KL divergence between old and new action-distributions, averaged over visited states. It measures how different the two policies are as probability distributions (in "nats"). See KL Divergence.
$δ$ — the trust-region size: the maximum allowed KL. A speed limit measured in distribution-space.

Exercise 1.2 — Which lives where?

For each item, say whether it is measured in parameter-space (distances between $θ$ vectors) or distribution-space (distances between probability distributions): (a) $∥ θ - θ_{old} ∥$ , (b) $\overset{ˉ}{D}_{KL}$ , (c) the Fisher matrix $F$ .

Recall Solution

(a) $∥ θ - θ_{old} ∥$ — parameter-space. Plain Euclidean length of the step vector $s$ — how far the weights moved.
(b) $\overset{ˉ}{D}_{KL}$ — distribution-space. It ignores how the weights are laid out and asks only how different the resulting policies are.
(c) $F$ — the bridge between the two. $F$ is the local map that turns a small parameter step $s$ into the distribution-distance it causes: $\overset{ˉ}{D}_{KL} \approx \frac{1}{2} s^{⊤} F s$ . That is exactly why the natural gradient uses $F$ .

Look at the picture below: the arrow $g$ points straight uphill in flat weight-space, but the trust region is a squashed ellipse (because $F$ stretches some directions), so the safe step $s$ is not along $g$ — it is bent by $F^{- 1}$ onto the ellipse boundary.

Figure — Trust Region Policy Optimization (TRPO)

Level 2 — Application

Now we compute, using the TRPO step formula. Recall from the definitions above that $g$ is the policy gradient, $F$ the Fisher matrix, and $s$ the parameter step we solve for:

s = \frac{2 δ}{g ^{⊤} F ^{- 1} g} F^{- 1} g .

Read it as: take the raw uphill direction $g$ , bend it by $F^{- 1}$ (this is the natural gradient direction), then scale the whole arrow so it lands exactly on the KL trust-region boundary.

Exercise 2.1 — Diagonal Fisher step

Let $g = [34]$ , $F = [9004]$ , $δ = 0.01$ . Compute $F^{- 1} g$ , then $g^{⊤} F^{- 1} g$ , then the scale factor, then the full step $s$ . Verify $\frac{1}{2} s^{⊤} F s = δ$ .

Recall Solution

Step 1 (natural gradient). $F$ is diagonal, so its inverse just divides each entry: $F^{- 1} g = [3/9 4/4] = [1/3 1] .$ Why: inverting a diagonal matrix means reciprocating each diagonal entry — no heavy linear algebra. Step 2 (denominator). $g^{⊤} F^{- 1} g = 3 \cdot \frac{1}{3} + 4 \cdot 1 = 1 + 4 = 5.$ Step 3 (scale). $\frac{2 δ}{5} = \frac{0.02}{5} = 0.004 = 0.06324 \dots$ Step 4 (step). $s = 0.06324 [1/3 1] = [0.02108 0.06325] .$ Verify. $\frac{1}{2} s^{⊤} F s = \frac{1}{2} (9 \cdot 0.0210 8^{2} + 4 \cdot 0.0632 5^{2}) = \frac{1}{2} (0.004 + 0.016) = \frac{1}{2} (0.02) = 0.01 = δ .$ ✓

Exercise 2.2 — Importance ratio sign

Old policy $π (a ∣ s) = 0.4$ , new $π_{θ} (a ∣ s) = 0.25$ . Compute the surrogate contribution of this sample when (a) $A = + 2$ , (b) $A = - 2$ . Interpret each sign.

Recall Solution

Ratio $= \frac{0.25}{0.4} = 0.625$ .

(a) $A = + 2$ : contribution $= 0.625 \times 2 = 1.25$ . The action is good, but the new policy made it less likely (ratio $< 1$ ), so we recorded a smaller gain — the objective is telling us we moved the wrong way for this action.
(b) $A = - 2$ : contribution $= 0.625 \times (- 2) = - 1.25$ . The action is bad, and we reduced its probability, so this is still a negative term but less negative than the ratio-1 case — reducing a bad action is rewarded relative to keeping it.

Exercise 2.3 — KL as a speed limit in nats

A step produces $\overset{ˉ}{D}_{KL} = 0.013$ but $δ = 0.01$ . Is the step accepted? What does TRPO do next?

Recall Solution

Rejected: $0.013 > 0.01$ , the true KL exceeds the trust region. TRPO runs a backtracking line search: shrink the step by a factor $β^{j}$ (e.g. $β = 0.5$ : try full, then half, then quarter…) until the true KL $\leq δ$ and the surrogate objective actually improved. The quadratic KL approximation can under-estimate real KL, which is exactly why this safety check exists.

Level 3 — Analysis

Now we reason about why the machinery is built this way.

Exercise 3.1 — Non-diagonal Fisher

Let $g = [11]$ and $F = [2112]$ , $δ = 0.02$ . Compute the natural gradient $F^{- 1} g$ and compare its direction to the raw gradient $g$ . What did $F$ change?

Recall Solution

$det F = 2 \cdot 2 - 1 \cdot 1 = 3$ , so $F^{- 1} = \frac{1}{3} [2 - 1 - 1 2], F^{- 1} g = \frac{1}{3} [2 - 1 - 1 + 2] = [1/3 1/3] .$ Here $F^{- 1} g$ points the same direction as $g$ (both are $[1, 1]$ ) because $g$ happens to be an eigenvector of $F$ (eigenvalue $3$ ). In general the direction changes: $F$ stretches directions of high curvature (large distribution-change per unit $θ$ ) and shrinks the step there, so equal-looking parameter moves cause equal policy moves. See Natural Gradient Descent and Fisher Information Matrix. The scale: $g^{⊤} F^{- 1} g = 1 \cdot \frac{1}{3} + 1 \cdot \frac{1}{3} = \frac{2}{3}$ ; scale $= 2 (0.02) / (2/3) = 0.06 = 0.2449$ ; step $s = 0.2449 [1/3 1/3] = [0.08165 0.08165] .$

Exercise 3.2 — Why the KL Hessian, not the KL gradient

The parent note says the constraint is approximated by $\frac{1}{2} s^{⊤} F s$ , using the second derivative of KL, not the first. Explain why the first-order (gradient) term of KL is useless here.

Recall Solution

At $θ = θ_{old}$ the two policies are identical, so $\overset{ˉ}{D}_{KL} = 0$ there, and it is a minimum (KL is $\geq 0$ ). At a minimum the gradient is zero: $\nabla_{θ} \overset{ˉ}{D}_{KL}_{θ_{old}} = 0$ . So a first-order Taylor expansion would say "KL stays 0 in every direction," which is false. The leading nonzero information is the curvature — the Hessian of KL — and that Hessian is the Fisher matrix $F$ . That is why we must go to second order to see the trust region at all.

Exercise 3.3 — What happens as $γ \to 1$ ?

The theoretical penalty coefficient is $C = \frac{4 ϵ γ}{( 1 - γ ) ^{2}}$ . Describe its behaviour as $γ \to 1$ and explain why that makes the theoretical guaranteed step tiny.

Recall Solution

As $γ \to 1$ , the denominator $(1 - γ)^{2} \to 0$ , so $C \to \infty$ . The guaranteed-improvement bound is $J (π^{'}) \geq L (π^{'}) - C \cdot (KL)$ ; a huge $C$ means even a tiny KL subtracts an enormous penalty, so the largest provably safe step shrinks toward zero. Intuition: with $γ$ near $1$ the agent cares about the far future, so a small policy change can ripple across many timesteps and the worst-case damage grows. This blow-up is exactly why TRPO abandons the literal $C$ and uses a hard tunable constraint $δ$ plus a line search instead.

Level 4 — Synthesis

Now assemble multiple ideas into one pipeline.

Exercise 4.1 — Order the TRPO update

Put these steps in the correct order for one TRPO update, and name the tool used at each: (i) line search, (ii) estimate advantages, (iii) collect trajectories, (iv) compute $F^{- 1} g$ , (v) compute policy gradient $g$ , (vi) scale to the trust-region boundary.

Recall Solution

(iii) Collect trajectories by running $π_{θ_{old}}$ in the environment.
(ii) Estimate advantages $A (s, a)$ from those trajectories — tool: Advantage Estimation (GAE).
(v) Compute the policy gradient $g = \nabla_{θ} L$ of the (importance-weighted) surrogate — tool: Policy Gradient Methods.
(iv) Compute $F^{- 1} g$ by solving $F x = g$ with Conjugate Gradient Method using Fisher-vector products (never building $F$ ).
(vi) Scale to the trust-region boundary via the factor $2 δ / (g^{⊤} F^{- 1} g)$ , giving the full step $s$ .
(i) Line search — backtrack $β^{j}$ until true KL $\leq δ$ and the surrogate improved.

Exercise 4.2 — Full mini-pipeline on numbers

You collected two samples. Sample A: old prob $0.5$ , new prob $0.6$ , advantage $+ 1$ . Sample B: old prob $0.5$ , new prob $0.2$ , advantage $- 2$ . Compute the empirical surrogate objective (average of ratio × advantage). Is this update improving the surrogate?

Recall Solution

Sample A: ratio $= 0.6/0.5 = 1.2$ , term $= 1.2 \times (+ 1) = 1.2$ .
Sample B: ratio $= 0.2/0.5 = 0.4$ , term $= 0.4 \times (- 2) = - 0.8$ .
Surrogate $= \frac{1.2 + ( - 0.8 )}{2} = \frac{0.4}{2} = 0.2$ . Positive surrogate ( $0.2 > 0$ ) means the new policy improves on the old under the frozen state distribution — it raised probability of the good action and lowered probability of the bad one. Whether it improves the true return still needs the KL check + line search.

Exercise 4.3 — Connect TRPO to PPO

State one thing TRPO does with the KL constraint that Proximal Policy Optimization (PPO) replaces, and why PPO's version is cheaper.

Recall Solution

TRPO enforces a hard KL constraint solved with conjugate gradient + Fisher-vector products + line search — mathematically clean but heavy per step. PPO removes the second-order machinery: it either adds a KL penalty or, more commonly, clips the importance ratio to $[1 - ϵ, 1 + ϵ]$ so that pushing the ratio too far stops helping the objective. This keeps the "don't move too far" spirit using only first-order gradients (plain SGD/Adam), so it is far cheaper and easier to implement, at the cost of TRPO's exact trust-region guarantee.

Level 5 — Mastery

Full derivations from first principles.

Exercise 5.1 — Derive the step formula

Starting from $max_{s} g^{⊤} s$ s.t. $\frac{1}{2} s^{⊤} F s \leq δ$ ( $F$ symmetric positive-definite), derive $s = \frac{2 δ}{g ^{⊤} F ^{- 1} g} F^{- 1} g$ . State where the constraint is active.

Recall Solution

Lagrangian. Since maximizing $g^{⊤} s$ pushes $s$ as far as allowed, the constraint is active (equality) at the optimum: $\frac{1}{2} s^{⊤} F s = δ$ . Form $L (s, λ) = g^{⊤} s - λ (\frac{1}{2} s^{⊤} F s - δ) .$ Stationarity. $\nabla_{s} L = g - λ F s = 0 \Rightarrow s = \frac{1}{λ} F^{- 1} g .$ (Uses $F$ symmetric so $\nabla_{s} (\frac{1}{2} s^{⊤} F s) = F s$ .) Solve for $λ$ . Plug into the active constraint: $\frac{1}{2} s^{⊤} F s = \frac{1}{2} (\frac{1}{λ} F^{- 1} g)^{⊤} F (\frac{1}{λ} F^{- 1} g) = \frac{1}{2 λ ^{2}} g^{⊤} F^{- 1} g = δ,$ using $(F^{- 1})^{⊤} = F^{- 1}$ and $F^{- 1} F F^{- 1} = F^{- 1}$ . Hence $λ = \frac{g ^{⊤} F ^{- 1} g}{2 δ}$ (positive root, so $g^{⊤} s > 0$ ). Assemble. $s = \frac{1}{λ} F^{- 1} g = \frac{2 δ}{g ^{⊤} F ^{- 1} g} F^{- 1} g .$ $■$

Exercise 5.2 — Guaranteed-improvement check

With bound $J (π^{'}) \geq L (π^{'}) - C \cdot D_{KL}$ , suppose a step gives surrogate improvement $L (π^{'}) - J (π) = 0.5$ , KL $= 0.01$ , and $C = 30$ . Is monotonic improvement guaranteed by the bound? What if $C = 60$ ?

Recall Solution

The lower bound on the true improvement is $(L (π^{'}) - J (π)) - C \cdot KL$ .

$C = 30$ : $0.5 - 30 (0.01) = 0.5 - 0.3 = 0.2 > 0$ . Guaranteed improvement. ✓
$C = 60$ : $0.5 - 60 (0.01) = 0.5 - 0.6 = - 0.1 < 0$ . The bound no longer guarantees improvement (worst case could decrease $J$ ). ✗ Lesson: a larger penalty coefficient demands a smaller KL step to stay provably safe — precisely why the theoretical $C$ forces tiny steps and TRPO prefers a tuned $δ$ + line search.

Exercise 5.3 — Two-parameter full solve

Let $g = [2 - 1]$ , $F = [4001]$ , $δ = 0.05$ . Compute $F^{- 1} g$ , $g^{⊤} F^{- 1} g$ , the scale, the full step $s$ , and verify the KL constraint is met exactly.

Recall Solution

$F^{- 1} g = [2/4 - 1/1] = [0.5 - 1] .$
$g^{⊤} F^{- 1} g = 2 (0.5) + (- 1) (- 1) = 1 + 1 = 2.$
scale $= 2 (0.05) /2 = 0.05 = 0.2236.$
$s = 0.2236 [0.5 - 1] = [0.1118 - 0.2236] .$
Verify: $\frac{1}{2} s^{⊤} F s = \frac{1}{2} (4 (0.1118)^{2} + 1 (0.2236)^{2}) = \frac{1}{2} (0.05 + 0.05) = 0.05 = δ .$ ✓

Look at the picture below: the penalty $C \cdot KL$ eats into the surrogate gain. For the same KL step, a steeper penalty line ( $C = 60$ ) drops the guaranteed bound below zero.

Recall Self-test checklist

Name every symbol in the TRPO problem ::: importance ratio, advantage, mean KL, trust-region size $δ$ . What are g, F, and s ::: g is the policy gradient (uphill direction in weight-space), F the Fisher matrix (parameter-to-distribution sensitivity), s the parameter step we solve for. Why is the KL constraint quadratic, not linear, in $s$ ::: because KL is minimized (=0) at $θ_{old}$ , so its gradient vanishes and the Fisher Hessian is the leading term. Direction and scale of the TRPO step ::: direction $F^{- 1} g$ (natural gradient), scale $2 δ / (g^{⊤} F^{- 1} g)$ . Why never invert $F$ ::: too big; solve $F x = g$ with conjugate gradient via Fisher-vector products. Why a line search after the step ::: the quadratic KL approximation may violate the true constraint, so backtrack until true KL $\leq δ$ and surrogate improves.