REINFORCE

Overview

REINFORCE is the simplest and most famous policy gradient algorithm in reinforcement learning. It trains a policy directly. The policy is a function, usually a neural network, that outputs the probability of each action in each state. After each episode, REINFORCE raises the probability of actions that were followed by a high return and lowers the probability of actions followed by a low return.

The method is easy to write, needs no value function and works with both discrete and continuous actions. Its weakness is noise. Because it learns from full episodes, the gradient estimate has high variance and learning can be slow. Most modern methods, such as A2C, A3C, TRPO and PPO, can be seen as REINFORCE with extra machinery to reduce that variance and keep updates safe. Understanding REINFORCE is therefore the best way to understand the whole policy gradient family.

What it is

REINFORCE is a Monte Carlo policy gradient algorithm. "Monte Carlo" means it waits until an episode finishes and uses the real total return, instead of an estimate of the future. "Policy gradient" means it computes the gradient of expected return with respect to the policy parameters and takes a step uphill.

The policy is written as pi(a | s; theta), the probability of action a in state s with parameters theta. The goal is to maximize J(theta), the expected total return when following the policy.

The core idea in one sentence

If an action was followed by a good outcome, make it more likely. If it was followed by a bad outcome, make it less likely.

An everyday analogy

Imagine learning to cook by trial and error. You try a recipe with certain choices: more salt, longer baking, a different pan. At the end you taste the dish and score it. REINFORCE says: nudge every choice you made toward being repeated if the dish was good, and away from being repeated if the dish was bad. You do not need to know which choice caused the result. Over many dishes, the choices that really help are repeated more often. The weakness is clear too: with only one score per dish, you cannot tell which choice mattered, so learning needs many dishes.

What it needs and does not need

Why the name

The name comes from the idea of reinforcement: actions that lead to reward are reinforced. In the original paper the name was written in capitals as an acronym for a family of update rules that combine a reward, an offset and an eligibility term.

Where it came from

REINFORCE was introduced in 1992 in a paper on simple statistical gradient-following algorithms for connectionist reinforcement learning. It showed that a certain class of update rules follows the gradient of expected reward in expectation.

Earlier work on learning automata and stochastic neural units motivated the idea. The result gave a clean, general recipe: sample actions from a stochastic policy, observe reward, and adjust parameters in proportion to reward times the gradient of the log-probability.

Later work built the theory around it.

• The policy gradient theorem (published around 1999 and 2000) gave a general form for the gradient and showed that it holds with function approximation. It also justified subtracting a baseline and led to actor-critic methods.
• Natural gradient ideas and trust-region ideas led to TRPO in 2015 and then PPO in 2017.
• Asynchronous and synchronous actor-critic methods, A3C and A2C (2016), used parallel workers and a learned critic as a better baseline.

Even in the deep learning era, REINFORCE remains a common choice for problems where the "environment" is a non-differentiable score. Examples include training models with discrete sampling steps, optimizing sequence generation by a final metric, and neural architecture search.

How it works

Step 1: define a stochastic policy

The network takes a state and outputs a distribution over actions. For discrete actions, this is a softmax over action logits. For continuous actions, it can output the mean and standard deviation of a Gaussian.

Step 2: collect an episode

Run the current policy in the environment from start to end. Record each state, action and reward: (s_0, a_0, r_1), (s_1, a_1, r_2), and so on.

Step 3: compute returns

For each time step t, compute the discounted return from that point to the end:

G_t = r_(t+1) + gamma * r_(t+2) + gamma^2 * r_(t+3) + ...

This is the actual reward collected after step t, not an estimate.

Step 4: compute the gradient estimate

The policy gradient theorem gives:

gradient of J = expected value of [ sum over t of G_t * gradient of log pi(a_t | s_t) ]

The gradient of the log-probability points in the direction that makes the chosen action more likely. Multiplying by G_t scales the push by how good the outcome was. This is sometimes called the log-derivative trick or the likelihood ratio trick.

Step 5: take a step

Update the parameters by gradient ascent:

theta = theta + alpha * G_t * gradient of log pi(a_t | s_t)

In practice you minimize the negative of the objective with an optimizer such as Adam.

Step 6: repeat

Collect new episodes with the updated policy and repeat. The data from old policies is thrown away, which makes REINFORCE on-policy.

Why the log-derivative trick matters

The environment is usually a black box. You cannot differentiate through it. But you can differentiate the policy's own probabilities. The trick turns the gradient of an expectation over trajectories into an expectation of a quantity you can compute: returns times the gradient of log-probabilities. That is why the method works with any reward, even one that is not differentiable.

Adding a baseline

The raw estimate has high variance. A baseline b(s_t) subtracts a reference value from the return:

(G_t - b(s_t)) * gradient of log pi(a_t | s_t)

Subtracting a baseline that does not depend on the action leaves the expected gradient unchanged but can reduce variance a lot. A common baseline is the average return. A better one is a learned state-value function, which turns the method into an actor-critic such as A2C.

Why a baseline works

Suppose every return in a task is large and positive. Without a baseline, every action gets reinforced, even bad ones, and only the size of the push differs. Centering the returns means actions that did better than usual are pushed up and those that did worse are pushed down. The signal is cleaner.

Reward-to-go

Instead of using the full-episode return for every step, use the return from step t onward. Rewards before step t cannot have been caused by action a_t, so including them only adds noise. This simple change, called reward-to-go, lowers variance without adding bias.

Entropy bonus

Adding a term that rewards a high-entropy policy discourages the policy from becoming deterministic too early. It keeps exploration alive. This is a popular addition in practice.

Putting the loop together

Key concepts and terms

A worked example

We will train a REINFORCE agent on a tiny task: a two-armed bandit with a twist, where the best arm depends on a one-bit state. This keeps the numbers clear. Then we show a neural network version.

Numeric walk-through

Policy for one state with two actions, with logits z = (0, 0). The probabilities are (0.5, 0.5).

• The agent samples action 1 and receives return G = 2.
• The baseline is b = 1.
• The advantage is 2 - 1 = 1.

For a softmax policy, the gradient of log-probability of the chosen action with respect to the logits is (one-hot of the action) minus the probabilities. For action 1 (the first), it is (1 - 0.5, 0 - 0.5) = (0.5, -0.5).

With learning rate 0.1, the logits change by 0.1 * 1 * (0.5, -0.5) = (0.05, -0.05). New logits are (0.05, -0.05) and the probabilities move to about (0.525, 0.475).

If instead the return had been 0 with the same baseline, the advantage would be -1 and the logits would move the other way, lowering the chance of action 1.

Code: a minimal REINFORCE agent

import torch
import torch.nn as nn
import torch.nn.functional as F

class Policy(nn.Module):
    def __init__(self, state_dim, n_actions, hidden=64):
        super().__init__()
        self.net = nn.Sequential(
            nn.Linear(state_dim, hidden), nn.Tanh(),
            nn.Linear(hidden, n_actions),
        )

    def forward(self, s):
        return F.log_softmax(self.net(s), dim=-1)

policy = Policy(state_dim=4, n_actions=2)
opt = torch.optim.Adam(policy.parameters(), lr=1e-3)
gamma = 0.99

Code: sampling an episode

def run_episode(env, policy):
    log_probs, rewards = [], []
    s = env.reset()
    done = False
    while not done:
        logp = policy(torch.as_tensor(s, dtype=torch.float32))
        a = torch.distributions.Categorical(logits=logp).sample()
        log_probs.append(logp[a])
        s, r, done, _ = env.step(a.item())
        rewards.append(r)
    return log_probs, rewards

Code: returns and update

def discounted_returns(rewards, gamma):
    G, out = 0.0, []
    for r in reversed(rewards):
        G = r + gamma * G
        out.append(G)
    out.reverse()
    return torch.tensor(out)

def update(log_probs, rewards):
    G = discounted_returns(rewards, gamma)
    G = (G - G.mean()) / (G.std() + 1e-8)       # baseline and scale
    loss = -(torch.stack(log_probs) * G).sum()
    opt.zero_grad()
    loss.backward()
    opt.step()

Code: the training loop

for episode in range(2000):
    log_probs, rewards = run_episode(env, policy)
    update(log_probs, rewards)
    if episode % 100 == 0:
        print(episode, sum(rewards))

What to expect

On a small control task, the return climbs noisily. Different seeds give different curves. With the mean baseline and normalization the curve is smoother than without. A learned value baseline or a larger batch of episodes per update reduces the noise further.

Batching episodes

Averaging the gradient over several episodes before each step reduces variance. A batch of ten or more episodes per update is common for small tasks. The cost is more environment interaction per update.

Variance reduction options compared

A mental picture of the update

Picture the policy as a dial for each action in each state. After an episode, every dial that was used gets turned a little. The size of the turn is the advantage. The direction is toward the action that was taken if the advantage is positive, and away from it if the advantage is negative. Over many episodes, dials that matter get turned consistently in one direction while dials that do not matter wiggle around zero.

Why the estimator is correct in expectation

The trick is that the expectation of the gradient of the log-probability is zero when summed over all actions. This is why subtracting any action-independent baseline leaves the average gradient unchanged. It also explains why the signal comes only from the correlation between the action and the return. If an action has no effect on return, its average push is zero.

Continuous action policies

For a Gaussian policy, the network outputs a mean and a log standard deviation per action dimension. The log-probability of a sampled action has a closed form, and the gradient flows into both outputs.

mean, log_std = net(state)
dist = torch.distributions.Normal(mean, log_std.exp())
action = dist.sample()
log_prob = dist.log_prob(action).sum(-1)

Clip or squash the action to the valid range after sampling, and keep the log-std within sensible bounds so the policy does not become too narrow or too wide.

Using REINFORCE for a sampled structure

Suppose a model picks a subset of columns from a table. Let each column have a keep probability p_i. Sample a keep mask, score the mask with a validation metric, and update the probabilities.

logits = nn.Parameter(torch.zeros(n_cols))
opt = torch.optim.Adam([logits], lr=0.05)
baseline = 0.0

for step in range(500):
    probs = torch.sigmoid(logits)
    mask = torch.bernoulli(probs).detach()
    score = evaluate_model(mask)               # validation metric
    logp = (mask * torch.log(probs + 1e-8)
            + (1 - mask) * torch.log(1 - probs + 1e-8)).sum()
    baseline = 0.9 * baseline + 0.1 * score    # moving average baseline
    loss = -(score - baseline) * logp
    opt.zero_grad(); loss.backward(); opt.step()

The moving-average baseline here is the simplest form of variance reduction. This pattern needs no gradient through the evaluation function.

Strengths and limitations

Strengths

• Simple. The algorithm fits in a few lines and is easy to debug.
• Unbiased gradient. The estimator is correct in expectation, and Monte Carlo returns do not rely on a possibly wrong value estimate.
• Works with any policy form. Discrete, continuous or structured actions can be sampled and scored.
• No value function required. There is no critic to train, so fewer things can go wrong.
• Handles non-differentiable rewards. The reward can come from a black-box simulator or a human rating.
• Good for sequences. It underlies many methods that optimize generated sequences against a final score.

Limitations

• High variance. One episode gives a noisy gradient, so learning needs many samples.
• Sample inefficiency. Data is used once and then discarded because the method is on-policy.
• Needs full episodes. It cannot update mid-episode, which is slow for long tasks and awkward for continuing tasks.
• Credit assignment is crude. All actions in an episode share one return, so good actions in a bad episode are punished.
• Step size sensitivity. A bad step can wreck the policy, and the method has no built-in safeguard like a trust region.
• Local optima. Gradient ascent can get stuck in a poor policy.
• Slow on sparse rewards. If most episodes score zero, there is little signal.

How it compares with alternatives

REINFORCE sits at the base of this table. Move to A2C when you want a learned baseline, to PPO when you want safer updates, and to a value-based or off-policy method such as DQN or SAC when you need to reuse data.

Role in tabular foundation models

REINFORCE does not read tables by itself, but it plays several real roles around models that learn from raw tables. A tabular foundation model such as TabPFN is pre-trained on many synthetic or real tables and predicts on a new table through in-context learning, with no gradient step at prediction time. It handles rows and columns, mixed numeric and categorical types and missing values, and it does not need meaningful column names. See /model/research and /model/architecture.

Optimizing non-differentiable table objectives

Many things we care about in tabular work are not differentiable: the number of features selected, a business cost after a decision rule, a downstream accuracy after a data cleaning step. REINFORCE gives a way to optimize them. Sample a discrete choice from a policy, measure the score, and push the policy toward choices with better scores. This has been used in feature selection, data augmentation policy search and pipeline search.

Learning to choose features or columns

A policy can output the probability of keeping each column. The sampled subset is passed to a tabular model, and the validation score becomes the reward. REINFORCE updates the probabilities. With a baseline, the method learns which columns carry signal. Because tabular foundation models predict without retraining, the reward evaluation is fast, which makes this loop practical.

Imputation and data preparation policies

A policy can choose, for each column with missing values, among several imputation strategies. The reward is the downstream model quality. See imputation networks. The policy sees column statistics, not names, so it works on tables with missing or meaningless headers.

Anomaly review and sector-aware actions

In anomaly detection workflows, a policy can learn when to flag, hold or pass a row, rewarded by reviewer feedback. If a tabular model infers the semantic type or sector of a table, the policy can condition on that label and learn different behavior for different domains.

Fine-tuning with reward signals

When a pre-trained tabular or sequence model is adapted with a reward, for example to favor outputs with a particular property, policy gradient updates of the REINFORCE kind are the foundation. Modern variants add baselines and clipping, as in PPO, but the gradient is the same log-probability times advantage form.

Continual learning

On-policy methods learn from fresh data, which suits settings where tables drift. The cost is that old data is not reused, so forgetting depends on the stream. Mixed strategies keep a small memory of past tables to evaluate the policy and to guard against drift.

Honest limits

REINFORCE is not pre-trained on tables and does not perform in-context learning. It is an optimizer for policies. Its value in tabular work is as a way to tune discrete decisions around a table model, not as a table model itself. For measured results of table models, see /model/benchmarks.

Practical guidance and best practices

Always use a baseline

At minimum, subtract the batch mean return. Better, learn a value function and use the advantage. This one change makes the largest difference in stability.

Use reward-to-go

Count only rewards after the action. It lowers variance with no bias.

Normalize returns

Dividing by the standard deviation of returns in a batch keeps update sizes consistent across tasks with different reward scales.

Use batches

Average the gradient over many episodes before updating. Small batches give noisy steps.

Add an entropy bonus

A small entropy term keeps exploration alive. Decay it over time as the policy becomes sure.

Tune the learning rate carefully

Policy gradient is sensitive to step size. Start small, such as 1e-3 or lower with Adam, and watch the entropy and return.

Clip gradients

Clip the gradient norm to guard against rare large updates.

Track the right signals

When to move on

If REINFORCE is too slow or too noisy, switch to A2C for a learned baseline or PPO for safer, reusable updates. Use DQN or SAC if data reuse is essential.

Debugging order

1. Test the environment with random actions and confirm that rewards look correct.
2. Check that probabilities sum to one and log-probabilities are finite.
3. Train on a trivial task, such as a one-step bandit, and confirm the best action wins.
4. Check the sign of the loss by watching whether returns rise.
5. Turn on baselines and normalization, then compare curves.
6. Add complexity only after the simple version works.

Choosing the number of episodes per update

Scaling up

REINFORCE parallelizes easily. Run many environment copies, gather their episodes, and take one averaged step. The synchronous version of this idea is close to A2C. If you let workers update shared parameters without waiting, you get ideas close to A3C.

Checklist

• Stochastic policy with correct log-probabilities
• Reward-to-go and a baseline
• Batches of episodes
• Entropy bonus and gradient clipping
• Several seeds

Common mistakes

1. No baseline. The variance is so high that learning looks random.
2. Using the full-episode return for every step. Reward-to-go is better.
3. Forgetting the minus sign. Optimizers minimize, so the loss is the negative of advantage times log-probability.
4. Detaching the wrong tensor. The advantage must not carry gradient into the log-probability term in a way that changes the objective.
5. Sampling actions without recording log-probabilities from the same forward pass. The gradient needs the exact probabilities used.
6. Reusing old data. The estimator assumes data from the current policy. Reuse needs importance sampling or a different algorithm.
7. Collapsing entropy. Without a bonus the policy may become deterministic early and stop exploring.
8. Too large a learning rate. One bad step can destroy a policy, and recovery is slow.
9. Judging by one seed. Results are noisy. Use several seeds.
10. Mismatched discounting. Using a discount in the update but not in the evaluation, or the reverse, causes confusion about progress.

Frequently asked questions

What is REINFORCE in simple terms?

REINFORCE is a way to train a policy by trial and error. The agent plays an episode, sees how much reward it got, and then makes the actions it took more likely if the reward was good and less likely if it was bad. Repeated over many episodes, the policy gets better.

Why is REINFORCE called a Monte Carlo method?

It waits until an episode ends and uses the actual total reward collected, rather than a bootstrapped guess about the future. Monte Carlo methods estimate quantities by sampling real outcomes. This makes the estimate unbiased but noisy.

Why does REINFORCE have high variance?

Each update uses one sampled trajectory, and the return depends on many random choices. All actions in the trajectory share the same credit, so the signal for any single action is noisy. Baselines, reward-to-go and batching all help reduce this noise.

What does a baseline do?

A baseline is a reference number subtracted from the return so that only better-than-expected outcomes push probabilities up. As long as the baseline does not depend on the action taken, it does not change the expected gradient, but it can greatly reduce variance. A learned state-value function is the most common strong baseline.

Is REINFORCE on-policy or off-policy?

It is on-policy. The gradient estimate assumes the data came from the current policy, so old data must be discarded after each update. Off-policy variants exist using importance weights, but they add their own variance problems.

How is REINFORCE different from actor-critic methods?

REINFORCE uses the full sampled return, and at most a simple baseline. Actor-critic methods such as A2C train a critic that estimates the value of states and use it to form lower-variance advantages, which allows updates before an episode ends. The cost is some bias from the critic's errors.

Can REINFORCE handle continuous actions?

Yes. The policy can output the parameters of a continuous distribution, such as the mean and spread of a Gaussian, and the log-probability of the sampled action is used in the gradient. This is one advantage over value-based methods that need a maximum over actions.

Is REINFORCE still used today?

It is used for teaching, as a baseline, and in settings where the reward is a black-box score and the action is a discrete sample, such as optimizing a generated sequence or a choice of features. Most large-scale systems use descendants like PPO, which add a critic and clipped updates.

How is REINFORCE related to tabular machine learning?

It is not a table model, but it can optimize discrete decisions around one, such as which columns to keep or which imputation method to use. The reward is the downstream score of a tabular model, which does not need to be differentiable.

How many episodes does REINFORCE need?

There is no fixed number. Simple control tasks may need thousands of episodes, and harder tasks need far more. Using baselines, reward-to-go, batching and normalization can cut the requirement a lot, and moving to a method with a critic cuts it further.

Glossary

• Advantage: The return minus a baseline.
• Baseline: A reference value subtracted to reduce variance.
• Discount factor: A number below one that reduces the weight of later rewards.
• Entropy bonus: A term added to encourage the policy to stay random enough to explore.
• Episode: One run from a start state to a terminal state.
• Log-derivative trick: The identity that turns a gradient of a probability into probability times the gradient of its log.
• Monte Carlo return: The actual discounted sum of rewards observed after a step.
• On-policy: Learning from data made by the current policy.
• Policy: A function that maps states to action probabilities.
• Policy gradient: The gradient of expected return with respect to policy parameters.
• Reward-to-go: The return counting only rewards after the action.
• Stochastic policy: A policy that samples actions rather than always picking one.
• Trajectory: The sequence of states, actions and rewards in an episode.
• Variance: The spread of a gradient estimate across samples.

Summary

REINFORCE trains a policy directly by raising the probability of actions that led to high returns. It uses the log-derivative trick to estimate the gradient from sampled episodes, needs no value function and works with any action type. Its main weakness is high variance, which baselines, reward-to-go, normalization and batching reduce.

It is the foundation of the policy gradient family, leading to A2C, A3C, TRPO and PPO. In tabular work, it is a practical way to optimize non-differentiable choices around a model such as TabPFN, for example column selection, imputation strategy or anomaly triage. See reinforcement learning for the wider context and /model/research, /model/architecture and /model/benchmarks for model details.

Related

It belongs to Reinforcement learning in my stack, under AI and machine learning. Others in the same group: