Understanding Variance in Policy Gradients

The REINFORCE algorithm is a method for directly optimizing the policy parameters $\theta$ based on the gradient of the expected return. Its main idea is to increase the probability of actions that lead to higher returns and decrease the probability of actions leading to lower returns. In the simplest Monte Carlo version of REINFORCE, the gradient estimate for a single trajectory is proportional to:

$$\sum_{t=0}^{T-1} G_t \nabla_\theta \log \pi(A_t|S_t; \theta)$$

Here, $G_t = \sum_{k=t+1}^T \gamma^{k-t-1} R_k$ is the total discounted return experienced starting from state $S_t$ and taking action $A_t$ in that specific episode. While this estimate is unbiased (meaning its expected value is the true gradient $\nabla_\theta J(\theta)$), it often suffers from a significant practical problem: high variance.

The Problem of High Variance

Variance refers to how much a random variable deviates from its expected value. In the context of REINFORCE, the gradient estimate $G_t \nabla_\theta \log \pi(A_t|S_t; \theta)$ can vary dramatically from one episode (or even one time step) to the next.

Why does this happen? It stems directly from the use of the Monte Carlo return $G_t$.

1. Dependence on Full Trajectories: $G_t$ depends on the entire sequence of rewards received after time step $t$ in a single, specific episode. RL environments are often stochastic, meaning the same action in the same state can lead to different next states and rewards. Furthermore, the agent's policy itself might be stochastic.
2. Sensitivity to Randomness: A few lucky or unlucky outcomes (high or low rewards) later in the episode can drastically change the value of $G_t$. This means that even if an action $A_t$ taken in state $S_t$ is generally good on average, a single unlucky trajectory might yield a very low $G_t$, incorrectly telling the algorithm to decrease the probability of that action. Conversely, a generally poor action might accidentally be followed by a sequence of fortunate events, leading to a high $G_t$ and an incorrect update signal.

Consider an agent learning to play a game. An action taken early in the game might be strategically sound, but if the agent happens to get unlucky with random events much later, the resulting $G_t$ might be very low or even negative. The REINFORCE update would then penalize this initially good action based on outcomes that were largely unrelated to the action itself.

Consequences of High Variance

High variance in the gradient estimates has several negative consequences for the learning process:

• Slow Convergence: Because individual gradient estimates are so noisy, the learning process requires many samples (episodes) to average out this noise and find the true underlying gradient direction. This can make training extremely slow, especially in complex environments.
• Instability: The parameter updates $\Delta \theta$ can fluctuate wildly from one iteration to the next. The learning process might appear erratic, with performance jumping up and down rather than improving steadily. It becomes difficult to choose a suitable learning rate $\alpha$. A large $\alpha$ might cause the parameters to diverge due to large, noisy updates, while a very small $\alpha$ exacerbates the slow convergence problem.

Imagine trying to find the bottom of a valley (representing the optimal policy parameters) by taking steps based on very noisy measurements of the slope. Each measurement might point you in a wildly different direction. Only by averaging many noisy measurements can you get a reliable sense of the actual downhill direction. REINFORCE faces a similar challenge.

High variance estimates fluctuate significantly around the true gradient direction, making learning unstable. Low variance estimates provide a more consistent signal, leading to smoother convergence.

The core issue is that the magnitude of the update step, determined by $G_t$, is noisy. We are multiplying the score function $\nabla_\theta \log \pi(A_t|S_t; \theta)$ (which tells us which direction to nudge the parameters to make action $A_t$ more or less likely) by a potentially unreliable estimate of how good that action actually was in the long run for that specific trajectory.

This variance problem is a major challenge for basic policy gradient methods. Fortunately, there are ways to mitigate it. The next section introduces a common and effective technique: using baselines to reduce variance while keeping the gradient estimate unbiased.