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

Abstract

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.

References in corpus (20)

• Continuous control with deep reinforcement learning
• Trust Region Policy Optimization
• High-Dimensional Continuous Control Using Generalized Advantage Estimation
• On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift
• Provably Efficient Maximum Entropy Exploration
• Neural Policy Gradient Methods: Global Optimality and Rates of Convergence
• The Anisotropic Noise in Stochastic Gradient Descent: Its Behavior of Escaping from Sharp Minima and Regularization Effects
• On the Global Convergence Rates of Softmax Policy Gradient Methods
• The Heavy-Tail Phenomenon in SGD
• FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs
• A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks
• PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning
• Mirror Descent Policy Optimization
• Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networks
• Fractional Underdamped Langevin Dynamics: Retargeting SGD with Momentum under Heavy-Tailed Gradient Noise
• Non-Asymptotic Analysis of Fractional Langevin Monte Carlo for Non-Convex Optimization
• First Exit Time Analysis of Stochastic Gradient Descent Under Heavy-Tailed Gradient Noise
• Model-free Representation Learning and Exploration in Low-rank MDPs
• Randomized Value Functions via Posterior State-Abstraction Sampling
• On Proximal Policy Optimization's Heavy-tailed Gradients