Reinforcement Learning1992intermediate9 min read

Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning

خوارزميات إحصائية بسيطة لتتبُّع التدرُّج في التعلُّم بالتعزيز للشبكات العصبية

Williams, R. J. — Machine Learning

The problem

By 1992, neural networks had mastered through , but — where an receives only a scalar signal, not a correct answer — remained unsolved for networks. The reward signal tells you how well you did, not what you should have done. There is no target output to backpropagate against. How do you compute a when the depends on actions sampled from the network's own stochastic outputs?

The contribution

Williams introduced the family of algorithms, proving that a stunningly simple update — the reward times the gradient of the log-probability of the action taken — follows the gradient of the expected reward. This "" (or ) requires no model of the environment and no differentiable reward function. The paper also introduced baselines: subtracting a -dependent value from the reward to reduce the variance of the gradient estimate without introducing bias. This made methods practical for the first time.

The impact

REINFORCE is the ancestor of every modern gradient method. PPO (which trains ChatGPT, Claude, and Gemini via RLHF), A3C, TRPO, and the entire family all descend from Williams' insight that you can differentiate through a using the log-probability trick. The same mathematical identity powers variational autoencoders, black-box , and . It is one of the most reused ideas in all of machine learning.

In supervised learning, a teacher marks every answer: "the cat should be labeled cat." The network computes a loss and backpropagates.

In reinforcement learning, there is no teacher — only a scorekeeper. The network flips coins to pick actions, and the scorekeeper says "+10" or "−3" at the end. The scorekeeper never says which action was right.

REINFORCE's insight: if you got +10, go back and ask each coin flip, "how would I need to tilt you to make this exact sequence of actions more likely?" Then tilt each coin by that amount, scaled by the +10. Good trajectories become more probable; bad ones fade away.

The problem: no target to backpropagate against

In supervised learning, the network predicts $\hat{y}$ , compares it to a known target $y$ , and backpropagates the gradient of the loss $\nabla_\theta L(y, \hat{y})$ . Every weight knows exactly how to move.

Reinforcement learning breaks this recipe in two places:

No target output. The agent picks action $a$ in state $s$ , and the environment returns a scalar reward $r$ . Nobody tells the agent what the correct action was.
Non-differentiable feedback loop. The reward comes from the environment — a physics engine, a game, a human rater — which is a black box. You cannot differentiate through a black box.

Before Williams, neural-network approaches to reinforcement learning either required a differentiable model of the environment or resorted to finite-difference estimates (perturb each weight, observe the change — absurdly expensive for large networks).

Open in Lab

Click each tab to compare the information flow in supervised learning vs reinforcement learning. Notice how the RL path has no "correct answer" arrow.

The demo wakes as you arrive…

Step 1: Make the network stochastic

Williams' first move is elegant: instead of outputting a deterministic action, the network outputs a probability distribution over actions. This is the stochastic policy $\pi_\theta(a \mid s)$ — the probability of taking action $a$ in state $s$ , given network weights $\theta$ .

For a discrete action space, the output layer uses a (just like ). The agent then samples from this distribution to pick its action. This sampling is what generates the the agent needs to discover good strategies.

The goal is to find weights $\theta$ that maximize the expected total reward:

$J(\theta) = \mathbb{E}_{\pi_\theta}\left[\sum_t r_t\right]$

Williams asks: can we compute $\nabla_\theta J(\theta)$ — the gradient of expected reward — so we can do gradient ascent?

Open in Lab

Adjust the network weights to see how the policy distribution over actions changes. Click "Sample!" to draw an action from the current distribution.

The demo wakes as you arrive…

Step 2: The log-derivative trick — the heart of REINFORCE

Here is the core mathematical insight. We want $\nabla_\theta \mathbb{E}_{\pi_\theta}[R]$ , but the expectation is over trajectories sampled from the policy we are trying to optimize. The sampling step is not differentiable.

Williams' trick uses a single identity from calculus: $\nabla_\theta \, p_\theta(x) = p_\theta(x) \, \nabla_\theta \log p_\theta(x)$

This is just the chain rule applied to $\log$ : since $\frac{d}{d\theta}\log f = \frac{1}{f}\frac{df}{d\theta}$ , multiplying both sides by $f$ gives the identity above.

Now apply it to the expected reward:

\nabla_\theta J(\theta) = \mathbb{E}_{\pi_\theta}\!\left[R \cdot \nabla_\theta \log \pi_\theta(a \mid s)\right]

The REINFORCE gradient estimator (Policy Gradient Theorem for episodic case) — The gradient of expected reward equals the expected value of: reward × gradient of log-probability of the action taken. No model of the environment needed. No differentiable reward needed. Just sample trajectories, compute rewards, and differentiate the log-policy.

Open in Lab

Follow the derivation step by step. Click "Next" to see how the log-derivative trick transforms an intractable gradient into a simple expectation.

The demo wakes as you arrive…

The REINFORCE algorithm step by step

Putting it all together, the algorithm is:

Run an . Let the stochastic policy $\pi_\theta$ interact with the environment, recording the full : states $s_t$ , actions $a_t$ , rewards $r_t$ .
Compute the . For each time step $t$ , compute the discounted cumulative reward (return) $G_t = \sum_{k=0}^{T-t} \gamma^k r_{t+k}$ .
Compute the gradient. For each step, compute the policy gradient estimate: $\Delta\theta = \alpha \, G_t \, \nabla_\theta \log \pi_\theta(a_t \mid s_t)$ .
Update the weights. Apply $\theta \leftarrow \theta + \Delta\theta$ .
Repeat from step 1.

This is a method: it uses complete episodes (no bootstrapping) and the return $G_t$ is an unbiased sample of the true expected reward from time $t$ onward.

Open in Lab

Watch the REINFORCE algorithm run on a simple grid world. Each episode generates a trajectory; the return weights the log-probability gradients to update the policy.

The demo wakes as you arrive…

REINFORCE in ~25 lines of Pythonpython

Simplified to show the idea — not the real implementation.

import numpy as np
def softmax(x):
    e = np.exp(x - x.max())
    return e / e.sum()

# Policy network: state → action probabilities W = np.random.randn(4, 2) * 0.01   # 4 states, 2 actions
alpha = 0.01    # learning rate gamma = 0.99    # discount factor
for episode in range(1000):
    states, actions, rewards = [], [], []
    s = env.reset()

    # 1) Roll out an episode
    while not done:
        probs = softmax(W[s])
        a = np.random.choice(len(probs), p=probs)
        s_next, r, done = env.step(a)
        states.append(s); actions.append(a); rewards.append(r)
        s = s_next

    # 2) Compute returns G_t for each step
    G = 0
    returns = []
    for r in reversed(rewards):
        G = r + gamma * G
        returns.insert(0, G)

    # 3-4) Update weights using policy gradient
    for t in range(len(states)):
        s, a, G_t = states[t], actions[t], returns[t]
        probs = softmax(W[s])
        # grad log pi(a|s) for softmax: one-hot(a) - probs
        grad_log = -probs.copy()
        grad_log[a] += 1.0
        W[s] += alpha * G_t * grad_log   # THE update

The variance problem and baselines

REINFORCE's gradient is unbiased — on average it points in the right direction. But its variance is enormous. Why? Because the return $G_t$ can swing wildly between episodes. One lucky trajectory might get $G_t = 100$ , the next gets $G_t = -50$ . The gradient oscillates madly, and learning crawls.

Williams' solution: subtract a $b(s)$ from the return before multiplying:

$\nabla_\theta J \approx \frac{1}{N}\sum_{i} (G_t^{(i)} - b(s_t)) \nabla_\theta \log \pi_\theta(a_t^{(i)} \mid s_t)$

The crucial theorem: any baseline that does not depend on the action $a$ preserves the unbiasedness of the estimator (because $\mathbb{E}_a[\nabla_\theta \log \pi_\theta(a|s)] = 0$ ). But it can drastically reduce variance by centering the reward signal around zero.

The optimal baseline is close to the state $V^\pi(s)$ , which is exactly the expected return from state $s$ . This connection leads directly to the actor-critic architecture: the "critic" learns $V^\pi(s)$ and the "actor" uses $G_t - V(s_t)$ — the — as its gradient weight.

Open in Lab

Watch 50 gradient estimates with and without a baseline. The baseline version converges far faster because its signal is centered near zero.

The demo wakes as you arrive…

Integration with backpropagation

A key contribution of the paper is showing how REINFORCE integrates naturally with backpropagation. If the policy is a multi-layer neural network, the gradient $\nabla_\theta \log \pi_\theta(a|s)$ is computed by standard backpropagation — the only difference is what is backpropagated.

In supervised learning: backpropagate $\nabla \text{loss}(y, \hat{y})$ .

In REINFORCE: backpropagate $\nabla \log \pi_\theta(a|s)$ , then multiply the weight update by $G_t - b$ .

This means any neural network architecture — convolutional, recurrent, or (later) — can serve as the policy network. Williams' formulation is architecture- agnostic: it only requires that the output layer defines a differentiable probability distribution over actions.

Open in Lab

Watch the policy evolve over 100 episodes. Actions that led to high returns get reinforced; those that led to poor returns get suppressed.

The demo wakes as you arrive…

The legacy: from REINFORCE to RLHF

The policy gradient identity from this paper is one of the most consequential equations in machine learning. Nearly every modern RL method uses it:

1992
REINFORCE
Williams proves the policy gradient theorem for stochastic policies. Monte Carlo, episodic, high variance — but the identity is exact and the math is clean.
2000
Policy Gradient Theorem (Sutton et al.)
Generalizes Williams' result to continuing (non-episodic) tasks and provides the formal foundation for actor-critic methods.
2015
TRPO
Uses policy gradient but constrains each update to a trust region where the linear approximation is valid, preventing catastrophic policy collapse.
2016
A3C
Runs many agents in parallel, each using policy gradients with a learned baseline (the critic). Scaled RL to complex 3D environments.
2017
PPO
Simplifies TRPO into a clipped surrogate objective. Became the workhorse of deep RL and later the backbone of RLHF for training language models.
2022
RLHF for LLMs
PPO (a descendant of REINFORCE) fine-tunes GPT, Claude, and Gemini based on human preferences. Williams' 1992 gradient identity sits at the heart of the most impactful AI systems of the decade.

CitationWilliams, R. J.. Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning. Machine Learning, 1992.

Terms in this paper

REINFORCEخوارزمية REINFORCE
Policy Gradientتدرج السياسة التشغيلية
Log-Derivative Trickحيلة المشتقّة اللوغاريتمية
Score Function Estimatorمُقدِّر دالّة الرصيد
Baseline (RL)خطّ الأساس (في التعلّم بالتعزيز)
Variance Reductionتقليل التباين
Stochastic Policyالسياسة العشوائية
Return (Cumulative Reward)العائد التراكمي