Abstract
Policy gradient methods have demonstrated success in reinforcement learning tasks that have high-dimensional continuous state and action spaces. However, policy gradient methods are also notoriously sample inefficient. This can be attributed, at least in part, to the high variance in estimating the gradient of the task objective with Monte Carlo methods. Previous research has endeavored to contend with this problem by studying control variates (CVs) that can reduce the variance of estimates without introducing bias, including the early use of baselines, state dependent CVs, and the more recent state-action dependent CVs. In this work, we analyze the properties and drawbacks of previous CV techniques and, surprisingly, we find that these works have overlooked an important fact that Monte Carlo gradient estimates are generated by trajectories of states and actions. We show that ignoring the correlation across the trajectories can result in suboptimal variance reduction, and we propose a simple fix: a class of "trajectory-wise" CVs, that can further drive down the variance. We show that constructing trajectory-wise CVs can be done recursively and requires only learning state-action value functions like the previous CVs for policy gradient. We further prove that the proposed trajectory-wise CVs are optimal for variance reduction under reasonable assumptions.
Introduction
Reinforcement Learning (RL) using policy gradients, such as the REINFORCE algorithm, is a powerful framework for continuous control. However, these methods suffer from extreme sample inefficiency due to high variance in Monte Carlo gradient estimates. This noise originates from three primary sources: the agent's history, the randomness of the current action, and the stochasticity of all future actions and state transitions within the trajectory.
While traditional "baselines" (state-dependent) and "critics" (state-action dependent) mitigate some of this noise, they often ignore correlations across the entire trajectory. As the task horizon increases, this ignored future noise becomes the dominant source of variance, significantly hindering the learning process.
Methodology: Trajectory-wise Control Variates (TrajCV)
The core contribution of this work is the introduction of TrajCV, a "Divide-and-Conquer" strategy to systematically eliminate variance by accounting for the chronological structure of trajectories ($S_t \to A_t \to S_{t+1} \to A_{t+1} \dots$).
Variance Decomposition and Recursive Computation
TrajCV utilizes the law of total variance to decompose the gradient's variance into a sequence of terms. Unlike previous methods that only subtract a baseline at the current time step, TrajCV recursively adds terms that cancel out variance from future actions. This can be implemented using standard state-action value function ($Q$-function) approximators without requiring an environment dynamics model.
As illustrated in Figure 2(b), while standard state-action CVs (red) only address local variance at a specific time step, TrajCV (blue) covers the cumulative variance across the trajectory, leading to much more effective reduction. The authors mathematically prove that this chronological ordering is the optimal way to structure control variates when environment dynamics are unknown.
Policy Reparameterization
To facilitate the construction of these control variates, the authors utilize policy reparameterization. This involves expressing the action $A_k$ as a deterministic function $\omega$ of the state $S_k$ and a random variable $R_k$. This structural change allows for more precise variance reduction by isolating the sources of randomness.
Experimental Evaluation
The proposed method was evaluated on the CartPole balancing task within the OpenAI Gym environment, using the DART physics engine. To test the limits of TrajCV, the researchers focused on long-horizon versions of the task ($h=1000, 2000, \text{and } 4000$ steps).
Key Results
- Superior Convergence: TrajCV consistently outperformed vanilla Monte Carlo (REINFORCE), state-dependent baselines, and state-action dependent CVs (e.g., Q-prop). The performance gap widened as the horizon $h$ increased, proving TrajCV's effectiveness for long-term tasks.
- Empirical Validation: Experiments confirmed that future trajectory randomness dominates variance during the rapid improvement phase. Neutralizing this term allowed agents to reach peak performance significantly faster.
- Robustness: Even with simple linearizations or Monte Carlo sampling for $Q$-function approximation, TrajCV provided a noticeable boost in learning speed compared to previous state-of-the-art techniques.
Conclusion
TrajCV offers a theoretically grounded and practically effective way to reduce variance in policy gradient methods without introducing bias. While its effectiveness depends on the quality of the $Q$-function approximation, it remains a robust, model-free friendly tool that significantly accelerates learning in complex, long-horizon tasks.
Summary updated