mlsanityData to 14 Oct 2026

On the Sample Complexity and Metastability of Heavy-tailed Policy Search in Continuous Control

arXiv 2106.08414 ↗First posted 15 Jun 2021cs.LG cs.AI cs.SYcited by 12

Not on the map. Why?

Abstract (arXiv)

Reinforcement learning is a framework for interactive decision-making with incentives sequentially revealed across time without a system dynamics model. Due to its scaling to continuous spaces, we focus on policy search where one iteratively improves a parameterized policy with stochastic policy gradient (PG) updates. In tabular Markov Decision Problems (MDPs), under persistent exploration and suitable parameterization, global optimality may be obtained. By contrast, in continuous space, the non-convexity poses a pathological challenge as evidenced by existing convergence results being mostly limited to stationarity or arbitrary local extrema. To close this gap, we step towards persistent exploration in continuous space through policy parameterizations defined by distributions of heavier tails defined by tail-index parameter alpha, which increases the likelihood of jumping in state space. Doing so invalidates smoothness conditions of the score function common to PG. Thus, we establish how the convergence rate to stationarity depends on the policy's tail index alpha, a Holder continuity parameter, integrability conditions, and an exploration tolerance parameter introduced here for the first time. Further, we characterize the dependence of the set of local maxima on the tail index through an exit and transition time analysis of a suitably defined Markov chain, identifying that policies associated with Levy Processes of a heavier tail converge to wider peaks. This phenomenon yields improved stability to perturbations in supervised learning, which we corroborate also manifests in improved performance of policy search, especially when myopic and farsighted incentives are misaligned.

Key facts. Cited by 12 papers in the map (data through 14 Oct 2026). Builds on 43 of its 109 references that are in the map. First posted on arXiv 15 Jun 2021.

Builds on

43 of 109 references.

References · 43

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2015Continuous control with deep reinforcement learningcited by 3,407
  3. 2015Trust Region Policy Optimizationcited by 2,580
  4. 2015High-Dimensional Continuous Control Using Generalized Advantage Estimationcited by 2,026
  5. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,150
  6. 2017A Distributional Perspective on Reinforcement Learningcited by 765
  7. 2017Exploring Generalization in Deep Learningcited by 600
  8. 2016Deep Exploration via Bootstrapped DQNcited by 527
  9. 2018Is Q-learning Provably Efficient?cited by 487
  10. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 264
  11. 2018Provably Efficient Maximum Entropy Explorationcited by 242
  12. 2017High-dimensional dynamics of generalization error in neural networkscited by 241
31 more
  1. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 233
  2. 2019A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networkscited by 214
  3. 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 177
  4. 2014Learning to Optimize via Information-Directed Samplingcited by 168
  5. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 159
  6. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 156
  7. 2019Global Optimality Guarantees For Policy Gradient Methodscited by 150
  8. 2019Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policiescited by 124
  9. 2020The Heavy-Tail Phenomenon in SGDcited by 124
  10. 2016Why is Posterior Sampling Better than Optimism for Reinforcement Learning?cited by 117
  11. 2019Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learningcited by 114
  12. 2020Variational Policy Gradient Method for Reinforcement Learning with General Utilitiescited by 111
  13. 2018Stochastic Variance-Reduced Policy Gradientcited by 106
  14. 2020Mirror Descent Policy Optimizationcited by 106
  15. 2020PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learningcited by 92
  16. 2019Reinforcement Learning to Optimize Long-term User Engagement in Recommender Systemscited by 90
  17. 2020Sample Efficient Reinforcement Learning with REINFORCEcited by 86
  18. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  19. 2018Efficient Exploration through Bayesian Deep Q-Networkscited by 67
  20. 2020Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networkscited by 62
  21. 2019First Exit Time Analysis of Stochastic Gradient Descent Under Heavy-Tailed Gradient Noisecited by 44
  22. 2020Fractional Underdamped Langevin Dynamics: Retargeting SGD with Momentum under Heavy-Tailed Gradient Noisecited by 33
  23. 2021On Proximal Policy Optimization's Heavy-tailed Gradientscited by 31
  24. 2018State Aggregation Learning from Markov Transition Datacited by 20
  25. 2019The problem with DDPG: understanding failures in deterministic environments with sparse rewardscited by 20
  26. 2019Non-Asymptotic Analysis of Fractional Langevin Monte Carlo for Non-Convex Optimizationcited by 8
  27. 2018Stochastic Policy Gradient Ascent in Reproducing Kernel Hilbert Spacescited by 7
  28. 2020Policy Gradient using Weak Derivatives for Reinforcement Learningcited by 7
  29. 2018Local Optimality and Generalization Guarantees for the Langevin Algorithm via Empirical Metastabilitycited by 6
  30. 2020Approximation Benefits of Policy Gradient Methods with Aggregated Statescited by 5
  31. 2020Randomized Value Functions via Posterior State-Abstraction Samplingcited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 3; 2023: 5; 2024: 1; 2025: 2; 2026: 1.

12 papers.

  1. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 58
  2. 2023A Fisher-Rao gradient flow for entropy-regularised Markov decision processes in Polish spacescited by 23
  3. 2023Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Spacecited by 18
  4. 2022On the Hidden Biases of Policy Mirror Ascent in Continuous Action Spacescited by 11
  5. 2025TIC-GRPO: Provable and Efficient Optimization for Reinforcement Learning from Human Feedbackcited by 11
  6. 2023Policy Gradient Algorithms Implicitly Optimize by Continuationcited by 4
  7. 2022Dealing with Sparse Rewards in Continuous Control Robotics via Heavy-Tailed Policiescited by 2
  8. 2024q-exponential family for policy optimizationcited by 2
  9. 2026Revisiting Mixture Policies in Entropy-Regularized Actor-Criticcited by 1
  10. 2022Occupancy Information Ratio: Infinite-Horizon, Information-Directed, Parameterized Policy Searchcited by 0
  11. 2023Confidence-Controlled Exploration: Efficient Sparse-Reward Policy Learning for Robot Navigationcited by 0
  12. 2025Distributions as Actions: A Unified Framework for Diverse Action Spacescited by 0