REINFORCE: Monte Carlo Policy Gradient

REINFORCE is a Monte Carlo policy-gradient algorithm: it optimizes a parameterized policy $\pi_\theta(a \mid s)$ directly by ascending an estimate of the gradient of expected return, where that estimate comes entirely from sampled, complete episodes. The policy is typically a differentiable function — a softmax over a linear combination of features, or a neural network — whose parameters $\theta$ are updated after each episode finishes. The starting point is the policy-gradient theorem, which states that the gradient of the expected return $J(\theta)$ with respect to $\theta$ can be written as

where $G_t$ is the return (sum of discounted future rewards) from time step $t$ onward, and the expectation is over trajectories generated by following $\pi_\theta$. REINFORCE simply replaces this expectation with a sample: run one full episode under the current policy, compute the actual returns $G_t$ observed at each time step, and use these as an unbiased Monte Carlo estimate of the gradient. Because $G_t$ requires knowledge of all rewards from time $t$ to episode end, REINFORCE is inherently an episodic algorithm — it cannot update mid-episode, only afterward. The key mechanical idea is the score function trick: $\nabla_\theta \log \pi_\theta(a\mid s)$ (the eligibility vector or score function) tells you the direction in parameter space that most increases the probability of action $a$ in state $s$. Multiplying this direction by the observed return $G_t$ means that actions followed by high returns get pushed to be more likely, and actions followed by low (or negative) returns get pushed to be less likely. No explicit value function estimation is required — the return itself, sampled directly from the environment, serves as the training signal. This is what distinguishes pure REINFORCE from Actor-Critic Methods, which replace the Monte Carlo return with a bootstrapped, learned estimate to reduce variance at the cost of some bias.

The algorithm alternates between two phases: generate a full episode using the current stochastic policy, then learn by walking backward (or forward) through the episode, accumulating gradient updates weighted by returns. Concretely, for each time step $t$ in the episode, REINFORCE computes the return $G_t = \sum_{k=t}^{T-1} \gamma^{k-t} R_{k+1}$ and performs the update

where $\alpha$ is a learning rate and $\gamma \in [0,1]$ is the discount factor. The $\gamma^t$ factor arises directly from the derivation of the policy-gradient theorem for the discounted setting (it discounts the weight of each per-step gradient contribution according to how far into the episode it occurs); many practical implementations omit it for episodic tasks with $\gamma$ close to 1, trading a small amount of theoretical correctness for simplicity and often better empirical performance. ``` Algorithm: REINFORCE (Monte Carlo Policy Gradient) Input: a differentiable policy parameterization π_θ(a | s) learning rate α > 0 discount factor γ ∈ [0, 1] Initialize policy parameters θ arbitrarily repeat forever (for each episode): generate an episode S_0, A_0, R_1, S_1, A_1, R_2, ..., S_{T-1}, A_{T-1}, R_T following π_θ(· | ·) for t = 0 to T - 1: G_t ← sum_{k=t}^{T-1} γ^(k - t) R_{k+1} // return from step t for t = 0 to T - 1: θ ← θ + α γ^t G_t ∇_θ log π_θ(A_t | S_t) until θ converges or a stopping criterion is met ``` Two implementation details matter in practice. First, the returns $G_t$ can be computed efficiently backward in a single pass, $G_{T-1} = R_T$ and $G_{t} = R_{t+1} + \gamma G_{t+1}$, avoiding the naive $O(T^2)$ recomputation. Second, the policy's score function $\nabla_\theta \log \pi_\theta(a\mid s)$ is computed automatically by backpropagation in a neural-network implementation: define the negative log-likelihood loss weighted by the return, and let automatic differentiation produce the gradient. ``` Algorithm: REINFORCE with backward return computation for each episode: collect (S_0,A_0,R_1), (S_1,A_1,R_2), ..., (S_{T-1},A_{T-1},R_T) G ← 0 grad_accum ← 0 // accumulate the parameter update for t = T - 1 down to 0: G ← R_{t+1} + γ G grad_accum ← grad_accum + γ^t G ∇_θ log π_θ(A_t | S_t) θ ← θ + α grad_accum ```

Time complexity. Generating one episode costs $O(T)$ environment interactions, where $T$ is the episode length (a random variable in general). Computing all returns $G_0, \dots, G_{T-1}$ via the backward recurrence costs $O(T)$ arithmetic operations rather than the naive $O(T^2)$ from recomputing each sum from scratch. Each parameter update costs $O(d)$ where $d = |\theta|$ is the number of policy parameters (for a neural network, this is one backward pass). Total per-episode cost is $O(T \cdot d)$, dominated by the $T$ gradient computations, each of size $d$. Over $N$ episodes, total time is $O(N \cdot T \cdot d)$.

Space complexity. REINFORCE must store the entire episode trajectory — every state, action, and reward — before it can compute any return, since $G_t$ depends on rewards arbitrarily far in the future. This costs $O(T)$ space for the trajectory plus $O(d)$ for the parameters and their gradients, giving $O(T + d)$ total. This is the price of being purely Monte Carlo: unlike temporal-difference methods, no update can happen until the episode is fully observed, so nothing can be discarded early.

Correctness — why the estimator is unbiased. The core justification is that the sample-based gradient is an unbiased estimator of the true policy gradient given by the policy-gradient theorem. Formally, for the discounted episodic objective,

Since a single episode $\tau$ is a valid sample from the trajectory distribution induced by $\pi_\theta$, the per-episode gradient computed by REINFORCE,

satisfies $\mathbb{E}_\tau[\hat{g}(\tau)] = \nabla_\theta J(\theta)$ by construction — this is exactly what the policy-gradient theorem guarantees, since $G_t$ is itself an unbiased sample of $Q^{\pi_\theta}(S_t, A_t)$ (the expected return conditioned on state and action, averaged over the remaining trajectory). Averaging $\hat{g}(\tau)$ over many independently sampled episodes and taking a step in that averaged direction is standard stochastic gradient ascent, which converges to a stationary point of $J(\theta)$ under the Robbins-Monro conditions on the learning-rate schedule ($\sum_n \alpha_n = \infty$, $\sum_n \alpha_n^2 < \infty$) and standard smoothness assumptions on $J$.

The tradeoff: unbiasedness at the cost of variance. $G_t$ is a single noisy sample of a potentially very stochastic long-horizon quantity — different episodes starting from similar states can end with wildly different total returns due to unrelated randomness later in the trajectory. This is precisely the motivation for the follow-up techniques of subtracting a state-dependent baseline (which does not bias the gradient in expectation, since $\mathbb{E}_{a\sim\pi_\theta}[\nabla_\theta \log \pi_\theta(a\mid s)] = 0$ for any fixed $b(s)$) and bootstrapping with a learned value function in actor-critic methods, both of which trade some bias or complexity for dramatically reduced variance.

Consider a two-state, two-action toy MDP: states $\{s_1, s_2\}$, actions $\{\text{left}, \text{right}\}$, deterministic transitions (left keeps you moving forward, right ends the episode), reward $0$ at every step except a terminal reward of $+1$ if you reach a goal and $-1$ if you fall off. Suppose the policy is a softmax over a single scalar parameter $\theta$ controlling the preference for "right":

Initialize $\theta = 0$, so $\pi_0(\text{right}) = \pi_0(\text{left}) = 0.5$. Take $\alpha = 0.1$, $\gamma = 1$ (no discounting, short episodes).

Episode 1. The agent samples: $s_1 \to$ right $\to$ goal, reward $+1$, episode ends ($T=1$).

• $G_0 = 1$.
• $\nabla_\theta \log \pi_\theta(\text{right}\mid s_1) = 1 - \pi_\theta(\text{right}) = 1 - 0.5 = 0.5$ (standard softmax-gradient identity for two actions).
• Update: $\theta \leftarrow 0 + 0.1 \times 1 \times 0.5 = 0.05$.

Episode 2. Now $\pi_{0.05}(\text{right}) = \frac{e^{0.05}}{e^{0.05}+1} \approx 0.5125$. Agent samples: $s_1 \to$ left $\to s_2 \to$ right $\to$ off the edge, reward $-1$ ($T=2$, rewards $R_1=0, R_2=-1$).

• $G_1 = -1$ (return from the second step onward).
• $G_0 = R_1 + \gamma G_1 = 0 + (-1) = -1$.
• At $t=0$ action was left: $\nabla_\theta \log \pi_\theta(\text{left}\mid s_1) = -\pi_\theta(\text{right}) = -0.5125$.
• At $t=1$ action was right: $\nabla_\theta \log \pi_\theta(\text{right}\mid s_2) = 1 - 0.5125 = 0.4875$.
• Updates:

$\theta \leftarrow \theta + 0.1 \times G_0 \times (-0.5125) = \theta + 0.1\times(-1)\times(-0.5125) = \theta + 0.05125$ $\theta \leftarrow \theta + 0.1 \times G_1 \times 0.4875 = \theta + 0.1\times(-1)\times 0.4875 = \theta - 0.04875$

• Net change this episode: $+0.05125 - 0.04875 = +0.0025$, so $\theta \approx 0.0525$.

Notice the qualitative behavior: the good episode (reward $+1$ for taking "right" immediately) pushed $\theta$ strongly upward, increasing the probability of "right." The bad episode (reward $-1$, ending in "right" at the second state) pushed the specific action that led to disaster ("right" at $s_2$) downward, while also pushing "left" at $s_1$ downward too — because $G_0 = -1$ was negative, and the gradient for the action not taken (right) moves in the opposite direction of the gradient for the action taken (left). This illustrates exactly how REINFORCE assigns credit (and blame) using only the total return, without any explicit value function to disentangle which step in a multi-step episode was truly responsible for the outcome — the seed of the variance problem that motivated baselines and actor-critic methods.

REINFORCE was introduced by Ronald J. Williams in a 1992 paper that formalized a whole family of "REINFORCE" algorithms — the name itself is an acronym-like mnemonic for "REward Increment = Nonnegative Factor times Offset Reinforcement times Characteristic Eligibility," capturing the update's structure: a nonnegative learning rate, times a return-based reinforcement signal, times the eligibility (score function) of the action taken.

REINFORCE's direct descendants are everywhere in modern machine learning. Reinforcement learning from human feedback (RLHF), used to align large language models, applies policy-gradient updates that are structurally identical to REINFORCE (often via Proximal Policy Optimization, which adds a trust-region correction on top of the same score-function gradient). Robotics research uses REINFORCE-style updates when reward signals are sparse and only available at episode end, such as in manipulation or locomotion tasks with binary success signals. Neural architecture search has used REINFORCE to train a controller network whose "actions" are architectural decisions and whose "reward" is the validation accuracy of the resulting network. Combinatorial optimization systems (routing, scheduling) sometimes use REINFORCE to train sequence-generating policies where the objective — tour length, makespan — is only observable after a full solution is constructed. More broadly, any system that needs to differentiate through a discrete or stochastic sampling step — where standard backpropagation cannot pass a gradient — can fall back on the score-function trick that REINFORCE popularized, making it a foundational tool far beyond classical control-style reinforcement learning. It also serves as essential scaffolding for understanding Baselines and Variance Reduction and the shift toward bootstrapped, lower-variance updates in Actor-Critic Methods.

Ask the tutor: How does subtracting a baseline from the return reduce variance without introducing bias into the REINFORCE gradient estimate?