# Sample Efficient Reinforcement Learning with REINFORCE

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

## Key facts

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

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

- [ReMax: A Simple, Effective, and Efficient Reinforcement Learning Method for Aligning Large Language Models](https://mlsanity.com/paper/2310.10505/) (2023)
- [Recent Advances in Reinforcement Learning in Finance](https://mlsanity.com/paper/2112.04553/) (2021)
- [A Review of Large Language Models and Autonomous Agents in Chemistry](https://mlsanity.com/paper/2407.01603/) (2024)
- [Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence](https://mlsanity.com/paper/2105.11066/) (2021)
- [A general sample complexity analysis of vanilla policy gradient](https://mlsanity.com/paper/2107.11433/) (2021)
- [On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method](https://mlsanity.com/paper/2102.08607/) (2021)
- [Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies](https://mlsanity.com/paper/2302.01734/) (2023)
- [Softmax Policy Gradient Methods Can Take Exponential Time to Converge](https://mlsanity.com/paper/2102.11270/) (2021)
- [Consistent Paths Lead to Truth: Self-Rewarding Reinforcement Learning for LLM Reasoning](https://mlsanity.com/paper/2506.08745/) (2025)
- [Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHF](https://mlsanity.com/paper/2402.06886/) (2024)
- [Single-Rollout Asynchronous Optimization for Agentic Reinforcement Learning](https://mlsanity.com/paper/2607.07508/) (2026)
- [Verifying Learning-Based Robotic Navigation Systems](https://mlsanity.com/paper/2205.13536/) (2022)
- [Navigating to the Best Policy in Markov Decision Processes](https://mlsanity.com/paper/2106.02847/) (2021)
- [Domain Adaptive Fake News Detection via Reinforcement Learning](https://mlsanity.com/paper/2202.08159/) (2022)
- [On the Global Optimum Convergence of Momentum-based Policy Gradient](https://mlsanity.com/paper/2110.10116/) (2021)
- [Policy Gradient Methods Find the Nash Equilibrium in N-player General-sum Linear-quadratic Games](https://mlsanity.com/paper/2107.13090/) (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)
- [Just One Byte (per gradient): A Note on Low-Bandwidth Decentralized Language Model Finetuning Using Shared Randomness](https://mlsanity.com/paper/2306.10015/) (2023)
- [Bregman Gradient Policy Optimization](https://mlsanity.com/paper/2106.12112/) (2021)
- [Understanding the Complexity Gains of Single-Task RL with a Curriculum](https://mlsanity.com/paper/2212.12809/) (2022)
- [QuantFactor REINFORCE: Mining Steady Formulaic Alpha Factors with Variance-bounded REINFORCE](https://mlsanity.com/paper/2409.05144/) (2024)
- [On the Sample Complexity and Metastability of Heavy-tailed Policy Search in Continuous Control](https://mlsanity.com/paper/2106.08414/) (2021)
- [On the Hidden Biases of Policy Mirror Ascent in Continuous Action Spaces](https://mlsanity.com/paper/2201.12332/) (2022)
- [Verifying Generalization in Deep Learning](https://mlsanity.com/paper/2302.05745/) (2023)
- [Iterative Self-Incentivization Empowers Large Language Models as Agentic Searchers](https://mlsanity.com/paper/2505.20128/) (2025)
- [Efficient Exploration via Epistemic-Risk-Seeking Policy Optimization](https://mlsanity.com/paper/2302.09339/) (2023)
- [Stochastic Gradient Succeeds for Bandits](https://mlsanity.com/paper/2402.17235/) (2024)
- [Offline-Boosted Actor-Critic: Adaptively Blending Optimal Historical Behaviors in Deep Off-Policy RL](https://mlsanity.com/paper/2405.18520/) (2024)

## Abstract (arXiv)

Policy gradient methods are among the most effective methods for large-scale reinforcement learning, and their empirical success has prompted several works that develop the foundation of their global convergence theory. However, prior works have either required exact gradients or state-action visitation measure based mini-batch stochastic gradients with a diverging batch size, which limit their applicability in practical scenarios. In this paper, we consider classical policy gradient methods that compute an approximate gradient with a single trajectory or a fixed size mini-batch of trajectories under soft-max parametrization and log-barrier regularization, along with the widely-used REINFORCE gradient estimation procedure. By controlling the number of "bad" episodes and resorting to the classical doubling trick, we establish an anytime sub-linear high probability regret bound as well as almost sure global convergence of the average regret with an asymptotically sub-linear rate. These provide the first set of global convergence and sample efficiency results for the well-known REINFORCE algorithm and contribute to a better understanding of its performance in practice.