Foundations — Trust Region Policy Optimization (TRPO)

This page builds every symbol the parent note leans on, starting from a smart 12-year-old who has never seen a single one. Read top to bottom: each block only uses things defined above it.

---

0. The stage: agent, states, actions, rewards

Before any Greek letter, picture a game.

Figure s01 — the RL loop. The violet agent (holding its strategy) sends an action (magenta arrow) to the orange environment, which returns the next state and a reward (navy arrow). Round and round: this loop is the entire game TRPO plays. (The symbols $\pi ,a,s,r$ for these four objects are defined just below.)

Why we need them: reinforcement learning is the loop state → action → reward → next state, repeated. TRPO's whole job is to improve the policy $\pi$. See Policy Gradient Methods for the base loop.

---

1. $\pi (a\mid s)$ — a policy is a probability, not a fixed choice

The dial doesn't pick one action; it assigns a probability to each.

---

2. $\theta$ — the knobs that shape the policy

The policy is produced by a neural network. That network has millions of adjustable numbers.

${\pi }_{{\theta }_{\text{old}}}$ just means the policy before this update (the one that collected our data); ${\pi }_{\theta }$ is the candidate new policy we are searching for.

---

3. $\mathbb{E}[\cdot ]$ — the expected (average) value

The subscript names what randomness we average over: ${\mathbb{E}}_{a\sim \pi }[\dots ]$ = "average over actions $a$ drawn from policy $\pi$." The squiggle $\sim$ reads "sampled from."

Why the topic needs it: rewards are random (the policy is random, the world may be random). We can't talk about "the return" — only its average, which is exactly what we try to raise.

---

4. $\gamma$, the start distribution ${\rho }_0$, and the return $J$ — the number we maximize

---

5. $V^{\pi }$, $Q^{\pi }$, and the advantage $A^{\pi }$ — "how good is this move?"

We need to score individual states and actions, not just whole games.

Figure s02 — advantage as height above the average. The violet bars are the action-values $Q(s,a)$ for four actions; the orange line is the state's average value $V(s)$. Each magenta arrow is the advantage $A=Q-V$: actions above the line have $A>0$ (do more of them), below have $A<0$ (do less).

---

6. $d^{\pi }$ — how often each state is visited

The surrogate we build next averages over states. We must say precisely which states, and how often each counts.

Why the topic needs it: when we average an advantage "over the states the policy sees," $d^{\pi }$ is exactly that weighting. The old policy's version, $d^{{\pi }_{{\theta }_{\text{old}}}}$, is the distribution of states we actually have samples from.

---

7. The performance-difference lemma → the surrogate $L$

Now the heart of the matter: why the surrogate objective has the exact shape it does.

The lemma is exact but useless as written: it needs $s\sim d^{{\pi }^{\prime }}$ and $a\sim {\pi }^{\prime }$ — samples from the new policy we don't have yet. So we make one approximation: since we search only near the old policy, replace $d^{{\pi }^{\prime }}\approx d^{{\pi }_{{\theta }_{\text{old}}}}$ (the states barely move if behaviour barely moves). For the actions, we still only sampled $a\sim {\pi }_{{\theta }_{\text{old}}}$, so we re-weight them with the importance ratio (defined in §8). Dropping the constant $\frac{1}{1-\gamma }$ (it doesn't change the argmax) gives:

---

8. The importance ratio $\frac{{\pi }_{\theta }(a\mid s)}{{\pi }_{{\theta }_{\text{old}}}(a\mid s)}$

We collected data by playing ${\pi }_{{\theta }_{\text{old}}}$, but we want to score the candidate ${\pi }_{\theta }$.

---

9. The policy gradient $g={\nabla }_{\theta }L$ — and why it becomes the log-prob score

We want $g={\nabla }_{\theta }L$ evaluated at $\theta ={\theta }_{\text{old}}$ — the improvement direction TRPO will step along. Here is the key simplification, one line at a time.

---

10. $D_{\mathrm{KL}}$ — measuring the distance between two policies

Now we make "how differently the policy behaves" a real number.

Figure s03 — KL as loss of overlap. Magenta is the old policy's action distribution, violet is the new one; the orange shaded region is their overlap. As the new curve slides away, the overlap shrinks and the KL divergence grows — a single number for "how far behaviour drifted."

$D_{\mathrm{KL}}$ above compares the two policies in one fixed state $s$. But a policy acts across many states, so TRPO averages this per-state KL over the states the old policy actually visits.

---

11. $F$ — the Fisher Information Matrix, curvature of behaviour-space

We want to relate small slider moves $s=\theta -{\theta }_{\text{old}}$ to the resulting mean KL.

---

12. Natural gradient $F^{-1}g$ and the final step — full derivation

Now we have every piece. Near ${\theta }_{\text{old}}$ the surrogate is nearly linear and the constraint nearly quadratic, so TRPO solves this clean sub-problem (with $s=\theta -{\theta }_{\text{old}}$):

Step A — set up the Lagrangian. At the best $s$ the boundary is active ($\frac{1}{2}{s}^{\top }Fs=\delta$: you always spend the whole budget). Glue objective and constraint with a multiplier $\lambda >0$: $\mathcal{L}(s,\lambda )=g^{\top }s-\lambda (\frac{1}{2}{s}^{\top }Fs-\delta ).$ What/why: at the optimum, any further push that raises $g^{\top }s$ is exactly cancelled by the constraint's pushback — that balance is a zero gradient of $\mathcal{L}$.

Step B — differentiate in $s$ and set to zero. ${\nabla }_s\mathcal{L}=g-\lambda Fs=0⟹s=\frac{1}{\lambda }{F}^{-1}g.$ What this says: the direction is forced to be the natural gradient $F^{-1}g$; only its length ($1/\lambda$) is still unknown.

Step C — pin the length using the active constraint. Substitute $s=\frac{1}{\lambda }{F}^{-1}g$ into $\frac{1}{2}{s}^{\top }Fs=\delta$, using that $F$ is symmetric so $(F^{-1}g{)}^{\top }F(F^{-1}g)=g^{\top }{F}^{-1}g$:

\;\;\Longrightarrow\;\; \frac1\lambda=\sqrt{\frac{2\delta}{g^\top F^{-1}g}}.$$ **Step D — assemble.** Put $1/\lambda$ back into $s=\tfrac1\lambda F^{-1}g$: > [!formula] The TRPO step (derived from every symbol above) > $$s^\star=\sqrt{\dfrac{2\delta}{g^\top F^{-1} g}}\;\; F^{-1}g$$ > The **direction** is the natural gradient $F^{-1}g$; the square-root **scalar** shrinks it so it lands exactly on the trust-region boundary $\bar D_{\mathrm{KL}}=\delta$. > [!intuition] What $F^{-1}$ actually does to $g$ > Plain gradient $g$ says "uphill in slider-space." Multiplying by $F^{-1}$ **rescales** it into "uphill in behaviour-space" — it *slows down* directions where behaviour is sensitive (steep $F$) and *speeds up* safe directions. That corrected direction $F^{-1}g$ is the ==natural gradient==. See [[Natural Gradient Descent]]. > [!definition] Two computational tools you'll meet > - **[[Conjugate Gradient Method]]** — solves $Fx=g$ (i.e. finds $F^{-1}g$) *without ever building or inverting $F$*, using only cheap products $Fv$. > - **Line search** — after computing $s^\star$, TRPO shrinks it by a factor $\beta^j$ until the *true* KL is $\le\delta$ and the surrogate really improved, because the quadratic bowl was only an approximation. The refinement [[Proximal Policy Optimization (PPO)]] keeps this same behaviour-limit idea but replaces the exact constraint with a cheap clipped objective. --- ## Prerequisite map ```mermaid graph TD A["state s and action a"] --> B["policy pi as probability"] B --> C["parameters theta and network pi-theta"] D["expectation E average"] --> E["return J with discount gamma and start rho0"] E --> F["value V and Q and advantage A"] E --> V["state visitation d-pi"] F --> P["performance difference lemma"] V --> P P --> S["surrogate objective L"] B --> H["importance ratio new over old"] H --> S S --> G["policy gradient g equals grad L"] G --> LG["log prob score form"] B --> I["KL divergence between policies"] I --> J["trust region size delta"] I --> K["Fisher matrix F curvature"] G --> L["natural gradient F-inverse g"] K --> L J --> N["TRPO constrained step"] L --> N S --> N ``` --- ## Equipment checklist Test yourself — say the answer, then reveal. What does $\pi(a\mid s)=0.7$ mean in plain words? ::: In state $s$, the strategy chooses action $a$ 70\% of the time; probabilities over actions sum to 1. What is the difference between parameter space and behaviour space? ::: Parameter space = the network knobs $\theta$; behaviour space = the actual action probabilities $\pi_\theta(\cdot\mid s)$. Equal knob moves can cause tiny or huge behaviour changes. What role does the initial-state distribution $\rho_0$ play in $J$? ::: Every trajectory starts from $s_0\sim\rho_0$; averaging over it makes $J$ a single well-defined number rather than depending on where you happened to begin. How does the infinite-horizon return handle episodes that terminate? ::: A terminal state is made absorbing with reward 0, so all rewards after termination are 0 and the infinite discounted sum equals the finite episode's return. Why do we subtract $V$ to get the advantage $A=Q-V$? ::: To measure how much better an action is than the policy's *average* behaviour in that state, removing baseline noise from the learning signal. What is $d^\pi(s)$ and over which policy do we use it in the surrogate? ::: The discounted state-visitation distribution — how often, discounted, $\pi$ lands in $s$. In the surrogate we use $d^{\pi_{\theta_{\text{old}}}}$, the states we actually sampled. State the performance-difference lemma in words. ::: A new policy's return minus the old one's equals (up to $1/(1-\gamma)$) the average old-policy advantage collected over the new policy's visited states. Which approximation turns the lemma into the surrogate $L$? ::: Replacing the new policy's state visitation $d^{\pi'}$ with the old one's $d^{\pi_{\theta_{\text{old}}}}$, valid only when the policies are close; actions are re-weighted by importance sampling. Over exactly which distributions are $s$ and $a$ sampled in $L(\theta)$? ::: $s\sim d^{\pi_{\theta_{\text{old}}}}$ and $a\sim\pi_{\theta_{\text{old}}}$ — precisely the state–action