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

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

## 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 (most cited first, 30 of 41)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [Diversity is All You Need: Learning Skills without a Reward Function](https://mlsanity.com/paper/1802.06070/) (2018)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [Provably Efficient Maximum Entropy Exploration](https://mlsanity.com/paper/1812.02690/) (2018)
- [A Divergence Minimization Perspective on Imitation Learning Methods](https://mlsanity.com/paper/1911.02256/) (2019)
- [Neural Policy Gradient Methods: Global Optimality and Rates of Convergence](https://mlsanity.com/paper/1909.01150/) (2019)
- [Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes](https://mlsanity.com/paper/2102.00135/) (2021)
- [Exploration-Exploitation in Constrained MDPs](https://mlsanity.com/paper/2003.02189/) (2020)
- [On the Convergence Rates of Policy Gradient Methods](https://mlsanity.com/paper/2201.07443/) (2022)
- [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013)
- [Variational Policy Gradient Method for Reinforcement Learning with General Utilities](https://mlsanity.com/paper/2007.02151/) (2020)
- [Stochastic Variance-Reduced Policy Gradient](https://mlsanity.com/paper/1806.05618/) (2018)
- [Reward is enough for convex MDPs](https://mlsanity.com/paper/2106.00661/) (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)
- [An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods](https://mlsanity.com/paper/2211.07937/) (2022)
- [Reinforcement Learning with Convex Constraints](https://mlsanity.com/paper/1906.09323/) (2019)
- [Sample Efficient Policy Gradient Methods with Recursive Variance Reduction](https://mlsanity.com/paper/1909.08610/) (2019)
- [An Improved Convergence Analysis of Stochastic Variance-Reduced Policy Gradient](https://mlsanity.com/paper/1905.12615/) (2019)
- [Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies](https://mlsanity.com/paper/2302.01734/) (2023)
- [Concave Utility Reinforcement Learning: the Mean-Field Game Viewpoint](https://mlsanity.com/paper/2106.03787/) (2021)
- [Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies](https://mlsanity.com/paper/2210.01400/) (2022)
- [Stochastic Heavy Ball](https://mlsanity.com/paper/1609.04228/) (2016)
- [The Importance of Non-Markovianity in Maximum State Entropy Exploration](https://mlsanity.com/paper/2202.03060/) (2022)
- [Momentum-Based Policy Gradient Methods](https://mlsanity.com/paper/2007.06680/) (2020)
- [Challenging Common Assumptions in Convex Reinforcement Learning](https://mlsanity.com/paper/2202.01511/) (2022)
- [On the Global Optimum Convergence of Momentum-based Policy Gradient](https://mlsanity.com/paper/2110.10116/) (2021)
- [Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2110.10117/) (2021)

## Built on by (most cited first, 18 of 18)

- [From Gradient Clipping to Normalization for Heavy Tailed SGD](https://mlsanity.com/paper/2410.13849/) (2024)
- [Flow Density Control: Generative Optimization Beyond Entropy-Regularized Fine-Tuning](https://mlsanity.com/paper/2511.22640/) (2025)
- [Global Reinforcement Learning: Beyond Linear and Convex Rewards via Submodular Semi-gradient Methods](https://mlsanity.com/paper/2407.09905/) (2024)
- [Taming Nonconvex Stochastic Mirror Descent with General Bregman Divergence](https://mlsanity.com/paper/2402.17722/) (2024)
- [On the Global Optimality of Policy Gradient Methods in General Utility Reinforcement Learning](https://mlsanity.com/paper/2410.04108/) (2024)
- [MetaCURL: Non-stationary Concave Utility Reinforcement Learning](https://mlsanity.com/paper/2405.19807/) (2024)
- [Convex Markov Games: A New Frontier for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2410.16600/) (2024)
- [Soft Forward-Backward Representations for Zero-shot Reinforcement Learning with General Utilities](https://mlsanity.com/paper/2602.06769/) (2026)
- [A Unified Density Operator View of Flow Control and Merging](https://mlsanity.com/paper/2602.08012/) (2026)
- [On the Stochastic (Variance-Reduced) Proximal Gradient Method for Regularized Expected Reward Optimization](https://mlsanity.com/paper/2401.12508/) (2024)
- [Convex Markov Games and Beyond: New Proof of Existence, Characterization and Learning Algorithms for Nash Equilibria](https://mlsanity.com/paper/2602.12181/) (2026)
- [Refined Analysis of Entropy-Regularized Actor-Critic](https://mlsanity.com/paper/2605.24357/) (2026)
- [Robust General Utility for Reinforcement Learning](https://mlsanity.com/paper/2608.03562/) (2026)
- [Off-OAB: Off-Policy Policy Gradient Method with Optimal Action-Dependent Baseline](https://mlsanity.com/paper/2405.02572/) (2024)
- [Online Episodic Convex Reinforcement Learning](https://mlsanity.com/paper/2505.07303/) (2025)
- [Bayesian Risk-Sensitive Policy Optimization For MDPs With General Loss Functions](https://mlsanity.com/paper/2509.15509/) (2025)
- [Global Optimality for Constrained Exploration via Penalty Regularization](https://mlsanity.com/paper/2604.28144/) (2026)
- [Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedback](https://mlsanity.com/paper/2605.26373/) (2026)

## 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.