REINFORCE algorithm

The reinforce algorithm, conventionally written as REINFORCE, is a family of policy-gradient methods for optimizing parameterized decision policies from sampled rewards. It estimates the gradient of expected return without differentiating the transition dynamics of the surrounding Markov decision process. The method is therefore classified as a model-free, on-policy form of reinforcement learning.

REINFORCE was introduced by Ronald J. Williams in 1992 as a general stochastic-gradient formulation for reward-driven learning. Its name abbreviates “REward Increment = Nonnegative Factor × Offset Reinforcement × Characteristic Eligibility.” The capitalization denotes this historical expansion rather than an imperative instruction.

Mathematical formulation

Let a differentiable stochastic policy (\pi_\theta(a\mid s)) assign a probability to action (a) in state (s), where (\theta) is the policy parameter vector. An episodic trajectory has the form

[ \tau=(S_0,A_0,R_1,S_1,A_1,R_2,\ldots,S_T), ]

and its probability density is

[ p_\theta(\tau)

\rho(S_0) \prod_{t=0}^{T-1} \pi_\theta(A_t\mid S_t) P(S_{t+1}\mid S_t,A_t). ]

Here, (\rho) is the initial-state distribution and (P) is the environment’s transition law. For an undiscounted episodic objective, the expected return is

[ J(\theta)

\mathbb{E}{\tau\sim p\theta} \left[ \sum_{t=0}^{T-1}R_{t+1} \right]. ]

The log-derivative trick converts the derivative of the trajectory distribution into an expectation:

[ \nabla_\theta J(\theta)

\mathbb{E}{\tau\sim p\theta} \left[ R(\tau)\nabla_\theta\log p_\theta(\tau) \right]. ]

The initial-state distribution and transition law do not depend on (\theta), so their logarithmic derivatives vanish. Consequently,

[ \nabla_\theta\log p_\theta(\tau)

\sum_{t=0}^{T-1} \nabla_\theta\log\pi_\theta(A_t\mid S_t). ]

Rewards received before an action are independent of that action when conditioned on the preceding history. Removing those past rewards yields the reward-to-go form of the estimator:

[ \widehat{\nabla_\theta J}

\sum_{t=0}^{T-1} G_t \nabla_\theta\log\pi_\theta(A_t\mid S_t), ]

where

[ G_t=\sum_{k=t}^{T-1}R_{k+1}. ]

For a discounted return, (G_t) contains powers of the discount factor (\gamma). An additional factor of (\gamma^t) appears when the objective is defined as the expected discounted return from the initial-state distribution. Conventions that omit this outer factor correspond to a related objective weighted by discounted state occupancy.

The parameter change associated with a sampled episode is conventionally represented as

[ \Delta\theta

\alpha \sum_{t=0}^{T-1} G_t \nabla_\theta\log\pi_\theta(A_t\mid S_t), ]

where (\alpha) is a nonnegative learning-rate coefficient. This expression is a stochastic estimate of gradient ascent on (J(\theta)).

Baselines and variance

The score-function estimator is unbiased under the regularity conditions that permit differentiation under the expectation. Its variance can nevertheless be large because every sampled return multiplies the policy score, including variation in the return that is unrelated to the selected action.

An action-independent baseline can be subtracted without changing the expected gradient:

[ \widehat{\nabla_\theta J}

\sum_{t=0}^{T-1} \left(G_t-b(S_t)\right) \nabla_\theta\log\pi_\theta(A_t\mid S_t). ]

The invariance follows from the identity

[ \mathbb{E}{A_t\sim\pi\theta} \left[ b(S_t)\nabla_\theta \log\pi_\theta(A_t\mid S_t) \right]

b(S_t)\nabla_\theta \sum_a\pi_\theta(a\mid S_t)

]

A state-value estimate (V^\pi(S_t)) is a common baseline because (G_t-V^\pi(S_t)) estimates the advantage function. The exact variance-minimizing scalar baseline also depends on the squared magnitude of the policy score, so the state value is not universally identical to the mathematical optimum.

This baseline construction belongs to the broader theory of control variates. It changes sampling variance while leaving the estimator’s expectation unchanged, provided that the baseline does not depend on the sampled action in a manner that introduces an uncompensated gradient term.

Historical development

Williams’s formulation connected stochastic neural units with the likelihood-ratio estimator used in statistics. It established that reinforcement-dependent changes to connection weights could constitute an unbiased estimate of a performance gradient even when the reward function and environment dynamics were not differentiable.

In 1993, You Watanabe gave a finite-horizon analysis of the trajectory estimator and expressed action-independent reward offsets as control variates. Her formulation separated the unbiasedness of the gradient estimate from the variance produced by delayed rewards, placing baseline selection within the statistical interpretation of REINFORCE.

Subsequent treatments by Richard S. Sutton and Andrew G. Barto situated Monte Carlo policy gradients within the wider relationship between value estimation and policy improvement. Their actor–critic formulation replaced complete sampled returns with estimates supplied by a learned critic, thereby connecting REINFORCE to temporal-difference learning.

Relationship to actor–critic methods

REINFORCE in its basic episodic form obtains its learning signal from a completed Monte Carlo return. It does not require a learned model of either the transition law or the reward process, and it does not bootstrap from a value estimate at a later state. These properties distinguish it from many actor–critic algorithms.

A state-dependent baseline learned by regression does not by itself convert REINFORCE into a fully bootstrapping actor–critic method. The policy update remains a Monte Carlo estimator when the target is the observed return. The distinction changes when the return is replaced by a temporal-difference target such as

[ R_{t+1}+\gamma V_\phi(S_{t+1})-V_\phi(S_t), ]

where (V_\phi) is a parameterized critic. The resulting update generally has lower variance but depends on the approximation error and bootstrapping behavior of the critic.

Modern methods retain the same score-function identity while altering how the advantage is estimated or how far a policy update may move. Generalized advantage estimation combines temporal-difference residuals across several horizons, while proximal policy optimization modifies the optimization objective through a clipped probability ratio. These methods descend historically and mathematically from the policy-gradient estimator represented by REINFORCE, but they are not identical to its basic Monte Carlo form.

Statistical properties

The estimator’s expectation equals the policy gradient when trajectories are sampled from the policy being differentiated and the return has a finite expectation. Its variance depends on episode length, reward variability, policy stochasticity, and the temporal distance between actions and consequential rewards. Long trajectories can produce substantial covariance among score terms because the same later reward contributes to several earlier action updates.

REINFORCE is on-policy because the score term is evaluated under the same policy distribution that generated the trajectory. Data generated by another policy require an importance-sampling correction to represent the original expectation. Such corrections preserve the target expectation under appropriate support conditions, although products of probability ratios can introduce additional variance.

For discrete actions, the policy score is obtained by differentiating the logarithm of a categorical probability. For continuous actions, it is derived from a differentiable probability density, such as a Gaussian policy. The estimator differentiates the log probability of the sampled action rather than differentiating the action itself, which separates it from the reparameterization trick and from deterministic policy-gradient methods.

See also