The REINFORCE Algorithm

REINFORCE waits for full episodes, then raises the probability of actions that led to high returns and lowers the probability of actions that led to low returns.

REINFORCE rolls one episode with rewards 2.0 and 8.0, builds returns 10.0 and 8.0, and moves theta from 0.0 to 0.1

Why Does This Exist?

Value methods pick actions by maximizing $Q(s, a)$ over the action set. That works for a few discrete buttons and breaks for a robot arm, where the action is a continuous torque vector and the maximum has no closed form. They also struggle to represent stochastic policies, which you need when one observation demands a mix of actions.

REINFORCE, introduced by Williams in 1992, skips values and tunes the policy directly. The policy $\pi_\theta(a \mid s)$ is a parameterized distribution, such as a Gaussian mean and variance for continuous joints or logits for discrete moves. The puzzle it solved: how do you differentiate expected return when the environment dynamics behind it are unknown? The log derivative trick turns the gradient of an expectation into an expectation of gradients, which single episode rollouts can estimate. For the general family this belongs to, read policy gradient. For the lower variance successor, read actor critic architecture.

The one idea you need first

An expected return $J(\theta)$ is the average total reward your policy collects, where the average runs over all the randomness in trajectories. REINFORCE climbs this average with gradient ascent: it estimates which way in weight space raises the average, then steps that way. Everything below is how to get that direction from one played episode.

Think of It Like This

A coach who only reviews full game tape

A basketball coach is not allowed to shout instructions during the game. She watches the whole 48 minutes, lets the players try things, and waits for the final buzzer. Then she rewinds the tape. Every possession that fed a scoring run gets a note saying do that dribble move more often. Every possession that fed turnovers gets a note saying cut that risky pass down.

Credit is noisy, because one brilliant first quarter pass sits inside a game lost on fourth quarter defense. But across hundreds of games, the moves that systematically precede wins get reinforced and the rest fade. That is Monte Carlo learning: judge each decision by the full return that followed it, and average over many completions.

Where the analogy stops: the coach understands why a play worked, while REINFORCE only knows the score that followed. It assigns credit by timing, weighting early actions by everything that came after, which is exactly why its estimates wobble so much.

How It Actually Works

The likelihood ratio trick

Write a trajectory as $\tau = (s_0, a_0, r_1, s_1, a_1, \dots)$ . Here $s_t$ is the state, $a_t$ the action taken, and $r$ the rewards collected. The objective is the expected trajectory return:

J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta}[R(\tau)]

A trajectory's probability splits into the start distribution, your policy, and the unknown environment transitions $\mathcal{P}$ :

P(\tau; \theta) = \rho_0(s_0) \prod_{t} \pi_\theta(a_t \mid s_t) \mathcal{P}(s_{t+1} \mid s_t, a_t)

Differentiating looks hopeless because $\mathcal{P}$ is unknown. The trick is the identity $\nabla_\theta P = P \nabla_\theta \log P$ , which moves the gradient onto the log. Since $\log$ turns the product into a sum and $\mathcal{P}$ does not depend on $\theta$ , every environment term differentiates to zero:

\nabla_\theta \log P(\tau; \theta) = \sum_{t} \nabla_\theta \log \pi_\theta(a_t \mid s_t)

That leaves the policy gradient estimator:

\nabla_\theta J(\theta) = \mathbb{E}\left[ \sum_{t} \nabla_\theta \log \pi_\theta(a_t \mid s_t) G_t \right]

Here $G_t$ is the return to go from step $t$ , meaning rewards from $t$ onward discounted back: $G_t = \sum_{k \ge t} \gamma^{k-t} R_{k+1}$ with discount factor $\gamma$ . Using $G_t$ instead of the whole episode return respects causality, since your action at $t$ cannot affect rewards already banked before $t$ .

Baselines cut variance without bias

Full episode returns swing wildly, and that swing passes straight into the gradient. The standard fix subtracts a baseline $b(s_t)$ , a number that may depend on the state but not on the sampled action:

\theta \leftarrow \theta + \alpha \sum_{t} \nabla_\theta \log \pi_\theta(a_t \mid s_t)(G_t - b(s_t))

Here $\alpha$ is the learning rate. The baseline adds no bias because its expected contribution is zero: averaging $\nabla_\theta \log \pi_\theta(a_t \mid s_t)$ over the policy's own action distribution always gives zero, so scaling it by $b(s_t)$ still gives zero. A constant average return works, and a learned state value works better. The diagram below walks the numbers once through this update.

Worked example

Two steps, two actions, one weight $\theta$ . The policy is a sigmoid: action $a_1$ gets logit $\theta$ and $a_2$ gets logit $0$ , so $\pi(a_1) = \sigma(\theta)$ and $\pi(a_2) = 1 - \sigma(\theta)$ . Start at $\theta = 0.0$ , so both actions have probability $0.5$ . Set $\gamma = 1.0$ , $\alpha = 0.1$ , baseline $b = 5.0$ . The episode plays $a_1$ for reward $2.0$ , then $a_2$ for reward $8.0$ .

Returns to go, computed backward: $G_1 = 8.0$ and $G_0 = 2.0 + 8.0 = 10.0$ . Minus the baseline, the advantages are $A_0 = 10.0 - 5.0 = +5.0$ and $A_1 = 8.0 - 5.0 = +3.0$ .

Log probability gradients at $\sigma(0) = 0.5$ : for the taken $a_1$ , $1 - 0.5 = +0.5$ . For the taken $a_2$ , $-0.5$ . Total gradient: $0.5 \times 5.0 + (-0.5) \times 3.0 = 2.5 - 1.5 = +1.0$ . Update: $\theta = 0.0 + 0.1 \times 1.0 = 0.1$ . The new $P(a_1) = \sigma(0.1) \approx 0.5250$ . The good first move gets reinforced more than the second move gets suppressed, so its probability rises.

Code

This snippet runs the worked update with plain arithmetic. Check each printed number against the hand computation above.

1import numpy as np2
3
4def reinforce_update(theta: float, actions: list[int], rewards: list[float], gamma: float = 1.0, alpha: float = 0.1, baseline: float = 5.0) -> tuple[float, list[float]]:5    """One Monte Carlo REINFORCE update over a single episode."""6    returns: list[float] = [0.0] * len(rewards)7    g = 0.08    for t in reversed(range(len(rewards))):9        g = rewards[t] + gamma * g10        returns[t] = g11    prob_a1 = 1.0 / (1.0 + np.exp(-theta))12    total_grad = 0.013    for t, action in enumerate(actions):14        advantage = returns[t] - baseline15        grad_log = (1.0 - prob_a1) if action == 0 else (-prob_a1)16        total_grad += grad_log * advantage17    return theta + alpha * total_grad, returns18
19
20if __name__ == "__main__":21    new_theta, rets = reinforce_update(0.0, [0, 1], [2.0, 8.0])22    print(f"returns: {rets}")23    print(f"theta: {new_theta:.2f}")24    print(f"P(a1): {1.0 / (1.0 + np.exp(-new_theta)):.4f}")

1# -> expected output:2returns: [10.0, 8.0]3theta: 0.104P(a1): 0.5250

Watch Out For

Full episode variance stalls long horizon training

The symptom: updates thrash, the policy jitters, and longer episodes train worse than short ones at the same learning rate. The cause is Monte Carlo credit: one noisy late transition alters $G_t$ for every earlier step, so the whole episode's gradient inherits the noise of its worst moment.

The fix: always use returns to go rather than whole episode return, subtract a baseline (constant at minimum, learned state value when episodes run long), and normalize advantages within each batch. Past a few hundred steps per episode, move to an actor critic that bootstraps after $n$ steps instead of waiting for termination.

Forgetting the baseline must ignore the sampled action

The symptom: adding a baseline shifts the final policy instead of just calming training. The cause is a baseline that peeks at the action just taken, such as an advantage estimate built from the same sample. The zero expectation proof breaks, and the update turns biased.

The fix: let the baseline depend on state (and time) only. Audit any learned baseline to confirm it never receives the current action as input, and keep the gradient term as the only place the sampled action appears.

The Quick Version

REINFORCE tunes the policy directly with the log derivative trick, so unknown environment dynamics drop out of the gradient.
Updates wait for full episodes and weight each step's log probability gradient by its return to go $G_t$ .
A state dependent baseline subtracts from $G_t$ with zero bias and much lower variance.
The worked episode gives returns 10.0 and 8.0, gradient +1.0, new theta 0.1, and $P(a_1)$ rising from 0.5000 to 0.5250.
Past a few hundred steps per episode, bootstrap with an actor critic instead of pure Monte Carlo returns.