Study guide · Robotics & reinforcement learning · 2015

Trust Region Policy Optimization

John Schulman, Sergey Levine, Philipp Moritz, Michael Jordan, Pieter Abbeel · ICML 2015

Policy-gradient methods learn by nudging an agent's behaviour towards whatever just worked, but a nudge that is too big can wreck a good policy in one step. This paper derives a limit on how far each update may move the policy, a "trust region" measured by KL divergence, proves that a penalised version of it never makes things worse, and turns it into a practical algorithm that learns swimming, hopping and walking gaits and plays Atari from pixels.

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.

Everyday pictureA tennis coach watching you serve says "toss the ball a bit higher". If you take that literally and throw it twice as high, your serve collapses. The advice was only good for small changes near what you were doing.

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.

A toy re-creation of the idea, not the paper's experiment. Stacked bars show the policy's probabilities for the three machines after each of 60 updates (green = best machine). Plain steps use REINFORCE with an average-reward baseline. Trust-region steps use the same estimate but halve the step until KL(old ‖ new) ≤ 0.01, the paper's δ. Large plain steps often lock onto the 0.7 machine for good; run 200 agents to see how often.

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.

Old policy: 50% A, 30% B, 20% C (grey bars). The slider moves probability from C towards A (or the other way); amber bars are the new policy. KL(old ‖ new) = Σ old × log(old / new). Inside the budget the step would be allowed as is; outside it, TRPO would shorten the step.

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 δ.

Everyday pictureClimbing a hill in fog, you can only see a few metres. A rule like "never step further than you can see the ground" is cautious, but you will never walk off a cliff, and you still get to the top.

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.

Later refinementTRPO's update needs second-order machinery (a conjugate-gradient solve and a line search), which is awkward with large networks or shared policy-and-value networks. In 2017 the same first author proposed PPO, which gets similar stability by simply clipping how much each action's probability ratio can count, using ordinary gradient steps. PPO largely replaced TRPO and later became the standard optimiser for fine-tuning language models from human feedback (InstructGPT).

TakeawayA single KL budget made policy-gradient learning reliable across robots and Atari. Its successor PPO kept the idea and dropped the heavy maths.

Follow the idea

Led to: PPO (2017)