The paper in four sentences
A "policy" is the agent's set of habits: for each situation, how likely it is to choose each action. Policy-gradient learning shifts those probabilities toward actions that turned out well.
The estimate of "what turned out well" is only trustworthy for behaviour close to what the agent just did, so a big step can push the policy somewhere much worse, and then the agent collects worse data and may never recover.
The paper proves that if you limit how much the action probabilities change (measured by a quantity called KL divergence), you can guarantee improvement in theory, and turns this into a practical rule: take the biggest step that keeps the average change under a small budget.
With one budget setting (δ = 0.01) the method learns robot swimming, hopping and walking in simulation, and plays several Atari games from screen pixels.
Idea · §1–2
Learning habits directly
There are two broad ways to learn by trial and error. One, used by DQN, learns a score for every action and then picks the best-scoring one. The other learns the policy directly: a network that takes in the situation and outputs probabilities for each action (or, for a robot joint, a range of likely torques). This second approach copes naturally with smooth, continuous actions like motor commands.
The basic recipe, called a policy gradient, is simple: try things, then make actions that turned out better than usual a bit more likely and actions that turned out worse a bit less likely. "Better than usual" is called the advantage: how much better this action did than the agent's average from that situation.
The catch is the phrase "a bit". How big a step should you take? Too small and learning crawls. Too large and something nasty happens, as the next idea shows.
TakeawayPolicy gradients adjust action probabilities directly. The size of each adjustment is the hard part.
Idea · §1 · §4
Why one big step can ruin everything
Each update is based on a small, noisy batch of experience, and it only tells you which way is uphill near the current policy. If one step pushes almost all the probability onto a mediocre action, the agent then almost never tries anything else. Its new data carry no information about the better actions, so it cannot climb back out. This is different from ordinary supervised learning, where a bad step is corrected by the next batch of the same data; here, a bad policy changes the data itself.
Below, an agent learns which of three slot machines to play (average payouts 1.0, 0.7 and 0.2, with lots of noise). Each round it plays 8 times and updates. "Plain steps" moves by a fixed multiple of the estimated gradient. "Trust region" takes the same direction but shrinks the step until the policy changes by no more than a small budget.
TakeawayIn reinforcement learning, a policy that collapses onto a bad habit stops gathering the evidence it would need to recover. Small, controlled steps prevent this.
Check yourself
- Why can't the plain learner recover after locking onto the 0.7 machine?
- Once it almost never plays the 1.0 machine, its batches contain almost no evidence about that machine, so the gradient never points back towards it.
- What does the trust-region rule limit: the step in parameters or the change in behaviour?
- The change in behaviour: how different the new action probabilities are from the old ones, whatever parameter change that takes.
Idea · §3–4
Measuring how far a policy moved
To limit the size of a step you need a ruler. Measuring how far the network's weights moved is a poor ruler: in some directions a tiny weight change transforms behaviour, in others a big one does almost nothing. TRPO instead measures how different the behaviour is, using the Kullback–Leibler (KL) divergence between the old and new action probabilities.
KL divergence is zero when the two are identical and grows as they differ. It is especially sensitive when an action the old policy liked becomes rare. The paper limits the average KL over the situations the agent visited to δ = 0.01 per update.
TakeawayTRPO measures step size by how much the behaviour changes (KL divergence), not by how much the weights change.
Idea · §3 · Theorem 1 · Algorithm 1
A guarantee, then a practical shortcut
The paper's theory starts from a neat fact: you can write the new policy's performance as the old performance plus the advantages of the new policy's choices, if you knew which situations it will visit. You do not know that yet, so the paper uses the old policy's situations instead. That estimate is accurate for small changes and increasingly wrong for big ones.
The authors prove how wrong it can get: the error is at most a constant times the largest KL divergence between old and new. So "estimate minus penalty" is a pessimistic lower bound on true performance. Raise the lower bound and the true performance must rise too. Repeating this gives a sequence of policies that never gets worse, at least when every quantity is computed exactly.
The penalty the theory demands is so large that steps become tiny. The practical algorithm keeps the spirit but swaps the penalty for a budget: maximise the estimate, subject to the average KL being at most δ.
TakeawayTheory: estimate minus a KL penalty is a lower bound, so improving it guarantees progress. Practice: replace the penalty with a fixed KL budget per step.
Idea · §8 · Figs. 2–4 · Table 1
Results, and the simpler successor
The authors trained neural-network policies to control simulated robots in the MuJoCo physics engine: a swimmer, a one-legged hopper and a two-legged walker, with torques on each joint as actions. The same method with the same budget learned all three gaits; a natural-gradient method with a fixed step did well on easier tasks but did not learn to hop or walk.
They then applied the same algorithm, barely changed, to seven Atari games from pixels. It was not better than DQN across the board (it won on some games and lost on others), but it showed that one general method could handle both robot control and video games.
TakeawayA single KL budget made policy-gradient learning reliable across robots and Atari. Its successor PPO kept the idea and dropped the heavy maths.
Abstract, restated
An iterative procedure for optimising policies with guaranteed monotonic improvement. Several approximations to the theoretically justified procedure yield Trust Region Policy Optimization (TRPO), similar to natural policy gradient methods and effective for optimising large nonlinear policies such as neural networks. It performs robustly on simulated robotic swimming, hopping and walking, and on Atari games from raw images, with little hyperparameter tuning, despite approximations that deviate from the theory. ICML 2015 (PMLR 37), arXiv:1502.05477.
Section · §2 · Eqs. 1–6
Preliminaries: the surrogate L
Infinite-horizon discounted MDP with initial distribution ρ0; η(π) = 𝔼[Σt γt r(st)] is expected discounted return, Aπ(s, a) = Qπ(s, a) − Vπ(s). Kakade and Langford's identity gives the return of another policy π̃ exactly:
with ρπ̃ the discounted visitation frequency. The dependence of ρπ̃ on π̃ makes this hard to optimise, so the local approximation replaces it with ρπ:
For a parameterised policy, L matches η to first order at θ0 (Eq. 4): equal values and equal gradients. So a sufficiently small step that improves L improves η, but the identity says nothing about how small. Kakade and Langford's conservative policy iteration answered this for mixture policies πnew = (1 − α)πold + απ′ (Eq. 5), with the bound
Mixtures are unwieldy in practice. The paper's first contribution is to extend the bound to general stochastic policies.
Section · §3 · Theorem 1 · Eqs. 7–10 · Algorithm 1
Monotonic improvement by minorisation–maximisation
Replace α by the maximum total-variation divergence DTVmax(π, π̃) = maxs DTV(π(·|s) ‖ π̃(·|s)) (Eq. 7). Theorem 1: with α = DTVmax(πold, πnew) and ε = maxs,a |Aπ(s, a)|,
Since DTV(p ‖ q)2 ≤ DKL(p ‖ q) (Pinsker), this gives
Algorithm 1 iterates πi+1 = argmaxπ [Lπi(π) − C DKLmax(πi, π)]. Writing Mi(π) for the bracket, η(πi+1) ≥ Mi(πi+1) and η(πi) = Mi(πi), so η(πi+1) − η(πi) ≥ Mi(πi+1) − Mi(πi) ≥ 0 (Eq. 10). This is a minorisation–maximisation (MM) algorithm: Mi is a surrogate that touches η at πi and lies below it everywhere.
The figure shows MM in one dimension. The local surrogate is drawn as its linear part (which is what L agrees with to first order); the penalty is quadratic, as KL is to second order. The true curve's curvature is bounded by 2, so any penalty coefficient of at least 1 makes M a valid lower bound.
Section · §4–6 · Eqs. 11–14, 17 · Appendix C
The practical algorithm
With the theoretical C, steps are very small. The paper instead imposes a trust-region constraint (Eq. 11), and since a constraint on the maximum KL over all states is intractable, uses the average KL under the old state distribution:
Replacing sums by sample averages, Σs ρ by an expectation, advantages by Q-values (a constant shift) and Σa by importance sampling with distribution q:
Sampling schemes (§5). Single path: roll out πθold, q = πθold, estimate Q by the discounted return from each state; works on a physical system. Vine: from a set of states on trunk trajectories, branch K actions each and run short rollouts with common random numbers; much lower variance per Q estimate but needs many more simulator calls and the ability to reset to arbitrary states.
Solving the subproblem (§6, Appendix C). Linearise the objective (gradient g) and quadratise the constraint with the Fisher information matrix F, computed as the analytic Hessian of the KL rather than the covariance of gradients. Compute the search direction s ≈ F−1g with conjugate gradient using only Fisher–vector products (on a 10% subsample of the data), scale it to the maximal step β = √(2δ / sTFs), then backtrack with a line search until the surrogate improves and the KL constraint holds.
Relation to natural policy gradient (§7, Eq. 17). Linearising L and quadratising KL gives θnew = θold + (1/λ)F−1∇L. Natural policy gradient fixes the step 1/λ; TRPO fixes the KL δ and chooses the step to meet it, and the line search enforces the constraint on the actual nonlinear policy. With a Euclidean constraint the same derivation gives vanilla policy gradient (Eq. 18), and with no constraint, policy iteration.
TRPO, one iteration (single path) collect trajectories with π_θold estimate Q (or advantages) by discounted returns g = ∇θ of the importance-weighted surrogate at θold s = ConjugateGradient(F, g) F·v via Hessian of mean KL β = sqrt(2δ / sᵀF s) for j = 0, 1, 2, …: backtracking line search θ = θold + 0.5ʲ β s if surrogate(θ) > surrogate(θold) and meanKL(θold, θ) ≤ δ: break θold ← θ
Check yourself
- Which two approximations separate the practical algorithm from the guaranteed one?
- A hard constraint with a chosen δ replaces the penalty with the theoretical C, and the average KL over visited states replaces the maximum KL over all states. (Estimation error in the advantages is also ignored.)
- Why compute Fisher–vector products rather than the Fisher matrix?
- For a network with many thousands of parameters the matrix is too large to form or invert; conjugate gradient needs only products Fv, which cost about as much as a gradient.
Section · §8 · Tables 1–2 · Figs. 3–4
Experiments
Locomotion in MuJoCo (§8.1). Swimmer (10-D state), hopper (12-D) and walker; Gaussian policies from a one-hidden-layer network; δ = 0.01 throughout. Rewards favour forward velocity with small control costs (plus a bonus for each non-terminal step in hopper, and a penalty for strong foot impacts in walker).
| Swimmer | Hopper | Walker | |
|---|---|---|---|
| Policy parameters | 364 | 4,806 | 8,206 |
| Hidden units | 30 | 50 | 50 |
| Simulation steps per iteration | 50K | 1M | 1M |
| Policy iterations | 200 | 200 | 200 |
Baselines: cross-entropy method, CMA-ES, natural gradient with fixed step, empirical-FIM natural gradient, max-KL TRPO (cart-pole only) and reward-weighted regression. Single-path and vine TRPO solved all tasks; natural gradient did well on the easier tasks but failed to produce hopping and walking gaits; CEM and CMA-ES scaled poorly to larger policies.
Atari from pixels (§8.2, Table 1). A small convolutional policy (two conv layers of 16 channels with stride 2, one fully connected layer of 20 units; 33,500 parameters), 500 iterations, taking about 30 hours per game on a 16-core computer, one run per game.
| B. Rider | Breakout | Enduro | Pong | Q*bert | Seaquest | S. Inv. | |
|---|---|---|---|---|---|---|---|
| Random | 354 | 1.2 | 0 | −20.4 | 157 | 110 | 179 |
| Human | 7456 | 31.0 | 368 | −3.0 | 18900 | 28010 | 3690 |
| DQN (2013) | 4092 | 168.0 | 470 | 20.0 | 1952 | 1705 | 581 |
| UCC-I | 5702 | 380 | 741 | 21 | 20025 | 2995 | 692 |
| TRPO single path | 1425.2 | 10.8 | 534.6 | 20.9 | 1973.5 | 1908.6 | 568.4 |
| TRPO vine | 859.5 | 34.2 | 430.8 | 20.9 | 7732.5 | 788.4 | 450.2 |
UCC-I is Guo et al. (2014), which trains a network by imitating Monte Carlo tree search run on the emulator. TRPO is competitive with DQN on some games and well behind on others (Breakout, Beam Rider); the authors' point is generality, since the same algorithm and δ handled both domains.
Section · §9 and lineage
Limitations and lineage
- Theory–practice gap. Monotonic improvement is proved only for the penalised max-KL update with exact advantages; the algorithm used constrains average KL with sampled estimates.
- Sample efficiency. On-policy: every batch is used for one update and then discarded. The authors suggest combining with model learning for real robots.
- Engineering complexity. Conjugate gradient, Fisher–vector products and line search are awkward with architectures that share parameters between policy and value function, or that use noise like dropout.
- Vine requires state resets, which only simulators provide.
Reference
Glossary
- Policy π(a|s)
- Probability of action a in state s.
- η(π)
- Expected discounted return of π.
- Advantage
- A(s, a) = Q(s, a) − V(s): how much better a is than the policy's average in s.
- KL divergence
- DKL(p ‖ q) = Σ p log(p/q); zero iff p = q.
- Trust region
- The set of parameters whose policy is within δ of the old one in average KL.
- MM algorithm
- Minorise–maximise: repeatedly maximise a surrogate that lower-bounds the objective and touches it at the current point.
- Fisher matrix
- Second-order approximation of KL in parameter space; defines the natural gradient.
- Conjugate gradient
- Iterative solver for Fx = g using only matrix–vector products.
- Single path / vine
- The paper's two sampling schemes for estimating Q.