I have a dirty secret. Well, I actually have many. But one of them is that I never understood the basic algorithms behind reinforcement learning. So I plan to remedy this with a series of blog posts, where I will cover foundational RL algorithms, from REINFORCE to the frontier.

Here's the first one, where I cover one of the oldest practical gradient estimators for reinforcement learning, the REINFORCE estimator, and show how it can get away without differentiating through the environment.

When the Data Distribution Depends on the Parameters

At first glance, reinforcement learning (RL) looks just like standard stochastic optimization: in both settings, we seek parameters $\theta \in \RR^d$ that optimize an expectation over data. The crucial difference lies in where the parameters $\theta$ appear. In supervised or unsupervised learning, we minimize an expected loss $\EE_{x \sim p_{\text{data}}}[\ell(x; \theta)] = \int p_{\text{data}}(x) \, \ell(x; \theta) \, \dif x$. Here, the data-generating distribution $p_{\text{data}}(x)$ is fixed by nature and does not depend on $\theta$. When we compute gradients, $\nabla_\theta$ passes straight inside the integral to differentiate $\ell(x; \theta)$—we never need to differentiate the data distribution itself.

In reinforcement learning, the roles are reversed. Over $T$ time steps, an agent interacts with an environment: at each step $t$, it observes a state $s_t$ and samples an action $a_t$ from a parameterized policy ${\color{colorpolicy}\pi_\theta(a_t | s_t)}$, which is simply a model with weights $\theta$ that outputs a probability distribution over actions given the current state. The environment then returns a scalar reward ${\color{colorreturn}r_t} = r(s_t, a_t)$ and transitions to a new state $s_{t+1}$. Unrolling this loop over $T$ steps produces a trajectory $\tau = (s_0, a_0, s_1, a_1, \ldots, s_{T-1}, a_{T-1}, s_T)$ with total reward (or return) ${\color{colorreturn}R(\tau)} = \sum_{t=0}^{T-1} {\color{colorreturn}r_t}$.

Our goal is to find policy parameters $\theta$ that maximize the expected return:For simplicity, we focus on undiscounted finite-horizon returns, though all derivations extend directly to discounted returns ${\color{colorreturn}R(\tau)} = \sum_{t=0}^{T-1} \gamma^t {\color{colorreturn}r_t}$ with $\gamma \in [0, 1)$. Throughout, we color-code the key quantities: ${\color{colorpolicy}\text{green}}$ for the policy, ${\color{colorreturn}\text{orange}}$ for the return, and ${\color{colordynamics}\text{purple}}$ for the environment dynamics. \begin{equation}\label{eq:objective} J(\theta) \defas \EE_{\tau \sim p_\theta}\left[ {\color{colorreturn}R(\tau)} \right] = \int p_\theta(\tau) \, {\color{colorreturn}R(\tau)} \, \dif\tau\,. \end{equation} Notice what changed compared to supervised learning: the function inside the expectation, ${\color{colorreturn}R(\tau)}$, does not depend on $\theta$, but the data-generating distribution $p_\theta(\tau)$ does, because the policy ${\color{colorpolicy}\pi_\theta(a_t | s_t)}$ governs which actions are chosen and thus which trajectories are likely. By the chain rule of probability, this trajectory distribution interleaves our policy with the environment's initial state distribution ${\color{colordynamics}p(s_0)}$ and transition dynamics ${\color{colordynamics}p(s_{t+1} | s_t, a_t)}$: \begin{equation}\label{eq:trajectory_prob} p_\theta(\tau) = {\color{colordynamics}p(s_0)} \prod_{t=0}^{T-1} {\color{colorpolicy}\pi_\theta(a_t | s_t)} \, {\color{colordynamics}p(s_{t+1} | s_t, a_t)}\,. \end{equation}

Because the data-generating distribution $p_\theta(\tau)$ depends on $\theta$, optimizing $J(\theta)$ via gradient ascent requires differentiating $p_\theta(\tau)$ directly: \begin{equation}\label{eq:naive_grad} \nabla_\theta J(\theta) = \nabla_\theta \int p_\theta(\tau) {\color{colorreturn}R(\tau)} \dif\tau = \int \nabla_\theta p_\theta(\tau) {\color{colorreturn}R(\tau)} \dif\tau\,. \end{equation} And here we hit a wall: differentiating $p_\theta(\tau)$ in $\eqref{eq:trajectory_prob}$ requires knowing the environment dynamics ${\color{colordynamics}p(s_{t+1} | s_t, a_t)}$, which are almost always a non-differentiable black box:

• Robotic control: $\tau$ is a sequence of sensor readings $s_t$ and motor torques $a_t$. While the policy ${\color{colorpolicy}\pi_\theta(a_t | s_t)}$ is a differentiable neural network, the transition ${\color{colordynamics}p(s_{t+1} | s_t, a_t)}$ is governed by real-world physics—contact forces, friction, and rigid-body collisions—whose analytical derivatives we do not have.
• Board and video games: $s_t$ is a board configuration or screen frame and $a_t$ is a discrete move. The transition ${\color{colordynamics}p(s_{t+1} | s_t, a_t)}$ is dictated by discrete game rules or an unknown opponent, offering no gradients.
• Language model post-training (RLHF and reasoning): $s_0$ is a prompt, each action $a_t$ is a sampled token appended to the context $s_{t+1} = (s_t, a_t)$, and ${\color{colorreturn}R(\tau)}$ is a score from a human rater or a code/math verifier at the end of generation. We cannot backpropagate through discrete token sampling or an external compiler.

REINFORCE is a way around this roadblock. Through a simple probabilistic identity, it rewrites $\nabla_\theta p_\theta(\tau)$ so that the unknown environment dynamics drop out, leaving only derivatives of the agent's own policy ${\color{colorpolicy}\pi_\theta(a_t | s_t)}$.

Judging an entire sequence of actions by a single reward at the end can be noisy, as gradient variance grows rapidly with the horizon length. Even so, REINFORCE-style algorithms have seen a resurgence in large language model alignment, proving both effective and simpler than actor-critic pipelines, and they form the direct foundation for modern policy gradient methods such as TRPO, PPO, and GRPO.

The Log-Derivative Trick

To move forward, we turn to a classic identity in stochastic optimization known as the log-derivative trick (also known as the likelihood-ratio method or score function estimator). For a broader perspective on score functions and their connection to integration by parts and randomized smoothing, see Francis Bach's excellent blog post. For any differentiable probability density $p_\theta(x) > 0$, we have the identity $\nabla_\theta p_\theta(x) = p_\theta(x) \, \nabla_\theta \log p_\theta(x)$, which follows from the chain rule: \begin{equation}\label{eq:log_derivative_trick} \nabla_\theta \log p_\theta(x) = \frac{\nabla_\theta p_\theta(x)}{p_\theta(x)}\,. \end{equation}

This identity lets us rewrite the problematic gradient $\nabla_\theta p_\theta(\tau)$ in terms of $\nabla_\theta \log p_\theta(\tau)$, converting the integral into an expectation: \begin{align} \nabla_\theta J(\theta) &\stackrel{\eqref{eq:naive_grad}}{=} \int \left( \nabla_\theta p_\theta(\tau) \right) {\color{colorreturn}R(\tau)} \dif\tau \nonumber \\ &\stackrel{\eqref{eq:log_derivative_trick}}{=} \int p_\theta(\tau) \nabla_\theta \log p_\theta(\tau) {\color{colorreturn}R(\tau)} \dif\tau \nonumber \\ &\stackrel{\eqref{eq:objective}}{=} \EE_{\tau \sim p_\theta}\left[ {\color{colorreturn}R(\tau)} \nabla_\theta \log p_\theta(\tau) \right]\,. \label{eq:rl_score_sub} \end{align} We have traded the intractable $\nabla_\theta p_\theta(\tau)$ for $\nabla_\theta \log p_\theta(\tau)$ inside an expectation. But is this any better?

The World Drops Out

At first glance, it doesn't seem like we have gained much. While we have rewritten the gradient of the expected return as an expectation, we are still left with computing the gradient of the log-trajectory probability $\nabla_\theta \log p_\theta(\tau)$, which does not appear to be any easier to compute. The key to resolving this comes from expanding that logarithm. Taking the logarithm of the trajectory probability $\eqref{eq:trajectory_prob}$ turns the product into a sum: \begin{equation}\label{eq:log_trajectory_prob} \log p_\theta(\tau) = \log {\color{colordynamics}p(s_0)} + \sum_{t=0}^{T-1} \log {\color{colorpolicy}\pi_\theta(a_t | s_t)} + \sum_{t=0}^{T-1} \log {\color{colordynamics}p(s_{t+1} | s_t, a_t)}\,. \end{equation} This is crucial: turning a multiplicative structure into an additive one makes differentiation much easier. Taking the gradient with respect to $\theta$ yields: \begin{equation}\label{eq:grad_log_trajectory} \nabla_\theta \log p_\theta(\tau) = \underbrace{\vphantom{\sum_{t=0}^{T-1}}\nabla_\theta \log {\color{colordynamics}p(s_0)}}_{= \, 0} + \sum_{t=0}^{T-1} \nabla_\theta \log {\color{colorpolicy}\pi_\theta(a_t | s_t)} + \underbrace{\sum_{t=0}^{T-1} \nabla_\theta \log {\color{colordynamics}p(s_{t+1} | s_t, a_t)}}_{= \, 0}\,. \end{equation} The environment dynamics ${\color{colordynamics}p(s_{t+1} | s_t, a_t)}$ describe the fixed laws of the environment, not the agent's policy, and so their derivatives with respect to $\theta$ are identically zero. Likewise, the initial state distribution ${\color{colordynamics}p(s_0)}$ does not depend on $\theta$. The unknown environment dynamics drop out entirely, leaving only our differentiable policy: \begin{equation}\label{eq:grad_log_simplified} \nabla_\theta \log p_\theta(\tau) = \sum_{t=0}^{T-1} \nabla_\theta \log {\color{colorpolicy}\pi_\theta(a_t | s_t)} \,. \end{equation}

The REINFORCE Estimator

Using our simplified formula for the score $\eqref{eq:grad_log_simplified}$ in the $\eqref{eq:rl_score_sub}$ gives our fundamental result, the REINFORCE estimator:Pronounced as it's written, but shouting.

Let $\hat{g}(\tau)$ be the REINFORCE estimator for a trajectory $\tau$, defined as: \begin{equation}\label{eq:reinforce} \hat{g}(\tau) = \left(\sum_{t=0}^{T-1} \nabla_\theta \log {\color{colorpolicy}\pi_\theta(a_t | s_t)}\right) {\color{colorreturn}R(\tau)}\,. \end{equation} This is an unbiased estimator of the expected return gradient, that is, \begin{equation}\label{eq:reinforce_expectation} \EE_{\tau \sim p_\theta} [\hat{g}(\tau)] = \nabla_\theta J(\theta)\,. \end{equation} This allows us to optimize expected return by sampling trajectories from the environment, without needing to differentiate through its transition dynamics.

The REINFORCE gradient estimator is commonly attributed to Williams (1992), Fun historical detail: REINFORCE is actually a backronym coined by Williams for REward Increment = Nonnegative Factor × Offset Reinforcement × Characteristic Eligibility, referring to the structure of the update rule. although the log-derivative trick was known well before that. In optimal control and simulation optimization, this general paradigm of directly parameterizing the control law is known as approximation in policy space, and the resulting estimator is referred to as the likelihood ratio method (see Chapter 3 of Bertsekas (2019) for a comprehensive exposition).

Notice what has happened. The gradient $\nabla_\theta J(\theta)$ is expressed as the expected value of the estimator $\hat{g}(\tau)$, which involves only the policy's log-probabilities and the return. The transition dynamics ${\color{colordynamics}p(s_{t+1} | s_t, a_t)}$ appear nowhere in the expression. They are implicit: they determine which trajectories are likely when we sample $\tau \sim p_\theta$, but we never need to know their functional form or differentiate through them. This is the key insight: the log-derivative trick converts "differentiate the distribution" into "evaluate a score function under the distribution".

Reward-to-Go (Causality)

Before analyzing variance, notice an immediate structural improvement to the vanilla REINFORCE estimator $\eqref{eq:reinforce}$. The total return ${\color{colorreturn}R(\tau)} = \sum_{t'=0}^{T-1} {\color{colorreturn}r_{t'}}$ includes rewards obtained both before and after action $a_t$ was taken. Expanding the sum in $\eqref{eq:reinforce}$ splits the return into past and future rewards: \begin{equation} \hat{g}(\tau) = \sum_{t=0}^{T-1} \nabla_\theta \log {\color{colorpolicy}\pi_\theta(a_t | s_t)} \left( \sum_{t'=0}^{t-1} {\color{colorreturn}r_{t'}} + \sum_{t'=t}^{T-1} {\color{colorreturn}r_{t'}} \right)\,. \end{equation} By causality, taking action $a_t$ at time step $t$ cannot retroactively influence rewards ${\color{colorreturn}r_{t'}}$ earned in previous steps ($t' < t$). Indeed, conditioning on the trajectory history up to state $s_t$, past rewards are already fixed while the action score has conditional mean zero: \begin{equation} \EE\left[ \nabla_\theta \log {\color{colorpolicy}\pi_\theta(a_t | s_t)} \, {\color{colorreturn}r_{t'}} \right]=\EE\left[ {\color{colorreturn}r_{t'}} \underbrace{\EE\left[ \nabla_\theta \log {\color{colorpolicy}\pi_\theta(a_t | s_t)} \ \Big|\ s_t, {\color{colorreturn}r_{t'}} \right]}_{=\, 0} \right]=0 \quad \text{for all } t' < t\,. \end{equation} Past rewards are therefore pure noise with respect to the gradient step at time $t$. Dropping them yields the Reward-to-Go estimator: \begin{equation}\label{eq:reward_to_go} \hat{g}_{\text{RTG}}(\tau) = \sum_{t=0}^{T-1} \nabla_\theta \log {\color{colorpolicy}\pi_\theta(a_t | s_t)} \, {\color{colorreturn}G_t}\,, \quad \text{where } {\color{colorreturn}G_t} \defas \sum_{t'=t}^{T-1} {\color{colorreturn}r_{t'}}\,. \end{equation} Because the expected value of the dropped past rewards is strictly zero, $\hat{g}_{\text{RTG}}(\tau)$ remains unbiased ($\EE[\hat{g}_{\text{RTG}}(\tau)] = \nabla_\theta J(\theta)$). Dropping past rewards reduces variance by an exact factor of 3 (since $\sum_{t=0}^{T-1} (T-t)^2 \approx \frac{1}{3} T^3$), but because the future return ${\color{colorreturn}G_t}$ still has an uncentered non-zero mean, its variance scaling remains cubic $O(T^3)$.

Variance

An unbiased estimator is a good start, but that's still far from practical. Ideally, this estimator should have low variance. Under standard assumptions, we can show that the variance of the REINFORCE gradient estimator is bounded as $O(T^3)$, and scales as $\Theta(T^3)$ whenever the expected per-step reward has a non-zero mean.

We'll make the following assumptions. First, per-step rewards are bounded by a constant ${\color{colorreturn}r_{\max}}$, that is, $|{\color{colorreturn}r_t}| \le {\color{colorreturn}r_{\max}}$ for all $t$. Second, the second moment of the per-step score is bounded, i.e., $\EE[\|\nabla_\theta \log {\color{colorpolicy}\pi_\theta(a_t | s_t)}\|^2] \le C$ for some constant $C > 0$ and all $t$.This assumption holds for standard policies: for softmax policies, whenever the logit gradients (network Jacobian) are bounded; for Gaussian policies $\mathcal{N}(\mu_\theta(s), \sigma^2 I)$, whenever the mean network has bounded gradients and the variance $\sigma^2$ is bounded away from zero.

Under the assumptions above, the total variance $\text{Var}(\hat{g}) \defas \EE[\|\hat{g}(\tau) - \EE[\hat{g}(\tau)]\|^2]$ of the REINFORCE estimator is bounded as: \begin{equation}\label{eq:variance_bound} \text{Var}(\hat{g}) \le T^3 {\color{colorreturn}r_{\max}}^2 C = O(T^3)\,. \end{equation}

A companion Lean 4 formalization verifies this proof for finite action spaces in any real Hilbert space.

To put this result in perspective: a cubic dependency on the horizon $T$ is terrible news. Cubic growth means that if you double the length of your episode (say, from $50$ to $100$ steps), the variance of your gradient estimates does not just double: it multiplies by eight ($2^3 = 8$). This makes the estimates incredibly noisy for long horizons.

Empirical Variance Scaling

What we derived in the previous section is an upper bound on the variance. For all we know, this bound could be very loose and the real variance scaling factor could be much smaller. To check how the empirical variance scales in practice, we simulate a simple synthetic MDP. Similar toy environments (such as linear-quadratic control systems and contextual bandits) have been used in the literature for isolating and studying gradient variance.

The setup is as follows: at each time step, the agent observes a state $s_t$ drawn uniformly from $[-1, 1]^4$ and selects one of $|\mathcal{A}| = 4$ actions according to a softmax linear policy $\pi_\theta(a | s) \propto \exp(\theta_a^\top s)$, with parameters $\theta$ drawn from a normal distribution $\mathcal{N}(0, 0.01^2)$. Each step yields a reward ${\color{colorreturn}r_t} = 1 + 0.1 \, \theta_{a_t}^\top s_t$. For each trajectory length $T \in \{5, 10, 20, 40, 80, 160, 320, 640\}$, we estimate $\text{Var}(\hat{g})$ from 30,000 independent trajectories:

• Left: Log-log plot of gradient estimator variance $\text{Var}(\hat{g})$ versus trajectory length $T$, yielding an empirical scaling exponent of $3.00$.
• Right: Normalized variance $\frac{\text{Var}(\hat{g})}{T^3}$ across various values of $T$, confirming that the ratio remains tightly around a constant.

The complete simulation script to reproduce this figure is available at gen_reinforce_variance_scaling.py.

The message here is that the $O(T^3)$ upper bound is not wildly pessimistic, but painfully accurate. Fitting a power law on a log-log scale matches the theoretical $O(T^3)$ bound with remarkable precision.

Why does the empirical variance scale tightly as $\Theta(T^3)$? Intuition comes from considering an environment where per-step rewards have a non-zero mean ${\color{colorreturn}\mu_r} = \EE[{\color{colorreturn}r_t}] \neq 0$. In that regime, the return is dominated by its mean, ${\color{colorreturn}R(\tau)} \approx T {\color{colorreturn}\mu_r}$, so the REINFORCE estimator behaves as $\hat{g}(\tau) \approx (T {\color{colorreturn}\mu_r}) {\color{colorpolicy}S(\tau)}$. Squaring $T \mu_r$ multiplies the linear $\Theta(T)$ variance of the uncorrelated score sum ${\color{colorpolicy}S(\tau)}$ by $T^2 \mu_r^2$, yielding a variance that scales strictly as $\Theta(T^3)$.

Summary

The central achievement of the REINFORCE algorithm is that it allows us to optimize policies without knowing or differentiating through the environment's transition dynamics. By applying the log-derivative trick, the product of transition probabilities turns into a sum, and all environment-dependent terms drop out.

However, the price we pay for this model-free elegance is high variance. Specifically, as we derived above, the variance of the REINFORCE estimator scales cubically with the trajectory length ($O(T^3)$). This stems from the combination of a return ${\color{colorreturn}R(\tau)}$ that grows linearly with $T$ (contributing an $O(T^2)$ term when squared) and a sum of score vectors ${\color{colorpolicy}S(\tau)}$ whose variance also grows linearly as $O(T)$ due to uncorrelated steps. As a result, even a moderate increase in the episode horizon $T$ leads to a massive explosion in variance, requiring a prohibitively large number of samples to obtain stable gradient estimates.

In Part 2: Baselines, we explore how centering the return around a baseline systematically drops this variance down to quadratic ($O(T^2)$).

Citing

If you find this blog post useful, please consider citing as:

Policy Gradients Part 1: The REINFORCE Estimator, Fabian Pedregosa, 2026

with bibtex entry:

@misc{pedregosa2026policygradient,
  author = {Pedregosa, Fabian},
  title = {Policy Gradients Part 1: The REINFORCE Estimator},
  year = {2026},
  howpublished = {\url{http://fa.bianp.net/blog/2026/policy-gradient/}},
}
  

References