Policy Gradient Methods

Everything up to here has learned a value and read a policy off it. Even the approximate control methods, which never tabulate anything, still estimate $\hat{q}(s,a,\mathbf{w})$ and then act $\epsilon$-greedily with respect to it. The policy is always a derived quantity.

Policy gradient methods drop the intermediary. They learn a parameterized policy $\pi (a\mid s,\mathbf{\theta })$ directly, selecting actions without consulting any value estimate. A value function may still be learned and used to help learn the policy weights, but it is no longer required for action selection.¹ The learner holds a parameter vector $\mathbf{\theta }\in {\mathbb{R}}^{d^{\prime }}$, defines a scalar performance measure$J(\mathbf{\theta })$, and moves $\mathbf{\theta }$ up the gradient of that performance:

where $\widehat{\nabla J({\mathbf{\theta }}_t)}$ is a stochastic estimate whose expectation approximates $\nabla J({\mathbf{\theta }}_t)$. Every method in this lesson is an instance of this gradient ascent on performance; they differ only in how the gradient estimate is constructed.

The one requirement on the parameterization is that $\pi (a\mid s,\mathbf{\theta })$ be differentiable in $\mathbf{\theta }$ — the gradient vector $\nabla \pi (a\mid s,\mathbf{\theta })$ must exist and be finite for every state and action.² To preserve exploration we also require the policy to stay stochastic: $\pi (a\mid s,\mathbf{\theta })\in (0,1)$ rather than committing hard to one action.

Why parameterize the policy directly

Learning $\pi$ rather than $q$ has three advantages.

Stochastic optima are reachable. With $\epsilon$-greedy action selection over values, the policy is always $1-\epsilon$ deterministic plus a uniform random tail — there is no way to express take right with probability $0.6$. Yet the best policy is sometimes genuinely stochastic. In card games with imperfect information the optimal play mixes two actions with specific probabilities (bluffing in poker is the canonical case), and under function approximation, where distinct states can look identical to the approximator, a stochastic policy can be strictly better than any deterministic one.³ A softmax over action preferences can represent any such mixture; a value-greedy policy cannot.

In Sutton and Barto's short-corridor task the reward is $-1$ per step and all three nonterminal states look identical to the approximator, so the policy must pick a single probability of going right and use it everywhere. With $\epsilon =0.1$, an $\epsilon$-greedy value method can only commit to right with probability $1-\epsilon /2=0.95$ or to left with the same probability. Those two extremes reach start-state values worse than $-44$ and worse than $-82$ respectively. A policy that instead selects right with probability near $0.59$ reaches roughly $-11.6$ — a four-fold improvement over the better $\epsilon$-greedy option, obtained purely by holding a genuinely stochastic policy the value method cannot express.

Continuous action spaces are handled directly. Value-based control must, in the end, compute $\arg {\max }_a\hat{q}(s,a)$, which is a search over the action set on every step. When actions are real-valued that maximization is itself an optimization problem. A policy can instead output the parameters of a distribution over actions (a mean and spread), sidestepping the max entirely — the last section builds exactly this.

Smoothness and stronger guarantees. With a continuous parameterization the action probabilities change smoothly as $\mathbf{\theta }$ changes. Under $\epsilon$-greedy the selected action can flip discontinuously the moment one estimated value nudges past another, however small the change. That continuity is precisely what lets policy-gradient methods approximate true gradient ascent, and it is why they enjoy stronger convergence guarantees than action-value methods.⁴ Finally, on some problems the policy is simply a simpler function to represent than the value function, so a policy-based method has less to learn.

Softmax in action preferences

For a discrete, not-too-large action space the standard parameterization forms a numerical preference $h(s,a,\mathbf{\theta })\in \mathbb{R}$ for each state-action pair and passes the preferences through an exponential softmax:

The denominator normalizes the probabilities in each state to sum to one. The preferences can be computed by any differentiable function — a deep network whose weights are $\mathbf{\theta }$ (the AlphaGo route), or a plain linear form in features,

with feature vectors $\mathbf{x}(s,a)\in {\mathbb{R}}^{d^{\prime }}$ built by any of the function-approximation recipes.

That last point is the key contrast with value methods. A softmax over action values would converge to fixed probabilities determined by the true values, never reaching determinism. Preferences have no such anchor: they are free to diverge to push one action's probability toward one, or to settle at whatever interior mixture is optimal.

The eligibility vector in closed form

Every algorithm below reduces to one vector, the eligibility vector$\nabla \ln \pi (a\mid s,\mathbf{\theta })$. For the linear-softmax parameterization it has an exact, cheap form worth deriving once. Start from the log of the softmax,

and differentiate. The first term contributes $\nabla h(s,a,\mathbf{\theta })$; the log-sum-exp term contributes a probability-weighted average of the preference gradients:

With linear preferences $h={\mathbf{\theta }}^{\top }\mathbf{x}(s,a)$ we have $\nabla h(s,a)=\mathbf{x}(s,a)$, and the eligibility vector collapses to the feature of the taken action minus the expected feature under the current policy:

The interpretation is geometric: raising $\pi (a\mid s)$ means pushing $\mathbf{\theta }$ toward the taken action's feature and away from the average feature. Actions that already have high probability contribute heavily to the average, so the update naturally discounts them — the same self-correction that the $1/\pi$ division supplied in the REINFORCE derivation.

A worked increment. Take a two-action state with features $\mathbf{x}(s,\text{right})=[1,0{]}^{\top }$ and $\mathbf{x}(s,\text{left})=[0,1{]}^{\top }$, and current parameters $\mathbf{\theta }=[0.4,0.0{]}^{\top }$. The preferences are $h(\text{right})=0.4$ and $h(\text{left})=0$, so $\pi (\text{right})=e^{0.4}/(e^{0.4}+e^0)=1.4918/2.4918=0.599$ and $\pi (\text{left})=0.401$. The averaged feature is ${\bar{\mathbf{x}}}_{\pi }=0.599[1,0{]}^{\top }+0.401[0,1{]}^{\top }=[0.599,0.401{]}^{\top }$. If the agent takes right, the eligibility vector is $[1,0{]}^{\top }-[0.599,0.401{]}^{\top }=[0.401,-0.401{]}^{\top }$; if it takes left it is $[0,1{]}^{\top }-[0.599,0.401{]}^{\top }=[-0.599,0.599{]}^{\top }$. A positive return after right therefore raises ${\theta }_1$ and lowers ${\theta }_2$, widening the gap toward right — exactly the direction that increases $\pi (\text{right})$ on the next visit.

The policy gradient theorem

To do gradient ascent we need $\nabla J(\mathbf{\theta })$. In the episodic case, assuming every episode starts in a fixed state $s_0$, performance is the value of that start state:

where $v_{{\pi }_{\mathbf{\theta }}}$ is the true value function for the policy ${\pi }_{\mathbf{\theta }}$. The difficulty is that performance depends on $\mathbf{\theta }$ through two channels: the action probabilities (easy to differentiate, since they are the parameterized policy) and the distribution of states in which those actions are taken (a function of the environment's dynamics, and typically unknown). Nudging $\mathbf{\theta }$ changes which states are visited, and we have no model of how.

The policy gradient theorem resolves this. It gives an exact expression for $\nabla J$ that involves the derivative of the policy but not the derivative of the state distribution:

Read it as a weighted sum: over states in the proportion the policy actually visits them ($\mu (s)$), and over actions weighted by how good they are ($q_{\pi }(s,a)$), push each action's probability up in the direction $\nabla \pi (a\mid s,\mathbf{\theta })$. The unknown $\nabla \mu$ does not appear; that is the value of the theorem.

Derivation sketch

The gradient of the state-value function unrolls into the theorem with nothing more than the product rule and the Bellman equation. Leaving the dependence on $\mathbf{\theta }$ implicit, start from $v_{\pi }(s)={\sum }_a\pi (a\mid s)q_{\pi }(s,a)$:

The first term is the direct effect through the action probabilities; the second term expands $q_{\pi }$ through the Bellman equation, exposing $\nabla v_{\pi }(s^{\prime })$ at the successor states. Substituting that expansion back into itself — unrolling — replaces $\nabla v_{\pi }(s^{\prime })$ by the same pattern one step further out, and again, and again. After repeated unrolling the recursion collapses into a sum over all states $x$ weighted by the probability of reaching $x$ from $s_0$ in any number of steps:

where $\mathrm{Pr}(s\to x,k,\pi )$ is the probability of transitioning from $s$ to $x$ in exactly $k$ steps under $\pi$. Setting $s=s_0$ and collecting the multi-step reaching probabilities into the on-policy distribution $\mu$ (a normalized count of how often each state is visited per episode) turns the double sum over $k$ into $\mu (s)$, leaving

The reaching-probability sum made concrete

The intermediate identity the proof reaches before normalizing,

is worth running on real numbers, because the $\eta (x)$ — the expected number of times $x$ is visited per episode — is the quantity that later normalizes into $\mu$.⁵ Take the smallest chain that still has two states and a choice at each: an episodic MDP with a start state $A=s_0$, one intermediate state $B$, and a terminal state, undiscounted ($\gamma =1$). Each state offers two actions, up and dn, and every action from $A$ lands in $B$ while every action from $B$ terminates, so an episode is exactly two steps, $A\to B\to \text{terminal}$. The rewards are

Parameterize each state with a single preference gap: at state $s$ set $h(s,\text{up})={\theta }_s$ and $h(s,\text{dn})=0$, so $\pi (\text{up}\mid s)=\sigma ({\theta }_s)$ is logistic and the two policy gradients with respect to ${\theta }_s$ are $\nabla \pi (\text{up}\mid s)=\pi (\text{up})\pi (\text{dn})$ and $\nabla \pi (\text{dn}\mid s)=-\pi (\text{up})\pi (\text{dn})$. Fix the current policy at $\pi (\text{up}\mid A)=0.6$ (so ${\theta }_A=\ln 1.5$) and $\pi (\text{up}\mid B)=0.5$ (so ${\theta }_B=0$).

Step 1 — action values, working back from the terminal state. At $B$ each action ends the episode, so $q_{\pi }(B,\text{up})=2$ and $q_{\pi }(B,\text{dn})=0$, giving $v_{\pi }(B)=0.5(2)+0.5(0)=1$. At $A$ each action pays its immediate reward and then continues from $B$: $q_{\pi }(A,\text{up})=1+v_{\pi }(B)=2$ and $q_{\pi }(A,\text{dn})=-1+v_{\pi }(B)=0$, so $v_{\pi }(A)=0.6(2)+0.4(0)=1.2$. That $1.2$ is the performance $J(\mathbf{\theta })=v_{\pi }(s_0)$ we are about to differentiate.

Step 2 — reaching probabilities. Every episode visits $A$ once and $B$ once, so the multi-step reaching sums collapse to $\eta (A)=1$ and $\eta (B)=1$ (and $\mu (A)=\mu (B)=0.5$ after normalizing). The chain is short enough that no infinite series is needed — the sum over $k$ is a single term at each state.

Step 3 — the inner per-state gradient sum. Because ${\theta }_A$ affects only the policy at $A$ and ${\theta }_B$ only the policy at $B$, each state contributes one component of $\nabla J$. At $A$, with $\pi (\text{up})\pi (\text{dn})=0.6(0.4)=0.24$:

At $B$, with $\pi (\text{up})\pi (\text{dn})=0.5(0.5)=0.25$:

Step 4 — assemble. Weighting each by its reaching count $\eta$ gives the two components of the gradient:

Both are positive, and both point in the expected direction: raising ${\theta }_A$ raises $\pi (\text{up}\mid A)$, and up is the better action at $A$ ($q=2$ versus $0$); the same holds at $B$. A gradient-ascent step ${\theta }_s\leftarrow {\theta }_s+\alpha \partial J/\partial {\theta }_s$ nudges both states toward up, which is optimal here — the greedy policy takes up everywhere for $J=v_{\ast }(A)=1+2=3$. Nowhere did the derivative of the state distribution appear: the $\eta (x)$ are plain visit counts, as the theorem states.

REINFORCE: Monte Carlo policy gradient

The theorem gives an expression proportional to the gradient; a learning algorithm still needs a way to sample something whose expectation equals that expression. The right-hand side is a sum over states weighted by how often $\pi$ visits them, so if we simply follow $\pi$, the states we encounter arrive in exactly those proportions. The state sum becomes an expectation under the policy:

The inner sum over actions is not yet an expectation under $\pi$, because its terms are not weighted by $\pi (a\mid S_t)$. Multiply and divide each term by $\pi (a\mid S_t,\mathbf{\theta })$, then replace the sum over $a$ by the single sampled action $A_t\sim \pi$:

where the last line uses ${\mathbb{E}}_{\pi }[G_t\mid S_t,A_t]=q_{\pi }(S_t,A_t)$: the sampled return $G_t$ is an unbiased sample of the action value. This is a quantity we can compute on every time step from experience alone, and its expectation is the gradient. Instantiating the gradient-ascent step gives the REINFORCE update:⁶

The fraction is compactly the gradient of the log-probability, by the identity $\nabla \ln x=\nabla x/x$:

This vector is the eligibility vector — the only place the policy parameterization enters the algorithm. It is the direction in parameter space that most increases the probability of repeating $A_t$ on future visits to $S_t$.

Each increment is the product of a return $G_t$ and the eligibility vector. The vector points where the parameters must move to make $A_t$ more likely; scaling by $G_t$ pushes hardest in the directions that favored high-return actions. Dividing by $\pi (A_t\mid S_t)$ inside the eligibility vector corrects for the fact that frequently selected actions accrue updates more often — without it, common actions would gain an unearned advantage.

Because $G_t$ is the complete return to the end of the episode, REINFORCE is a Monte Carlo method: every update waits for the episode to finish, and the algorithm is only well defined for episodic tasks. As a stochastic gradient method it has good convergence properties — the expected update points along the true gradient, so it improves for small enough $\alpha$ and converges to a local optimum — but like all Monte Carlo methods it can suffer high variance and therefore learn slowly. The factor ${\gamma }^t$ in the boxed update handles discounting in the general case; with $\gamma =1$ it disappears.

REINFORCE with a baseline

The variance can be reduced without introducing bias. The policy gradient theorem generalizes to include a comparison of each action value against an arbitrary baseline $b(s)$:⁷

The baseline can be any function — even a random variable — as long as it does not depend on the action $a$. Subtracting it leaves the gradient unchanged, because the extra term integrates to zero:

So the baseline introduces no bias. What it can change is variance. Carrying it through the same derivation gives a baselined REINFORCE update:

The natural choice is an estimate of the state value, $b(s)=\hat{v}(s,\mathbf{w})$, learned by any of the value-approximation methods with its own weight vector $\mathbf{w}\in {\mathbb{R}}^d$. The reason it cuts variance is a matter of scale: in a state where all actions are good, the raw returns $G_t$ are all large, so every update is large and most of the movement cancels noisily. Subtracting $\hat{v}(S_t)$ recenters the returns so the update responds to whether an action did better or worse than the state's average, not to the absolute level of return. Where actions differ sharply the baseline is high; where they are uniform it is low — a single number could not track that, but a state-dependent baseline can.

Note that the state-value weights $\mathbf{w}$ are used only as a baseline here — to recenter the return for the state whose estimate is being updated. They are not used to estimate the values of later states. That distinction matters for the next step.