# Beyond variance reduction: Understanding the true impact of baselines on policy optimization

arXiv: https://arxiv.org/abs/2008.13773 · HTML: https://mlsanity.com/paper/2008.13773/

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Aug 2020.

## Built on by (most cited first, 30 of 32)

- [TreeRL: LLM Reinforcement Learning with On-Policy Tree Search](https://mlsanity.com/paper/2506.11902/) (2025)
- [Tapered Off-Policy REINFORCE: Stable and efficient reinforcement learning for LLMs](https://mlsanity.com/paper/2503.14286/) (2025)
- [On Proximal Policy Optimization's Heavy-tailed Gradients](https://mlsanity.com/paper/2102.10264/) (2021)
- [Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2110.10117/) (2021)
- [The Role of Baselines in Policy Gradient Optimization](https://mlsanity.com/paper/2301.06276/) (2023)
- [Understanding the Effect of Stochasticity in Policy Optimization](https://mlsanity.com/paper/2110.15572/) (2021)
- [PAGE-PG: A Simple and Loopless Variance-Reduced Policy Gradient Method with Probabilistic Gradient Estimation](https://mlsanity.com/paper/2202.00308/) (2022)
- [Momentum-Based Policy Gradient with Second-Order Information](https://mlsanity.com/paper/2205.08253/) (2022)
- [Stochastic Gradient Succeeds for Bandits](https://mlsanity.com/paper/2402.17235/) (2024)
- [An Alternate Policy Gradient Estimator for Softmax Policies](https://mlsanity.com/paper/2112.11622/) (2021)
- [Averaging n-step Returns Reduces Variance in Reinforcement Learning](https://mlsanity.com/paper/2402.03903/) (2024)
- [Knowledge Infused Policy Gradients with Upper Confidence Bound for Relational Bandits](https://mlsanity.com/paper/2106.13895/) (2021)
- [When Bioprocess Engineering Meets Machine Learning: A Survey from the Perspective of Automated Bioprocess Development](https://mlsanity.com/paper/2209.01083/) (2022)
- [Non-Uniform Noise-to-Signal Ratio in the REINFORCE Policy-Gradient Estimator](https://mlsanity.com/paper/2602.01460/) (2026)
- [Behind the Myth of Exploration in Policy Gradients](https://mlsanity.com/paper/2402.00162/) (2024)
- [Multi-level Advantage Credit Assignment for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2508.06836/) (2025)
- [Robust Policy Optimization to Prevent Catastrophic Forgetting](https://mlsanity.com/paper/2602.08813/) (2026)
- [A Reinforcement Learning Approach to Domain-Knowledge Inclusion Using Grammar Guided Symbolic Regression](https://mlsanity.com/paper/2202.04367/) (2022)
- [On Advantage Estimates for Max@K Policy Gradients](https://mlsanity.com/paper/2606.06080/) (2026)
- [Coordinate-wise Control Variates for Deep Policy Gradients](https://mlsanity.com/paper/2107.04987/) (2021)
- [Coordinate Ascent for Off-Policy RL with Global Convergence Guarantees](https://mlsanity.com/paper/2212.05237/) (2022)
- [Target-independent XLA optimization using Reinforcement Learning](https://mlsanity.com/paper/2308.14364/) (2023)
- [Stabilizing Policy Gradient Methods via Reward Profiling](https://mlsanity.com/paper/2511.16629/) (2025)
- [How Log-Barrier Helps Exploration in Policy Optimization](https://mlsanity.com/paper/2603.15001/) (2026)
- [Variance Reduction for Score Functions Using Optimal Baselines](https://mlsanity.com/paper/2212.13587/) (2022)
- [Gradient Estimation and Variance Reduction in Stochastic and Deterministic Models](https://mlsanity.com/paper/2405.08661/) (2024)
- [Breaking Habits: On the Role of the Advantage Function in Learning Causal State Representations](https://mlsanity.com/paper/2506.11912/) (2025)
- [Reducing the Probability of Undesirable Outputs in Language Models Using Probabilistic Inference](https://mlsanity.com/paper/2510.21184/) (2025)
- [Kernel-Based Safe Exploration in Deep Reinforcement Learning](https://mlsanity.com/paper/2605.22207/) (2026)
- [Low Variance Trust Region Optimization with Independent Actors and Sequential Updates in Cooperative Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2606.25526/) (2026)

## Abstract (arXiv)

Bandit and reinforcement learning (RL) problems can often be framed as optimization problems where the goal is to maximize average performance while having access only to stochastic estimates of the true gradient. Traditionally, stochastic optimization theory predicts that learning dynamics are governed by the curvature of the loss function and the noise of the gradient estimates. In this paper we demonstrate that this is not the case for bandit and RL problems. To allow our analysis to be interpreted in light of multi-step MDPs, we focus on techniques derived from stochastic optimization principles (e.g., natural policy gradient and EXP3) and we show that some standard assumptions from optimization theory are violated in these problems. We present theoretical results showing that, at least for bandit problems, curvature and noise are not sufficient to explain the learning dynamics and that seemingly innocuous choices like the baseline can determine whether an algorithm converges. These theoretical findings match our empirical evaluation, which we extend to multi-state MDPs.