Challenges in Basic Policy Gradients

Policy gradient methods, such as REINFORCE, provide a direct approach to optimizing parameterized policies. However, these methods frequently face significant practical difficulties, particularly in complex environments. Addressing these challenges drives the creation of more advanced Actor-Critic algorithms.

Recall the basic policy gradient update, derived from the Policy Gradient Theorem. For an objective function $J(\theta)$ representing the expected total return, the gradient is estimated as:

$$\nabla_\theta J(\theta) = \mathbb{E}_{\tau \sim \pi_\theta} \left[ \sum_{t=0}^{T-1} \nabla_\theta \log \pi_\theta(a_t|s_t) G_t \right]$$

Here, $\tau$ is a trajectory $(s_0, a_0, r_1, s_1, a_1, ..., s_{T-1}, a_{T-1}, r_T, s_T)$ generated by following the policy $\pi_\theta$, and $G_t = \sum_{k=t}^{T-1} \gamma^{k-t} R_{k+1}$ is the discounted return starting from timestep $t$. In practice, this expectation is approximated using Monte Carlo sampling, averaging the gradient components over multiple trajectories collected using the current policy $\pi_\theta$.

High Variance in Gradient Estimates

The most prominent issue with basic policy gradient methods like REINFORCE is the high variance of the gradient estimates. This variance stems directly from the use of the Monte Carlo return $G_t$ as the scaling factor for the policy gradient term $\nabla_\theta \log \pi_\theta(a_t|s_t)$.

Why is $G_t$ noisy:

1. Stochasticity: The return $G_t$ depends on all subsequent actions $a_k$ (for $k \ge t$) and state transitions $p(s_{k+1}|s_k, a_k)$ (for $k \ge t$), which are often stochastic. Even from the same state $s_t$, executing the same policy can lead to very different trajectories and accumulated rewards simply due to the randomness in the environment or the policy itself.
2. Long Trajectories: In environments with long episodes, the return $G_t$ accumulates rewards over many steps. The effect of randomness compounds over time, making the final return highly variable. A single early random event can drastically alter the rest of the trajectory and its total return.

This high variance means that the gradient estimate obtained from a finite batch of trajectories can be very noisy. The estimated gradient direction might point far away from the true gradient direction, leading to several problems:

• Slow Convergence: Learning requires averaging over many trajectories to get a reliable signal, significantly slowing down the learning process.
• Instability: Noisy updates can cause the policy performance to oscillate wildly or even diverge. The policy might temporarily worsen significantly before finding an improvement path.
• Sensitivity: The learning process becomes highly sensitive to the choice of learning rate and initialization parameters.

Illustrative comparison of learning progress with high-variance gradient updates (typical of basic policy gradients) versus smoother, lower-variance updates. High variance can lead to erratic and slower overall improvement.

Sample Inefficiency

High variance directly contributes to sample inefficiency. Because each sample trajectory provides such a noisy estimate of the gradient, a large number of trajectories must be collected under the current policy to obtain a reasonably accurate update direction. This makes learning expensive in terms of interaction time and data requirements, especially compared to some value-based methods that can learn more effectively from individual transitions using bootstrapping (though bootstrapping introduces its own biases).

Furthermore, standard REINFORCE typically waits until the end of an episode to calculate the returns $G_t$ and perform updates. This means learning signals are delayed, and information from intermediate rewards is not used as promptly as in Temporal Difference (TD) methods.

The Credit Assignment Problem

Another related difficulty is the credit assignment problem. The basic REINFORCE algorithm updates the probability of all actions taken in a trajectory based on the total return $G_t$ (or often just $G_0$). If a trajectory yields a high total return, all actions within that trajectory are reinforced, even if some specific actions were actually detrimental but were counteracted by later lucky circumstances or good actions. Conversely, a single bad action leading to a poor overall return might unfairly penalize preceding good actions.

Using the return from the current time step onwards, $G_t$, instead of the total return $G_0$, helps alleviate this by only reinforcing actions based on subsequent rewards. However, $G_t$ still aggregates rewards over potentially many steps, making it difficult to isolate the immediate consequence of action $a_t$. The variance issue persists, as $G_t$ remains a noisy estimate of the action's true value.

These challenges. high variance, sample inefficiency, and difficult credit assignment. necessitate improvements over the basic policy gradient formulation. Actor-Critic methods, which we explore next, directly target the high variance issue by introducing a learned value function (the critic) to provide more stable and informative evaluations of the actor's actions, replacing or augmenting the noisy Monte Carlo returns $G_t$. This forms the basis for developing more stable and efficient policy optimization algorithms.