REINFORCE

REINFORCE is a Monte Carlo policy gradient algorithm introduced by Ronald Williams in 1992. It runs the current policy to the end of an episode, computes the return that followed each action, and nudges the policy to make each action more likely in proportion to that return.

The update rule

For an episode $s_0,a_0,r_1,\dots ,s_{T-1},a_{T-1},r_T$, REINFORCE updates the policy parameters as

where $\alpha$ is the step size, $G_t={\sum }_{k=t+1}^T{\gamma }^{k-t-1}{r}_k$ is the return from step $t$, and $b(s_t)$ is an optional baseline (Williams called the combination a reinforcement comparison). With $b=0$ this is plain REINFORCE. The extra ${\gamma }^t$ factor comes from the theorem for the discounted start-state objective and is often dropped in practice. The sampled return $G_t$ is an unbiased estimate of $Q^{\pi }(s_t,a_t)$, so the update is an unbiased estimate of the true gradient.

The algorithm in four steps

• Sample a full episode with the current policy.
• Compute $G_t$ for every step by summing rewards backwards.
• Accumulate $(G_t-b){\nabla }_{\theta }\log {\pi }_{\theta }(a_t\mid s_t)$ over the episode.
• Take one gradient step, discard the episode, repeat. The data is used once because the gradient must be estimated under the current policy (it is on-policy).

Worked example

A three-step episode yields rewards $0,0,1$ with $\gamma =1$. Every step has $G_t=1$, so all three actions get the same push, including any that were irrelevant. If instead the rewards were $1,0,0$, the returns would be $G_0=1$ and $G_1=G_2=0$, so only the first action is reinforced. REINFORCE credits each action with what happened after it, never before, which is its built-in answer to credit assignment.

Limitations

Because $G_t$ sums many random rewards, the gradient estimate has high variance, and learning can be slow or unstable. Adding a learned baseline, then replacing $G_t$ with a critic's estimate, leads step by step to actor-critic methods.

Why it matters

REINFORCE is short enough to implement in a dozen lines and is the cleanest way to see how policy gradients work. It has also come back into use for language models: when a whole response receives a single reward, REINFORCE with a baseline computed from other samples for the same prompt is a strong, simple alternative to PPO, and GRPO is close to this idea.

Related terms

• Policy gradient
• Baseline (policy gradient)
• Monte Carlo methods (RL)
• Actor-critic
• GRPO (Group Relative Policy Optimization)
• Credit assignment

Sources

1. Ronald J. Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning, 1992. doi.org
2. Richard S. Sutton, Andrew G. Barto. Reinforcement Learning: An Introduction (2nd edition), 2018. incompleteideas.net