Policy Gradients Part 1: The REINFORCE Estimator
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.
Setup
This is the notation I'll follow throughout the series. An agent interacts with an environment by observing states $s \in \mathcal{S}$, taking actions $a \in \mathcal{A}$, receiving rewards $r(s, a) \in \RR$, and transitioning to a new state $s'$ according to the environment's transition probability distribution ${\color{colordynamics}p(s' | s, a)}$. We write the initial state distribution over $s_0 \in \mathcal{S}$ simply as ${\color{colordynamics}p(s_0)}$.
The agent's behavior is determined by a policy ${\color{colorpolicy}\pi_\theta(a | s)}$, which maps states to distributions over actions. This policy has parameters $\theta \in \RR^d$, and we'd like to find parameters that maximize the expected return: \begin{equation}\label{eq:objective} J(\theta) \defas \EE_{\tau \sim {\color{colorpolicy}\pi_\theta}}\left[ {\color{colorreturn}R(\tau)} \right] = \int p(\tau | \theta) \, {\color{colorreturn}R(\tau)} \, \dif\tau\,, \end{equation} where ${\color{colorreturn}R(\tau)} = \sum_{t=0}^{T-1} {\color{colorreturn}r_t}$ is the return of a trajectory $\tau = (s_0, a_0, s_1, a_1, \ldots, s_{T-1}, a_{T-1}, s_T)$, with per-step reward ${\color{colorreturn}r_t} \defas r(s_t, a_t)$, $T$ is the trajectory length or horizon (which may be fixed or determined by the environment when reaching a terminal state), and $p(\tau | \theta)$ is the probability of observing that trajectory $\tau$ under policy ${\color{colorpolicy}\pi_\theta}$. For simplicity, we focus here 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 discount factor $\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.
When Things Go South
Suppose we want to maximize the expected return $J(\theta)$ using gradient ascent.
Writing out the gradient of the expected return gives:
\begin{equation}\label{eq:naive_grad}
\nabla_\theta J(\theta) = \nabla_\theta \int p(\tau | \theta) {\color{colorreturn}R(\tau)} \dif\tau = \int
\nabla_\theta p(\tau | \theta) {\color{colorreturn}R(\tau)} \dif\tau\,.
\end{equation}
To evaluate this integral, we need to compute the gradient of the trajectory probability $\nabla_\theta p(\tau |
\theta)$.
Using the chain rule of probability, the probability of a trajectory $\tau$ under policy
${\color{colorpolicy}\pi_\theta}$ is a product of initial state probabilities, policy choices, and environment
transitions:
Now we hit a wall. To compute $\nabla_\theta p(\tau | \theta)$, we would need to differentiate this product with respect to $\theta$. But the product contains the environment's transition dynamics ${\color{colordynamics}p(s_{t+1} | s_t, a_t)}$, which are typically a black box: a robot arm colliding with an object involves discontinuous contact forces, and a board game advances by discrete rules. In either case, we do not have analytical or differentiable access to the transition function, so we cannot compute $\nabla_\theta p(\tau | \theta)$ directly.
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).
This identity lets us rewrite the problematic gradient $\nabla_\theta p(\tau | \theta)$ in terms of $\nabla_\theta \log p(\tau | \theta)$, converting the integral into an expectation: \begin{align} \nabla_\theta J(\theta) &\stackrel{\eqref{eq:naive_grad}}{=} \int \left( \nabla_\theta p(\tau | \theta) \right) {\color{colorreturn}R(\tau)} \dif\tau \nonumber \\ &\stackrel{\eqref{eq:log_derivative_trick}}{=} \int p(\tau | \theta) \nabla_\theta \log p(\tau | \theta) {\color{colorreturn}R(\tau)} \dif\tau \nonumber \\ &\stackrel{\eqref{eq:objective}}{=} \EE_{\tau \sim {\color{colorpolicy}\pi_\theta}}\left[ {\color{colorreturn}R(\tau)} \nabla_\theta \log p(\tau | \theta) \right]\,. \label{eq:rl_score_sub} \end{align} We have traded the intractable $\nabla_\theta p(\tau | \theta)$ for $\nabla_\theta \log p(\tau | \theta)$ 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(\tau | \theta)$, 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(\tau | \theta) = \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(\tau | \theta) = \underbrace{\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(\tau | \theta) = \sum_{t=0}^{T-1} \nabla_\theta \log {\color{colorpolicy}\pi_\theta(a_t | s_t)} \,. \end{equation}
The REINFORCE Estimator
Substituting $\eqref{eq:grad_log_simplified}$ back into $\eqref{eq:rl_score_sub}$ gives our fundamental result, the
REINFORCE estimator:
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 {\color{colorpolicy}\pi_\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),
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 {\color{colorpolicy}\pi_\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".
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$.
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}
To derive this bound, let's write the estimator as a sum of per-step gradient contributions: $\hat{g}(\tau) =
\sum_{t=0}^{T-1} \nabla_\theta \log {\color{colorpolicy}\pi_\theta(a_t | s_t)} \, {{\color{colorreturn}R(\tau)}}$.
Using the definition of total variance $\text{Var}(\hat{g}) \defas \EE[\|\hat{g} - \EE[\hat{g}]\|^2] =
\EE[\|\hat{g}\|^2] - \|\EE[\hat{g}]\|^2$, we have
\begin{align}
\text{Var}(\hat{g}) &= \EE\left[\left\|\sum_{t=0}^{T-1} \nabla_\theta \log {\color{colorpolicy}\pi_\theta(a_t |
s_t)} \, {{\color{colorreturn}R(\tau)}}\right\|^2\right] - \|\nabla_\theta J(\theta)\|^2 \nonumber \\
&\leq \EE\left[\left\|\sum_{t=0}^{T-1} \nabla_\theta \log {\color{colorpolicy}\pi_\theta(a_t | s_t)} \,
{{\color{colorreturn}R(\tau)}}\right\|^2\right]\,, \label{eq:var_first_step}
\end{align}
where in the last inequality we have dropped the non-negative term $\|\nabla_\theta J(\theta)\|^2$.
Inside the inner expectation, the only remaining randomness is the action $a_{t'}$ (by conditioning,
everything up to $s_{t'}$ is fixed). Since $t < t'$, $X_t$ is fully determined by the conditioning set and can
be pulled out of the inner expectation. Furthermore, since $X_{t'}$ depends only on $s_{t'}$ and $a_{t'}$,
and $a_{t'}$ is drawn from ${\color{colorpolicy}\pi_\theta(\cdot \mid s_{t'})}$, we have $\EE[X_{t'} \mid
s_0, a_0, \ldots, s_{t'}]=\EE[X_{t'} \mid s_{t'}]=0$, giving us:
\begin{equation}\label{eq:uncorrelated_scores} \EE[X_t^\top X_{t'}]=\EE\Big[X_t^\top \underbrace{\EE[X_{t'}
\mid s_{t'}]}_{\stackrel{\eqref{eq:zero_score_mean}}{=}\, 0}\Big]=0\,. \end{equation} Therefore, score
vectors across different steps act as uncorrelated increments with zero conditional mean, so cross-terms
vanish when expanding the squared norm.
2️⃣ The return ${{\color{colorreturn}R(\tau)}}^2$ scales as $O(T^2)$. Using the bounded rewards assumption ($|{\color{colorreturn}r_t}| \leq {\color{colorreturn}r_{\max}}$), we have $|{\color{colorreturn}R(\tau)}| = |\sum_{t=0}^{T-1} {\color{colorreturn}r_t}| \leq T {\color{colorreturn}r_{\max}}$. \begin{equation}\label{eq:return_bound} {{\color{colorreturn}R(\tau)}}^2 \le T^2 {\color{colorreturn}r_{\max}}^2 = O(T^2)\,. \end{equation}
3️⃣ Summing over all time steps.
Substituting the return bound \eqref{eq:return_bound} into our per-step sum \eqref{eq:per_step_decomp}, and
applying the bounded score variance assumption ($\EE[\|X_t\|^2] \leq C$ for all $t$),
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)$.
Shrinking Return Scope: Reward-to-Go
In the above REINFORCE estimator, step $t$'s score $\nabla_\theta \log {\color{colorpolicy}\pi_\theta(a_t | s_t)}$ is multiplied by the full trajectory return ${\color{colorreturn}R(\tau)} = \sum_{k=0}^{T-1} {\color{colorreturn}r_k}$. Splitting this return into past ($k < t$) and future ($k \ge t$) rewards relative to step $t$ gives: $$\hat{g}(\tau)=\sum_{t=0}^{T-1} \nabla_\theta \log {\color{colorpolicy}\pi_\theta(a_t | s_t)} \left( \sum_{k=0}^{t-1} {\color{colorreturn}r_k} + \sum_{k=t}^{T-1} {\color{colorreturn}r_k} \right)\,.$$
Notice that past rewards ${\color{colorreturn}r_k}$ ($k < t$) are already determined before action $a_t$ is
chosen. By the score function identity,
Under bounded rewards ($|{\color{colorreturn}r_t}| \le {\color{colorreturn}r_{\max}}$) and bounded score variance ($\EE[\|\nabla_\theta \log {\color{colorpolicy}\pi_\theta(a_t | s_t)}\|^2] \le C$), the variance of Reward-to-Go is bounded by: \begin{align} \text{Var}(\hat{g}_{\text{RTG}}(\tau)) &\le {\color{colorreturn}r_{\max}}^2 C \frac{T(T+1)(2T+1)}{6} \nonumber \\ &= \boxed{\frac{1}{3}} ~T^3 {\color{colorreturn}r_{\max}}^2 C + O(T^2)\,.\label{eq:rtg_variance_bound} \end{align} Compared to vanilla REINFORCE, whose variance is bounded by $T^3 {\color{colorreturn}r_{\max}}^2 C$ (derived above), Reward-to-Go achieves an asymptotic factor of three improvement.
Because the orthogonal score decomposition $\eqref{eq:uncorrelated_scores}$ relies purely on the zero conditional mean of action scores $\eqref{eq:zero_score_mean}$ rather than the return multiplier, the per-step decomposition $\eqref{eq:per_step_decomp}$ holds identically when replacing ${\color{colorreturn}R(\tau)}$ with the future return ${\color{colorreturn}G_t} = \sum_{k=t}^{T-1} {\color{colorreturn}r_k}$, we have: \begin{equation}\label{eq:rtg_per_step} \text{Var}(\hat{g}_{\text{RTG}}) \stackrel{\eqref{eq:var_first_step}, \eqref{eq:per_step_decomp}}{\le} \sum_{t=0}^{T-1} \EE\left[ \|\nabla_\theta \log {\color{colorpolicy}\pi_\theta(a_t | s_t)}\|^2 \, {\color{colorreturn}G_t}^2 \right]\,. \end{equation}
Whereas the full trajectory return is uniformly bounded by $\eqref{eq:return_bound}$ as $T^2 {\color{colorreturn}r_{\max}}^2$, each future return is bounded by ${\color{colorreturn}G_t}^2 \le (T - t)^2 {\color{colorreturn}r_{\max}}^2$. Substituting this step-dependent bound alongside the score variance limit ($\EE[\|\nabla_\theta \log {\color{colorpolicy}\pi_\theta(a_t | s_t)}\|^2] \le C$) into $\eqref{eq:rtg_per_step}$ yields: \begin{equation}\label{eq:rtg_second_moment} \text{Var}(\hat{g}_{\text{RTG}}) \le {\color{colorreturn}r_{\max}}^2 C \sum_{t=0}^{T-1} (T - t)^2\,. \end{equation} Applying the sum-of-squares identity $\sum_{t=0}^{T-1} (T - t)^2 = \sum_{k=1}^T k^2 = \frac{T(T+1)(2T+1)}{6}$, we obtain $\text{Var}(\hat{g}_{\text{RTG}}) \le \boxed{\frac{1}{3}}\, T^3 {\color{colorreturn}r_{\max}}^2 C + O(T^2)$, completing the proof.
While Reward-to-Go does not change the cubic $O(T^3)$ scaling, this factor-of-three reduction still provides a substantial improvement over the vanilla estimator.
To verify this theoretical reduction, we simulated both estimators across varying trajectory lengths $T \in \{5, 10, \ldots, 640\}$. As shown below, both scale cubically ($\Theta(T^3)$) with log-log slopes near 3, yet Reward-to-Go consistently achieves a $3\times$ variance reduction, matching the asymptotic limit as $T$ grows.
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.
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/}},
}