Chapter 202: REINFORCE

What You'll Learn

State and explain the Policy Gradient Theorem
Implement the REINFORCE algorithm from scratch
Understand the log-derivative trick and why we use log probabilities
Identify and explain the variance problem in REINFORCE
Implement baselines to reduce gradient variance

We want to improve our policy by gradient ascent. But there’s a problem: the gradient of expected return involves the environment dynamics, which we don’t know. The Policy Gradient Theorem resolves this - we can compute the gradient using only samples from our policy.

Why REINFORCE?

In value-based methods like Q-learning, we learned a value function and derived a policy from it. REINFORCE takes a fundamentally different approach: optimize the policy directly.

What makes this possible is that we can compute policy gradients without knowing how the environment works. We just need to:

Sample trajectories from our current policy
Compute returns for those trajectories
Update the policy to make high-return actions more likely

Chapter Overview

This chapter derives the Policy Gradient Theorem and introduces REINFORCE, the simplest policy gradient algorithm. We’ll also tackle its main weakness - high variance - and introduce baselines as a solution.

The Policy Gradient Theorem

The mathematical foundation for computing policy gradients

The REINFORCE Algorithm

Monte Carlo policy gradients in action

The Variance Problem

Why REINFORCE gradients are noisy and unstable

Baselines

Reducing variance without introducing bias

The Big Picture

REINFORCE follows a simple recipe:

Collect a complete episode using the current policy
Compute the return (cumulative reward) from each timestep
Update the policy to increase the probability of actions that led to high returns

📖Policy Gradient

The gradient of the expected return with respect to the policy parameters. It tells us how to adjust the policy to increase expected reward.

The Policy Gradient Theorem shows us that this gradient takes a strikingly usable form:

$\nabla_\theta J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta} \left[ \sum_{t=0}^{T} \nabla_\theta \log \pi_\theta(a_t|s_t) \cdot G_t \right]$

High-return actions get reinforced; low-return actions get suppressed. That’s the essence of REINFORCE.

Throughout this chapter our test bed is CartPole, the running example: the algorithm sections train a REINFORCE agent to balance the pole, and the variance section measures exactly how noisy those gradient estimates are on it.

Prerequisites

This chapter assumes familiarity with:

The policy gradient objective from Introduction to Policy Gradients
Stochastic policies and probability distributions over actions
Basic calculus (gradients, chain rule)

Check Your Understanding

Check your understanding

1. Why does the policy gradient theorem let us avoid knowing the environment dynamics?

It assumes the dynamics are deterministic, so they cancel outWhen we take the gradient of log P(tau|theta), the dynamics terms do not depend on theta and vanishIt approximates the dynamics with a learned modelIt only applies to environments with known transition probabilities

2. REINFORCE is a Monte Carlo method. What does that imply about its estimates?

They are biased but have low variance, like TD bootstrappingThey are unbiased but high-variance, and require complete episodes before updatingThey are both biased and high-varianceThey converge faster than bootstrapped estimates

3. Why does subtracting a baseline b(s) from the return not bias the gradient?

Because the baseline is small compared to the returnsBecause the expected score E[grad log pi(a|s)] is zero, so any action-independent term contributes nothing in expectationBecause the baseline is subtracted from both good and bad trajectories equally oftenIt does bias the gradient, but the bias is worth the variance reduction

4. Why use reward-to-go G_t instead of the full trajectory return R(tau) when weighting the gradient at step t?

Reward-to-go gives a biased but much lower-variance estimateFull returns make the algorithm off-policyActions cannot influence rewards that came before them, so removing past rewards cuts variance while keeping the estimate unbiasedReward-to-go is required for the log-derivative trick to apply

5. On CartPole, why does plain REINFORCE typically need more episodes than DQN to solve the task?

Policy networks are harder to optimize than Q-networksREINFORCE uses each trajectory once and its gradient estimates are noisy; DQN replays every transition many times from its bufferREINFORCE cannot represent the optimal CartPole policyCartPole's reward structure is incompatible with policy gradients

The Policy Gradient Theorem removes the dynamics
Gradients of expected return depend only on grad log pi—the environment terms vanish because they carry no theta.
The log-derivative trick turns gradients into expectations
Which means we can estimate them by sampling trajectories from the current policy.
REINFORCE is the direct implementation
Update theta by alpha * grad log pi(a|s) * G_t, computed from complete episodes.
Unbiased but noisy
Monte Carlo returns make the estimate unbiased and high-variance—the exact opposite trade-off from TD bootstrapping.
Baselines are free variance reduction
Subtracting any state-dependent b(s) leaves the expected gradient unchanged while shrinking its variance.

Primary Sources

Williams (1992), “Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning,” Machine Learning 8 — the original REINFORCE paper, including the baseline idea. Springer page
Sutton, McAllester, Singh & Mansour (1999), “Policy Gradient Methods for Reinforcement Learning with Function Approximation,” NeurIPS 1999 — the general policy gradient theorem, including the function-approximation case

Next ChapterActor-Critic Methods→