mlsanityData to 14 Oct 2026

Sample Efficient Reinforcement Learning with REINFORCE

arXiv 2010.11364 ↗First posted 22 Oct 2020cs.LG math.OCcited by 86

Not on the map. Why?

Cited by 24 in Deep reinforcement learning methods, but placed by its own abstract, which didn’t fit.

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 16; 2022: 8; 2023: 10; 2024: 13; 2025: 21; 2026: 18.

86 papers.

Sort:

By area:

  1. 2023ReMax: A Simple, Effective, and Efficient Reinforcement Learning Method for Aligning Large Language Modelscited by 187
  2. 2021Recent Advances in Reinforcement Learning in Financecited by 110
  3. 2024A Review of Large Language Models and Autonomous Agents in Chemistrycited by 99
  4. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 84
  5. 2021A general sample complexity analysis of vanilla policy gradientcited by 76
  6. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 70
  7. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 58
  8. 2021Softmax Policy Gradient Methods Can Take Exponential Time to Convergecited by 48
  9. 2025Consistent Paths Lead to Truth: Self-Rewarding Reinforcement Learning for LLM Reasoningcited by 46
  10. 2024Principled Penalty-based Methods for Bilevel Reinforcement Learning and RLHFcited by 41
  11. 2026Single-Rollout Asynchronous Optimization for Agentic Reinforcement Learningcited by 37
  12. 2022Verifying Learning-Based Robotic Navigation Systemscited by 33
38 more
  1. 2021Navigating to the Best Policy in Markov Decision Processescited by 29
  2. 2022Domain Adaptive Fake News Detection via Reinforcement Learningcited by 27
  3. 2021On the Global Optimum Convergence of Momentum-based Policy Gradientcited by 26
  4. 2021Policy Gradient Methods Find the Nash Equilibrium in N-player General-sum Linear-quadratic Gamescited by 25
  5. 2021Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy Gradient Methods with Entropy Regularizationcited by 25
  6. 2023The Role of Baselines in Policy Gradient Optimizationcited by 25
  7. 2021Understanding the Effect of Stochasticity in Policy Optimizationcited by 18
  8. 2023Just One Byte (per gradient): A Note on Low-Bandwidth Decentralized Language Model Finetuning Using Shared Randomnesscited by 18
  9. 2021Bregman Gradient Policy Optimizationcited by 17
  10. 2022Understanding the Complexity Gains of Single-Task RL with a Curriculumcited by 17
  11. 2024QuantFactor REINFORCE: Mining Steady Formulaic Alpha Factors with Variance-bounded REINFORCEcited by 14
  12. 2021On the Sample Complexity and Metastability of Heavy-tailed Policy Search in Continuous Controlcited by 12
  13. 2022On the Hidden Biases of Policy Mirror Ascent in Continuous Action Spacescited by 11
  14. 2023Verifying Generalization in Deep Learningcited by 11
  15. 2025Iterative Self-Incentivization Empowers Large Language Models as Agentic Searcherscited by 11
  16. 2023Efficient Exploration via Epistemic-Risk-Seeking Policy Optimizationcited by 10
  17. 2024Stochastic Gradient Succeeds for Banditscited by 10
  18. 2024Offline-Boosted Actor-Critic: Adaptively Blending Optimal Historical Behaviors in Deep Off-Policy RLcited by 10
  19. 2025From Screens to Scenes: A Survey of Embodied AI in Healthcarecited by 10
  20. 2023GRACE: Loss-Resilient Real-Time Video through Neural Codecscited by 9
  21. 2026MedSAM-Agent: Empowering Interactive Medical Image Segmentation with Multi-turn Agentic Reinforcement Learningcited by 8
  22. 2021Theoretical Guarantees of Fictitious Discount Algorithms for Episodic Reinforcement Learning and Global Convergence of Policy Gradient Methodscited by 7
  23. 2024SEE-DPO: Self Entropy Enhanced Direct Preference Optimizationcited by 7
  24. 2025Breaking the Frozen Subspace: Importance Sampling for Low-Rank Optimization in LLM Pretrainingcited by 7
  25. 2025Compiler-R1: Towards Agentic Compiler Auto-tuning with Reinforcement Learningcited by 7
  26. 2021Smoothed functional-based gradient algorithms for off-policy reinforcement learning: A non-asymptotic viewpointcited by 5
  27. 2022Posterior Sampling for Continuing Environmentscited by 4
  28. 2023Policy Gradient Algorithms Implicitly Optimize by Continuationcited by 4
  29. 2024MLDGG: Meta-Learning for Domain Generalization on Graphscited by 4
  30. 2025Small steps no more: Global convergence of stochastic gradient bandits for arbitrary learning ratescited by 4
  31. 2025Learning to Plan Before Answering: Self-Teaching LLMs to Learn Abstract Plans for Problem Solvingcited by 4
  32. 2021Cogment: Open Source Framework For Distributed Multi-actor Training, Deployment & Operationscited by 3
  33. 2024Behind the Myth of Exploration in Policy Gradientscited by 3
  34. 2024Graphs Generalization under Distribution Shiftscited by 3
  35. 2025Learning Constraints-Based Adaptive Hypergraph Neural Networks for Solving Vehicle Routing Problemscited by 3
  36. 2022Understanding Curriculum Learning in Policy Optimization for Online Combinatorial Optimizationcited by 2
  37. 2022Policy Gradient Algorithms with Monte Carlo Tree Learning for Non-Markov Decision Processescited by 2
  38. 2022Scalable and Sample Efficient Distributed Policy Gradient Algorithms in Multi-Agent Networked Systemscited by 2

50 most cited of 86 All 86 (JSON)