---
title: Policy Gradient Methods
module: Approximate Solution Methods
moduleNumber: 3
lessonNumber: 9
order: 309
summary: >
  Every method so far learned values and read a policy off them. Policy gradient
  methods drop the intermediary: parameterize the policy directly and climb the
  performance gradient. We build the softmax-in-preferences parameterization,
  prove the policy gradient theorem that makes the gradient computable without the
  unknown state distribution, and derive REINFORCE and its variance-cutting
  state-value baseline — the launch point for the bootstrapping actor-critic that
  follows.
topics: [Approximation]
sources:
  - book: Sutton & Barto
    ref: "Ch. 13 — Policy Gradient Methods; §13.1 Policy Approximation and its Advantages; §13.2 The Policy Gradient Theorem"
  - book: Sutton & Barto
    ref: "§13.3 REINFORCE; §13.4 REINFORCE with Baseline"
---

Everything up to here has learned a **value** and read a policy off it. Even the
[approximate control](/reinforcement-learning/approximation/on-policy-control)
methods, which never tabulate anything, still estimate $\hat{q}(s,a,\mathbf{w})$
and then act $\varepsilon$-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, \boldsymbol{\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.[^sb-intro] The learner holds a parameter vector
$\boldsymbol{\theta} \in \mathbb{R}^{d'}$, defines a scalar **performance measure**
$J(\boldsymbol{\theta})$, and moves $\boldsymbol{\theta}$ up the gradient of that
performance:

$$
\boldsymbol{\theta}_{t+1} \;=\; \boldsymbol{\theta}_t + \alpha\,\widehat{\nabla J(\boldsymbol{\theta}_t)},
$$

where $\widehat{\nabla J(\boldsymbol{\theta}_t)}$ is a stochastic estimate whose
expectation approximates $\nabla J(\boldsymbol{\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,
\boldsymbol{\theta})$ be **differentiable** in $\boldsymbol{\theta}$ — the gradient
vector $\nabla \pi(a \mid s, \boldsymbol{\theta})$ must exist and be finite for
every state and action.[^sb-approx] To preserve exploration we also require the
policy to stay stochastic: $\pi(a \mid s, \boldsymbol{\theta}) \in (0,1)$ rather
than committing hard to one action.

$$
% caption: Value-based control (top) learns $\hat{q}(s,a,\mathbf{w})$ and acts
% $\varepsilon$-greedily off it; policy-gradient methods (bottom) learn
% $\pi(a\mid s,\boldsymbol{\theta})$ and sample the action straight from it.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=26mm, minimum height=11mm, align=center},
  act/.style={draw, minimum width=20mm, minimum height=11mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  % value-based (top row)
  \node[box] (q)  at (0,1.7)  {values\\q(s,a;w)};
  \node[box] (eg) at (4.2,1.7) {argmax +\\eps-greedy};
  \node[act] (a1) at (8.2,1.7) {action};
  \draw[->, thick] (q) -- (eg);
  \draw[->, thick] (eg) -- (a1);
  \node[anchor=east, text=black] at (-1.6,1.7) {value-based};
  % policy-gradient (bottom row)
  \node[box, draw=acc, text=acc, thick] (pi) at (0,0) {policy\\pi(a:s;theta)};
  \node[act] (a2) at (8.2,0) {action};
  \draw[->, acc, thick] (pi) -- (a2) node[midway, above, font=\scriptsize, text=acc] {sample};
  \node[anchor=east, text=acc] at (-1.6,0) {policy-gradient};
\end{tikzpicture}
$$

## Why parameterize the policy directly

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

**Stochastic optima are reachable.** With $\varepsilon$-greedy action selection
over values, the policy is always $1-\varepsilon$ 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.[^sb-example]
A softmax over action preferences can represent any such mixture; a value-greedy
policy cannot.

$$
% caption: The small-corridor task where states look identical to the
% approximator: performance $J(\boldsymbol{\theta}) = v_{\pi_{\boldsymbol{\theta}}}(S)$
% peaks at an interior mixing probability near 0.59, unreachable by either
% $\varepsilon$-greedy extreme.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % axes
  \draw[->, black] (0,0) -- (7.2,0) node[anchor=north east, text=black] {prob. of right action};
  \draw[->, black] (0,0) -- (0,4.0) node[anchor=south east, text=black] {J(theta)};
  % concave performance curve (peak near p=0.59, value about -11.6)
  \draw[acc, very thick]
    (0.15,0.35) .. controls (1.2,2.7) and (2.6,3.5) .. (4.0,3.55)
                .. controls (5.2,3.5) and (6.2,2.7) .. (6.9,0.4);
  % peak marker
  \fill[acc] (4.0,3.55) circle (2.2pt);
  \node[acc, anchor=south] at (4.0,3.65) {optimal stochastic policy};
  % epsilon-greedy extremes
  \fill[red] (0.15,0.35) circle (2pt);
  \node[red, anchor=west] at (0.35,0.55) {eps-greedy left};
  \fill[red] (6.9,0.4) circle (2pt);
  \node[red, anchor=east] at (6.7,0.6) {eps-greedy right};
\end{tikzpicture}
$$

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 $\varepsilon = 0.1$, an $\varepsilon$-greedy value method can
only commit to `right` with probability $1 - \varepsilon/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 $\varepsilon$-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 $\boldsymbol{\theta}$ changes. Under
$\varepsilon$-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.[^sb-pgt] 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,\boldsymbol{\theta}) \in \mathbb{R}$ for each
state-action pair and passes the preferences through an exponential softmax:

$$
\pi(a \mid s, \boldsymbol{\theta}) \;\doteq\; \frac{e^{h(s,a,\boldsymbol{\theta})}}{\sum_b e^{h(s,b,\boldsymbol{\theta})}}.
$$

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 $\boldsymbol{\theta}$ (the AlphaGo route), or a plain linear form
in features,

$$
h(s,a,\boldsymbol{\theta}) \;=\; \boldsymbol{\theta}^\top \mathbf{x}(s,a),
$$

with feature vectors $\mathbf{x}(s,a) \in \mathbb{R}^{d'}$ built by any of the
[function-approximation](/reinforcement-learning/approximation/on-policy-prediction)
recipes.

> **Definition (Softmax in action preferences).** A policy parameterization that
> sets $\pi(a \mid s, \boldsymbol{\theta}) \propto e^{h(s,a,\boldsymbol{\theta})}$
> for learned preferences $h$. Unlike a softmax over _action values_, the
> preferences are not estimates of anything — they are driven toward whatever
> produces the optimal stochastic policy, and if the optimum is deterministic they
> can grow without bound to approach it.

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, \boldsymbol{\theta})$. For the linear-softmax
parameterization it has an exact, cheap form worth deriving once. Start from the
log of the softmax,

$$
\ln \pi(a \mid s, \boldsymbol{\theta}) \;=\; h(s,a,\boldsymbol{\theta}) - \ln \sum_b e^{h(s,b,\boldsymbol{\theta})},
$$

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

$$
\nabla \ln \pi(a \mid s, \boldsymbol{\theta}) \;=\; \nabla h(s,a,\boldsymbol{\theta}) - \sum_b \pi(b \mid s, \boldsymbol{\theta})\,\nabla h(s,b,\boldsymbol{\theta}).
$$

With linear preferences $h = \boldsymbol{\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:

$$
\nabla \ln \pi(a \mid s, \boldsymbol{\theta}) \;=\; \mathbf{x}(s,a) - \sum_b \pi(b \mid s, \boldsymbol{\theta})\,\mathbf{x}(s,b) \;=\; \mathbf{x}(s,a) - \bar{\mathbf{x}}_\pi(s).
$$

The interpretation is geometric: raising $\pi(a \mid s)$ means pushing
$\boldsymbol{\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.

$$
% caption: The softmax eligibility vector at a three-action state. It is the taken
% action's feature $\mathbf{x}(s,a)$ minus the policy-averaged feature
% $\bar{\mathbf{x}}_\pi(s)$; the resulting arrow is the parameter direction that
% most raises $\pi(a\mid s)$, pointing away from the current average.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \draw[black, ->] (-0.4,0) -- (5.0,0) node[anchor=north east] {feature dim 1};
  \draw[black, ->] (0,-0.4) -- (0,3.6) node[anchor=north west] {feature dim 2};
  % three action features
  \fill[black] (3.8,0.7) circle (2pt) node[anchor=west, black] {x(s,a1)};
  \fill[black] (1.2,2.9) circle (2pt) node[anchor=south, black] {x(s,a2)};
  \fill[black] (2.0,0.5) circle (2pt) node[anchor=north, black] {x(s,a3)};
  % averaged feature
  \fill[acc] (2.2,1.35) circle (2.4pt) node[anchor=north east, acc] {avg feature};
  % eligibility vector for a2 (taken): from avg toward x(s,a2)
  \draw[->, red, very thick] (2.2,1.35) -- (1.2,2.9);
  \node[red, anchor=west] at (2.55,2.35) {grad ln pi(a2)};
\end{tikzpicture}
$$

**A worked increment.** Take a two-action state with features
$\mathbf{x}(s, \texttt{right}) = [1,0]^\top$ and
$\mathbf{x}(s, \texttt{left}) = [0,1]^\top$, and current parameters
$\boldsymbol{\theta} = [0.4, 0.0]^\top$. The preferences are
$h(\texttt{right}) = 0.4$ and $h(\texttt{left}) = 0$, so
$\pi(\texttt{right}) = e^{0.4}/(e^{0.4}+e^{0}) = 1.4918/2.4918 = 0.599$ and
$\pi(\texttt{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(\texttt{right})$ on the next
visit.

## The policy gradient theorem

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

$$
J(\boldsymbol{\theta}) \;\doteq\; v_{\pi_{\boldsymbol{\theta}}}(s_0),
$$

where $v_{\pi_{\boldsymbol{\theta}}}$ is the true value function for the policy
$\pi_{\boldsymbol{\theta}}$. The difficulty is that performance depends on
$\boldsymbol{\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 $\boldsymbol{\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:

> **Theorem (Policy Gradient Theorem, episodic case).**
> $$
> \nabla J(\boldsymbol{\theta}) \;\propto\; \sum_s \mu(s) \sum_a q_\pi(s,a)\,\nabla \pi(a \mid s, \boldsymbol{\theta}),
> $$
> where $\mu$ is the on-policy state distribution under $\pi$. In the episodic
> case the constant of proportionality is the average length of an episode; in the
> continuing case it is $1$, so the relation is an equality.

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, \boldsymbol{\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
$\boldsymbol{\theta}$ implicit, start from $v_\pi(s) = \sum_a \pi(a \mid s)\,q_\pi(s,a)$:

$$
\begin{aligned}
\nabla v_\pi(s)
&= \nabla \Big[\textstyle\sum_a \pi(a \mid s)\,q_\pi(s,a)\Big] \\
&= \sum_a \Big[\nabla \pi(a \mid s)\,q_\pi(s,a) + \pi(a \mid s)\,\nabla q_\pi(s,a)\Big] \\
&= \sum_a \Big[\nabla \pi(a \mid s)\,q_\pi(s,a) + \pi(a \mid s)\,\nabla\!\textstyle\sum_{s'} p(s' \mid s,a)\,v_\pi(s')\Big].
\end{aligned}
$$

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')$ at
the successor states. Substituting that expansion back into itself — **unrolling**
— replaces $\nabla v_\pi(s')$ 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:

$$
\nabla v_\pi(s) \;=\; \sum_x \sum_{k=0}^{\infty} \Pr(s \to x, k, \pi)\,\sum_a \nabla \pi(a \mid x)\,q_\pi(x,a),
$$

where $\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

$$
\nabla J(\boldsymbol{\theta}) \;=\; \nabla v_\pi(s_0) \;\propto\; \sum_s \mu(s) \sum_a q_\pi(s,a)\,\nabla \pi(a \mid s, \boldsymbol{\theta}).
$$

$$
% caption: Unrolling the Bellman recursion: $\nabla v_\pi(s_0)$ expands into a
% direct term at $s_0$ plus $\nabla v_\pi$ at each successor $s'$, then each $s''$,
% repeated until the multi-step reaching probabilities collect into $\mu(s)$.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  st/.style={circle, draw, minimum size=8.5mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[st, draw=acc, text=acc, thick] (s0) at (0,0) {s0};
  \node[st] (s1) at (2.9,1.1) {s-1};
  \node[st] (s2) at (2.9,-1.1) {s-2};
  \node[st] (s3) at (6.0,1.7) {s-3};
  \node[st] (s4) at (6.0,0.5) {s-4};
  \node[st] (s5) at (6.0,-1.1) {s-5};
  \draw[->, acc, thick] (s0) to[out=35,in=180] (s1);
  \draw[->, acc, thick] (s0) to[out=-35,in=180] (s2);
  \draw[->, black] (s1) to[out=20,in=180] (s3);
  \draw[->, black] (s1) to[out=-20,in=180] (s4);
  \draw[->, black] (s2) to[out=20,in=195] (s5);
  \node[anchor=south, text=acc] at (0,0.65) {direct term};
  \node[anchor=west, text=black] at (6.7,1.1) {unroll further};
  \node[text=black, anchor=north] at (6.0,-1.95) {: : :};
\end{tikzpicture}
$$

### The reaching-probability sum made concrete

The intermediate identity the proof reaches before normalizing,

$$
\nabla v_\pi(s_0) \;=\; \sum_x \eta(x) \sum_a \nabla \pi(a \mid x)\,q_\pi(x,a),
\qquad
\eta(x) \;\doteq\; \sum_{k=0}^{\infty} \Pr(s_0 \to x, k, \pi),
$$

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$.[^sb-eta] 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

$$
\begin{aligned}
&A,\ \texttt{up} \to B:\ r = +1, &&A,\ \texttt{dn} \to B:\ r = -1, \\
&B,\ \texttt{up} \to \text{terminal}:\ r = +2, \qquad &&B,\ \texttt{dn} \to \text{terminal}:\ r = 0.
\end{aligned}
$$

Parameterize each state with a single preference gap: at state $s$ set
$h(s, \texttt{up}) = \theta_s$ and $h(s, \texttt{dn}) = 0$, so
$\pi(\texttt{up} \mid s) = \sigma(\theta_s)$ is logistic and the two policy
gradients with respect to $\theta_s$ are
$\nabla \pi(\texttt{up} \mid s) = \pi(\texttt{up})\,\pi(\texttt{dn})$ and
$\nabla \pi(\texttt{dn} \mid s) = -\pi(\texttt{up})\,\pi(\texttt{dn})$. Fix the
current policy at $\pi(\texttt{up} \mid A) = 0.6$ (so $\theta_A = \ln 1.5$) and
$\pi(\texttt{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, \texttt{up}) = 2$ and
$q_\pi(B, \texttt{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, \texttt{up}) = 1 + v_\pi(B) = 2$ and
$q_\pi(A, \texttt{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(\boldsymbol{\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(\texttt{up})\pi(\texttt{dn}) = 0.6(0.4) = 0.24$:

$$
\sum_a \nabla \pi(a \mid A)\,q_\pi(A,a) = (0.24)(2) + (-0.24)(0) = 0.48.
$$

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

$$
\sum_a \nabla \pi(a \mid B)\,q_\pi(B,a) = (0.25)(2) + (-0.25)(0) = 0.50.
$$

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

$$
\frac{\partial J}{\partial \theta_A} = \eta(A)\cdot 0.48 = 0.48,
\qquad
\frac{\partial J}{\partial \theta_B} = \eta(B)\cdot 0.50 = 0.50.
$$

Both are positive, and both point in the expected direction: raising $\theta_A$
raises $\pi(\texttt{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 \gets \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.

$$
% caption: The two-state chain of the worked unrolling. An episode runs
% $A \to B \to$ terminal in two steps. The table beneath each state lists its
% action values and the per-state gradient sum $\sum_a \nabla\pi(a\mid s)\,q_\pi(s,a)$;
% weighting each by its reaching count $\eta = 1$ gives the gradient components
% $0.48$ at $A$ and $0.50$ at $B$.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  st/.style={circle, draw, minimum size=9mm, inner sep=0pt},
  term/.style={draw, minimum width=9mm, minimum height=9mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[st, draw=acc, text=acc, thick] (A) at (0,0) {A};
  \node[st] (B) at (3.6,0) {B};
  \node[term] (T) at (7.2,0) {end};
  \draw[->, acc, thick] (A) to[bend left=22] node[midway, above, font=\scriptsize] {up: r=+1} (B);
  \draw[->, black] (A) to[bend right=22] node[midway, below, font=\scriptsize] {dn: r=-1} (B);
  \draw[->, acc, thick] (B) to[bend left=22] node[midway, above, font=\scriptsize] {up: r=+2} (T);
  \draw[->, black] (B) to[bend right=22] node[midway, below, font=\scriptsize] {dn: r=0} (T);
  % per-state summary under each node
  \node[anchor=north, align=center, font=\scriptsize] at (0,-1.15)
    {q(up)=2, q(dn)=0\\eta=1, sum=0.48};
  \node[anchor=north, align=center, font=\scriptsize] at (3.6,-1.15)
    {q(up)=2, q(dn)=0\\eta=1, sum=0.50};
  \node[anchor=north, align=center, font=\scriptsize, text=acc] at (3.6,-2.35)
    {grad J = (0.48, 0.50)};
\end{tikzpicture}
$$

## 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:

$$
\nabla J(\boldsymbol{\theta}) \;\propto\; \mathbb{E}_\pi\!\Big[\textstyle\sum_a q_\pi(S_t,a)\,\nabla \pi(a \mid S_t, \boldsymbol{\theta})\Big].
$$

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, \boldsymbol{\theta})$, then replace the sum over $a$ by the single
sampled action $A_t \sim \pi$:

$$
\begin{aligned}
\nabla J(\boldsymbol{\theta})
&\propto \mathbb{E}_\pi\!\Big[\textstyle\sum_a \pi(a \mid S_t, \boldsymbol{\theta})\,q_\pi(S_t,a)\,\frac{\nabla \pi(a \mid S_t, \boldsymbol{\theta})}{\pi(a \mid S_t, \boldsymbol{\theta})}\Big] \\
&= \mathbb{E}_\pi\!\Big[q_\pi(S_t, A_t)\,\frac{\nabla \pi(A_t \mid S_t, \boldsymbol{\theta})}{\pi(A_t \mid S_t, \boldsymbol{\theta})}\Big] \\
&= \mathbb{E}_\pi\!\Big[G_t\,\frac{\nabla \pi(A_t \mid S_t, \boldsymbol{\theta})}{\pi(A_t \mid S_t, \boldsymbol{\theta})}\Big],
\end{aligned}
$$

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:[^sb-reinforce]

$$
\boldsymbol{\theta}_{t+1} \;\doteq\; \boldsymbol{\theta}_t + \alpha\,G_t\,\frac{\nabla \pi(A_t \mid S_t, \boldsymbol{\theta}_t)}{\pi(A_t \mid S_t, \boldsymbol{\theta}_t)}.
$$

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

$$
\frac{\nabla \pi(A_t \mid S_t, \boldsymbol{\theta})}{\pi(A_t \mid S_t, \boldsymbol{\theta})} \;=\; \nabla \ln \pi(A_t \mid S_t, \boldsymbol{\theta}).
$$

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

```algorithm
caption: $\textsc{Reinforce}$ — Monte Carlo policy gradient, estimate $\pi \approx \pi_\ast$
input: a differentiable policy $\pi(a \mid s, \boldsymbol{\theta})$, step size $\alpha > 0$
$\boldsymbol{\theta} \in \mathbb{R}^{d'} \gets$ arbitrary (e.g. $\mathbf{0}$)
for each episode do
  generate an episode following $\pi$: $S_0, A_0, R_1, \ldots, S_{T-1}, A_{T-1}, R_T$
  for $t = 0, 1, \ldots, T-1$ do
    $G \gets \sum_{k=t+1}^{T} \gamma^{k-t-1} R_k$
    $\boldsymbol{\theta} \gets \boldsymbol{\theta} + \alpha\,\gamma^t\,G\, \nabla \ln \pi(A_t \mid S_t, \boldsymbol{\theta})$
```

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.

$$
% caption: REINFORCE closes a loop: run a full episode under $\pi$, compute each
% return $G_t$, and step $\boldsymbol{\theta}$ along $G_t\,\nabla\ln\pi(A_t\mid S_t,\boldsymbol{\theta})$.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=27mm, minimum height=12mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box, draw=acc, text=acc, thick] (pol) at (0,0) {policy\\pi(a:s;theta)};
  \node[box] (epi) at (4.6,0)  {run episode\\S,A,R,...};
  \node[box] (ret) at (9.0,0)  {returns\\Gt (return)};
  \node[box] (upd) at (4.6,-2.4) {update theta\\+= alpha G grad-ln-pi};
  \draw[->, acc, thick] (pol) -- (epi) node[midway, above, font=\scriptsize] {sample};
  \draw[->, thick] (epi) -- (ret);
  \draw[->, thick] (ret) |- (upd);
  \draw[->, acc, thick] (upd) -- (pol);
\end{tikzpicture}
$$

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)$:[^sb-baseline]

$$
\nabla J(\boldsymbol{\theta}) \;\propto\; \sum_s \mu(s) \sum_a \big(q_\pi(s,a) - b(s)\big)\,\nabla \pi(a \mid s, \boldsymbol{\theta}).
$$

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:

$$
\sum_a b(s)\,\nabla \pi(a \mid s, \boldsymbol{\theta}) \;=\; b(s)\,\nabla \sum_a \pi(a \mid s, \boldsymbol{\theta}) \;=\; b(s)\,\nabla 1 \;=\; 0.
$$

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

$$
\boldsymbol{\theta}_{t+1} \;\doteq\; \boldsymbol{\theta}_t + \alpha\,\big(G_t - b(S_t)\big)\,\nabla \ln \pi(A_t \mid S_t, \boldsymbol{\theta}_t).
$$

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.

$$
% caption: Without a baseline (left) all updates share the return's raw magnitude
% and mostly cancel; subtracting $\hat{v}(s,\mathbf{w})$ (right) leaves the signed
% advantage $G_t-\hat{v}(S_t)$, tightening the estimate around the true gradient.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % left: no baseline -- wide spread of update magnitudes
  \draw[black, ->] (-0.3,0) -- (3.4,0) node[anchor=north, text=black] {update size};
  \node[anchor=south, text=black] at (1.5,2.0) {no baseline};
  \foreach \x/\h in {0.2/0.5, 0.6/1.3, 1.0/0.9, 1.4/1.6, 1.8/0.7, 2.2/1.4, 2.6/1.0, 3.0/1.5}
    \draw[acc, thick] (\x,0) -- (\x,\h);
  % right: baselined -- tight around zero, signed
  \begin{scope}[xshift=5.4cm]
    \draw[black, ->] (-0.3,0) -- (3.4,0) node[anchor=north, text=black] {advantage};
    \draw[black] (1.4,-0.9) -- (1.4,1.7);
    \node[anchor=south, text=black] at (1.5,2.0) {with baseline};
    \foreach \x/\h in {0.2/0.3, 0.6/-0.4, 1.0/0.2, 1.8/-0.2, 2.2/0.35, 2.6/-0.3, 3.0/0.25}
      \draw[red, thick] (\x,0) -- (\x,\h);
    \node[anchor=north, text=black] at (1.4,-1.0) {b(s) = v-hat(s,w)};
  \end{scope}
\end{tikzpicture}
$$

```algorithm
caption: $\textsc{Reinforce-with-Baseline}$ — estimate $\pi_{\boldsymbol{\theta}} \approx \pi_\ast$
input: a differentiable policy $\pi(a \mid s, \boldsymbol{\theta})$, a differentiable $\hat v(s, \mathbf{w})$
parameters: step sizes $\alpha^{\boldsymbol{\theta}} > 0$, $\alpha^{\mathbf{w}} > 0$
$\boldsymbol{\theta}, \mathbf{w} \gets$ arbitrary (e.g. $\mathbf{0}$)
for each episode do
  generate an episode following $\pi$: $S_0, A_0, R_1, \ldots, S_{T-1}, A_{T-1}, R_T$
  for $t = 0, 1, \ldots, T-1$ do
    $G \gets \sum_{k=t+1}^{T} \gamma^{k-t-1} R_k$
    $\delta \gets G - \hat v(S_t, \mathbf{w})$
    $\mathbf{w} \gets \mathbf{w} + \alpha^{\mathbf{w}}\,\delta\, \nabla \hat v(S_t, \mathbf{w})$
    $\boldsymbol{\theta} \gets \boldsymbol{\theta} + \alpha^{\boldsymbol{\theta}}\,\gamma^t\,\delta\, \nabla \ln \pi(A_t \mid S_t, \boldsymbol{\theta})$
```

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.

[^sb-intro]: **Sutton & Barto**, _Reinforcement Learning: An Introduction_ (2nd ed.), Ch. 13 — introduction: policy gradient methods learn a parameterized policy $\pi(a \mid s, \boldsymbol{\theta})$ that selects actions without a value function, updating $\boldsymbol{\theta}$ by stochastic gradient ascent on a scalar performance measure $J(\boldsymbol{\theta})$ (13.1).
[^sb-approx]: **Sutton & Barto**, §13.1 — Policy Approximation and its Advantages: the differentiability requirement on $\pi(a \mid s, \boldsymbol{\theta})$, the softmax-in-action-preferences parameterization (13.2), linear preferences $h = \boldsymbol{\theta}^\top \mathbf{x}(s,a)$ (13.3), and why preferences (unlike a softmax over action values) can approach a deterministic policy.
[^sb-example]: **Sutton & Barto**, §13.1, Example 13.1 (Short corridor with switched actions): a task where states are indistinguishable to the approximator, the optimal policy is stochastic with $\Pr(\texttt{right}) \approx 0.59$, and both $\varepsilon$-greedy extremes are far worse — the case for representing stochastic optima.
[^sb-pgt]: **Sutton & Barto**, §13.2 — The Policy Gradient Theorem: the theoretical advantage that continuous parameterization changes action probabilities smoothly (unlike the discontinuous $\varepsilon$-greedy switch), the episodic performance measure $J(\boldsymbol{\theta}) = v_{\pi_{\boldsymbol{\theta}}}(s_0)$ (13.4), the theorem (13.5) and its first-principles proof by unrolling the Bellman recursion for $\nabla v_\pi$.
[^sb-eta]: **Sutton & Barto**, §13.2 — proof of the Policy Gradient Theorem (box, p. 325) and the on-policy-distribution box (p. 199): $\eta(x) = \sum_{k=0}^\infty \Pr(s_0 \to x, k, \pi)$ is the expected number of visits to $x$ per episode, and $\mu(s) = \eta(s)/\sum_{s'}\eta(s')$ is its normalization into the on-policy distribution; the identity $\nabla v_\pi(s_0) = \sum_x \eta(x)\sum_a \nabla\pi(a\mid x)\,q_\pi(x,a)$ is the step before normalizing to $\mu$.
[^sb-reinforce]: **Sutton & Barto**, §13.3 — REINFORCE: Monte Carlo Policy Gradient: rewriting the theorem as an expectation under $\pi$ (13.6), the sampling step that introduces $A_t \sim \pi$ and the return $G_t$, the REINFORCE update (13.8), the eligibility vector $\nabla \ln \pi(A_t \mid S_t, \boldsymbol{\theta})$, and the boxed episodic algorithm with its $\gamma^t$ factor (Williams, 1992).
[^sb-baseline]: **Sutton & Barto**, §13.4 — REINFORCE with Baseline: the generalized theorem with baseline (13.10), the zero-subtraction argument that leaves the gradient unbiased, the baselined update (13.11), the choice $b(s) = \hat{v}(s, \mathbf{w})$, and the boxed algorithm with separate step sizes $\alpha^{\boldsymbol{\theta}}$ and $\alpha^{\mathbf{w}}$.