mlsanityData to 14 Oct 2026

Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Space

arXiv 2306.01854 ↗First posted 2 Jun 2023cs.LG math.OCcited by 18

Not on the map. Why?

Abstract (arXiv)

We consider the reinforcement learning (RL) problem with general utilities which consists in maximizing a function of the state-action occupancy measure. Beyond the standard cumulative reward RL setting, this problem includes as particular cases constrained RL, pure exploration and learning from demonstrations among others. For this problem, we propose a simpler single-loop parameter-free normalized policy gradient algorithm. Implementing a recursive momentum variance reduction mechanism, our algorithm achieves tildeO(ε-3) and tildeO(ε-2) sample complexities for ε-first-order stationarity and ε-global optimality respectively, under adequate assumptions. We further address the setting of large finite state action spaces via linear function approximation of the occupancy measure and show a tildeO(ε-4) sample complexity for a simple policy gradient method with a linear regression subroutine.

Key facts. Cited by 18 papers in the map (data through 14 Oct 2026). Builds on 41 of its 61 references that are in the map. First posted on arXiv 2 Jun 2023.

Builds on

41 of 61 references.

References · 41

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2015Trust Region Policy Optimizationcited by 2,580
  3. 2016OpenAI Gymcited by 1,736
  4. 2018Diversity is All You Need: Learning Skills without a Reward Functioncited by 752
  5. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 306
  6. 2018Provably Efficient Maximum Entropy Explorationcited by 242
  7. 2019A Divergence Minimization Perspective on Imitation Learning Methodscited by 190
  8. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 159
  9. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 156
  10. 2020Exploration-Exploitation in Constrained MDPscited by 149
  11. 2022On the Convergence Rates of Policy Gradient Methodscited by 119
  12. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 111
29 more
  1. 2020Variational Policy Gradient Method for Reinforcement Learning with General Utilitiescited by 111
  2. 2018Stochastic Variance-Reduced Policy Gradientcited by 106
  3. 2021Reward is enough for convex MDPscited by 84
  4. 2021A general sample complexity analysis of vanilla policy gradientcited by 76
  5. 2021On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Methodcited by 70
  6. 2022An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methodscited by 68
  7. 2019Reinforcement Learning with Convex Constraintscited by 60
  8. 2019Sample Efficient Policy Gradient Methods with Recursive Variance Reductioncited by 60
  9. 2019An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradientcited by 59
  10. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 58
  11. 2021Concave Utility Reinforcement Learning: the Mean-Field Game Viewpointcited by 56
  12. 2022Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policiescited by 46
  13. 2016Stochastic Heavy Ballcited by 42
  14. 2022The Importance of Non-Markovianity in Maximum State Entropy Explorationcited by 35
  15. 2020Momentum-Based Policy Gradient Methodscited by 30
  16. 2022Challenging Common Assumptions in Convex Reinforcement Learningcited by 30
  17. 2021On the Global Optimum Convergence of Momentum-based Policy Gradientcited by 26
  18. 2021Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy Gradient Methods with Entropy Regularizationcited by 25
  19. 2020Stochastic Recursive Momentum for Policy Gradient Methodscited by 24
  20. 2022Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Functioncited by 20
  21. 2022Sharp Analysis of Stochastic Optimization under Global Kurdyka-Lojasiewicz Inequalitycited by 20
  22. 2022Active Exploration via Experiment Design in Markov Chainscited by 19
  23. 2020Cautious Reinforcement Learning via Distributional Risk in the Dual Domaincited by 18
  24. 2020A Hybrid Stochastic Policy Gradient Algorithm for Reinforcement Learningcited by 18
  25. 2022PAGE-PG: A Simple and Loopless Variance-Reduced Policy Gradient Method with Probabilistic Gradient Estimationcited by 17
  26. 2022Momentum-Based Policy Gradient with Second-Order Informationcited by 13
  27. 2021On the Sample Complexity and Metastability of Heavy-tailed Policy Search in Continuous Controlcited by 12
  28. 2022On the Hidden Biases of Policy Mirror Ascent in Continuous Action Spacescited by 11
  29. 2022Policy Gradient for Reinforcement Learning with General Utilitiescited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 8; 2025: 3; 2026: 7.

18 papers.

Sort:

By area:

  1. 2024From Gradient Clipping to Normalization for Heavy Tailed SGDcited by 49
  2. 2025Flow Density Control: Generative Optimization Beyond Entropy-Regularized Fine-Tuningcited by 17
  3. 2024Global Reinforcement Learning: Beyond Linear and Convex Rewards via Submodular Semi-gradient Methodscited by 15
  4. 2024Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergencecited by 11
  5. 2024On the Global Optimality of Policy Gradient Methods in General Utility Reinforcement Learningcited by 6
  6. 2024MetaCURL: Non-stationary Concave Utility Reinforcement Learningcited by 4
  7. 2024Convex Markov Games: A New Frontier for Multi-Agent Reinforcement Learningcited by 3
  8. 2026Soft Forward-Backward Representations for Zero-shot Reinforcement Learning with General Utilitiescited by 3
  9. 2026A Unified Density Operator View of Flow Control and Mergingcited by 2
  10. 2024On the Stochastic (Variance-Reduced) Proximal Gradient Method for Regularized Expected Reward Optimizationcited by 1
  11. 2026Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibriacited by 1
  12. 2026Refined Analysis of Entropy-Regularized Actor-Criticcited by 1
6 more
  1. 2026Robust General Utility for Reinforcement Learningcited by 1
  2. 2024Off-OAB: Off-Policy Policy Gradient Method with Optimal Action-Dependent Baselinecited by 0
  3. 2025Online Episodic Convex Reinforcement Learningcited by 0
  4. 2025Bayesian Risk-Sensitive Policy Optimization For MDPs With General Loss Functionscited by 0
  5. 2026Global Optimality for Constrained Exploration via Penalty Regularizationcited by 0
  6. 2026Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedbackcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learning
  2. 2026Mathematical methods of reinforcement learning
  3. 2026Parameter Exploration for RLVR via Variational Learning
  4. 2024Deterministic Policies for Constrained Reinforcement Learning in Polynomial Time
  5. 2024Towards Sample-Efficiency and Generalization of Transfer and Inverse Reinforcement Learning: A Comprehensive Literature Review
  6. 2021A Generalised Inverse Reinforcement Learning Framework
  7. 2024A General Control-Theoretic Approach for Reinforcement Learning: Theory and Algorithms
  8. 2022On Practical Reinforcement Learning: Provable Robustness, Scalability, and Statistical Efficiency