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 (16)

• 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
• 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
• PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning
• A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks
• 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