REINFORCE: The Monte-Carlo Policy Gradient

From theorem to algorithm

REINFORCE is the most direct way to use the policy gradient theorem. It is a Monte-Carlo method: run the current policy to the end of an episode, then use the actual returns you observed as the weights in the gradient. No model, no bootstrapping, just sampled trajectories.

1. Sample a full episode by running the current policy: s0, a0, r1, s1, a1, r2, …
2. For each timestep t, compute the return Gt (the discounted sum of rewards from t onward).
3. Accumulate the gradient Σt Gt · ∇θ log π(at | st; θ) using the log-derivative trick.
4. Take an ascent step: θ ← θ + α · (that gradient). Repeat with fresh episodes.

Reward-to-go: don't blame the past

The naive version multiplies every action's log-probability by the whole-episode return. But an action taken at time t cannot possibly affect rewards that arrived before t. Keeping those past rewards in the weight only adds noise. The fix is reward-to-go: weight each action only by the return that came after it, Σ from t onward. The estimate stays unbiased and gets noticeably calmer.

Reward-to-go: each action is weighted only by the rewards that arrive at or after time t, never the rewards that came before it.

Baselines: subtract what you expected

A baseline subtracts a state-dependent reference b(st) from the return before it weights the gradient: (Gt − b(st)) · ∇θ log π. The magic, captured in the baseline-subtraction intuition, is that any baseline that does not depend on the action leaves the gradient unbiased — its expected contribution is exactly zero — yet a well-chosen baseline can slash the variance.

A baseline b(s_t) is subtracted from the return before it weights the gradient — cutting variance without adding any bias.

Why does it help? If every action in a state earns a return of +100, the raw signal pushes all of them up equally — the agent learns nothing about which was better, just that the numbers are big. Subtract the state's average return and you are left with the relative merit: which actions beat expectations. The most common choice for b(st) is an estimate of the state's value, which leads us straight to actor-critic.

Why REINFORCE alone is not enough

Even with reward-to-go and a baseline, vanilla REINFORCE suffers from high policy gradient variance. Because it waits for whole episodes, a single lucky or unlucky run can dominate an update, and sample efficiency is poor — every trajectory is used once and thrown away. In practice you will see it learn, but slowly and shakily on anything beyond toy problems.

# REINFORCE with reward-to-go and a baseline (one episode)
for t in range(T):
    G[t] = sum(gamma**(k-t) * r[k] for k in range(t, T))   # reward-to-go
advantage = G - baseline(states)                            # subtract reference
loss = -(advantage.detach() * logprob(actions, states)).sum()
loss.backward(); optimizer.step()