18  Policy Gradient Methods

Core idea. Policy gradient methods optimize a parameterized policy directly. Instead of first estimating an optimal value function and then extracting a greedy policy, we choose a differentiable family \(\{\pi_\theta:\theta\in\mathbb R^d\}\) and attempt to solve

\[ \max_\theta J(\theta), \]

where \(J(\theta)\) is the expected return generated by the policy \(\pi_\theta\). The key mathematical tool is the score-function identity, which converts the derivative of an expectation over random trajectories into an expectation that can be estimated from sampled trajectories.

18.1 Learning goals

After reading this chapter, students should be able to:

1. define a parameterized stochastic policy \(\pi_\theta(a\mid s)\) and the objective \(J(\theta)\);
2. derive the score-function identity;
3. derive the REINFORCE gradient estimator;
4. state the policy gradient theorem in discounted finite MDPs;
5. explain why baselines do not bias the policy gradient;
6. distinguish full-return, reward-to-go, and advantage-based estimators;
7. implement REINFORCE for a small finite problem;
8. explain the variance problem in Monte Carlo policy gradients;
9. connect policy gradients to stochastic approximation and optimization;
10. use AI tools to check derivations, debugging steps, and modeling assumptions.

18.2 15.1 Why optimize the policy directly?

The previous chapters emphasized value-based learning. In value iteration, SARSA, and Q-learning, the algorithm learns a value function and then uses that value function to choose actions. A typical pipeline is

\[ \text{learn values} \quad\Longrightarrow\quad \text{choose a greedy or nearly greedy policy}. \]

Policy gradient methods use a different pipeline:

\[ \text{choose a differentiable policy model} \quad\Longrightarrow\quad \text{optimize expected return by gradient ascent}. \]

This direct approach is useful when:

• the action space is large or continuous;
• the optimal policy is naturally stochastic;
• the policy must be smooth in state variables;
• the value function is hard to maximize over actions;
• the objective includes constraints or regularization terms;
• we want to use modern differentiable models such as neural networks.

For MA Applied Math students, policy gradients should be read as stochastic gradient methods for a nonconvex objective. For MS Statistics students, they should be read as likelihood-ratio estimation of a derivative of an expectation.

The central mathematical difficulty is that the probability law of the trajectory depends on the parameter \(\theta\). Policy gradients differentiate through this probability law without differentiating the environment transition probabilities.

18.3 15.2 Parameterized stochastic policies

Let \(S\) be a finite state space and \(A(s)\) the finite set of feasible actions in state \(s\). A parameterized stochastic policy is a family of conditional probability distributions

\[ \pi_\theta(a\mid s), \qquad \theta\in\mathbb R^d, \]

such that

\[ \pi_\theta(a\mid s)\geq 0, \qquad \sum_{a\in A(s)}\pi_\theta(a\mid s)=1. \]

The most common finite-action choice is a softmax policy. Suppose each state-action pair has a feature vector \(\phi(s,a)\in\mathbb R^d\). Define the score

\[ z_\theta(s,a)=\theta^T\phi(s,a), \]

and set

\[ \pi_\theta(a\mid s) = \frac{\exp(z_\theta(s,a))} {\sum_{b\in A(s)}\exp(z_\theta(s,b))}. \]

This policy is differentiable in \(\theta\) and assigns positive probability to every action.

For this softmax model,

\[ \nabla_\theta \log \pi_\theta(a\mid s) = \phi(s,a)-\sum_{b\in A(s)}\pi_\theta(b\mid s)\phi(s,b). \]

This formula is important because it shows that the policy gradient update compares the feature vector of the sampled action with the policy-weighted average feature vector.

18.3.1 Interactive: Softmax policy and score vectors

A softmax policy converts action preferences into probabilities. Lower temperature makes the policy more nearly greedy; higher temperature makes it more exploratory. The score vector \(\nabla_\theta\log\pi_\theta(a\mid s)\) determines the direction in which the chosen action’s probability is increased.

18.4 15.3 Trajectories and objectives

For an episodic problem, a trajectory is

\[ \tau=(S_0,A_0,R_1,S_1,A_1,R_2,\ldots,S_T), \]

where \(T\) may be fixed or may be a stopping time. Under policy \(\pi_\theta\), the probability of a trajectory has the form

\[ p_\theta(\tau) = \rho_0(S_0) \prod_{t=0}^{T-1} \pi_\theta(A_t\mid S_t) P(S_{t+1}\mid S_t,A_t), \]

where \(\rho_0\) is the initial state distribution. The environment transition probabilities \(P(S_{t+1}\mid S_t,A_t)\) do not depend on \(\theta\).

The return of the trajectory is

\[ G(\tau) = \sum_{t=0}^{T-1}\gamma^tR_{t+1}. \]

The objective is

\[ J(\theta)=\mathbb E_{\tau\sim p_\theta}[G(\tau)] = \sum_\tau p_\theta(\tau)G(\tau). \]

For infinite-horizon discounted problems, one often uses

\[ J(\theta)=\mathbb E_{S_0\sim \rho_0,\pi_\theta} \left[\sum_{t=0}^{\infty}\gamma^tR_{t+1}\right]. \]

Both viewpoints lead to the same policy-gradient ideas.

18.5 15.4 The score-function identity

The score-function identity is a basic result from statistics. Suppose \(X\) has density or probability mass function \(p_\theta(x)\) and \(f(x)\) is a function that does not explicitly depend on \(\theta\). Define

\[ F(\theta)=\mathbb E_\theta[f(X)] = \sum_x p_\theta(x)f(x). \]

If differentiation and summation may be interchanged, then

\[ \nabla_\theta F(\theta) = \sum_x \nabla_\theta p_\theta(x)f(x). \]

Since

\[ \nabla_\theta p_\theta(x) = p_\theta(x)\nabla_\theta\log p_\theta(x), \]

we get

\[ \nabla_\theta F(\theta) = \mathbb E_\theta \left[f(X)\nabla_\theta\log p_\theta(X)\right]. \]

This is also called the likelihood-ratio identity or log-derivative trick.

Applying it to trajectories gives

\[ \nabla_\theta J(\theta) = \mathbb E_{\tau\sim p_\theta} \left[ G(\tau)\nabla_\theta\log p_\theta(\tau) \right]. \]

Because only the policy depends on \(\theta\),

\[ \log p_\theta(\tau) = \log \rho_0(S_0) + \sum_{t=0}^{T-1}\log \pi_\theta(A_t\mid S_t) + \sum_{t=0}^{T-1}\log P(S_{t+1}\mid S_t,A_t), \]

and hence

\[ \nabla_\theta\log p_\theta(\tau) = \sum_{t=0}^{T-1} \nabla_\theta\log \pi_\theta(A_t\mid S_t). \]

Therefore

\[ \nabla_\theta J(\theta) = \mathbb E_{\tau\sim p_\theta} \left[ G(\tau) \sum_{t=0}^{T-1} \nabla_\theta\log \pi_\theta(A_t\mid S_t) \right]. \]

This identity is the mathematical basis of REINFORCE.

18.5.1 Interactive: Score-function gradient estimation

The policy gradient is an expectation of a return-weighted score. The figure compares the true gradient of a simple two-action bandit with noisy score-function estimates.

18.6 15.5 REINFORCE

The basic Monte Carlo policy gradient algorithm is called REINFORCE. For each sampled episode, compute the return \(G_t\) from time \(t\) onward and update

\[ \theta \leftarrow \theta + \alpha G_t\nabla_\theta\log\pi_\theta(A_t\mid S_t). \]

More explicitly, if one episode has length \(T\), then a batch update is

\[ \theta \leftarrow \theta + \alpha \sum_{t=0}^{T-1} G_t\nabla_\theta\log\pi_\theta(A_t\mid S_t), \]

where

\[ G_t=\sum_{k=t}^{T-1}\gamma^{k-t}R_{k+1}. \]

The update has an intuitive form:

\[ \text{parameter change} = \text{learning rate} imes \text{return} imes \text{direction that increases log-probability of the sampled action}. \]

If the return is high, the update increases the probability of the sampled action. If the return is low or negative, the update decreases the probability of the sampled action.

REINFORCE for an episodic task

1. Choose a differentiable stochastic policy \(\pi_\theta(a\mid s)\).
2. Generate an episode using \(\pi_\theta\).
3. For each time \(t\), compute the reward-to-go \(G_t\).
4. Update

\[ \theta \leftarrow \theta + \alpha G_t\nabla_\theta\log\pi_\theta(A_t\mid S_t). \]

5. Repeat for many episodes.

18.7 15.6 Full return versus reward-to-go

The first trajectory-gradient formula uses the full return \(G(\tau)\) for every action in the episode:

\[ G(\tau) \sum_{t=0}^{T-1}\nabla_\theta\log\pi_\theta(A_t\mid S_t). \]

However, an action at time \(t\) cannot affect rewards that occurred before time \(t\). Therefore, one can replace the full return with the reward-to-go

\[ G_t=R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+\cdots. \]

This gives the estimator

\[ \sum_{t=0}^{T-1} G_t\nabla_\theta\log\pi_\theta(A_t\mid S_t). \]

This estimator has the same expectation under standard assumptions but usually has lower variance.

The underlying conditional-independence idea is that earlier rewards are independent of the current action score after conditioning on the earlier history. In practice, reward-to-go is one of the first variance-reduction steps used in policy gradients.

18.7.1 Interactive: Full return versus reward-to-go

The same episode can produce different gradient estimators depending on whether one assigns the full trajectory return to every action or only the future return after that action.

18.8 15.7 Baselines and variance reduction

Monte Carlo policy gradient estimators often have high variance. A key variance-reduction technique is to subtract a baseline \(b(s)\) that does not depend on the action. The update becomes

\[ \theta \leftarrow \theta + \alpha \left(G_t-b(S_t)\right) \nabla_\theta\log\pi_\theta(A_t\mid S_t). \]

Why does this not change the expected gradient? For any state \(s\),

\[ \sum_a \pi_\theta(a\mid s) \nabla_\theta\log\pi_\theta(a\mid s) = \sum_a \nabla_\theta \pi_\theta(a\mid s) = \nabla_\theta \sum_a \pi_\theta(a\mid s) = \nabla_\theta 1 =0. \]

Therefore,

\[ \mathbb E_{A\sim\pi_\theta(\cdot\mid s)} \left[b(s)\nabla_\theta\log\pi_\theta(A\mid s)\right] =0. \]

Thus subtracting \(b(s)\) changes variance but not expectation.

A common choice is

\[ b(s)=V^{\pi_\theta}(s). \]

Then

\[ G_t-b(S_t) \]

is a Monte Carlo estimate of the advantage function

\[ A^{\pi_\theta}(s,a)=Q^{\pi_\theta}(s,a)-V^{\pi_\theta}(s). \]

18.8.1 Interactive: Baselines reduce variance

A baseline does not change the expected policy-gradient direction, but it can greatly reduce the spread of gradient estimates.

18.9 15.8 The policy gradient theorem

The trajectory derivation is simple and useful, but the most important structural result is the policy gradient theorem. For a discounted MDP, define the discounted state occupancy measure

\[ d_{\rho_0}^{\pi_\theta}(s) = (1-\gamma) \sum_{t=0}^{\infty}\gamma^t \mathbb P_{\rho_0,\pi_\theta}(S_t=s). \]

This is a probability distribution over states when \(0<\gamma<1\). The policy gradient theorem states that

\[ \nabla_\theta J(\theta) = \frac{1}{1-\gamma} \sum_s d_{\rho_0}^{\pi_\theta}(s) \sum_a \nabla_\theta\pi_\theta(a\mid s) Q^{\pi_\theta}(s,a). \]

Equivalently,

\[ \nabla_\theta J(\theta) = \frac{1}{1-\gamma} \mathbb E_{S\sim d_{\rho_0}^{\pi_\theta}, A\sim\pi_\theta} \left[ \nabla_\theta\log\pi_\theta(A\mid S) Q^{\pi_\theta}(S,A) \right]. \]

This equation is fundamental. It says that the gradient can be computed by weighting the score vector at state-action pairs by the action value \(Q^{\pi_\theta}(s,a)\).

A baseline can be subtracted:

\[ \nabla_\theta J(\theta) = \frac{1}{1-\gamma} \mathbb E \left[ \nabla_\theta\log\pi_\theta(A\mid S) A^{\pi_\theta}(S,A) \right]. \]

This is the bridge from policy gradient methods to actor-critic methods in Chapter 16.

18.9.1 Sketch of the theorem

For a fixed policy, the value satisfies

\[ V^{\pi_\theta}(s) = \sum_a \pi_\theta(a\mid s)Q^{\pi_\theta}(s,a). \]

Differentiate both sides:

\[ \nabla V^{\pi_\theta}(s) = \sum_a \nabla \pi_\theta(a\mid s)Q^{\pi_\theta}(s,a) + \sum_a \pi_\theta(a\mid s)\nabla Q^{\pi_\theta}(s,a). \]

The second term propagates derivatives to future states. Repeated substitution expands it into a discounted sum over future state visitation probabilities. This produces the occupancy-weighted expression in the theorem.

The policy gradient theorem avoids explicitly differentiating the transition probabilities. This is crucial because in model-free RL the transition law is unknown.

18.10 15.9 Bandit example: exact gradient

A one-state bandit is the simplest policy-gradient problem. There is one state and two actions. Let

\[ \pi_\theta(1)=\sigma(\theta)=\frac{1}{1+\exp(-\theta)}, \qquad \pi_\theta(0)=1-\sigma(\theta). \]

Suppose action \(0\) has mean reward \(\mu_0\) and action \(1\) has mean reward \(\mu_1\). Then

\[ J(\theta) = (1-\sigma(\theta))\mu_0+\sigma(\theta)\mu_1. \]

Since

\[ \frac{d}{d\theta}\sigma(\theta)=\sigma(\theta)(1-\sigma(\theta)), \]

we get

\[ J'(\theta) = \sigma(\theta)(1-\sigma(\theta))(\mu_1-\mu_0). \]

If \(\mu_1>\mu_0\), gradient ascent increases \(\theta\), which increases the probability of action \(1\). If \(\mu_1<\mu_0\), it decreases \(\theta\).

18.10.1 Python example: exact bandit gradient

import numpy as np


def sigmoid(x):
    return 1.0 / (1.0 + np.exp(-x))

mu0 = 0.2
mu1 = 1.1

def J(theta):
    p = sigmoid(theta)
    return (1 - p) * mu0 + p * mu1

def grad_J(theta):
    p = sigmoid(theta)
    return p * (1 - p) * (mu1 - mu0)

for theta in [-3, -1, 0, 1, 3]:
    print(theta, J(theta), grad_J(theta))

-3 0.24268328585981014 0.04065899375782093
-1 0.4420472792329956 0.1769507399173337
0 0.65 0.22500000000000003
1 0.8579527207670045 0.1769507399173337
3 1.0573167141401902 0.040658993757820804

This example makes clear that the policy-gradient objective may saturate: when \(\theta\) is very large or very negative, the policy becomes nearly deterministic and the gradient becomes small.

18.11 15.10 Python example: REINFORCE for a two-action bandit

The following code estimates the same gradient from sampled actions and rewards.

import numpy as np

rng = np.random.default_rng(7243)

mu = np.array([0.2, 1.1])
sigma = np.array([0.5, 0.5])

def sigmoid(theta):
    return 1.0 / (1.0 + np.exp(-theta))

def sample_action(theta):
    p1 = sigmoid(theta)
    return int(rng.random() < p1)

def grad_log_policy(theta, action):
    p1 = sigmoid(theta)
    # derivative of log pi(a) for Bernoulli policy
    return action - p1

theta = -2.0
alpha = 0.03
history = []

for k in range(4000):
    action = sample_action(theta)
    reward = rng.normal(mu[action], sigma[action])
    theta += alpha * reward * grad_log_policy(theta, action)
    if k % 100 == 0:
        history.append((k, theta, sigmoid(theta)))

print("final theta:", theta)
print("final probability of action 1:", sigmoid(theta))
print("last five records:")
for row in history[-5:]:
    print(row)

final theta: 4.538051705612645
final probability of action 1: 0.9894189344988508
last five records:
(3500, 4.335587019672742, 0.9870750563348626)
(3600, 4.361727822273363, 0.9874043463584794)
(3700, 4.402502151786762, 0.9879015075697716)
(3800, 4.4614943555053985, 0.9885866701014021)
(3900, 4.500189435728547, 0.9890151156308744)

The stochastic update is noisy, but it tends to increase the probability of the better action.

18.11.1 Interactive: REINFORCE on a bandit

The plot shows several noisy REINFORCE learning paths for a two-action bandit. Even in this simple setting, the gradient estimate is random because both the action and the reward are random.

18.12 15.11 Reward-to-go REINFORCE in a small episodic MDP

Now consider a finite episodic problem with states \(0,1,2\) and terminal state \(3\). The policy is softmax over two actions. A trajectory produces rewards along the way. A REINFORCE implementation has three ingredients:

1. a function for sampling actions from \(\pi_\theta\);
2. a function for computing \(\nabla_\theta\log\pi_\theta(A_t\mid S_t)\);
3. a backward pass for computing reward-to-go values \(G_t\).

The following compact example uses tabular preferences \(\theta_{s,a}\).

import numpy as np

rng = np.random.default_rng(5110)

n_states = 3
n_actions = 2
terminal = 3
gamma = 0.95

# next_state[s, a] and reward[s, a]
next_state = np.array([
    [1, 2],
    [0, 3],
    [3, 1]
])
reward = np.array([
    [0.0, 0.2],
    [0.0, 1.0],
    [0.6, 0.0]
])

def softmax(x):
    z = x - np.max(x)
    e = np.exp(z)
    return e / e.sum()

def sample_episode(theta, max_steps=30):
    s = 0
    episode = []
    for _ in range(max_steps):
        probs = softmax(theta[s])
        a = rng.choice(n_actions, p=probs)
        r = reward[s, a]
        sp = next_state[s, a]
        episode.append((s, a, r))
        if sp == terminal:
            break
        s = sp
    return episode

def returns_from_episode(episode, gamma):
    G = 0.0
    returns = []
    for (_, _, r) in reversed(episode):
        G = r + gamma * G
        returns.append(G)
    return list(reversed(returns))

def reinforce_update(theta, episode, returns, alpha):
    for (s, a, _), G in zip(episode, returns):
        probs = softmax(theta[s])
        grad = -probs
        grad[a] += 1.0
        theta[s] += alpha * G * grad
    return theta

theta = np.zeros((n_states, n_actions))
alpha = 0.05

for episode_index in range(2000):
    ep = sample_episode(theta)
    Gs = returns_from_episode(ep, gamma)
    theta = reinforce_update(theta, ep, Gs, alpha)

policy = np.vstack([softmax(theta[s]) for s in range(n_states)])
print(np.round(policy, 3))

[[0.011 0.989]
 [0.822 0.178]
 [0.01  0.99 ]]

This is the tabular ancestor of neural policy-gradient methods. Replacing the table \(\theta_{s,a}\) by a neural network changes the function class, but the mathematical score-function structure remains the same.

18.13 15.12 Standardizing returns

In implementations, one often standardizes sampled returns within a batch:

\[ \widehat G_t^{\text{std}} = \frac{G_t-\bar G}{s_G+\varepsilon}. \]

This does not produce the same clean unbiasedness statement as subtracting a state-dependent baseline independent of action, because \(\bar G\) and \(s_G\) are computed from the same batch. Nevertheless, standardization is often used as a practical variance-control technique.

For a mathematical textbook, it is important to separate three ideas:

• subtracting an action-independent baseline preserves the expected gradient;
• reward-to-go removes irrelevant past rewards and often reduces variance;
• batch standardization is a practical numerical heuristic.

18.14 15.13 Stochastic approximation viewpoint

A policy-gradient update can be written as

\[ \theta_{k+1} = \theta_k+ \alpha_k\widehat g_k, \]

where

\[ \mathbb E[\widehat g_k\mid\theta_k] = \nabla J(\theta_k) \]

for an ideal unbiased estimator. Thus

\[ \theta_{k+1} = \theta_k+ \alpha_k \left[\nabla J(\theta_k)+M_{k+1}\right], \]

where \(M_{k+1}\) is martingale-difference noise.

The associated limiting ODE is

\[ \dot\theta=\nabla J(\theta). \]

Unlike many tabular prediction problems, \(J(\theta)\) is generally nonconvex. Therefore convergence theory usually aims for stationarity rather than global optimality:

\[ \nabla J(\theta)=0. \]

Policy gradient methods are stochastic approximation algorithms for nonconvex expected-return objectives.

18.15 15.14 Natural policy gradient

The ordinary Euclidean gradient depends on the parameterization of the policy. A small Euclidean step in \(\theta\) can produce a large change in the policy distribution, or a large Euclidean step can produce a small distributional change. Natural gradients address this by measuring policy changes using information geometry.

The Fisher information matrix for the policy is

\[ F(\theta) = \mathbb E \left[ \nabla_\theta\log\pi_\theta(A\mid S) \nabla_\theta\log\pi_\theta(A\mid S)^T \right], \]

where the expectation is over states and actions generated by the current policy. The natural-gradient direction is

\[ F(\theta)^{-1}\nabla J(\theta). \]

A natural policy-gradient update is

\[ \theta_{k+1} = \theta_k+ \alpha F(\theta_k)^{-1}\nabla J(\theta_k). \]

One interpretation is that natural gradient ascent approximately solves

\[ \max_{\Delta\theta} \nabla J(\theta)^T\Delta\theta \quad\text{subject to}\quad \Delta\theta^TF(\theta)\Delta\theta\leq \varepsilon. \]

Thus the step is chosen to improve return while controlling the local information-geometric change in the policy.

18.15.1 Interactive: Euclidean gradient versus natural gradient

The natural-gradient direction rescales the ordinary gradient by local policy geometry. In elongated geometry, the natural direction can point very differently from the Euclidean gradient.

18.16 15.15 Relation to actor-critic methods

REINFORCE estimates policy gradients using complete Monte Carlo returns. This can be unbiased but high variance. Actor-critic methods reduce variance by learning a value function and using it inside the policy update.

The actor is the policy \(\pi_\theta\). The critic estimates one of the following:

\[ V^{\pi_\theta}(s), \qquad Q^{\pi_\theta}(s,a), \qquad A^{\pi_\theta}(s,a). \]

A common actor update is

\[ \theta \leftarrow \theta + \alpha \widehat A_t \nabla_\theta\log\pi_\theta(A_t\mid S_t), \]

where \(\widehat A_t\) is an estimated advantage. Chapter 16 develops this idea systematically.

18.17 15.16 Common implementation mistakes

Policy-gradient code is compact, but several mistakes are common.

Policy-gradient implementation checklist

1. Are actions sampled from the current policy, not from a stale policy unless importance weights are used?
2. Is the log-probability of the sampled action used, not the probability itself?
3. Are reward-to-go values computed in the correct temporal order?
4. Is the baseline independent of the action at the current state?
5. Is gradient ascent being used? Many optimizers are written for minimizing losses, so the implemented loss is often \(-G_t\log\pi_\theta(A_t\mid S_t)\).
6. Are probabilities clipped or logits stabilized to avoid numerical underflow?
7. Are episodes long enough to capture delayed rewards?
8. Are random seeds and evaluation episodes separated from training episodes?

18.18 15.17 AI-assisted learning components

AI tools can be helpful for policy-gradient learning, but they should be used as mathematical assistants, not as replacements for derivation.

AI prompt: Derivation audit

Ask an AI assistant:

Starting from \(J(\theta)=\sum_\tau p_\theta(\tau)G(\tau)\), derive the REINFORCE gradient. Explicitly identify where the environment transition terms disappear from the gradient. Then state the assumptions under which the interchange of gradient and summation is valid.

Check whether the response correctly uses \(\nabla p=p\nabla\log p\) and whether it avoids differentiating \(P(s'\mid s,a)\).

AI prompt: Baseline proof

Ask:

Prove that subtracting a baseline \(b(s)\) independent of the action does not change the expected policy gradient. Then give an example of a baseline that would bias the gradient.

A correct answer should show that \(\sum_a\nabla_\theta\pi_\theta(a\mid s)=0\).

AI prompt: Code review

Give an AI assistant your REINFORCE implementation and ask:

Check this code for policy-gradient sign errors, incorrect reward-to-go computation, misuse of probabilities instead of log-probabilities, and accidental gradient flow through sampled returns.

Then verify the comments by running small numerical tests.

18.19 15.18 Summary

Policy gradient methods optimize policies directly by differentiating expected return. The main chain of ideas is

\[ J(\theta)=\mathbb E_{\tau\sim p_\theta}[G(\tau)] \quad\Longrightarrow\quad \nabla J(\theta)= \mathbb E \left[ G(\tau)\nabla\log p_\theta(\tau) \right] \quad\Longrightarrow\quad \nabla\log p_\theta(\tau)= \sum_t\nabla\log\pi_\theta(A_t\mid S_t). \]

The resulting algorithms are easy to write but statistically noisy. Reward-to-go estimators, baselines, advantage functions, and natural gradients are all methods for improving the quality and stability of the basic gradient update.

The next chapter studies actor-critic methods, where a learned value function is used to construct lower-variance policy-gradient updates.

18.20 Exercises

18.20.1 Conceptual exercises

1. Explain why policy-gradient methods usually require stochastic policies during training.
2. Explain why the transition probabilities \(P(s'\mid s,a)\) do not appear in \(\nabla_\theta\log p_\theta(\tau)\) when the environment does not depend on \(\theta\).
3. Compare value-based control and policy-gradient control.
4. Explain the difference between full-return and reward-to-go estimators.
5. Explain why policy gradients can be high variance even when they are unbiased.
6. Explain why subtracting \(V^\pi(s)\) leads naturally to the advantage function.

18.20.2 Mathematical exercises

1. Derive the softmax identity

\[ \nabla_\theta \log \pi_\theta(a\mid s) = \phi(s,a)-\sum_b\pi_\theta(b\mid s)\phi(s,b). \]

2. For a two-action bandit with Bernoulli policy \(\pi_\theta(1)=\sigma(\theta)\), derive \(J'(\theta)\) explicitly.
3. Prove that an action-independent baseline does not change the expected policy gradient.
4. Show that the reward-to-go estimator removes terms involving rewards before time \(t\) without changing the expected gradient.
5. Derive the policy gradient theorem from the Bellman equation for \(V^\pi\).
6. For a softmax policy, compute the Fisher information matrix in a one-state, three-action bandit.
7. Show that the natural-gradient direction solves a local constrained linear optimization problem with a quadratic Fisher constraint.

18.20.3 Computational exercises

1. Implement REINFORCE for the two-action bandit example and compare the empirical learning curve for several learning rates.
2. Modify the small episodic MDP example by adding a baseline equal to the average return. Compare the variance of gradient estimates.
3. Implement reward-to-go and full-return REINFORCE. Compare their empirical variance on the same random episodes.
4. Use finite differences to check the policy-gradient estimate in a small tabular MDP where exact enumeration is possible.
5. Implement entropy-regularized REINFORCE by adding an entropy bonus to the objective. Study how the learned policy changes.
6. Implement a natural-gradient update for a one-state softmax bandit and compare it with ordinary gradient ascent.

18.20.4 AI-assisted exercises

1. Ask an AI assistant to derive REINFORCE. Identify any missing assumptions or unjustified steps.
2. Ask an AI assistant to review your REINFORCE code. Then create tests that confirm or reject its suggestions.
3. Ask an AI assistant to explain the difference between \(Q^\pi\), \(V^\pi\), and \(A^\pi\) in the policy-gradient theorem. Rewrite the explanation in your own mathematical notation.
4. Ask an AI assistant to propose a baseline for a small MDP. Determine whether the proposed baseline is action-independent and whether it preserves unbiasedness.

18.21 Notes for instructors

This chapter is a natural bridge between statistical estimation and modern deep RL. For MA Applied Math students, emphasize gradients of expectations, stochastic approximation, and information geometry. For MS Statistics students, emphasize likelihood-ratio estimation, variance reduction, baselines, and Monte Carlo uncertainty.

A good lecture sequence is:

1. begin with the two-action bandit;
2. derive the score-function identity;
3. move from random variables to trajectories;
4. introduce reward-to-go and baselines;
5. state the policy gradient theorem;
6. end with REINFORCE code and a discussion of variance.

The most important conceptual warning is that policy-gradient algorithms optimize a nonconvex objective and do not automatically guarantee global optimality. Their strength is not convexity but differentiability, scalability, and compatibility with flexible policy classes.

18.22 References

The REINFORCE algorithm was introduced by Williams (williams1992simple?). Standard textbook treatments appear in Sutton and Barto (sutton2018reinforcement?), Szepesvari (szepesvari2010algorithms?), and Bertsekas and Tsitsiklis (bertsekas1996neuro?). Actor-critic and natural-gradient ideas are developed further in Konda and Tsitsiklis (konda2000actor?).