The REINFORCE algorithm: derivation, pseudocode, numpy code and its variance problem

The REINFORCE algorithm is the simplest policy gradient method: run the current policy for a full episode, compute the return that followed each action, and nudge the policy's parameters so that actions followed by high returns become more likely. Introduced by Ronald Williams in 1992 [1], it is an unbiased Monte Carlo estimate of the policy gradient, which is why it works and also why it is slow: its gradient estimates are extremely noisy.

This page derives the update, gives pseudocode and a short numpy implementation you can run, and then measures the variance problem directly. On a three-state task, a single episode's gradient estimate points the wrong way 36% to 49% of the time, and the step-size range where plain REINFORCE learns without collapsing is narrow. Every number below comes from seeded runs we did for this article.

A task that needs a stochastic policy#

We use the short corridor from Sutton and Barto's textbook (Example 13.1) [2]. There are three non-terminal states in a row and a goal on the right. Every step costs −1, so the return is minus the episode length. Moving right in the first and third states moves right, but in the middle state the actions are swapped: "right" goes left and "left" goes right. The catch is that the agent cannot tell the states apart. It sees the same features everywhere, so its policy is a single number, the probability $p$ of pressing "right".

A deterministic policy fails completely. Always pressing right bounces between the first two states forever; always pressing left never leaves the first state. A value-based agent that acts $\epsilon$-greedily with $\epsilon =0.1$ is stuck with $p=0.05$ or $p=0.95$, worth −82.1 and −44.2. The best stochastic policy presses right with probability $p^{\ast }=2-\sqrt{2}\approx 0.586$ and has expected return −11.66. Finding that probability is exactly what a policy gradient method is for. (The policy gradient theorem page explains why stochastic, parameterized policies are the natural object here, and the Q-learning page covers the value-based alternative.)

The policy has one parameter, the logit $\theta$, with $p=\sigma (\theta )$. For a two-action logistic policy the score has a simple form: ${\nabla }_{\theta }\log {\pi }_{\theta }(a)=a-p$, where $a=1$ for right and 0 for left. So each right press contributes $(1-p)$ times its return and each left press contributes $-p$ times its return.

Deriving the REINFORCE update#

The objective is the expected return $J(\theta )={\mathbb{E}}_{\tau \sim {\pi }_{\theta }}[R(\tau )]$. The policy gradient theorem [3], derived in full on its own page, gives

where $T$ is the episode length, $r_k$ the reward at step $k$, $\gamma$ the discount factor, and $G_t$ the return from step $t$ onward. Two facts produce it: the log-derivative trick $\nabla p=p\nabla \log p$, which turns the gradient of an expectation into an expectation, and the fact that the environment's transition probabilities do not depend on $\theta$, so they drop out. Because the expectation is over the policy's own episodes, one sampled episode gives an unbiased estimate, and REINFORCE simply follows it:

Read it as weighted maximum likelihood. If you set every $G_t$ to 1 you would be doing supervised learning on your own actions. REINFORCE weights each action's log-likelihood gradient by the return that followed it, so actions in good episodes are imitated and actions in bad ones are pushed away. In the corridor $\gamma =1$ and the task is episodic, so $G_t=-(T-t)$, minus the number of steps still to go.

Williams's original form#

Williams wrote the update for a single unit as $\Delta w=\alpha (r-b)e$, with a learning-rate factor $\alpha \ge 0$, a reinforcement offset by a baseline $b$, and the characteristic eligibility $e=\partial \ln g/\partial w$, the derivative of the log-probability of the unit's output [1]. That is where the acronym comes from. He proved that the expected update lies in the direction of the gradient of expected reward for any baseline $b$ that does not depend on the action, and he described an episodic version that accumulates eligibilities over an episode. Modern presentations, including Sutton and Barto's [2], are the same algorithm in trajectory notation. The baseline was part of the algorithm from the start; we look at what happens without it first, and the baselines article covers what it buys.

REINFORCE pseudocode#

1. Initialize policy parameters $\theta$ (here, $p=0.05$, a policy that rarely presses right).
2. Repeat for each episode:
   1. Run ${\pi }_{\theta }$ until the episode ends, recording $s_0,a_0,r_0,\dots ,s_{T-1},a_{T-1},r_{T-1}$.
   2. For $t=T-1$ down to 0, compute the return-to-go $G_t=r_t+\gamma G_{t+1}$, with $G_T=0$.
   3. Accumulate $g={\sum }_t{\gamma }^t{G}_t{\nabla }_{\theta }\log {\pi }_{\theta }(a_t\mid s_t)$, using the parameters the episode was collected with.
   4. Update $\theta \leftarrow \theta +\alpha g$.

Sutton and Barto's boxed version updates $\theta$ after every step inside the episode; computing the whole episode's gradient at the old parameters and applying it once, as above, is the more common implementation and is exactly an unbiased gradient step. In practice you average $g$ over a batch of episodes before stepping, which is the same estimator with lower variance.

A numpy implementation#

The code below is the complete experiment. It runs as plain Python with numpy, in a few seconds.

import numpy as np

# Short corridor (Sutton and Barto, Example 13.1): states 0, 1, 2; state 3 is the goal.
# Action 1 = "right", 0 = "left". In state 1 the actions are swapped. Reward -1 per step.
NEXT = np.array([[0, 1],    # state 0: left stays, right -> 1
                 [2, 0],    # state 1: left -> 2, right -> 0 (reversed)
                 [1, 3]])   # state 2: left -> 1, right -> goal

def run_episode(p_right, rng, max_steps=10_000):
    s, actions = 0, []
    while s != 3 and len(actions) < max_steps:
        a = int(rng.random() < p_right)
        actions.append(a)
        s = NEXT[s, a]
    return np.array(actions)

def reinforce(alpha, episodes, seed, p0=0.05):
    rng = np.random.default_rng(seed)
    theta = np.log(p0 / (1 - p0))            # logit of "right"; same in every state
    returns = []
    for _ in range(episodes):
        p = 1 / (1 + np.exp(-theta))
        acts = run_episode(p, rng)
        T = len(acts)
        G = -(T - np.arange(T))               # reward-to-go: -1 per remaining step
        score = acts - p                      # d log pi(a) / d theta for a Bernoulli policy
        theta += alpha * np.sum(G * score)    # Monte Carlo policy gradient step
        returns.append(-T)
    return np.array(returns), 1 / (1 + np.exp(-theta))

if __name__ == "__main__":
    R = np.array([reinforce(2 ** -11, 1000, seed)[0] for seed in range(20)])
    print("mean return, first 100 episodes:", R[:, :100].mean().round(2))
    print("mean return, last 100 episodes: ", R[:, -100:].mean().round(2))

Run as shown, it prints a mean return of −36.69 over the first 100 episodes and −11.62 over the last 100 (20 seeds), against an optimum of −11.66. The last-100 average can sit slightly above the optimum by chance because individual episodes are noisy.

Setup (simulation). To mirror the textbook's Figure 13.1 we ran 100 independent runs of 1,000 episodes at three step sizes, each starting from $p=0.05$. We also ran the version with a learned baseline (a single scalar $w$, updated by $w\leftarrow w+2^{-6}(G_t-w)$ at every step) at a larger step size.

REINFORCE works. Every run at every step size moves toward the optimal stochastic policy, as the theory promises. But the slower step sizes are painfully slow on a problem with one parameter, and the obvious fix, a larger step size, runs straight into the variance problem.

Watch REINFORCE learn#

The figure reruns the same algorithm in your browser: 20 runs of 500 episodes on the corridor, starting at $p=0.05$. The top panel shows each run's return and the mean; the bottom panel plots where each run's policy ended on the exact return curve $J(p)$. Move the step size and toggle the baseline.

Why REINFORCE has high variance#

Unbiased is not the same as useful. To see how noisy a single episode's gradient estimate is, we froze the policy at several values of $p$, ran 20,000 episodes at each, and compared the one-episode estimate ${\sum }_t{G}_t(a_t-p)$ with the exact derivative $dJ/d\theta$ computed from the closed-form $J(p)$.

The last column uses the normal approximation $N=(1.645\sigma /|\nabla J|{)}^2$. Even far from the optimum, where the gradient is large, the noise is three to four times the signal. Near the optimum the true gradient shrinks while the noise does not, so the signal-to-noise ratio collapses: at $p=0.5$, still short of the best policy, you need about 500 episodes before a batch average reliably points the right way. Where does that noise come from?

• The return is a sum of many random terms. $G_t$ adds up every future reward, and each depends on every future random action. Its variance grows with the horizon. In the corridor, episode lengths at $p=0.05$ range from 3 steps to several hundred.
• Credit is smeared across the episode. Every action in an episode is weighted by roughly the same large return. Good and bad actions in a long episode are blamed together, and only averaging over many episodes separates them.
• There is no reference point. All returns in this task are negative, so every action's log-probability is pushed down after every episode. Only the difference in how hard it is pushed carries information. Adding a constant to every reward does not change the expected update but can increase its variance without limit. That is the problem a baseline solves; Greensmith, Bartlett and Baxter analysed baselines as control variates and derived the variance-optimal one [4].

The step-size trap#

Noise sets an upper limit on the step size. We swept the step size over 40 seeds of 500 episodes each, with episodes capped at 5,000 steps.

The failure mode is not slow learning but collapse. One unlucky long episode produces a huge update that drives $p$ toward 0 or 1. Both extremes are deterministic policies that never reach the goal, so the next episodes are very long, their score terms $(a-p)$ are tiny, and the policy has no way back. With a baseline the safe range extends by about a factor of two: $2^{-7}$ still learns, and collapse starts at $2^{-6}$. The general lesson carries over to large models: a policy gradient step that is too large can move the policy to a region where it no longer collects the data needed to undo the mistake, which is the motivation for the trust regions in TRPO and PPO.

REINFORCE vs actor-critic#

REINFORCE uses the actual sampled return $G_t$. Actor-critic methods replace it with an estimate built from a learned value function, for example the one-step temporal-difference error $r_t+\gamma V(s_{t+1})-V(s_t)$. The trade is bias for variance: a critic's estimate is far less noisy than a Monte Carlo return but is wrong wherever the critic is wrong. Actor-critic methods can also update before an episode ends, which matters for long or continuing tasks. Generalized advantage estimation interpolates between the two with a single parameter $\lambda$; at $\lambda =1$ it is REINFORCE with a value baseline. The actor-critic and GAE article measures that trade-off directly.

Where REINFORCE shows up today#

REINFORCE is rarely the first choice for control tasks. In a benchmark of continuous-control algorithms, Duan and colleagues found it effective on basic and locomotion tasks but prone to premature convergence to local optima, which left it behind natural-gradient methods on some tasks [6]. It has had a second life in reinforcement learning for language models, where an "episode" is one generated response and the reward arrives once at the end. There, the costs of a learned critic are high, and Ahmadian and colleagues reported that REINFORCE-style estimators with a sampled baseline, such as the leave-one-out average of other responses to the same prompt, matched or beat PPO for RLHF [5]. Group-relative methods used for reinforcement learning with verifiable rewards are close relatives: REINFORCE with a baseline computed from a group of samples. The variance analysis on this page applies to them directly.

Making REINFORCE work in practice#

1. Use reward-to-go and a baseline from the start. Both are free of bias. The baseline alone doubled the largest stable step size in our sweep.
2. Average over a batch of episodes. Variance falls as $1/N$. Near the optimum, our corridor needed hundreds of episodes for a reliable sign.
3. Tune the step size on a log grid and watch for collapse. Track the policy's entropy; a sudden drop to zero entropy with falling returns is the signature of the step-size trap.
4. Normalize or clip returns when their scale is unknown. Scaling returns to unit variance makes one step size work across tasks; it does not change the update direction within a batch.
5. Use several seeds when comparing variants. With estimates this noisy, a single run is an anecdote. See how to evaluate RL agents.
6. Move to a critic when episodes are long. Variance grows with the horizon; at some length an actor-critic method or GAE will learn faster per sample.

Failure modes to recognize#

• Collapse to a deterministic policy after one large update, as in the step-size sweep. Policies with zero probability on an action can never learn that it was good.
• Endless episodes when a degenerate policy cannot terminate. Always cap episode length and log how often the cap is hit.
• Reward scale sensitivity. Multiplying rewards by 10 multiplies the effective step size by 10. Adding a constant to rewards inflates variance unless you subtract a baseline.
• Stale data. REINFORCE is on-policy. Reusing episodes from older parameters without importance weighting estimates the wrong gradient.

Frequently asked questions#

Sources#

1. R. J. Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning, 1992. doi.org
2. R. S. Sutton, A. G. Barto. Reinforcement Learning: An Introduction (2nd ed.), 2018. incompleteideas.net
3. R. S. Sutton, D. McAllester, S. Singh, Y. Mansour. Policy Gradient Methods for Reinforcement Learning with Function Approximation, 1999. proceedings.neurips.cc
4. E. Greensmith, P. L. Bartlett, J. Baxter. Variance Reduction Techniques for Gradient Estimates in Reinforcement Learning, 2004. jmlr.org
5. A. Ahmadian, C. Cremer, M. Gallé, M. Fadaee, J. Kreutzer, O. Pietquin, A. Üstün, S. Hooker. Back to Basics: Revisiting REINFORCE Style Optimization for Learning from Human Feedback in LLMs, 2024. arxiv.org
6. Y. Duan, X. Chen, R. Houthooft, J. Schulman, P. Abbeel. Benchmarking Deep Reinforcement Learning for Continuous Control, 2016. arxiv.org