Policy Gradient Methods

Overview

Value-based methods learn values and derive a policy from them. Policy gradient methods change the policy directly, in the direction that increases the expected return [1, 2]. This is the family used to train language models with human feedback on Day 4. This day derives REINFORCE, the basic algorithm of the family, measures how noisy its estimates are and reduces the noise with a baseline. It introduces actor-critic methods with generalised advantage estimation [3, 4], and limits the size of each update with the clipped objective of proximal policy optimisation, abbreviated PPO [5]. It ends with entropy, the measure of how much a policy still explores, and a metric that hides its collapse.

Day at a glance

flowchart LR
  A["Why optimise the policy?"] --> B["REINFORCE"]
  B --> C["Variance and baselines"]
  C --> D["Actor-critic"]
  D --> E["PPO"]
  E --> F["Entropy"]
  F --> G["Your field"]

Why optimise the policy directly?

A policy can be written as a function with parameters that gives a probability to every action, for example a softmax over scores. Changing the parameters changes the behaviour smoothly, which suits continuous actions and stochastic policies, and it is the natural form of a language model, which already outputs a probability for every next word. The question is in which direction to change the parameters to collect more reward.

A stochastic policy draws its action at random with the probabilities that it assigns, while a deterministic policy always takes the same action in a state. The greedy policy of the value-based methods of Day 2 is deterministic, and its exploration is added from outside. The randomness of a policy with parameters is its exploration. A continuous action is a number from a range, such as a steering angle, so there are infinitely many actions. A value-based agent would have to find the best of them before every step. A policy with parameters describes a distribution over the actions and draws one from it, which also suits very large sets of actions, such as the vocabulary of a language model. Smoothly means that a small change of the parameters changes every probability a little, whereas a small change of one action value can make a greedy policy jump to another action.

The project uses the simplest policy of this kind on TokenWorld, a table with a softmax. The parameters are written with the Greek letter theta, \(\theta\). The policy that they define is written \(\pi_\theta(a \mid s)\), with the Greek letter pi as on Day 1 and the parameters as its index. The table holds one parameter \(\theta_{s,a}\) for every pair of a state \(s\) and an action \(a\), called a preference, or a logit in the vocabulary of neural networks. The softmax function turns the preferences of a state into probabilities:

Here \(e \approx 2.718\) is the base of the natural logarithm, and the sum runs over all actions \(b\) of the state. The exponential makes every term positive, and the division makes the probabilities of a state add up to 1. Adding the same number to all preferences of a state changes nothing. In TokenWorld the agent chooses a token in 40 of the 161 states, the unfinished sentences, so the table holds \(40 \times 4 = 160\) parameters. All start at zero, which gives every token the probability \(1/4\): the random policy of Day 1.

The quality of a policy is one number, the return that it collects on average over an episode, called the objective \(J(\theta)\). Gradient ascent improves it step by step:

In the first line, \(G_0\) is the return of an episode from its first step, and \(\mathbb{E}\) is the expectation: the average over all episodes that the policy can produce, each weighted by its probability. The random policy of TokenWorld has \(J = -0.49\), and no policy exceeds the exact optimum of Day 1, 2.75. In the second line, the gradient \(\nabla_\theta J(\theta)\), written with the symbol nabla, is the vector of the slopes of \(J\) with respect to all parameters, the direction in which \(J\) grows fastest. The arrow reads is replaced by, and the learning rate \(\alpha\), the Greek letter alpha, sets the size of the step. The open question is how to obtain the gradient: The agent knows only the episodes that it has played.

REINFORCE

The policy gradient theorem answers it [2]. Its core is one step of calculus, shown here for a single decision, as in the bandit of Day 1, where action \(a\) earns on average the reward \(\mu_a\), the Greek letter mu. The objective is the average reward of each action, weighted by the probability \(\pi_\theta(a)\) of the action:

The gradient of \(J\) is the sum of the terms \(\nabla_\theta \pi_\theta(a)\, \mu_a\). This sum needs the average reward of every action, also of those that the policy almost never takes, so it cannot be estimated by letting the policy act. A rule of calculus helps: The slope of \(\log f\) is the slope of \(f\) divided by \(f\). Here \(\log\) is the natural logarithm, the \(\ln\) of Day 1. Therefore \(\nabla_\theta \pi_\theta(a) = \pi_\theta(a)\, \nabla_\theta \log \pi_\theta(a)\), and the sum becomes an average over the actions that the policy itself chooses:

The index \(a \sim \pi_\theta\) reads: The action is drawn from the policy, and \(r\) is the reward that it then receives. Such an average can be estimated from samples: Act, observe the reward, and multiply it by the gradient of the logarithm of the probability of the action taken. The logarithm of a probability is called a log-probability, and its gradient is the score function. The rewriting is the score-function identity, also called the log-derivative trick.

For a whole episode, the same step is applied to the probability of the episode, a product of the probabilities of its actions and its transitions. The logarithm turns the product into a sum, and the transitions do not depend on \(\theta\), so only the log-probabilities of the actions remain. An action cannot change the rewards that came before it, and their contribution is zero on average. Each log-probability is therefore multiplied by \(G_t\), the return that followed its action:

The sum runs over the steps \(t\) of an episode, and the expectation over the episodes of the current policy. REINFORCE turns the answer into an algorithm [1]: Play an episode, and for every action taken, push its log-probability up in proportion to the return that followed. Actions followed by high returns become more likely, actions followed by low returns less likely. The name is an acronym of the form of the update: REward Increment = Nonnegative Factor times Offset Reinforcement times Characteristic Eligibility. In the words of this day, the three factors are the learning rate, the return minus a baseline, and the gradient of the log-probability. The baseline belongs to the next section and is zero for now. In practice the expectation is replaced by the average over a batch of \(B\) episodes. This gives the estimate of the gradient, written \(\hat{g}\) with a hat, and the update:

The index \((i)\) numbers the episodes of the batch, and one round of playing a batch and updating is called an iteration. On TokenWorld, REINFORCE starts with all parameters at zero and runs 400 iterations with \(B = 32\) and \(\alpha = 0.35\). TokenWorld is not discounted, so the discount factor \(\gamma\), the Greek letter gamma, is 1. It pays its only reward at the end, so \(G_t\) is the reward of the finished sentence at every step. For the softmax policy, the gradient of a log-probability involves only the preferences of the visited state \(s\). Its slope with respect to the preference of an action \(b\) is

The symbol \(\partial\) marks a slope with respect to one parameter while the others are held fixed. Put together, the gradient is a vector with a 1 at the position of the action taken and 0 elsewhere, called a one-hot vector, minus the vector of the probabilities. A positive return therefore raises the preference of the action taken and lowers the others, and a negative return does the opposite.

The estimate is unbiased, but it is noisy, because one episode's return reflects many random choices, as the animation shows. Unbiased means that the average of many such estimates is the true gradient, and noisy that a single one can lie far from it. The animation applies the update to a bandit with three arms that pay a reward of 1 with the probabilities 0.2, 0.8 and 0.5, where every pull is an episode of one step. With the settings shown at the start, a learning rate of 0.1 and a baseline, the probability of the best arm climbs steadily to 0.96 after 600 pulls. With a learning rate of 1 and without the baseline, a few early rewards first drive the probability of the arm with 0.5 up to 0.97. The policy then needs about 100 pulls to turn to the best arm.

Variance and baselines

The noise of an estimate is measured by its variance, the average squared distance of the estimate from its own mean. For a random number \(X\) it is

A variance of zero means that every repetition gives the same number, and the square root of the variance is the standard deviation. The mean of \(B\) independent estimates has the variance of one estimate divided by \(B\), so a larger batch is one remedy, paid for with more episodes. The two tricks of this section cost no additional episodes.

Subtracting a baseline from the return, for example the average return from that state, does not change the expected gradient but can reduce its variance considerably. The baseline is written \(b(s)\), and the policy gradient with a baseline is

The baseline may be any number that depends on the state but not on the action taken in it. It leaves the expectation unchanged, because in every state the gradients of the log-probabilities, weighted by the probabilities of their actions, add up to zero:

The first step is the score-function identity read backwards. The second uses that the probabilities of a state add up to 1 for every value of the parameters, and a constant has a slope of zero. A baseline multiplies this sum by \(b(s)\) and so adds nothing on average, but it changes the size of the single terms.

The usual baseline is an estimate of the value of the state, \(b(s) = \hat{V}(s)\), so that \(G_t - \hat{V}(s_t)\) tells how much better the episode went than is usual from that state. Here the baseline is learned as a running average: After an episode, every visited state moves its baseline a fraction \(\alpha_b\) of the way towards the return that followed. The fraction is 0.05 in the variance measurement and 0.15 during training.

The second trick concerns the return itself. The policy gradient above multiplies each log-probability by \(G_t\), the rewards that come after the action, which is called the reward-to-go. A simpler estimator multiplies every step of an episode by the total return \(G_0\). The variance of these estimators can be measured directly. At the parameters of the random policy of TokenWorld, \(\hat{g}\) is computed sixty times from fresh episodes, the variance of each of the 160 components is taken over the sixty repetitions, and the 160 variances are averaged. The table shows this variance for three batch sizes.

A baseline reduces it on TokenWorld, while another popular trick, using only the rewards that come after each action, changes nothing there, because the whole reward of TokenWorld arrives at the end. With a single reward at the end, \(G_t = G_0\) at every step, and the first two rows are the same estimator. The baseline lowers the variance by a factor of 1.2 to 1.3, and the batch lowers it roughly in proportion to \(1/B\): Dividing 0.0217 by 8 and by 64 gives 0.0027 and 0.00034. The last section of this lecture, Going further, pays rewards along the way, and there the reward-to-go does help. A trick is only as good as its fit to the problem.

Python code in the Colab notebook, Section 2. Open Section 2 of the Colab notebook and run it. The function reinforce_grad computes the estimate \(\hat{g}\) from one batch: Its option baseline subtracts a baseline, and use_rtg switches between the reward-to-go and the total return. The cell repeats the estimate sixty times for each batch size and prints the variances of the table above.

Actor-critic

An actor-critic method learns a value function, the critic, alongside the policy, the actor, and uses the critic to judge each action: The advantage tells how much better an action was than expected [4]. In the symbols of Days 1 and 2, the advantage of action \(a\) in state \(s\) under the policy \(\pi\) is

The action value \(Q^{\pi}(s, a)\) is the return expected after taking \(a\) in \(s\) and following the policy afterwards, and the state value \(V^{\pi}(s)\) is the return expected when the policy also chooses the first action. An estimate of the advantage of the action of step \(t\) is written \(\hat{A}_t\). The return minus the baseline, \(G_t - \hat{V}(s_t)\), is one such estimate, with the noise of the whole rest of the episode. The critic offers a second one that looks a single step ahead, the temporal difference (TD) error of Day 2, written with the Greek letter delta:

The first two terms estimate the value of the action taken: the reward received plus the discounted value that the critic gives to the next state, which is zero after the end of the episode. This estimate contains the randomness of a single step, so its variance is low. While the values of the critic are wrong, however, it is wrong in the same direction every time, and such a systematic error is called a bias. The simplest actor-critic uses \(\delta_t\) after every step for both learners:

The first line is the TD learning of Day 2 with the step size \(\alpha_V\) of the critic, and the second is the REINFORCE update with \(\delta_t\) in place of the return. The gridworlds of the section Your field use this one-step actor-critic.

Generalised advantage estimation blends advantages over one step and over many steps with a parameter lambda [3]; small lambda trusts the critic more, large lambda trusts the observed returns more. The method is abbreviated GAE, and its parameter \(\lambda\), the Greek letter lambda, is a number between 0 and 1. The estimate adds up the TD errors of the following steps, and a TD error that lies \(k\) steps ahead is weighted by \((\gamma\lambda)^k\):

Here \(T\) is the number of steps of the episode. The sum is computed backwards with the recursion \(\hat{A}_t = \delta_t + \gamma\lambda\, \hat{A}_{t+1}\), which starts with zero after the last step. With \(\lambda = 0\) only the first term remains, \(\hat{A}_t = \delta_t\): low variance and the bias of the critic. With \(\lambda = 1\) the values of the states in between cancel in the sum, and what remains is \(\hat{A}_t = G_t - \hat{V}(s_t)\): REINFORCE with the critic as its baseline, without bias and with the full noise of the return. Values in between trade one error against the other, which makes \(\lambda\) a bias-variance dial.

On TokenWorld, this actor-critic trains with batches of 32 episodes. The critic is a table of one value per state and is updated after every episode with \(\alpha_V = 0.25\). The actor is updated once per batch with \(\alpha = 0.35\) and \(\hat{A}_t\) in place of \(G_t\). The figure shows the reference for this experiment: REINFORCE with the three estimators of the previous section, each run eight times with different seeds of the random number generator.

All three curves rise from about \(-0.44\), the return of the random policy in the first batches, to 2.71 after 400 iterations, which is 98.4 to 98.5 percent of the optimum. The curves of the total return and of the reward-to-go coincide exactly, as the variance table predicts. The baseline changes little: Its curve passes 90 percent of the optimum at iteration 90 instead of 110. The right panel explains the missing 1.5 percent. The entropy, the measure of the remaining randomness of a policy that a later section defines, falls from 1.39 to 0.06 but not to zero. In every seed the most likely sentence is the best one, the cat sat <eos>, and now and then the policy still draws another token.

Python code in the Colab notebook, Section 3. Open Section 3 of the Colab notebook and run it. The function train_reinforce contains the whole algorithm, and its line theta += lr * g is the update. The cell trains the three estimators over eight seeds, prints their final returns and draws the figure shown here.

The actor-critic is trained with four values of \(\lambda\) over six seeds. The table gives the mean return at the last recorded iteration, its standard deviation (SD) over the seeds, and the first recorded iteration at which the mean return exceeds 90 percent of the optimum.

On TokenWorld a middle value works best. With \(\lambda = 0.5\) the return ends at 2.73, which is 99.4 percent of the optimum, and passes 90 percent first. The margin is small, however: The four final returns differ by less than 0.07, the size of their standard deviations. The dial shows more clearly early in training. Both tables start at zero, and a critic that knows nothing yet is of little use: After 50 iterations the mean return is 1.68 for \(\lambda = 0\) and 1.96 for \(\lambda = 1\).

Python code in the Colab notebook, Section 4. Open Section 4 of the Colab notebook and run it. In the function train_actor_critic, the list deltas holds the TD errors, and the loop with the line run = deltas[t] + lam * run is the recursion of GAE. The cell trains the four values of \(\lambda\) over six seeds and prints the table above.

Trust regions and PPO

A policy gradient step that is too large can destroy a good policy in one update, and reusing the same data for several updates makes this worse. The estimate \(\hat{g}\) is computed from episodes of the current policy and is valid only close to that policy. After an update the policy is a different one, and strictly its batch would have to be thrown away. Episodes are expensive, however, so practical methods take several gradient steps on the same batch, each called a pass or an epoch. From the second pass on, the data come from a policy that no longer exists.

The region around the old policy in which its data can still be trusted is called a trust region. The idea goes back to the natural policy gradient, which measures a step by the change of the policy and not of the parameters. Trust region policy optimisation, abbreviated TRPO, allows only updates that keep the new policy within a fixed distance of the old one [8]. The distance between two probability distributions \(p\) and \(q\) over the same actions is measured by the Kullback-Leibler divergence, named after its authors and abbreviated KL divergence:

It is zero when the two distributions are equal and grows as they move apart. As an example, the policy of a state moves from the uniform \(q = (0.25, 0.25, 0.25, 0.25)\) to \(p = (0.7, 0.1, 0.1, 0.1)\). The ratio \(p(a) / q(a)\) is \(0.7 / 0.25 = 2.8\) for the first action and \(0.1 / 0.25 = 0.4\) for each of the other three, so \(D_{\mathrm{KL}} = 0.7 \log 2.8 + 3 \times 0.1 \log 0.4 = 0.721 - 0.275 = 0.45\). The experiments of this section report this divergence between the policy after and the policy before every update, averaged over the 40 states of the table.

Proximal policy optimisation limits each change [5]. It compares the new and the old probability of each action as a ratio and clips the ratio to a small range around one, so that the objective stops rewarding changes beyond it. Proximal means near: The new policy stays near the old one. The ratio is written here with the Greek letter rho:

The policy \(\pi_{\mathrm{old}}\) is the one that played the batch, and it stays fixed during the passes. Before the first pass the ratio is 1 for every step, and a ratio of 1.3 means that the action has become 30 percent more likely than it was when it was played. PPO maximises the clipped objective

The symbol \(\mathbb{E}_t\) is the average over all steps of the batch, and \(\hat{A}_t\) is the advantage of the action of step \(t\). The function \(\mathrm{clip}(x, \mathrm{low}, \mathrm{high})\) returns \(x\) when it lies between the two bounds and the nearer bound otherwise. The clip range \(\varepsilon\), the Greek letter epsilon, is 0.2 here, which gives the range from 0.8 to 1.2. The same letter stood for the exploration rate on Days 1 and 2 and has another meaning here.

The first term in the minimum, \(\rho_t \hat{A}_t\), is the objective without a clip, which rewards a change of the ratio without limit. By the score-function identity its gradient is \(\rho_t \hat{A}_t \nabla_\theta \log \pi_\theta(a_t \mid s_t)\): the term of the policy gradient, with the advantage in place of the return, times the ratio. The minimum takes the more cautious of the two terms. For a positive advantage the objective stops growing once the ratio exceeds \(1 + \varepsilon\), and for a negative advantage once the ratio has fallen below \(1 - \varepsilon\). Such a step then contributes no gradient at all. A step whose ratio has moved in the wrong direction is never clipped, so a mistake can always be corrected.

An experiment on TokenWorld isolates the effect of the clip. Both learners use the same advantages, from GAE with \(\lambda = 0.95\) and a critic with \(\alpha_V = 0.25\). The advantages of a batch are first shifted and scaled to a mean of zero and a standard deviation of one, which is called advantage normalisation:

In every pass the plain policy gradient adds \(\hat{A}_t \nabla_\theta \log \pi_\theta(a_t \mid s_t)\) for every step of the batch, and PPO adds the gradient of the clipped objective. The sum is divided by the number of steps in the batch, about 100, so a learning rate of 1 here is comparable to the 0.35 of the earlier sections. Three settings are trained for 300 iterations over six seeds. The first takes one pass with \(\alpha = 1\), where a clip would change nothing, because every ratio is still 1. The other two take eight passes with \(\alpha = 20\), without and with the clip.

On TokenWorld with eight passes over each batch, PPO keeps learning where the plain gradient overshoots. Without the clip, three of the six seeds end on a worse sentence: the the cat sat with a reward of 2.5, the cat <eos> with 2.0 and the sat cat <eos> with 1.75, the worst seed of the table. With the clip, five seeds find the best sentence and one ends on the cat the sat with 2.5.

The panels show how this happens. In the middle panel, the first update of the plain gradient with eight passes moves the policy by a KL divergence of 0.23, about ten times as far as PPO with 0.02. The single pass moves it by less than 0.0001. In the right panel, this one update takes the entropy of the plain learner from 1.39 to 0.71. After ten iterations it is 0.005, against 0.10 for PPO: The policy has stopped exploring before it has seen enough. In the left panel, both fast learners gain most of their return within ten iterations, where the single pass needs about a hundred. The plain one then stays at 2.08 for thirty iterations and ends at 2.42.

The clip is no cure-all: With a very large learning rate, PPO also fails. The first pass over a batch starts at a ratio of 1 for every step, where nothing is clipped, so the first step is as large as the learning rate makes it. The last section of this lecture, Going further, measures this limit. Part C of the interactive lab evaluates the clipped objective by hand, and Part A trains a policy with and without the clip.

Python code in the Colab notebook, Section 5. Open Section 5 of the Colab notebook and run it. The function train_pg contains both learners: With clip=None it follows the plain policy gradient, with clip=0.2 the clipped objective, and epochs is the number of passes. The cell prints the table above and draws the three panels of the figure.

Entropy

The entropy of a policy measures how spread out its choices are. In one state \(s\) it is

With the natural logarithm, the unit of entropy is the nat. The entropy is zero when one action has a probability of 1. It is largest when all \(K\) actions are equally likely, where it equals \(\log K\). For the four tokens of TokenWorld this is \(\log 4 = 1.386\) nats. A policy that has stopped exploring has almost zero entropy. When a policy loses its randomness in this way during training, it is said to collapse.

An entropy bonus in the objective keeps exploration alive, at the cost of some return. The entropy of the states is added to the objective with a weight \(\beta\), the Greek letter beta, called the entropy coefficient:

Here \(L(\theta)\) stands for the objective without the bonus, in this section the clipped objective as a sum over the steps of the batch. The second sum runs over the 40 states of the table. Every update then also pushes the preferences of a state towards each other, each along the slope of the entropy:

For the policy \((0.97, 0.01, 0.01, 0.01)\) of the worked example, with \(H(s) = 0.168\), the slope of the favourite is \(-0.97 \times (\log 0.97 + 0.168) = -0.97 \times (-0.030 + 0.168) = -0.13\). The slope of each of the other three actions is \(-0.01 \times (\log 0.01 + 0.168) = -0.01 \times (-4.605 + 0.168) = 0.04\): The favourite loses, and the neglected actions gain. The interactive lab uses this slope. The experiment of this section uses a simpler push with the constant 1 in place of \(H(s)\), which also raises the entropy of a state with a clear favourite.

The entropy of a whole policy is an average over its states, and the weights of this average decide what the number says. Two averages are compared:

The weight \(d(s)\) is the share of all decisions of the policy that are taken in state \(s\), computed exactly from the probabilities of the policy. The second average gives every state the same weight, whether the policy ever reaches it or not. The comparison also shows a metric that hides a collapse: The entropy averaged over all states looks healthy, while over the states the policy actually visits it is almost zero.

After training with PPO and without a bonus, the average over the visited states is 0.007 nats. The average over all states, 1.17 nats in the first seed, lies close to the maximum of 1.39. In that seed, four states receive 99.9 percent of the visits: the empty sentence, the, the cat and the cat sat. In each of them the entropy is below 0.01 nats, while 30 of the 40 states still have more than 1.3 nats. The states off this path are hardly ever visited, their preferences hardly move, and their almost untouched entropy masks the collapse. The table and the figure show the sweep over five coefficients, each trained with PPO over six seeds.

The entropy over the visited states rises steadily with the bonus, from 0.007 to 0.017 nats, although the policy stays nearly deterministic at these sizes. The return shows no clear trend: All five values lie between 99.2 and 99.9 percent of the optimum, and in each a single seed with a few weaker sentences accounts for most of the gap. The cost of the bonus, which the title of the figure names, appears with larger coefficients. Trained in the same way, a coefficient of 2 ends at 95 percent of the optimum with 0.19 nats, and a coefficient of 10 at 65 percent with 0.75 nats. A policy that is kept random cannot always write the best sentence.

Python code in the Colab notebook, Section 6. Open Section 6 of the Colab notebook and run it. The function policy_entropy of Section 1 computes both averages: over the visited states and, with weighted=False, over all states. The cell trains PPO with the five entropy coefficients over six seeds, prints the table above and draws the figure.

Entropy completes the tools of the day. All of them return on Day 4, which applies the REINFORCE update to a language model, a use that is called reinforcement learning from human feedback, abbreviated RLHF. The table is the bridge between the two days.

The algorithm changes very little. What changes is that the reward becomes a learned and imperfect function, and this single substitution is where the subject becomes difficult.

Your field

The application of the day loads the gridworld of Day 2 for one of three fields and trains three policy gradient learners in it: REINFORCE without and with a baseline, and an actor-critic. Each world is a grid with walls, hazards, a start and a goal. The agent moves up, down, left or right, and a move into a wall or off the grid leaves it in place. Every step has a reward of \(-1\), except the step onto the goal, which has a reward of 0 and ends the episode. A step onto a hazard has the penalty of the table as its reward and puts the agent back at the start. With the slip probability, the chosen action is replaced by a random one of the four. An episode is cut off after 150 steps.

All three learners keep four preferences for every cell, divide the rewards by 10 and discount with \(\gamma = 0.98\). REINFORCE updates at the end of every episode with the discounted return \(G_t = r_{t+1} + \gamma\, G_{t+1}\) and \(\alpha = 0.1\), in its second version with a baseline. The actor-critic is the one-step version of the section above with \(\alpha = 0.3\) and \(\alpha_V = 0.2\). Each learner plays 1000 episodes with two seeds and is judged by the plain sum of the rewards of an episode, averaged over the last 300 episodes.

In the warehouse the baseline already helps; on the windy drone route and in the burning building, only the actor-critic learns within the budget, because returns from whole episodes are too noisy when hazards and slips are common. In the warehouse the mean return is \(-104\) for REINFORCE without a baseline and \(-13\) with it, level with the actor-critic at \(-12\). The shortest route there has 12 steps and a return of \(-11\). On the drone route and in the building, REINFORCE stays below \(-120\) with or without the baseline, while the actor-critic reaches \(-13.5\) and \(-17.6\). One slip into a hazard changes the return of an episode by 50 or 100. REINFORCE sees only this total at the end of the episode, and the actor-critic corrects its values and its policy after every step.

Python code in the Colab notebook, Section 7. Open Section 7 of the Colab notebook. Its first line is a switch, DOMAIN = "warehouse". Replace the word by drone or evacuation and run the section. The functions reinforce_domain and actor_critic_domain train the three learners, and the cell prints the mean return of each over the last 300 episodes.

Going further (optional)

The variance measurement is repeated on a variant of TokenWorld with rewards along the way, where using only the later rewards does help. A sweep of the learning rate then shows how much aggressiveness the clip of PPO can absorb before it fails. In the variant, every token is paid at once for the change that it makes to the score of the sentence. With \(R(s)\) for the score of the sentence written so far, and \(R = 0\) for the empty sentence, the reward of a step is

The rewards of an episode still add up to the score of the finished sentence: the cat sat <eos> earns 0.25, 1.75, 0.75 and 0, in total 2.75. Rewards that are paid along the way are called dense, and a reward that comes only at the end is called sparse. With dense rewards, \(G_t\) and \(G_0\) differ. At a batch of 64 episodes the reward-to-go lowers the variance from 0.000359 to 0.000296, a factor of 1.22. The baseline of the section on variance and baselines, which was fitted to the returns of the original TokenWorld, adds nothing further here: The variance with it is 0.000300.

The table shows the sweep of the learning rate as a percentage of the optimum, for eight passes, 200 iterations and three seeds. The plain gradient begins to lose return at a learning rate of 5. With the clip the optimum is held up to 20, and 97 percent is still reached at 60: The clip absorbs about ten times as much aggressiveness. At 150 the clipped objective ends lower than the plain one, 73 against 82 percent, though three seeds leave this comparison uncertain. The KL divergence of the first update shows where the clip gives out. With the clip it grows from 0.02 at a learning rate of 20 to 0.10 at 60 and 0.26 at 150, because the first pass is never clipped. Such details decide results in practice. A study of PPO found that choices in the implementation, such as the scaling of the rewards and the schedule of the learning rate, account for most of its gain over TRPO [9].

Python code in the Colab notebook, Section 8. Open Section 8 of the Colab notebook, which is optional, and run it. The function dense_step pays the reward of each token at once, and dense_grad measures the variance on these rewards. The second part of the cell calls train_pg for five learning rates, without and with the clip, and prints the table above.

Python step 3: Vectors, the softmax and learning curves

Python code in the Colab notebook, right after Section 0 (setup). Open the notebook and run this step cell by cell: It consists of short pieces of Python code with their explanations, a quick check and three exercises. Topics: Preferences and the softmax · The gradient of a log-probability · REINFORCE on a bandit, with and without a baseline · A learning curve.

The notebook continues with the hands-on sections, and the interactive lab holds three practice parts and the self-assessment. The study path, the daily task and the research assignment are on the day overview.

Review cards

Select a card to turn it over.

References

[1] Williams, R. J. (1992). Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning, 8(3-4), 229-256.

[2] Sutton, R. S., McAllester, D., Singh, S., & Mansour, Y. (2000). Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems 12 (NIPS 1999) (pp. 1057-1063).

[3] Schulman, J., Moritz, P., Levine, S., Jordan, M., & Abbeel, P. (2016). High-dimensional continuous control using generalized advantage estimation. In 4th International Conference on Learning Representations (ICLR 2016). arXiv:1506.02438.

[4] Mnih, V., Badia, A. P., Mirza, M., Graves, A., Lillicrap, T., Harley, T., Silver, D., & Kavukcuoglu, K. (2016). Asynchronous methods for deep reinforcement learning. In Proceedings of the 33rd International Conference on Machine Learning (ICML 2016), PMLR 48, 1928-1937. https://proceedings.mlr.press/v48/mniha16.html

[5] Schulman, J., Wolski, F., Dhariwal, P., Radford, A., & Klimov, O. (2017). Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347. https://arxiv.org/abs/1707.06347

[6] Harris, C. R., Millman, K. J., van der Walt, S. J., Gommers, R., Virtanen, P., Cournapeau, D., Wieser, E., Taylor, J., Berg, S., Smith, N. J., et al. (2020). Array programming with NumPy. Nature, 585(7825), 357-362. https://doi.org/10.1038/s41586-020-2649-2

[7] Hunter, J. D. (2007). Matplotlib: A 2D graphics environment. Computing in Science & Engineering, 9(3), 90-95.

[8] Schulman, J., Levine, S., Abbeel, P., Jordan, M., & Moritz, P. (2015). Trust region policy optimization. In Proceedings of the 32nd International Conference on Machine Learning (ICML 2015), PMLR 37, 1889-1897.

[9] Engstrom, L., Ilyas, A., Santurkar, S., Tsipras, D., Janoos, F., Rudolph, L., & Madry, A. (2020). Implementation matters in deep RL: A case study on PPO and TRPO. In 8th International Conference on Learning Representations (ICLR 2020).