Policy gradients

A robot chooses between two actions. Its policy is a dial that sets the probability of action A, with action B taking the remaining probability.

At probability 0.5 the robot earns 20 units over ten episodes, or 2 per episode. At probability 0.7 it earns 21 units, or 2.1 per episode. At probability 0.9 it earns 10 units, or 1 per episode. Somewhere between 0 and 1 there is a best setting, but the robot cannot see the curve. The section asks how to improve a policy without knowing the world, and the answer is to estimate which way the dial should move from the episodes the robot plays. !The robot can set the dial to any p, but it sees only the returns of the settings it tries: 2 at p = 0.5, 2.1 at p = 0.7, 1 at p = 0.9. The curve between the points is not observed, and three points do not show where the best setting lies. A policy gradient estimates the slope from sampled episodes and turns the dial a little. The figure is synthetic: the three returns are the section's worked example, not a measurement. Status: synthetic.

That estimate is the job of a policy gradient method, which turns the returns into a small turn of the dial. The robot sees only the returns, never the curve itself.

The policy is written π and depends on a parameter vector θ [S:83:343]. A parameter vector is a list of numbers, one per knob; here the knobs are the action scores. For two actions, a common form turns a score for each action into a probability with the softmax rule: exponentiate each score and divide by the sum [S:83:344]. The number e is the base of the natural exponential: e^x is the factor by which a quantity growing at rate one is multiplied over x steps, so e^0.1 is the factor for one step of size 0.1. Here the scores are the parameters, so changing a score changes the dial smoothly.

A policy can also be deliberately random. A value-based agent usually acts greedily, with a fixed chance of a random action [S:83:344]. A policy can represent a chosen uneven mix, which matters in games where unpredictability is part of the strategy [S:83:345]. That is one reason to learn the policy directly.

The policy gradient theorem says the slope of expected return can be estimated from experience, without differentiating the unknown effect of the policy on the world [S:83:348]. The slope of expected return with respect to the parameters means: nudge each parameter a little, and read off how much the expected return changes per unit of nudge. That is the key theoretical fact. It turns an impossible derivative into an average over episodes. The actions actually taken supply the sample, and the world's hidden state distribution, the probability that the world is in each state when the agent acts, never needs to be written down.

The classic algorithm is REINFORCE. It waits until an episode ends, then moves the parameters in the direction that makes the actions taken more likely, in proportion to the return that followed [S:83:349]. The step size is written α.

That line says: if an action was followed by a good return, raise its probability; if the return was poor, lower it. The step size α controls how far the dial turns. The vertical bar reads "given": π(taken action | state, θ) is the probability the policy assigns to that action in that state with parameters θ. The logarithm appears because the slope of a probability divided by the probability equals the slope of the logarithm, which is easier to write down and compute.

The slope is a vector with one component per score. For two actions the components are $1-\pi (A)$ for the chosen action and $-\pi (B)$ for the other. The chosen score rises by α times the return times one minus its probability, and the other falls by α times the return times its own probability. The two changes are equal in size because the probabilities sum to one.

Worked example. Start with equal scores, so each action has probability 0.5. One episode returns 2 and takes action A, with α = 0.1. The rule adds 0.1 × 2 × 0.5 = 0.1 to A's score and subtracts 0.1 from B's; the 0.5 is the probability of the chosen action before the update, and its complement is also 0.5. The new probability of A is e^0.1/(e^0.1 + e^−0.1) = 0.5498, about 0.55, so one episode has moved the dial five points.

The return multiplies the whole update, so a return of 0 leaves the dial unchanged. A zero return may mean a bad episode, but the update cannot tell that apart from a genuinely neutral one. A baseline subtracts what was expected, so the update responds to the surprise instead of the raw level.

A baseline is a number subtracted from the return before the update. It leaves the average update unchanged, because the subtracted term averages to zero: the baseline does not depend on the action, so its probability-weighted contribution vanishes. It can still reduce the variance of the estimate [S:83:351]. Variance is the spread of the update around its average; a high-variance update jumps far from episode to episode even when its average is right. A natural baseline is the value of the state, which says how good the episode was relative to what was expected.

An actor-critic method learns the policy and a value function together. The policy is the actor, and the value function is the critic that judges the action [S:83:353]. The critic supplies a lower-variance signal than the raw return, at the cost of its own approximation error [S:83:353].

Think of adjusting a shower tap. You turn it a little, feel the temperature, and turn again. The comparison breaks because a shower answers at once, while a policy's return may arrive after many actions.

The cost is variance. REINFORCE may be of high variance and thus produce slow learning [S:83:351]. One lucky episode can dominate an update, and one unlucky episode can undo good progress. A baseline helps, but it does not remove the problem, and the method can settle in a local optimum [S:83:351]. A local optimum is a setting where every small change lowers the return, even though a distant setting would do better.

The formal statement. Let the policy $\pi (\text{action}\mid \text{state},\theta )$ be a differentiable function of the parameter vector $\theta$ [S:83:343]. For discrete actions the softmax form turns a score for each action into a probability, by exponentiating the score and dividing by the sum over actions [S:83:344]. Performance is the value of the start state under the policy [S:83:346]. The policy gradient theorem states that the gradient of performance is proportional to a state-weighted sum of action values times the gradient of the policy [S:83:348]. The weight is the on-policy state distribution, and the constant of proportionality is the average episode length [S:83:348].

The derivation. Start from $v_{\pi }(s)={\sum }_a\pi (a\mid s)q_{\pi }(s,a)$ and differentiate. The product rule gives two sums. The second does not vanish: substituting $q_{\pi }(s,a)={\sum }_{s^{\prime },r}p(s^{\prime },r\mid s,a)[r+\gamma v_{\pi }(s^{\prime })]$ turns it into ${\sum }_{s^{\prime }}p(s^{\prime }\mid s,a)\nabla v_{\pi }(s^{\prime })$, so the same expansion reappears one step later. Unrolling $k$ times weights each state $x$ by $\mathrm{Pr}(s\to x,k,\pi )$, the probability of reaching it in $k$ steps; summing over $k$ gives the unnormalised on-policy distribution $\eta (x)$. Then $\nabla J(\theta )={\sum }_x\eta (x){\sum }_a{q}_{\pi }(x,a)\nabla \pi (a\mid x)$, and dividing by the expected episode length ${\sum }_x\eta (x)$ gives the theorem's $\mu (s)$ weighting. No term cancels at any stage [S:83:347]. The omitted step is the unrolling, written out in full in the book's proof box.

From theorem to algorithm. Multiply and divide each term by the action probability. The sum over actions becomes an expectation over the action the policy actually takes. Replace the action value by the sampled return and you have REINFORCE: move the parameters along the gradient of the log probability, scaled by the return [S:83:349]. The identity that the gradient of a probability equals the probability times the gradient of its logarithm is the whole trick.

The edge case. L1's update multiplies by "the return". The algorithm multiplies by the return from that step, not from the start of the episode [S:83:349]. Use the return from the start at every step and an early action is credited with rewards that came before it had any influence on them. That is a bias, not a rescaling, and a long episode makes it large.

What L1 hid. L1 said a baseline leaves the average update unchanged. The condition is sharper: the baseline may be any function of the state, even a random one, as long as it does not vary with the action [S:83:351]. Subtract something that depends on the action and the extra term no longer sums to zero, so the gradient points somewhere else. L1's phrasing suggested that any number works.

Where the analogy breaks. A shower answers within a second, so you can turn the tap, feel the result and turn again. A policy's return can arrive after a hundred actions, and the credit for it is spread across all of them. The shower is a one-step problem. The policy gradient is not.

Original sources. REINFORCE is the classical algorithm of Williams, 1992, stated with the return-weighted log-derivative update [S:83:349]. The policy gradient theorem, with the proof that avoids differentiating the state distribution, is given in §13.2 [S:83:347-348]. The softmax parameterisation also lets the policy approach a deterministic one, which epsilon-greedy action selection over action values cannot do [S:83:344]. The baseline form and its variance argument are in §13.4 [S:83:351].

An open question. Policy-gradient estimators differ in bias and variance: the full-return estimator is unbiased and noisy; a critic bootstrapped from a learned value function is quieter and biased. Not every change is a trade. A state-dependent baseline reduces variance while leaving the expected update unchanged [S:83:351], and replacing the episode return $G_0$ with the return from the current step $G_t$ removes a bias and lowers variance at the same time [S:83:349]. The book notes that the critic's bias is not caused by bootstrapping as such [S:83:353]. The method is a stochastic gradient ascent on a scalar performance measure, so the estimator only needs to be right in expectation [S:83:343]. What no general rule fixes is how much bias to accept for a given reduction in variance on a given task and budget. Evidence that would settle a rule: a bound on mean-squared error for each estimator as a function of samples and horizon, plus a task where the predicted winner is the measured winner.

A frontier result. PPO keeps the policy-gradient update and constrains how far one batch of data may move the policy [S:287:1]. The clipped objective is a lower bound on the unclipped surrogate objective, since clipping can only reduce each term [S:287:1]. The surrogate objective that lower-bounds the policy's performance is the one penalised by the maximum KL between the old and new policies [S:287:2]. The guarantee therefore comes from the trust-region penalty, not from the clipping; what clipping buys is several epochs of reuse of one batch [S:287:1]. The variance problem that L1 names is managed by limiting the step, not by removing the noise.

What to read next. Read §13.1 of Sutton and Barto for the softmax policy [S:83:344], §13.2 for the theorem, §13.3 for REINFORCE, and §13.4 for the baseline [S:83:351]. Read the PPO paper for the clipped objective and its motivation [S:287:1]. Then read §13.5 for the critic that replaces the sampled return [S:83:353], and §13.6 for the continuing case, which swaps the start-state value for the average reward rate [S:83:355].